?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
2008-06-04 Xinliang David Li <davidxl@google.com>
[official-gcc.git] / gcc / df-problems.c
blobb1e60b3ab71fb9f37be2531f078499966d111057
1 /* Standard problems for dataflow support routines.
2 Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008
3
4 Free Software Foundation, Inc.
5 Originally contributed by Michael P. Hayes
6 (m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com)
7 Major rewrite contributed by Danny Berlin (dberlin@dberlin.org)
8 and Kenneth Zadeck (zadeck@naturalbridge.com).
9
10 This file is part of GCC.
11
12 GCC is free software; you can redistribute it and/or modify it under
13 the terms of the GNU General Public License as published by the Free
14 Software Foundation; either version 3, or (at your option) any later
15 version.
16
17 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
18 WARRANTY; without even the implied warranty of MERCHANTABILITY or
19 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 for more details.
21
22 You should have received a copy of the GNU General Public License
23 along with GCC; see the file COPYING3. If not see
24 <http://www.gnu.org/licenses/>. */
25
26 #include "config.h"
27 #include "system.h"
28 #include "coretypes.h"
29 #include "tm.h"
30 #include "rtl.h"
31 #include "tm_p.h"
32 #include "insn-config.h"
33 #include "recog.h"
34 #include "function.h"
35 #include "regs.h"
36 #include "output.h"
37 #include "alloc-pool.h"
38 #include "flags.h"
39 #include "hard-reg-set.h"
40 #include "basic-block.h"
41 #include "sbitmap.h"
42 #include "bitmap.h"
43 #include "timevar.h"
44 #include "df.h"
45 #include "except.h"
46 #include "dce.h"
47 #include "vecprim.h"
48
49 /* Note that turning REG_DEAD_DEBUGGING on will cause
50 gcc.c-torture/unsorted/dump-noaddr.c to fail because it prints
51 addresses in the dumps. */
52 #if 0
53 #define REG_DEAD_DEBUGGING
54 #endif
55
56 #define DF_SPARSE_THRESHOLD 32
57
58 static bitmap seen_in_block = NULL;
59 static bitmap seen_in_insn = NULL;
60
61 \f
62 /*----------------------------------------------------------------------------
63 Public functions access functions for the dataflow problems.
64 ----------------------------------------------------------------------------*/
65 /* Get the live at out set for BB no matter what problem happens to be
66 defined. This function is used by the register allocators who
67 choose different dataflow problems depending on the optimization
68 level. */
69
70 bitmap
71 df_get_live_out (basic_block bb)
72 {
73 gcc_assert (df_lr);
74
75 if (df_live)
76 return DF_LIVE_OUT (bb);
77 else
78 return DF_LR_OUT (bb);
79 }
80
81 /* Get the live at in set for BB no matter what problem happens to be
82 defined. This function is used by the register allocators who
83 choose different dataflow problems depending on the optimization
84 level. */
85
86 bitmap
87 df_get_live_in (basic_block bb)
88 {
89 gcc_assert (df_lr);
90
91 if (df_live)
92 return DF_LIVE_IN (bb);
93 else
94 return DF_LR_IN (bb);
95 }
96
97 /*----------------------------------------------------------------------------
98 Utility functions.
99 ----------------------------------------------------------------------------*/
100
101 /* Generic versions to get the void* version of the block info. Only
102 used inside the problem instance vectors. */
103
104 /* Grow the bb_info array. */
105
106 void
107 df_grow_bb_info (struct dataflow *dflow)
108 {
109 unsigned int new_size = last_basic_block + 1;
110 if (dflow->block_info_size < new_size)
111 {
112 new_size += new_size / 4;
113 dflow->block_info = xrealloc (dflow->block_info,
114 new_size *sizeof (void*));
115 memset (dflow->block_info + dflow->block_info_size, 0,
116 (new_size - dflow->block_info_size) *sizeof (void *));
117 dflow->block_info_size = new_size;
118 }
119 }
120
121 /* Dump a def-use or use-def chain for REF to FILE. */
122
123 void
124 df_chain_dump (struct df_link *link, FILE *file)
125 {
126 fprintf (file, "{ ");
127 for (; link; link = link->next)
128 {
129 fprintf (file, "%c%d(bb %d insn %d) ",
130 DF_REF_REG_DEF_P (link->ref) ? 'd' : 'u',
131 DF_REF_ID (link->ref),
132 DF_REF_BBNO (link->ref),
133 DF_REF_INSN (link->ref) ? DF_REF_INSN_UID (link->ref) : -1);
134 }
135 fprintf (file, "}");
136 }
137
138
139 /* Print some basic block info as part of df_dump. */
140
141 void
142 df_print_bb_index (basic_block bb, FILE *file)
143 {
144 edge e;
145 edge_iterator ei;
146
147 fprintf (file, "\n( ");
148 FOR_EACH_EDGE (e, ei, bb->preds)
149 {
150 basic_block pred = e->src;
151 fprintf (file, "%d%s ", pred->index, e->flags & EDGE_EH ? "(EH)" : "");
152 }
153 fprintf (file, ")->[%d]->( ", bb->index);
154 FOR_EACH_EDGE (e, ei, bb->succs)
155 {
156 basic_block succ = e->dest;
157 fprintf (file, "%d%s ", succ->index, e->flags & EDGE_EH ? "(EH)" : "");
158 }
159 fprintf (file, ")\n");
160 }
161
162
163
164 /* Make sure that the seen_in_insn and seen_in_block sbitmaps are set
165 up correctly. */
166
167 static void
168 df_set_seen (void)
169 {
170 seen_in_block = BITMAP_ALLOC (&df_bitmap_obstack);
171 seen_in_insn = BITMAP_ALLOC (&df_bitmap_obstack);
172 }
173
174
175 static void
176 df_unset_seen (void)
177 {
178 BITMAP_FREE (seen_in_block);
179 BITMAP_FREE (seen_in_insn);
180 }
181
182
183 \f
184 /*----------------------------------------------------------------------------
185 REACHING DEFINITIONS
186
187 Find the locations in the function where each definition site for a
188 pseudo reaches. In and out bitvectors are built for each basic
189 block. The id field in the ref is used to index into these sets.
190 See df.h for details.
191 ----------------------------------------------------------------------------*/
192
193 /* This problem plays a large number of games for the sake of
194 efficiency.
195
196 1) The order of the bits in the bitvectors. After the scanning
197 phase, all of the defs are sorted. All of the defs for the reg 0
198 are first, followed by all defs for reg 1 and so on.
199
200 2) There are two kill sets, one if the number of defs is less or
201 equal to DF_SPARSE_THRESHOLD and another if the number of defs is
202 greater.
203
204 <= : Data is built directly in the kill set.
205
206 > : One level of indirection is used to keep from generating long
207 strings of 1 bits in the kill sets. Bitvectors that are indexed
208 by the regnum are used to represent that there is a killing def
209 for the register. The confluence and transfer functions use
210 these along with the bitmap_clear_range call to remove ranges of
211 bits without actually generating a knockout vector.
212
213 The kill and sparse_kill and the dense_invalidated_by_call and
214 sparse_invalidated_by_call both play this game. */
215
216 /* Private data used to compute the solution for this problem. These
217 data structures are not accessible outside of this module. */
218 struct df_rd_problem_data
219 {
220 /* The set of defs to regs invalidated by call. */
221 bitmap sparse_invalidated_by_call;
222 /* The set of defs to regs invalidate by call for rd. */
223 bitmap dense_invalidated_by_call;
224 /* An obstack for the bitmaps we need for this problem. */
225 bitmap_obstack rd_bitmaps;
226 };
227
228 /* Set basic block info. */
229
230 static void
231 df_rd_set_bb_info (unsigned int index,
232 struct df_rd_bb_info *bb_info)
233 {
234 gcc_assert (df_rd);
235 gcc_assert (index < df_rd->block_info_size);
236 df_rd->block_info[index] = bb_info;
237 }
238
239
240 /* Free basic block info. */
241
242 static void
243 df_rd_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
244 void *vbb_info)
245 {
246 struct df_rd_bb_info *bb_info = (struct df_rd_bb_info *) vbb_info;
247 if (bb_info)
248 {
249 BITMAP_FREE (bb_info->kill);
250 BITMAP_FREE (bb_info->sparse_kill);
251 BITMAP_FREE (bb_info->gen);
252 BITMAP_FREE (bb_info->in);
253 BITMAP_FREE (bb_info->out);
254 pool_free (df_rd->block_pool, bb_info);
255 }
256 }
257
258
259 /* Allocate or reset bitmaps for DF_RD blocks. The solution bits are
260 not touched unless the block is new. */
261
262 static void
263 df_rd_alloc (bitmap all_blocks)
264 {
265 unsigned int bb_index;
266 bitmap_iterator bi;
267 struct df_rd_problem_data *problem_data;
268
269 if (!df_rd->block_pool)
270 df_rd->block_pool = create_alloc_pool ("df_rd_block pool",
271 sizeof (struct df_rd_bb_info), 50);
272
273 if (df_rd->problem_data)
274 {
275 problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
276 bitmap_clear (problem_data->sparse_invalidated_by_call);
277 bitmap_clear (problem_data->dense_invalidated_by_call);
278 }
279 else
280 {
281 problem_data = XNEW (struct df_rd_problem_data);
282 df_rd->problem_data = problem_data;
283
284 bitmap_obstack_initialize (&problem_data->rd_bitmaps);
285 problem_data->sparse_invalidated_by_call
286 = BITMAP_ALLOC (&problem_data->rd_bitmaps);
287 problem_data->dense_invalidated_by_call
288 = BITMAP_ALLOC (&problem_data->rd_bitmaps);
289 }
290
291 df_grow_bb_info (df_rd);
292
293 /* Because of the clustering of all use sites for the same pseudo,
294 we have to process all of the blocks before doing the
295 analysis. */
296
297 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
298 {
299 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
300 if (bb_info)
301 {
302 bitmap_clear (bb_info->kill);
303 bitmap_clear (bb_info->sparse_kill);
304 bitmap_clear (bb_info->gen);
305 }
306 else
307 {
308 bb_info = (struct df_rd_bb_info *) pool_alloc (df_rd->block_pool);
309 df_rd_set_bb_info (bb_index, bb_info);
310 bb_info->kill = BITMAP_ALLOC (&problem_data->rd_bitmaps);
311 bb_info->sparse_kill = BITMAP_ALLOC (&problem_data->rd_bitmaps);
312 bb_info->gen = BITMAP_ALLOC (&problem_data->rd_bitmaps);
313 bb_info->in = BITMAP_ALLOC (&problem_data->rd_bitmaps);
314 bb_info->out = BITMAP_ALLOC (&problem_data->rd_bitmaps);
315 }
316 }
317 df_rd->optional_p = true;
318 }
319
320
321 /* Process a list of DEFs for df_rd_bb_local_compute. */
322
323 static void
324 df_rd_bb_local_compute_process_def (struct df_rd_bb_info *bb_info,
325 struct df_ref **def_rec,
326 enum df_ref_flags top_flag)
327 {
328 while (*def_rec)
329 {
330 struct df_ref *def = *def_rec;
331 if (top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
332 {
333 unsigned int regno = DF_REF_REGNO (def);
334 unsigned int begin = DF_DEFS_BEGIN (regno);
335 unsigned int n_defs = DF_DEFS_COUNT (regno);
336
337 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
338 || (regno >= FIRST_PSEUDO_REGISTER))
339 {
340 /* Only the last def(s) for a regno in the block has any
341 effect. */
342 if (!bitmap_bit_p (seen_in_block, regno))
343 {
344 /* The first def for regno in insn gets to knock out the
345 defs from other instructions. */
346 if ((!bitmap_bit_p (seen_in_insn, regno))
347 /* If the def is to only part of the reg, it does
348 not kill the other defs that reach here. */
349 && (!(DF_REF_FLAGS (def) &
350 (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))))
351 {
352 if (n_defs > DF_SPARSE_THRESHOLD)
353 {
354 bitmap_set_bit (bb_info->sparse_kill, regno);
355 bitmap_clear_range(bb_info->gen, begin, n_defs);
356 }
357 else
358 {
359 bitmap_set_range (bb_info->kill, begin, n_defs);
360 bitmap_clear_range (bb_info->gen, begin, n_defs);
361 }
362 }
363
364 bitmap_set_bit (seen_in_insn, regno);
365 /* All defs for regno in the instruction may be put into
366 the gen set. */
367 if (!(DF_REF_FLAGS (def)
368 & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
369 bitmap_set_bit (bb_info->gen, DF_REF_ID (def));
370 }
371 }
372 }
373 def_rec++;
374 }
375 }
376
377 /* Compute local reaching def info for basic block BB. */
378
379 static void
380 df_rd_bb_local_compute (unsigned int bb_index)
381 {
382 basic_block bb = BASIC_BLOCK (bb_index);
383 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
384 rtx insn;
385
386 bitmap_clear (seen_in_block);
387 bitmap_clear (seen_in_insn);
388
389 /* Artificials are only hard regs. */
390 if (!(df->changeable_flags & DF_NO_HARD_REGS))
391 df_rd_bb_local_compute_process_def (bb_info,
392 df_get_artificial_defs (bb_index),
393 0);
394
395 FOR_BB_INSNS_REVERSE (bb, insn)
396 {
397 unsigned int uid = INSN_UID (insn);
398
399 if (!INSN_P (insn))
400 continue;
401
402 df_rd_bb_local_compute_process_def (bb_info,
403 DF_INSN_UID_DEFS (uid), 0);
404
405 /* This complex dance with the two bitmaps is required because
406 instructions can assign twice to the same pseudo. This
407 generally happens with calls that will have one def for the
408 result and another def for the clobber. If only one vector
409 is used and the clobber goes first, the result will be
410 lost. */
411 bitmap_ior_into (seen_in_block, seen_in_insn);
412 bitmap_clear (seen_in_insn);
413 }
414
415 /* Process the artificial defs at the top of the block last since we
416 are going backwards through the block and these are logically at
417 the start. */
418 if (!(df->changeable_flags & DF_NO_HARD_REGS))
419 df_rd_bb_local_compute_process_def (bb_info,
420 df_get_artificial_defs (bb_index),
421 DF_REF_AT_TOP);
422 }
423
424
425 /* Compute local reaching def info for each basic block within BLOCKS. */
426
427 static void
428 df_rd_local_compute (bitmap all_blocks)
429 {
430 unsigned int bb_index;
431 bitmap_iterator bi;
432 unsigned int regno;
433 struct df_rd_problem_data *problem_data
434 = (struct df_rd_problem_data *) df_rd->problem_data;
435 bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
436 bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
437
438 df_set_seen ();
439
440 df_maybe_reorganize_def_refs (DF_REF_ORDER_BY_REG);
441
442 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
443 {
444 df_rd_bb_local_compute (bb_index);
445 }
446
447 /* Set up the knockout bit vectors to be applied across EH_EDGES. */
448 EXECUTE_IF_SET_IN_BITMAP (df_invalidated_by_call, 0, regno, bi)
449 {
450 if (DF_DEFS_COUNT (regno) > DF_SPARSE_THRESHOLD)
451 bitmap_set_bit (sparse_invalidated, regno);
452 else
453 bitmap_set_range (dense_invalidated,
454 DF_DEFS_BEGIN (regno),
455 DF_DEFS_COUNT (regno));
456 }
457 df_unset_seen ();
458 }
459
460
461 /* Initialize the solution bit vectors for problem. */
462
463 static void
464 df_rd_init_solution (bitmap all_blocks)
465 {
466 unsigned int bb_index;
467 bitmap_iterator bi;
468
469 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
470 {
471 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
472
473 bitmap_copy (bb_info->out, bb_info->gen);
474 bitmap_clear (bb_info->in);
475 }
476 }
477
478 /* In of target gets or of out of source. */
479
480 static void
481 df_rd_confluence_n (edge e)
482 {
483 bitmap op1 = df_rd_get_bb_info (e->dest->index)->in;
484 bitmap op2 = df_rd_get_bb_info (e->src->index)->out;
485
486 if (e->flags & EDGE_FAKE)
487 return;
488
489 if (e->flags & EDGE_EH)
490 {
491 struct df_rd_problem_data *problem_data
492 = (struct df_rd_problem_data *) df_rd->problem_data;
493 bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
494 bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
495 bitmap_iterator bi;
496 unsigned int regno;
497 bitmap tmp = BITMAP_ALLOC (&df_bitmap_obstack);
498
499 bitmap_copy (tmp, op2);
500 bitmap_and_compl_into (tmp, dense_invalidated);
501
502 EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi)
503 {
504 bitmap_clear_range (tmp,
505 DF_DEFS_BEGIN (regno),
506 DF_DEFS_COUNT (regno));
507 }
508 bitmap_ior_into (op1, tmp);
509 BITMAP_FREE (tmp);
510 }
511 else
512 bitmap_ior_into (op1, op2);
513 }
514
515
516 /* Transfer function. */
517
518 static bool
519 df_rd_transfer_function (int bb_index)
520 {
521 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
522 unsigned int regno;
523 bitmap_iterator bi;
524 bitmap in = bb_info->in;
525 bitmap out = bb_info->out;
526 bitmap gen = bb_info->gen;
527 bitmap kill = bb_info->kill;
528 bitmap sparse_kill = bb_info->sparse_kill;
529
530 if (bitmap_empty_p (sparse_kill))
531 return bitmap_ior_and_compl (out, gen, in, kill);
532 else
533 {
534 struct df_rd_problem_data *problem_data;
535 bool changed = false;
536 bitmap tmp;
537
538 /* Note that TMP is _not_ a temporary bitmap if we end up replacing
539 OUT with TMP. Therefore, allocate TMP in the RD bitmaps obstack. */
540 problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
541 tmp = BITMAP_ALLOC (&problem_data->rd_bitmaps);
542
543 bitmap_copy (tmp, in);
544 EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi)
545 {
546 bitmap_clear_range (tmp,
547 DF_DEFS_BEGIN (regno),
548 DF_DEFS_COUNT (regno));
549 }
550 bitmap_and_compl_into (tmp, kill);
551 bitmap_ior_into (tmp, gen);
552 changed = !bitmap_equal_p (tmp, out);
553 if (changed)
554 {
555 BITMAP_FREE (out);
556 bb_info->out = tmp;
557 }
558 else
559 BITMAP_FREE (tmp);
560 return changed;
561 }
562 }
563
564
565 /* Free all storage associated with the problem. */
566
567 static void
568 df_rd_free (void)
569 {
570 struct df_rd_problem_data *problem_data
571 = (struct df_rd_problem_data *) df_rd->problem_data;
572
573 if (problem_data)
574 {
575 free_alloc_pool (df_rd->block_pool);
576 bitmap_obstack_release (&problem_data->rd_bitmaps);
577
578 df_rd->block_info_size = 0;
579 free (df_rd->block_info);
580 free (df_rd->problem_data);
581 }
582 free (df_rd);
583 }
584
585
586 /* Debugging info. */
587
588 static void
589 df_rd_start_dump (FILE *file)
590 {
591 struct df_rd_problem_data *problem_data
592 = (struct df_rd_problem_data *) df_rd->problem_data;
593 unsigned int m = DF_REG_SIZE(df);
594 unsigned int regno;
595
596 if (!df_rd->block_info)
597 return;
598
599 fprintf (file, ";; Reaching defs:\n\n");
600
601 fprintf (file, " sparse invalidated \t");
602 dump_bitmap (file, problem_data->sparse_invalidated_by_call);
603 fprintf (file, " dense invalidated \t");
604 dump_bitmap (file, problem_data->dense_invalidated_by_call);
605
606 for (regno = 0; regno < m; regno++)
607 if (DF_DEFS_COUNT (regno))
608 fprintf (file, "%d[%d,%d] ", regno,
609 DF_DEFS_BEGIN (regno),
610 DF_DEFS_COUNT (regno));
611 fprintf (file, "\n");
612
613 }
614
615
616 /* Debugging info at top of bb. */
617
618 static void
619 df_rd_top_dump (basic_block bb, FILE *file)
620 {
621 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
622 if (!bb_info || !bb_info->in)
623 return;
624
625 fprintf (file, ";; rd in \t(%d)\n", (int) bitmap_count_bits (bb_info->in));
626 dump_bitmap (file, bb_info->in);
627 fprintf (file, ";; rd gen \t(%d)\n", (int) bitmap_count_bits (bb_info->gen));
628 dump_bitmap (file, bb_info->gen);
629 fprintf (file, ";; rd kill\t(%d)\n", (int) bitmap_count_bits (bb_info->kill));
630 dump_bitmap (file, bb_info->kill);
631 }
632
633
634 /* Debugging info at top of bb. */
635
636 static void
637 df_rd_bottom_dump (basic_block bb, FILE *file)
638 {
639 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
640 if (!bb_info || !bb_info->out)
641 return;
642
643 fprintf (file, ";; rd out \t(%d)\n", (int) bitmap_count_bits (bb_info->out));
644 dump_bitmap (file, bb_info->out);
645 }
646
647 /* All of the information associated with every instance of the problem. */
648
649 static struct df_problem problem_RD =
650 {
651 DF_RD, /* Problem id. */
652 DF_FORWARD, /* Direction. */
653 df_rd_alloc, /* Allocate the problem specific data. */
654 NULL, /* Reset global information. */
655 df_rd_free_bb_info, /* Free basic block info. */
656 df_rd_local_compute, /* Local compute function. */
657 df_rd_init_solution, /* Init the solution specific data. */
658 df_worklist_dataflow, /* Worklist solver. */
659 NULL, /* Confluence operator 0. */
660 df_rd_confluence_n, /* Confluence operator n. */
661 df_rd_transfer_function, /* Transfer function. */
662 NULL, /* Finalize function. */
663 df_rd_free, /* Free all of the problem information. */
664 df_rd_free, /* Remove this problem from the stack of dataflow problems. */
665 df_rd_start_dump, /* Debugging. */
666 df_rd_top_dump, /* Debugging start block. */
667 df_rd_bottom_dump, /* Debugging end block. */
668 NULL, /* Incremental solution verify start. */
669 NULL, /* Incremental solution verify end. */
670 NULL, /* Dependent problem. */
671 TV_DF_RD, /* Timing variable. */
672 true /* Reset blocks on dropping out of blocks_to_analyze. */
673 };
674
675
676
677 /* Create a new DATAFLOW instance and add it to an existing instance
678 of DF. The returned structure is what is used to get at the
679 solution. */
680
681 void
682 df_rd_add_problem (void)
683 {
684 df_add_problem (&problem_RD);
685 }
686
687
688 \f
689 /*----------------------------------------------------------------------------
690 LIVE REGISTERS
691
692 Find the locations in the function where any use of a pseudo can
693 reach in the backwards direction. In and out bitvectors are built
694 for each basic block. The regno is used to index into these sets.
695 See df.h for details.
696 ----------------------------------------------------------------------------*/
697
698 /* Private data used to verify the solution for this problem. */
699 struct df_lr_problem_data
700 {
701 bitmap *in;
702 bitmap *out;
703 };
704
705
706 /* Set basic block info. */
707
708 static void
709 df_lr_set_bb_info (unsigned int index,
710 struct df_lr_bb_info *bb_info)
711 {
712 gcc_assert (df_lr);
713 gcc_assert (index < df_lr->block_info_size);
714 df_lr->block_info[index] = bb_info;
715 }
716
717
718 /* Free basic block info. */
719
720 static void
721 df_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
722 void *vbb_info)
723 {
724 struct df_lr_bb_info *bb_info = (struct df_lr_bb_info *) vbb_info;
725 if (bb_info)
726 {
727 BITMAP_FREE (bb_info->use);
728 BITMAP_FREE (bb_info->def);
729 BITMAP_FREE (bb_info->in);
730 BITMAP_FREE (bb_info->out);
731 pool_free (df_lr->block_pool, bb_info);
732 }
733 }
734
735
736 /* Allocate or reset bitmaps for DF_LR blocks. The solution bits are
737 not touched unless the block is new. */
738
739 static void
740 df_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
741 {
742 unsigned int bb_index;
743 bitmap_iterator bi;
744
745 if (!df_lr->block_pool)
746 df_lr->block_pool = create_alloc_pool ("df_lr_block pool",
747 sizeof (struct df_lr_bb_info), 50);
748
749 df_grow_bb_info (df_lr);
750
751 EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
752 {
753 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
754 if (bb_info)
755 {
756 bitmap_clear (bb_info->def);
757 bitmap_clear (bb_info->use);
758 }
759 else
760 {
761 bb_info = (struct df_lr_bb_info *) pool_alloc (df_lr->block_pool);
762 df_lr_set_bb_info (bb_index, bb_info);
763 bb_info->use = BITMAP_ALLOC (NULL);
764 bb_info->def = BITMAP_ALLOC (NULL);
765 bb_info->in = BITMAP_ALLOC (NULL);
766 bb_info->out = BITMAP_ALLOC (NULL);
767 }
768 }
769
770 df_lr->optional_p = false;
771 }
772
773
774 /* Reset the global solution for recalculation. */
775
776 static void
777 df_lr_reset (bitmap all_blocks)
778 {
779 unsigned int bb_index;
780 bitmap_iterator bi;
781
782 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
783 {
784 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
785 gcc_assert (bb_info);
786 bitmap_clear (bb_info->in);
787 bitmap_clear (bb_info->out);
788 }
789 }
790
791
792 /* Compute local live register info for basic block BB. */
793
794 static void
795 df_lr_bb_local_compute (unsigned int bb_index)
796 {
797 basic_block bb = BASIC_BLOCK (bb_index);
798 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
799 rtx insn;
800 struct df_ref **def_rec;
801 struct df_ref **use_rec;
802
803 /* Process the registers set in an exception handler. */
804 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
805 {
806 struct df_ref *def = *def_rec;
807 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
808 {
809 unsigned int dregno = DF_REF_REGNO (def);
810 bitmap_set_bit (bb_info->def, dregno);
811 bitmap_clear_bit (bb_info->use, dregno);
812 }
813 }
814
815 /* Process the hardware registers that are always live. */
816 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
817 {
818 struct df_ref *use = *use_rec;
819 /* Add use to set of uses in this BB. */
820 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
821 bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
822 }
823
824 FOR_BB_INSNS_REVERSE (bb, insn)
825 {
826 unsigned int uid = INSN_UID (insn);
827
828 if (!INSN_P (insn))
829 continue;
830
831 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
832 {
833 struct df_ref *def = *def_rec;
834 /* If the def is to only part of the reg, it does
835 not kill the other defs that reach here. */
836 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
837 {
838 unsigned int dregno = DF_REF_REGNO (def);
839 bitmap_set_bit (bb_info->def, dregno);
840 bitmap_clear_bit (bb_info->use, dregno);
841 }
842 }
843
844 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
845 {
846 struct df_ref *use = *use_rec;
847 /* Add use to set of uses in this BB. */
848 bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
849 }
850 }
851
852 /* Process the registers set in an exception handler or the hard
853 frame pointer if this block is the target of a non local
854 goto. */
855 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
856 {
857 struct df_ref *def = *def_rec;
858 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
859 {
860 unsigned int dregno = DF_REF_REGNO (def);
861 bitmap_set_bit (bb_info->def, dregno);
862 bitmap_clear_bit (bb_info->use, dregno);
863 }
864 }
865
866 #ifdef EH_USES
867 /* Process the uses that are live into an exception handler. */
868 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
869 {
870 struct df_ref *use = *use_rec;
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 }
875 #endif
876
877 /* If the df_live problem is not defined, such as at -O0 and -O1, we
878 still need to keep the luids up to date. This is normally done
879 in the df_live problem since this problem has a forwards
880 scan. */
881 if (!df_live)
882 df_recompute_luids (bb);
883 }
884
885
886 /* Compute local live register info for each basic block within BLOCKS. */
887
888 static void
889 df_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
890 {
891 unsigned int bb_index;
892 bitmap_iterator bi;
893
894 bitmap_clear (df->hardware_regs_used);
895
896 /* The all-important stack pointer must always be live. */
897 bitmap_set_bit (df->hardware_regs_used, STACK_POINTER_REGNUM);
898
899 /* Before reload, there are a few registers that must be forced
900 live everywhere -- which might not already be the case for
901 blocks within infinite loops. */
902 if (!reload_completed)
903 {
904 /* Any reference to any pseudo before reload is a potential
905 reference of the frame pointer. */
906 bitmap_set_bit (df->hardware_regs_used, FRAME_POINTER_REGNUM);
907
908 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
909 /* Pseudos with argument area equivalences may require
910 reloading via the argument pointer. */
911 if (fixed_regs[ARG_POINTER_REGNUM])
912 bitmap_set_bit (df->hardware_regs_used, ARG_POINTER_REGNUM);
913 #endif
914
915 /* Any constant, or pseudo with constant equivalences, may
916 require reloading from memory using the pic register. */
917 if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
918 && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
919 bitmap_set_bit (df->hardware_regs_used, PIC_OFFSET_TABLE_REGNUM);
920 }
921
922 EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
923 {
924 if (bb_index == EXIT_BLOCK)
925 {
926 /* The exit block is special for this problem and its bits are
927 computed from thin air. */
928 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (EXIT_BLOCK);
929 bitmap_copy (bb_info->use, df->exit_block_uses);
930 }
931 else
932 df_lr_bb_local_compute (bb_index);
933 }
934
935 bitmap_clear (df_lr->out_of_date_transfer_functions);
936 }
937
938
939 /* Initialize the solution vectors. */
940
941 static void
942 df_lr_init (bitmap all_blocks)
943 {
944 unsigned int bb_index;
945 bitmap_iterator bi;
946
947 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
948 {
949 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
950 bitmap_copy (bb_info->in, bb_info->use);
951 bitmap_clear (bb_info->out);
952 }
953 }
954
955
956 /* Confluence function that processes infinite loops. This might be a
957 noreturn function that throws. And even if it isn't, getting the
958 unwind info right helps debugging. */
959 static void
960 df_lr_confluence_0 (basic_block bb)
961 {
962 bitmap op1 = df_lr_get_bb_info (bb->index)->out;
963 if (bb != EXIT_BLOCK_PTR)
964 bitmap_copy (op1, df->hardware_regs_used);
965 }
966
967
968 /* Confluence function that ignores fake edges. */
969
970 static void
971 df_lr_confluence_n (edge e)
972 {
973 bitmap op1 = df_lr_get_bb_info (e->src->index)->out;
974 bitmap op2 = df_lr_get_bb_info (e->dest->index)->in;
975
976 /* Call-clobbered registers die across exception and call edges. */
977 /* ??? Abnormal call edges ignored for the moment, as this gets
978 confused by sibling call edges, which crashes reg-stack. */
979 if (e->flags & EDGE_EH)
980 bitmap_ior_and_compl_into (op1, op2, df_invalidated_by_call);
981 else
982 bitmap_ior_into (op1, op2);
983
984 bitmap_ior_into (op1, df->hardware_regs_used);
985 }
986
987
988 /* Transfer function. */
989
990 static bool
991 df_lr_transfer_function (int bb_index)
992 {
993 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
994 bitmap in = bb_info->in;
995 bitmap out = bb_info->out;
996 bitmap use = bb_info->use;
997 bitmap def = bb_info->def;
998
999 return bitmap_ior_and_compl (in, use, out, def);
1000 }
1001
1002
1003 /* Run the fast dce as a side effect of building LR. */
1004
1005 static void
1006 df_lr_finalize (bitmap all_blocks ATTRIBUTE_UNUSED)
1007 {
1008 if (df->changeable_flags & DF_LR_RUN_DCE)
1009 {
1010 run_fast_df_dce ();
1011 if (df_lr->problem_data && df_lr->solutions_dirty)
1012 {
1013 /* If we are here, then it is because we are both verifying
1014 the solution and the dce changed the function. In that case
1015 the verification info built will be wrong. So we leave the
1016 dirty flag true so that the verifier will skip the checking
1017 part and just clean up.*/
1018 df_lr->solutions_dirty = true;
1019 }
1020 else
1021 df_lr->solutions_dirty = false;
1022 }
1023 else
1024 df_lr->solutions_dirty = false;
1025 }
1026
1027
1028 /* Free all storage associated with the problem. */
1029
1030 static void
1031 df_lr_free (void)
1032 {
1033 if (df_lr->block_info)
1034 {
1035 unsigned int i;
1036 for (i = 0; i < df_lr->block_info_size; i++)
1037 {
1038 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (i);
1039 if (bb_info)
1040 {
1041 BITMAP_FREE (bb_info->use);
1042 BITMAP_FREE (bb_info->def);
1043 BITMAP_FREE (bb_info->in);
1044 BITMAP_FREE (bb_info->out);
1045 }
1046 }
1047 free_alloc_pool (df_lr->block_pool);
1048
1049 df_lr->block_info_size = 0;
1050 free (df_lr->block_info);
1051 }
1052
1053 BITMAP_FREE (df_lr->out_of_date_transfer_functions);
1054 free (df_lr);
1055 }
1056
1057
1058 /* Debugging info at top of bb. */
1059
1060 static void
1061 df_lr_top_dump (basic_block bb, FILE *file)
1062 {
1063 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1064 struct df_lr_problem_data *problem_data;
1065 if (!bb_info || !bb_info->in)
1066 return;
1067
1068 fprintf (file, ";; lr in \t");
1069 df_print_regset (file, bb_info->in);
1070 if (df_lr->problem_data)
1071 {
1072 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1073 fprintf (file, ";; old in \t");
1074 df_print_regset (file, problem_data->in[bb->index]);
1075 }
1076 fprintf (file, ";; lr use \t");
1077 df_print_regset (file, bb_info->use);
1078 fprintf (file, ";; lr def \t");
1079 df_print_regset (file, bb_info->def);
1080 }
1081
1082
1083 /* Debugging info at bottom of bb. */
1084
1085 static void
1086 df_lr_bottom_dump (basic_block bb, FILE *file)
1087 {
1088 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1089 struct df_lr_problem_data *problem_data;
1090 if (!bb_info || !bb_info->out)
1091 return;
1092
1093 fprintf (file, ";; lr out \t");
1094 df_print_regset (file, bb_info->out);
1095 if (df_lr->problem_data)
1096 {
1097 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1098 fprintf (file, ";; old out \t");
1099 df_print_regset (file, problem_data->out[bb->index]);
1100 }
1101 }
1102
1103
1104 /* Build the datastructure to verify that the solution to the dataflow
1105 equations is not dirty. */
1106
1107 static void
1108 df_lr_verify_solution_start (void)
1109 {
1110 basic_block bb;
1111 struct df_lr_problem_data *problem_data;
1112 if (df_lr->solutions_dirty)
1113 {
1114 df_lr->problem_data = NULL;
1115 return;
1116 }
1117
1118 /* Set it true so that the solution is recomputed. */
1119 df_lr->solutions_dirty = true;
1120
1121 problem_data = XNEW (struct df_lr_problem_data);
1122 df_lr->problem_data = problem_data;
1123 problem_data->in = XNEWVEC (bitmap, last_basic_block);
1124 problem_data->out = XNEWVEC (bitmap, last_basic_block);
1125
1126 FOR_ALL_BB (bb)
1127 {
1128 problem_data->in[bb->index] = BITMAP_ALLOC (NULL);
1129 problem_data->out[bb->index] = BITMAP_ALLOC (NULL);
1130 bitmap_copy (problem_data->in[bb->index], DF_LR_IN (bb));
1131 bitmap_copy (problem_data->out[bb->index], DF_LR_OUT (bb));
1132 }
1133 }
1134
1135
1136 /* Compare the saved datastructure and the new solution to the dataflow
1137 equations. */
1138
1139 static void
1140 df_lr_verify_solution_end (void)
1141 {
1142 struct df_lr_problem_data *problem_data;
1143 basic_block bb;
1144
1145 if (df_lr->problem_data == NULL)
1146 return;
1147
1148 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1149
1150 if (df_lr->solutions_dirty)
1151 /* Do not check if the solution is still dirty. See the comment
1152 in df_lr_finalize for details. */
1153 df_lr->solutions_dirty = false;
1154 else
1155 FOR_ALL_BB (bb)
1156 {
1157 if ((!bitmap_equal_p (problem_data->in[bb->index], DF_LR_IN (bb)))
1158 || (!bitmap_equal_p (problem_data->out[bb->index], DF_LR_OUT (bb))))
1159 {
1160 /*df_dump (stderr);*/
1161 gcc_unreachable ();
1162 }
1163 }
1164
1165 /* Cannot delete them immediately because you may want to dump them
1166 if the comparison fails. */
1167 FOR_ALL_BB (bb)
1168 {
1169 BITMAP_FREE (problem_data->in[bb->index]);
1170 BITMAP_FREE (problem_data->out[bb->index]);
1171 }
1172
1173 free (problem_data->in);
1174 free (problem_data->out);
1175 free (problem_data);
1176 df_lr->problem_data = NULL;
1177 }
1178
1179
1180 /* All of the information associated with every instance of the problem. */
1181
1182 static struct df_problem problem_LR =
1183 {
1184 DF_LR, /* Problem id. */
1185 DF_BACKWARD, /* Direction. */
1186 df_lr_alloc, /* Allocate the problem specific data. */
1187 df_lr_reset, /* Reset global information. */
1188 df_lr_free_bb_info, /* Free basic block info. */
1189 df_lr_local_compute, /* Local compute function. */
1190 df_lr_init, /* Init the solution specific data. */
1191 df_worklist_dataflow, /* Worklist solver. */
1192 df_lr_confluence_0, /* Confluence operator 0. */
1193 df_lr_confluence_n, /* Confluence operator n. */
1194 df_lr_transfer_function, /* Transfer function. */
1195 df_lr_finalize, /* Finalize function. */
1196 df_lr_free, /* Free all of the problem information. */
1197 NULL, /* Remove this problem from the stack of dataflow problems. */
1198 NULL, /* Debugging. */
1199 df_lr_top_dump, /* Debugging start block. */
1200 df_lr_bottom_dump, /* Debugging end block. */
1201 df_lr_verify_solution_start,/* Incremental solution verify start. */
1202 df_lr_verify_solution_end, /* Incremental solution verify end. */
1203 NULL, /* Dependent problem. */
1204 TV_DF_LR, /* Timing variable. */
1205 false /* Reset blocks on dropping out of blocks_to_analyze. */
1206 };
1207
1208
1209 /* Create a new DATAFLOW instance and add it to an existing instance
1210 of DF. The returned structure is what is used to get at the
1211 solution. */
1212
1213 void
1214 df_lr_add_problem (void)
1215 {
1216 df_add_problem (&problem_LR);
1217 /* These will be initialized when df_scan_blocks processes each
1218 block. */
1219 df_lr->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
1220 }
1221
1222
1223 /* Verify that all of the lr related info is consistent and
1224 correct. */
1225
1226 void
1227 df_lr_verify_transfer_functions (void)
1228 {
1229 basic_block bb;
1230 bitmap saved_def;
1231 bitmap saved_use;
1232 bitmap saved_adef;
1233 bitmap saved_ause;
1234 bitmap all_blocks;
1235
1236 if (!df)
1237 return;
1238
1239 saved_def = BITMAP_ALLOC (NULL);
1240 saved_use = BITMAP_ALLOC (NULL);
1241 saved_adef = BITMAP_ALLOC (NULL);
1242 saved_ause = BITMAP_ALLOC (NULL);
1243 all_blocks = BITMAP_ALLOC (NULL);
1244
1245 FOR_ALL_BB (bb)
1246 {
1247 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1248 bitmap_set_bit (all_blocks, bb->index);
1249
1250 if (bb_info)
1251 {
1252 /* Make a copy of the transfer functions and then compute
1253 new ones to see if the transfer functions have
1254 changed. */
1255 if (!bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1256 bb->index))
1257 {
1258 bitmap_copy (saved_def, bb_info->def);
1259 bitmap_copy (saved_use, bb_info->use);
1260 bitmap_clear (bb_info->def);
1261 bitmap_clear (bb_info->use);
1262
1263 df_lr_bb_local_compute (bb->index);
1264 gcc_assert (bitmap_equal_p (saved_def, bb_info->def));
1265 gcc_assert (bitmap_equal_p (saved_use, bb_info->use));
1266 }
1267 }
1268 else
1269 {
1270 /* If we do not have basic block info, the block must be in
1271 the list of dirty blocks or else some one has added a
1272 block behind our backs. */
1273 gcc_assert (bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1274 bb->index));
1275 }
1276 /* Make sure no one created a block without following
1277 procedures. */
1278 gcc_assert (df_scan_get_bb_info (bb->index));
1279 }
1280
1281 /* Make sure there are no dirty bits in blocks that have been deleted. */
1282 gcc_assert (!bitmap_intersect_compl_p (df_lr->out_of_date_transfer_functions,
1283 all_blocks));
1284
1285 BITMAP_FREE (saved_def);
1286 BITMAP_FREE (saved_use);
1287 BITMAP_FREE (saved_adef);
1288 BITMAP_FREE (saved_ause);
1289 BITMAP_FREE (all_blocks);
1290 }
1291
1292
1293 \f
1294 /*----------------------------------------------------------------------------
1295 LIVE AND MUST-INITIALIZED REGISTERS.
1296
1297 This problem first computes the IN and OUT bitvectors for the
1298 must-initialized registers problems, which is a forward problem.
1299 It gives the set of registers for which we MUST have an available
1300 definition on any path from the entry block to the entry/exit of
1301 a basic block. Sets generate a definition, while clobbers kill
1302 a definition.
1303
1304 In and out bitvectors are built for each basic block and are indexed by
1305 regnum (see df.h for details). In and out bitvectors in struct
1306 df_live_bb_info actually refers to the must-initialized problem;
1307
1308 Then, the in and out sets for the LIVE problem itself are computed.
1309 These are the logical AND of the IN and OUT sets from the LR problem
1310 and the must-initialized problem.
1311 ----------------------------------------------------------------------------*/
1312
1313 /* Private data used to verify the solution for this problem. */
1314 struct df_live_problem_data
1315 {
1316 bitmap *in;
1317 bitmap *out;
1318 };
1319
1320 /* Scratch var used by transfer functions. This is used to implement
1321 an optimization to reduce the amount of space used to compute the
1322 combined lr and live analysis. */
1323 static bitmap df_live_scratch;
1324
1325 /* Set basic block info. */
1326
1327 static void
1328 df_live_set_bb_info (unsigned int index,
1329 struct df_live_bb_info *bb_info)
1330 {
1331 gcc_assert (df_live);
1332 gcc_assert (index < df_live->block_info_size);
1333 df_live->block_info[index] = bb_info;
1334 }
1335
1336
1337 /* Free basic block info. */
1338
1339 static void
1340 df_live_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
1341 void *vbb_info)
1342 {
1343 struct df_live_bb_info *bb_info = (struct df_live_bb_info *) vbb_info;
1344 if (bb_info)
1345 {
1346 BITMAP_FREE (bb_info->gen);
1347 BITMAP_FREE (bb_info->kill);
1348 BITMAP_FREE (bb_info->in);
1349 BITMAP_FREE (bb_info->out);
1350 pool_free (df_live->block_pool, bb_info);
1351 }
1352 }
1353
1354
1355 /* Allocate or reset bitmaps for DF_LIVE blocks. The solution bits are
1356 not touched unless the block is new. */
1357
1358 static void
1359 df_live_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
1360 {
1361 unsigned int bb_index;
1362 bitmap_iterator bi;
1363
1364 if (!df_live->block_pool)
1365 df_live->block_pool = create_alloc_pool ("df_live_block pool",
1366 sizeof (struct df_live_bb_info), 100);
1367 if (!df_live_scratch)
1368 df_live_scratch = BITMAP_ALLOC (NULL);
1369
1370 df_grow_bb_info (df_live);
1371
1372 EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions, 0, bb_index, bi)
1373 {
1374 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1375 if (bb_info)
1376 {
1377 bitmap_clear (bb_info->kill);
1378 bitmap_clear (bb_info->gen);
1379 }
1380 else
1381 {
1382 bb_info = (struct df_live_bb_info *) pool_alloc (df_live->block_pool);
1383 df_live_set_bb_info (bb_index, bb_info);
1384 bb_info->kill = BITMAP_ALLOC (NULL);
1385 bb_info->gen = BITMAP_ALLOC (NULL);
1386 bb_info->in = BITMAP_ALLOC (NULL);
1387 bb_info->out = BITMAP_ALLOC (NULL);
1388 }
1389 }
1390 df_live->optional_p = (optimize <= 1);
1391 }
1392
1393
1394 /* Reset the global solution for recalculation. */
1395
1396 static void
1397 df_live_reset (bitmap all_blocks)
1398 {
1399 unsigned int bb_index;
1400 bitmap_iterator bi;
1401
1402 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1403 {
1404 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1405 gcc_assert (bb_info);
1406 bitmap_clear (bb_info->in);
1407 bitmap_clear (bb_info->out);
1408 }
1409 }
1410
1411
1412 /* Compute local uninitialized register info for basic block BB. */
1413
1414 static void
1415 df_live_bb_local_compute (unsigned int bb_index)
1416 {
1417 basic_block bb = BASIC_BLOCK (bb_index);
1418 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1419 rtx insn;
1420 struct df_ref **def_rec;
1421 int luid = 0;
1422
1423 FOR_BB_INSNS (bb, insn)
1424 {
1425 unsigned int uid = INSN_UID (insn);
1426 struct df_insn_info *insn_info = DF_INSN_UID_GET (uid);
1427
1428 /* Inserting labels does not always trigger the incremental
1429 rescanning. */
1430 if (!insn_info)
1431 {
1432 gcc_assert (!INSN_P (insn));
1433 df_insn_create_insn_record (insn);
1434 }
1435
1436 DF_INSN_LUID (insn) = luid;
1437 if (!INSN_P (insn))
1438 continue;
1439
1440 luid++;
1441 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1442 {
1443 struct df_ref *def = *def_rec;
1444 unsigned int regno = DF_REF_REGNO (def);
1445
1446 if (DF_REF_FLAGS_IS_SET (def,
1447 DF_REF_PARTIAL | DF_REF_CONDITIONAL))
1448 /* All partial or conditional def
1449 seen are included in the gen set. */
1450 bitmap_set_bit (bb_info->gen, regno);
1451 else if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER))
1452 /* Only must clobbers for the entire reg destroy the
1453 value. */
1454 bitmap_set_bit (bb_info->kill, regno);
1455 else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
1456 bitmap_set_bit (bb_info->gen, regno);
1457 }
1458 }
1459
1460 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
1461 {
1462 struct df_ref *def = *def_rec;
1463 bitmap_set_bit (bb_info->gen, DF_REF_REGNO (def));
1464 }
1465 }
1466
1467
1468 /* Compute local uninitialized register info. */
1469
1470 static void
1471 df_live_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
1472 {
1473 unsigned int bb_index;
1474 bitmap_iterator bi;
1475
1476 df_grow_insn_info ();
1477
1478 EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions,
1479 0, bb_index, bi)
1480 {
1481 df_live_bb_local_compute (bb_index);
1482 }
1483
1484 bitmap_clear (df_live->out_of_date_transfer_functions);
1485 }
1486
1487
1488 /* Initialize the solution vectors. */
1489
1490 static void
1491 df_live_init (bitmap all_blocks)
1492 {
1493 unsigned int bb_index;
1494 bitmap_iterator bi;
1495
1496 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1497 {
1498 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1499 struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1500
1501 /* No register may reach a location where it is not used. Thus
1502 we trim the rr result to the places where it is used. */
1503 bitmap_and (bb_info->out, bb_info->gen, bb_lr_info->out);
1504 bitmap_clear (bb_info->in);
1505 }
1506 }
1507
1508 /* Forward confluence function that ignores fake edges. */
1509
1510 static void
1511 df_live_confluence_n (edge e)
1512 {
1513 bitmap op1 = df_live_get_bb_info (e->dest->index)->in;
1514 bitmap op2 = df_live_get_bb_info (e->src->index)->out;
1515
1516 if (e->flags & EDGE_FAKE)
1517 return;
1518
1519 bitmap_ior_into (op1, op2);
1520 }
1521
1522
1523 /* Transfer function for the forwards must-initialized problem. */
1524
1525 static bool
1526 df_live_transfer_function (int bb_index)
1527 {
1528 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1529 struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1530 bitmap in = bb_info->in;
1531 bitmap out = bb_info->out;
1532 bitmap gen = bb_info->gen;
1533 bitmap kill = bb_info->kill;
1534
1535 /* We need to use a scratch set here so that the value returned from
1536 this function invocation properly reflects if the sets changed in
1537 a significant way; i.e. not just because the lr set was anded
1538 in. */
1539 bitmap_and (df_live_scratch, gen, bb_lr_info->out);
1540 /* No register may reach a location where it is not used. Thus
1541 we trim the rr result to the places where it is used. */
1542 bitmap_and_into (in, bb_lr_info->in);
1543
1544 return bitmap_ior_and_compl (out, df_live_scratch, in, kill);
1545 }
1546
1547
1548 /* And the LR info with the must-initialized registers, to produce the LIVE info. */
1549
1550 static void
1551 df_live_finalize (bitmap all_blocks)
1552 {
1553
1554 if (df_live->solutions_dirty)
1555 {
1556 bitmap_iterator bi;
1557 unsigned int bb_index;
1558
1559 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1560 {
1561 struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1562 struct df_live_bb_info *bb_live_info = df_live_get_bb_info (bb_index);
1563
1564 /* No register may reach a location where it is not used. Thus
1565 we trim the rr result to the places where it is used. */
1566 bitmap_and_into (bb_live_info->in, bb_lr_info->in);
1567 bitmap_and_into (bb_live_info->out, bb_lr_info->out);
1568 }
1569
1570 df_live->solutions_dirty = false;
1571 }
1572 }
1573
1574
1575 /* Free all storage associated with the problem. */
1576
1577 static void
1578 df_live_free (void)
1579 {
1580 if (df_live->block_info)
1581 {
1582 unsigned int i;
1583
1584 for (i = 0; i < df_live->block_info_size; i++)
1585 {
1586 struct df_live_bb_info *bb_info = df_live_get_bb_info (i);
1587 if (bb_info)
1588 {
1589 BITMAP_FREE (bb_info->gen);
1590 BITMAP_FREE (bb_info->kill);
1591 BITMAP_FREE (bb_info->in);
1592 BITMAP_FREE (bb_info->out);
1593 }
1594 }
1595
1596 free_alloc_pool (df_live->block_pool);
1597 df_live->block_info_size = 0;
1598 free (df_live->block_info);
1599
1600 if (df_live_scratch)
1601 BITMAP_FREE (df_live_scratch);
1602 }
1603 BITMAP_FREE (df_live->out_of_date_transfer_functions);
1604 free (df_live);
1605 }
1606
1607
1608 /* Debugging info at top of bb. */
1609
1610 static void
1611 df_live_top_dump (basic_block bb, FILE *file)
1612 {
1613 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1614 struct df_live_problem_data *problem_data;
1615
1616 if (!bb_info || !bb_info->in)
1617 return;
1618
1619 fprintf (file, ";; live in \t");
1620 df_print_regset (file, bb_info->in);
1621 if (df_live->problem_data)
1622 {
1623 problem_data = (struct df_live_problem_data *)df_live->problem_data;
1624 fprintf (file, ";; old in \t");
1625 df_print_regset (file, problem_data->in[bb->index]);
1626 }
1627 fprintf (file, ";; live gen \t");
1628 df_print_regset (file, bb_info->gen);
1629 fprintf (file, ";; live kill\t");
1630 df_print_regset (file, bb_info->kill);
1631 }
1632
1633
1634 /* Debugging info at bottom of bb. */
1635
1636 static void
1637 df_live_bottom_dump (basic_block bb, FILE *file)
1638 {
1639 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1640 struct df_live_problem_data *problem_data;
1641
1642 if (!bb_info || !bb_info->out)
1643 return;
1644
1645 fprintf (file, ";; live out \t");
1646 df_print_regset (file, bb_info->out);
1647 if (df_live->problem_data)
1648 {
1649 problem_data = (struct df_live_problem_data *)df_live->problem_data;
1650 fprintf (file, ";; old out \t");
1651 df_print_regset (file, problem_data->out[bb->index]);
1652 }
1653 }
1654
1655
1656 /* Build the datastructure to verify that the solution to the dataflow
1657 equations is not dirty. */
1658
1659 static void
1660 df_live_verify_solution_start (void)
1661 {
1662 basic_block bb;
1663 struct df_live_problem_data *problem_data;
1664 if (df_live->solutions_dirty)
1665 {
1666 df_live->problem_data = NULL;
1667 return;
1668 }
1669
1670 /* Set it true so that the solution is recomputed. */
1671 df_live->solutions_dirty = true;
1672
1673 problem_data = XNEW (struct df_live_problem_data);
1674 df_live->problem_data = problem_data;
1675 problem_data->in = XNEWVEC (bitmap, last_basic_block);
1676 problem_data->out = XNEWVEC (bitmap, last_basic_block);
1677
1678 FOR_ALL_BB (bb)
1679 {
1680 problem_data->in[bb->index] = BITMAP_ALLOC (NULL);
1681 problem_data->out[bb->index] = BITMAP_ALLOC (NULL);
1682 bitmap_copy (problem_data->in[bb->index], DF_LIVE_IN (bb));
1683 bitmap_copy (problem_data->out[bb->index], DF_LIVE_OUT (bb));
1684 }
1685 }
1686
1687
1688 /* Compare the saved datastructure and the new solution to the dataflow
1689 equations. */
1690
1691 static void
1692 df_live_verify_solution_end (void)
1693 {
1694 struct df_live_problem_data *problem_data;
1695 basic_block bb;
1696
1697 if (df_live->problem_data == NULL)
1698 return;
1699
1700 problem_data = (struct df_live_problem_data *)df_live->problem_data;
1701
1702 FOR_ALL_BB (bb)
1703 {
1704 if ((!bitmap_equal_p (problem_data->in[bb->index], DF_LIVE_IN (bb)))
1705 || (!bitmap_equal_p (problem_data->out[bb->index], DF_LIVE_OUT (bb))))
1706 {
1707 /*df_dump (stderr);*/
1708 gcc_unreachable ();
1709 }
1710 }
1711
1712 /* Cannot delete them immediately because you may want to dump them
1713 if the comparison fails. */
1714 FOR_ALL_BB (bb)
1715 {
1716 BITMAP_FREE (problem_data->in[bb->index]);
1717 BITMAP_FREE (problem_data->out[bb->index]);
1718 }
1719
1720 free (problem_data->in);
1721 free (problem_data->out);
1722 free (problem_data);
1723 df_live->problem_data = NULL;
1724 }
1725
1726
1727 /* All of the information associated with every instance of the problem. */
1728
1729 static struct df_problem problem_LIVE =
1730 {
1731 DF_LIVE, /* Problem id. */
1732 DF_FORWARD, /* Direction. */
1733 df_live_alloc, /* Allocate the problem specific data. */
1734 df_live_reset, /* Reset global information. */
1735 df_live_free_bb_info, /* Free basic block info. */
1736 df_live_local_compute, /* Local compute function. */
1737 df_live_init, /* Init the solution specific data. */
1738 df_worklist_dataflow, /* Worklist solver. */
1739 NULL, /* Confluence operator 0. */
1740 df_live_confluence_n, /* Confluence operator n. */
1741 df_live_transfer_function, /* Transfer function. */
1742 df_live_finalize, /* Finalize function. */
1743 df_live_free, /* Free all of the problem information. */
1744 df_live_free, /* Remove this problem from the stack of dataflow problems. */
1745 NULL, /* Debugging. */
1746 df_live_top_dump, /* Debugging start block. */
1747 df_live_bottom_dump, /* Debugging end block. */
1748 df_live_verify_solution_start,/* Incremental solution verify start. */
1749 df_live_verify_solution_end, /* Incremental solution verify end. */
1750 &problem_LR, /* Dependent problem. */
1751 TV_DF_LIVE, /* Timing variable. */
1752 false /* Reset blocks on dropping out of blocks_to_analyze. */
1753 };
1754
1755
1756 /* Create a new DATAFLOW instance and add it to an existing instance
1757 of DF. The returned structure is what is used to get at the
1758 solution. */
1759
1760 void
1761 df_live_add_problem (void)
1762 {
1763 df_add_problem (&problem_LIVE);
1764 /* These will be initialized when df_scan_blocks processes each
1765 block. */
1766 df_live->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
1767 }
1768
1769
1770 /* Set all of the blocks as dirty. This needs to be done if this
1771 problem is added after all of the insns have been scanned. */
1772
1773 void
1774 df_live_set_all_dirty (void)
1775 {
1776 basic_block bb;
1777 FOR_ALL_BB (bb)
1778 bitmap_set_bit (df_live->out_of_date_transfer_functions,
1779 bb->index);
1780 }
1781
1782
1783 /* Verify that all of the lr related info is consistent and
1784 correct. */
1785
1786 void
1787 df_live_verify_transfer_functions (void)
1788 {
1789 basic_block bb;
1790 bitmap saved_gen;
1791 bitmap saved_kill;
1792 bitmap all_blocks;
1793
1794 if (!df)
1795 return;
1796
1797 saved_gen = BITMAP_ALLOC (NULL);
1798 saved_kill = BITMAP_ALLOC (NULL);
1799 all_blocks = BITMAP_ALLOC (NULL);
1800
1801 df_grow_insn_info ();
1802
1803 FOR_ALL_BB (bb)
1804 {
1805 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1806 bitmap_set_bit (all_blocks, bb->index);
1807
1808 if (bb_info)
1809 {
1810 /* Make a copy of the transfer functions and then compute
1811 new ones to see if the transfer functions have
1812 changed. */
1813 if (!bitmap_bit_p (df_live->out_of_date_transfer_functions,
1814 bb->index))
1815 {
1816 bitmap_copy (saved_gen, bb_info->gen);
1817 bitmap_copy (saved_kill, bb_info->kill);
1818 bitmap_clear (bb_info->gen);
1819 bitmap_clear (bb_info->kill);
1820
1821 df_live_bb_local_compute (bb->index);
1822 gcc_assert (bitmap_equal_p (saved_gen, bb_info->gen));
1823 gcc_assert (bitmap_equal_p (saved_kill, bb_info->kill));
1824 }
1825 }
1826 else
1827 {
1828 /* If we do not have basic block info, the block must be in
1829 the list of dirty blocks or else some one has added a
1830 block behind our backs. */
1831 gcc_assert (bitmap_bit_p (df_live->out_of_date_transfer_functions,
1832 bb->index));
1833 }
1834 /* Make sure no one created a block without following
1835 procedures. */
1836 gcc_assert (df_scan_get_bb_info (bb->index));
1837 }
1838
1839 /* Make sure there are no dirty bits in blocks that have been deleted. */
1840 gcc_assert (!bitmap_intersect_compl_p (df_live->out_of_date_transfer_functions,
1841 all_blocks));
1842 BITMAP_FREE (saved_gen);
1843 BITMAP_FREE (saved_kill);
1844 BITMAP_FREE (all_blocks);
1845 }
1846 \f
1847 /*----------------------------------------------------------------------------
1848 CREATE DEF_USE (DU) and / or USE_DEF (UD) CHAINS
1849
1850 Link either the defs to the uses and / or the uses to the defs.
1851
1852 These problems are set up like the other dataflow problems so that
1853 they nicely fit into the framework. They are much simpler and only
1854 involve a single traversal of instructions and an examination of
1855 the reaching defs information (the dependent problem).
1856 ----------------------------------------------------------------------------*/
1857
1858 #define df_chain_problem_p(FLAG) (((enum df_chain_flags)df_chain->local_flags)&(FLAG))
1859
1860 /* Create a du or ud chain from SRC to DST and link it into SRC. */
1861
1862 struct df_link *
1863 df_chain_create (struct df_ref *src, struct df_ref *dst)
1864 {
1865 struct df_link *head = DF_REF_CHAIN (src);
1866 struct df_link *link = pool_alloc (df_chain->block_pool);
1867
1868 DF_REF_CHAIN (src) = link;
1869 link->next = head;
1870 link->ref = dst;
1871 return link;
1872 }
1873
1874
1875 /* Delete any du or ud chains that start at REF and point to
1876 TARGET. */
1877 static void
1878 df_chain_unlink_1 (struct df_ref *ref, struct df_ref *target)
1879 {
1880 struct df_link *chain = DF_REF_CHAIN (ref);
1881 struct df_link *prev = NULL;
1882
1883 while (chain)
1884 {
1885 if (chain->ref == target)
1886 {
1887 if (prev)
1888 prev->next = chain->next;
1889 else
1890 DF_REF_CHAIN (ref) = chain->next;
1891 pool_free (df_chain->block_pool, chain);
1892 return;
1893 }
1894 prev = chain;
1895 chain = chain->next;
1896 }
1897 }
1898
1899
1900 /* Delete a du or ud chain that leave or point to REF. */
1901
1902 void
1903 df_chain_unlink (struct df_ref *ref)
1904 {
1905 struct df_link *chain = DF_REF_CHAIN (ref);
1906 while (chain)
1907 {
1908 struct df_link *next = chain->next;
1909 /* Delete the other side if it exists. */
1910 df_chain_unlink_1 (chain->ref, ref);
1911 pool_free (df_chain->block_pool, chain);
1912 chain = next;
1913 }
1914 DF_REF_CHAIN (ref) = NULL;
1915 }
1916
1917
1918 /* Copy the du or ud chain starting at FROM_REF and attach it to
1919 TO_REF. */
1920
1921 void
1922 df_chain_copy (struct df_ref *to_ref,
1923 struct df_link *from_ref)
1924 {
1925 while (from_ref)
1926 {
1927 df_chain_create (to_ref, from_ref->ref);
1928 from_ref = from_ref->next;
1929 }
1930 }
1931
1932
1933 /* Remove this problem from the stack of dataflow problems. */
1934
1935 static void
1936 df_chain_remove_problem (void)
1937 {
1938 bitmap_iterator bi;
1939 unsigned int bb_index;
1940
1941 /* Wholesale destruction of the old chains. */
1942 if (df_chain->block_pool)
1943 free_alloc_pool (df_chain->block_pool);
1944
1945 EXECUTE_IF_SET_IN_BITMAP (df_chain->out_of_date_transfer_functions, 0, bb_index, bi)
1946 {
1947 rtx insn;
1948 struct df_ref **def_rec;
1949 struct df_ref **use_rec;
1950 basic_block bb = BASIC_BLOCK (bb_index);
1951
1952 if (df_chain_problem_p (DF_DU_CHAIN))
1953 for (def_rec = df_get_artificial_defs (bb->index); *def_rec; def_rec++)
1954 DF_REF_CHAIN (*def_rec) = NULL;
1955 if (df_chain_problem_p (DF_UD_CHAIN))
1956 for (use_rec = df_get_artificial_uses (bb->index); *use_rec; use_rec++)
1957 DF_REF_CHAIN (*use_rec) = NULL;
1958
1959 FOR_BB_INSNS (bb, insn)
1960 {
1961 unsigned int uid = INSN_UID (insn);
1962
1963 if (INSN_P (insn))
1964 {
1965 if (df_chain_problem_p (DF_DU_CHAIN))
1966 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1967 DF_REF_CHAIN (*def_rec) = NULL;
1968 if (df_chain_problem_p (DF_UD_CHAIN))
1969 {
1970 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
1971 DF_REF_CHAIN (*use_rec) = NULL;
1972 for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
1973 DF_REF_CHAIN (*use_rec) = NULL;
1974 }
1975 }
1976 }
1977 }
1978
1979 bitmap_clear (df_chain->out_of_date_transfer_functions);
1980 df_chain->block_pool = NULL;
1981 }
1982
1983
1984 /* Remove the chain problem completely. */
1985
1986 static void
1987 df_chain_fully_remove_problem (void)
1988 {
1989 df_chain_remove_problem ();
1990 BITMAP_FREE (df_chain->out_of_date_transfer_functions);
1991 free (df_chain);
1992 }
1993
1994
1995 /* Create def-use or use-def chains. */
1996
1997 static void
1998 df_chain_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
1999 {
2000 df_chain_remove_problem ();
2001 df_chain->block_pool = create_alloc_pool ("df_chain_block pool",
2002 sizeof (struct df_link), 50);
2003 df_chain->optional_p = true;
2004 }
2005
2006
2007 /* Reset all of the chains when the set of basic blocks changes. */
2008
2009 static void
2010 df_chain_reset (bitmap blocks_to_clear ATTRIBUTE_UNUSED)
2011 {
2012 df_chain_remove_problem ();
2013 }
2014
2015
2016 /* Create the chains for a list of USEs. */
2017
2018 static void
2019 df_chain_create_bb_process_use (bitmap local_rd,
2020 struct df_ref **use_rec,
2021 enum df_ref_flags top_flag)
2022 {
2023 bitmap_iterator bi;
2024 unsigned int def_index;
2025
2026 while (*use_rec)
2027 {
2028 struct df_ref *use = *use_rec;
2029 unsigned int uregno = DF_REF_REGNO (use);
2030 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
2031 || (uregno >= FIRST_PSEUDO_REGISTER))
2032 {
2033 /* Do not want to go through this for an uninitialized var. */
2034 int count = DF_DEFS_COUNT (uregno);
2035 if (count)
2036 {
2037 if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
2038 {
2039 unsigned int first_index = DF_DEFS_BEGIN (uregno);
2040 unsigned int last_index = first_index + count - 1;
2041
2042 EXECUTE_IF_SET_IN_BITMAP (local_rd, first_index, def_index, bi)
2043 {
2044 struct df_ref *def;
2045 if (def_index > last_index)
2046 break;
2047
2048 def = DF_DEFS_GET (def_index);
2049 if (df_chain_problem_p (DF_DU_CHAIN))
2050 df_chain_create (def, use);
2051 if (df_chain_problem_p (DF_UD_CHAIN))
2052 df_chain_create (use, def);
2053 }
2054 }
2055 }
2056 }
2057
2058 use_rec++;
2059 }
2060 }
2061
2062
2063 /* Create chains from reaching defs bitmaps for basic block BB. */
2064
2065 static void
2066 df_chain_create_bb (unsigned int bb_index)
2067 {
2068 basic_block bb = BASIC_BLOCK (bb_index);
2069 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
2070 rtx insn;
2071 bitmap cpy = BITMAP_ALLOC (NULL);
2072 struct df_ref **def_rec;
2073
2074 bitmap_copy (cpy, bb_info->in);
2075 bitmap_set_bit (df_chain->out_of_date_transfer_functions, bb_index);
2076
2077 /* Since we are going forwards, process the artificial uses first
2078 then the artificial defs second. */
2079
2080 #ifdef EH_USES
2081 /* Create the chains for the artificial uses from the EH_USES at the
2082 beginning of the block. */
2083
2084 /* Artificials are only hard regs. */
2085 if (!(df->changeable_flags & DF_NO_HARD_REGS))
2086 df_chain_create_bb_process_use (cpy,
2087 df_get_artificial_uses (bb->index),
2088 DF_REF_AT_TOP);
2089 #endif
2090
2091 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2092 {
2093 struct df_ref *def = *def_rec;
2094 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
2095 {
2096 unsigned int dregno = DF_REF_REGNO (def);
2097 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
2098 bitmap_clear_range (cpy,
2099 DF_DEFS_BEGIN (dregno),
2100 DF_DEFS_COUNT (dregno));
2101 bitmap_set_bit (cpy, DF_REF_ID (def));
2102 }
2103 }
2104
2105 /* Process the regular instructions next. */
2106 FOR_BB_INSNS (bb, insn)
2107 {
2108 struct df_ref **def_rec;
2109 unsigned int uid = INSN_UID (insn);
2110
2111 if (!INSN_P (insn))
2112 continue;
2113
2114 /* Now scan the uses and link them up with the defs that remain
2115 in the cpy vector. */
2116
2117 df_chain_create_bb_process_use (cpy, DF_INSN_UID_USES (uid), 0);
2118
2119 if (df->changeable_flags & DF_EQ_NOTES)
2120 df_chain_create_bb_process_use (cpy, DF_INSN_UID_EQ_USES (uid), 0);
2121
2122
2123 /* Since we are going forwards, process the defs second. This
2124 pass only changes the bits in cpy. */
2125 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
2126 {
2127 struct df_ref *def = *def_rec;
2128 unsigned int dregno = DF_REF_REGNO (def);
2129 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
2130 || (dregno >= FIRST_PSEUDO_REGISTER))
2131 {
2132 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
2133 bitmap_clear_range (cpy,
2134 DF_DEFS_BEGIN (dregno),
2135 DF_DEFS_COUNT (dregno));
2136 if (!(DF_REF_FLAGS (def)
2137 & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
2138 bitmap_set_bit (cpy, DF_REF_ID (def));
2139 }
2140 }
2141 }
2142
2143 /* Create the chains for the artificial uses of the hard registers
2144 at the end of the block. */
2145 if (!(df->changeable_flags & DF_NO_HARD_REGS))
2146 df_chain_create_bb_process_use (cpy,
2147 df_get_artificial_uses (bb->index),
2148 0);
2149
2150 BITMAP_FREE (cpy);
2151 }
2152
2153 /* Create def-use chains from reaching use bitmaps for basic blocks
2154 in BLOCKS. */
2155
2156 static void
2157 df_chain_finalize (bitmap all_blocks)
2158 {
2159 unsigned int bb_index;
2160 bitmap_iterator bi;
2161
2162 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2163 {
2164 df_chain_create_bb (bb_index);
2165 }
2166 }
2167
2168
2169 /* Free all storage associated with the problem. */
2170
2171 static void
2172 df_chain_free (void)
2173 {
2174 free_alloc_pool (df_chain->block_pool);
2175 BITMAP_FREE (df_chain->out_of_date_transfer_functions);
2176 free (df_chain);
2177 }
2178
2179
2180 /* Debugging info. */
2181
2182 static void
2183 df_chain_top_dump (basic_block bb, FILE *file)
2184 {
2185 if (df_chain_problem_p (DF_DU_CHAIN))
2186 {
2187 rtx insn;
2188 struct df_ref **def_rec = df_get_artificial_defs (bb->index);
2189 if (*def_rec)
2190 {
2191
2192 fprintf (file, ";; DU chains for artificial defs\n");
2193 while (*def_rec)
2194 {
2195 struct df_ref *def = *def_rec;
2196 fprintf (file, ";; reg %d ", DF_REF_REGNO (def));
2197 df_chain_dump (DF_REF_CHAIN (def), file);
2198 fprintf (file, "\n");
2199 def_rec++;
2200 }
2201 }
2202
2203 FOR_BB_INSNS (bb, insn)
2204 {
2205 unsigned int uid = INSN_UID (insn);
2206 if (INSN_P (insn))
2207 {
2208 def_rec = DF_INSN_UID_DEFS (uid);
2209 if (*def_rec)
2210 {
2211 fprintf (file, ";; DU chains for insn luid %d uid %d\n",
2212 DF_INSN_LUID (insn), uid);
2213
2214 while (*def_rec)
2215 {
2216 struct df_ref *def = *def_rec;
2217 fprintf (file, ";; reg %d ", DF_REF_REGNO (def));
2218 if (def->flags & DF_REF_READ_WRITE)
2219 fprintf (file, "read/write ");
2220 df_chain_dump (DF_REF_CHAIN (def), file);
2221 fprintf (file, "\n");
2222 def_rec++;
2223 }
2224 }
2225 }
2226 }
2227 }
2228 }
2229
2230
2231 static void
2232 df_chain_bottom_dump (basic_block bb, FILE *file)
2233 {
2234 if (df_chain_problem_p (DF_UD_CHAIN))
2235 {
2236 rtx insn;
2237 struct df_ref **use_rec = df_get_artificial_uses (bb->index);
2238
2239 if (*use_rec)
2240 {
2241 fprintf (file, ";; UD chains for artificial uses\n");
2242 while (*use_rec)
2243 {
2244 struct df_ref *use = *use_rec;
2245 fprintf (file, ";; reg %d ", DF_REF_REGNO (use));
2246 df_chain_dump (DF_REF_CHAIN (use), file);
2247 fprintf (file, "\n");
2248 use_rec++;
2249 }
2250 }
2251
2252 FOR_BB_INSNS (bb, insn)
2253 {
2254 unsigned int uid = INSN_UID (insn);
2255 if (INSN_P (insn))
2256 {
2257 struct df_ref **eq_use_rec = DF_INSN_UID_EQ_USES (uid);
2258 use_rec = DF_INSN_UID_USES (uid);
2259 if (*use_rec || *eq_use_rec)
2260 {
2261 fprintf (file, ";; UD chains for insn luid %d uid %d\n",
2262 DF_INSN_LUID (insn), uid);
2263
2264 while (*use_rec)
2265 {
2266 struct df_ref *use = *use_rec;
2267 fprintf (file, ";; reg %d ", DF_REF_REGNO (use));
2268 if (use->flags & DF_REF_READ_WRITE)
2269 fprintf (file, "read/write ");
2270 df_chain_dump (DF_REF_CHAIN (use), file);
2271 fprintf (file, "\n");
2272 use_rec++;
2273 }
2274 while (*eq_use_rec)
2275 {
2276 struct df_ref *use = *eq_use_rec;
2277 fprintf (file, ";; eq_note reg %d ", DF_REF_REGNO (use));
2278 df_chain_dump (DF_REF_CHAIN (use), file);
2279 fprintf (file, "\n");
2280 eq_use_rec++;
2281 }
2282 }
2283 }
2284 }
2285 }
2286 }
2287
2288
2289 static struct df_problem problem_CHAIN =
2290 {
2291 DF_CHAIN, /* Problem id. */
2292 DF_NONE, /* Direction. */
2293 df_chain_alloc, /* Allocate the problem specific data. */
2294 df_chain_reset, /* Reset global information. */
2295 NULL, /* Free basic block info. */
2296 NULL, /* Local compute function. */
2297 NULL, /* Init the solution specific data. */
2298 NULL, /* Iterative solver. */
2299 NULL, /* Confluence operator 0. */
2300 NULL, /* Confluence operator n. */
2301 NULL, /* Transfer function. */
2302 df_chain_finalize, /* Finalize function. */
2303 df_chain_free, /* Free all of the problem information. */
2304 df_chain_fully_remove_problem,/* Remove this problem from the stack of dataflow problems. */
2305 NULL, /* Debugging. */
2306 df_chain_top_dump, /* Debugging start block. */
2307 df_chain_bottom_dump, /* Debugging end block. */
2308 NULL, /* Incremental solution verify start. */
2309 NULL, /* Incremental solution verify end. */
2310 &problem_RD, /* Dependent problem. */
2311 TV_DF_CHAIN, /* Timing variable. */
2312 false /* Reset blocks on dropping out of blocks_to_analyze. */
2313 };
2314
2315
2316 /* Create a new DATAFLOW instance and add it to an existing instance
2317 of DF. The returned structure is what is used to get at the
2318 solution. */
2319
2320 void
2321 df_chain_add_problem (enum df_chain_flags chain_flags)
2322 {
2323 df_add_problem (&problem_CHAIN);
2324 df_chain->local_flags = (unsigned int)chain_flags;
2325 df_chain->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
2326 }
2327
2328 #undef df_chain_problem_p
2329
2330 \f
2331 /*----------------------------------------------------------------------------
2332 BYTE LEVEL LIVE REGISTERS
2333
2334 Find the locations in the function where any use of a pseudo can
2335 reach in the backwards direction. In and out bitvectors are built
2336 for each basic block. There are two mapping functions,
2337 df_byte_lr_get_regno_start and df_byte_lr_get_regno_len that are
2338 used to map regnos into bit vector postions.
2339
2340 This problem differs from the regular df_lr function in the way
2341 that subregs, *_extracts and strict_low_parts are handled. In lr
2342 these are consider partial kills, here, the exact set of bytes is
2343 modeled. Note that any reg that has none of these operations is
2344 only modeled with a single bit since all operations access the
2345 entire register.
2346
2347 This problem is more brittle that the regular lr. It currently can
2348 be used in dce incrementally, but cannot be used in an environment
2349 where insns are created or modified. The problem is that the
2350 mapping of regnos to bitmap positions is relatively compact, in
2351 that if a pseudo does not do any of the byte wise operations, only
2352 one slot is allocated, rather than a slot for each byte. If insn
2353 are created, where a subreg is used for a reg that had no subregs,
2354 the mapping would be wrong. Likewise, there are no checks to see
2355 that new pseudos have been added. These issues could be addressed
2356 by adding a problem specific flag to not use the compact mapping,
2357 if there was a need to do so.
2358
2359 ----------------------------------------------------------------------------*/
2360
2361 /* Private data used to verify the solution for this problem. */
2362 struct df_byte_lr_problem_data
2363 {
2364 /* Expanded versions of bitvectors used in lr. */
2365 bitmap invalidated_by_call;
2366 bitmap hardware_regs_used;
2367
2368 /* Indexed by regno, this is true if there are subregs, extracts or
2369 strict_low_parts for this regno. */
2370 bitmap needs_expansion;
2371
2372 /* The start position and len for each regno in the various bit
2373 vectors. */
2374 unsigned int* regno_start;
2375 unsigned int* regno_len;
2376 /* An obstack for the bitmaps we need for this problem. */
2377 bitmap_obstack byte_lr_bitmaps;
2378 };
2379
2380
2381 /* Get the starting location for REGNO in the df_byte_lr bitmaps. */
2382
2383 int
2384 df_byte_lr_get_regno_start (unsigned int regno)
2385 {
2386 struct df_byte_lr_problem_data *problem_data
2387 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;;
2388 return problem_data->regno_start[regno];
2389 }
2390
2391
2392 /* Get the len for REGNO in the df_byte_lr bitmaps. */
2393
2394 int
2395 df_byte_lr_get_regno_len (unsigned int regno)
2396 {
2397 struct df_byte_lr_problem_data *problem_data
2398 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;;
2399 return problem_data->regno_len[regno];
2400 }
2401
2402
2403 /* Set basic block info. */
2404
2405 static void
2406 df_byte_lr_set_bb_info (unsigned int index,
2407 struct df_byte_lr_bb_info *bb_info)
2408 {
2409 gcc_assert (df_byte_lr);
2410 gcc_assert (index < df_byte_lr->block_info_size);
2411 df_byte_lr->block_info[index] = bb_info;
2412 }
2413
2414
2415 /* Free basic block info. */
2416
2417 static void
2418 df_byte_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
2419 void *vbb_info)
2420 {
2421 struct df_byte_lr_bb_info *bb_info = (struct df_byte_lr_bb_info *) vbb_info;
2422 if (bb_info)
2423 {
2424 BITMAP_FREE (bb_info->use);
2425 BITMAP_FREE (bb_info->def);
2426 BITMAP_FREE (bb_info->in);
2427 BITMAP_FREE (bb_info->out);
2428 pool_free (df_byte_lr->block_pool, bb_info);
2429 }
2430 }
2431
2432
2433 /* Check all of the refs in REF_REC to see if any of them are
2434 extracts, subregs or strict_low_parts. */
2435
2436 static void
2437 df_byte_lr_check_regs (struct df_ref **ref_rec)
2438 {
2439 struct df_byte_lr_problem_data *problem_data
2440 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2441
2442 for (; *ref_rec; ref_rec++)
2443 {
2444 struct df_ref *ref = *ref_rec;
2445 if (DF_REF_FLAGS_IS_SET (ref, DF_REF_SIGN_EXTRACT
2446 | DF_REF_ZERO_EXTRACT
2447 | DF_REF_STRICT_LOW_PART)
2448 || GET_CODE (DF_REF_REG (ref)) == SUBREG)
2449 bitmap_set_bit (problem_data->needs_expansion, DF_REF_REGNO (ref));
2450 }
2451 }
2452
2453
2454 /* Expand bitmap SRC which is indexed by regno to DEST which is indexed by
2455 regno_start and regno_len. */
2456
2457 static void
2458 df_byte_lr_expand_bitmap (bitmap dest, bitmap src)
2459 {
2460 struct df_byte_lr_problem_data *problem_data
2461 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2462 bitmap_iterator bi;
2463 unsigned int i;
2464
2465 bitmap_clear (dest);
2466 EXECUTE_IF_SET_IN_BITMAP (src, 0, i, bi)
2467 {
2468 bitmap_set_range (dest, problem_data->regno_start[i],
2469 problem_data->regno_len[i]);
2470 }
2471 }
2472
2473
2474 /* Allocate or reset bitmaps for DF_BYTE_LR blocks. The solution bits are
2475 not touched unless the block is new. */
2476
2477 static void
2478 df_byte_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
2479 {
2480 unsigned int bb_index;
2481 bitmap_iterator bi;
2482 basic_block bb;
2483 unsigned int regno;
2484 unsigned int index = 0;
2485 unsigned int max_reg = max_reg_num();
2486 struct df_byte_lr_problem_data *problem_data
2487 = problem_data = XNEW (struct df_byte_lr_problem_data);
2488
2489 df_byte_lr->problem_data = problem_data;
2490
2491 if (!df_byte_lr->block_pool)
2492 df_byte_lr->block_pool = create_alloc_pool ("df_byte_lr_block pool",
2493 sizeof (struct df_byte_lr_bb_info), 50);
2494
2495 df_grow_bb_info (df_byte_lr);
2496
2497 /* Create the mapping from regnos to slots. This does not change
2498 unless the problem is destroyed and recreated. In particular, if
2499 we end up deleting the only insn that used a subreg, we do not
2500 want to redo the mapping because this would invalidate everything
2501 else. */
2502
2503 bitmap_obstack_initialize (&problem_data->byte_lr_bitmaps);
2504 problem_data->regno_start = XNEWVEC (unsigned int, max_reg);
2505 problem_data->regno_len = XNEWVEC (unsigned int, max_reg);
2506 problem_data->hardware_regs_used = BITMAP_ALLOC (&problem_data->byte_lr_bitmaps);
2507 problem_data->invalidated_by_call = BITMAP_ALLOC (&problem_data->byte_lr_bitmaps);
2508 problem_data->needs_expansion = BITMAP_ALLOC (&problem_data->byte_lr_bitmaps);
2509
2510 /* Discover which regno's use subregs, extracts or
2511 strict_low_parts. */
2512 FOR_EACH_BB (bb)
2513 {
2514 rtx insn;
2515 FOR_BB_INSNS (bb, insn)
2516 {
2517 if (INSN_P (insn))
2518 {
2519 df_byte_lr_check_regs (DF_INSN_DEFS (insn));
2520 df_byte_lr_check_regs (DF_INSN_USES (insn));
2521 }
2522 }
2523 bitmap_set_bit (df_byte_lr->out_of_date_transfer_functions, bb->index);
2524 }
2525
2526 bitmap_set_bit (df_byte_lr->out_of_date_transfer_functions, ENTRY_BLOCK);
2527 bitmap_set_bit (df_byte_lr->out_of_date_transfer_functions, EXIT_BLOCK);
2528
2529 /* Allocate the slots for each regno. */
2530 for (regno = 0; regno < max_reg; regno++)
2531 {
2532 int len;
2533 problem_data->regno_start[regno] = index;
2534 if (bitmap_bit_p (problem_data->needs_expansion, regno))
2535 len = GET_MODE_SIZE (GET_MODE (regno_reg_rtx[regno]));
2536 else
2537 len = 1;
2538
2539 problem_data->regno_len[regno] = len;
2540 index += len;
2541 }
2542
2543 df_byte_lr_expand_bitmap (problem_data->hardware_regs_used,
2544 df->hardware_regs_used);
2545 df_byte_lr_expand_bitmap (problem_data->invalidated_by_call,
2546 df_invalidated_by_call);
2547
2548 EXECUTE_IF_SET_IN_BITMAP (df_byte_lr->out_of_date_transfer_functions, 0, bb_index, bi)
2549 {
2550 struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb_index);
2551 if (bb_info)
2552 {
2553 bitmap_clear (bb_info->def);
2554 bitmap_clear (bb_info->use);
2555 }
2556 else
2557 {
2558 bb_info = (struct df_byte_lr_bb_info *) pool_alloc (df_byte_lr->block_pool);
2559 df_byte_lr_set_bb_info (bb_index, bb_info);
2560 bb_info->use = BITMAP_ALLOC (&problem_data->byte_lr_bitmaps);
2561 bb_info->def = BITMAP_ALLOC (&problem_data->byte_lr_bitmaps);
2562 bb_info->in = BITMAP_ALLOC (&problem_data->byte_lr_bitmaps);
2563 bb_info->out = BITMAP_ALLOC (&problem_data->byte_lr_bitmaps);
2564 }
2565 }
2566
2567 df_byte_lr->optional_p = true;
2568 }
2569
2570
2571 /* Reset the global solution for recalculation. */
2572
2573 static void
2574 df_byte_lr_reset (bitmap all_blocks)
2575 {
2576 unsigned int bb_index;
2577 bitmap_iterator bi;
2578
2579 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2580 {
2581 struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb_index);
2582 gcc_assert (bb_info);
2583 bitmap_clear (bb_info->in);
2584 bitmap_clear (bb_info->out);
2585 }
2586 }
2587
2588
2589 /* Compute local live register info for basic block BB. */
2590
2591 static void
2592 df_byte_lr_bb_local_compute (unsigned int bb_index)
2593 {
2594 struct df_byte_lr_problem_data *problem_data
2595 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2596 basic_block bb = BASIC_BLOCK (bb_index);
2597 struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb_index);
2598 rtx insn;
2599 struct df_ref **def_rec;
2600 struct df_ref **use_rec;
2601
2602 /* Process the registers set in an exception handler. */
2603 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2604 {
2605 struct df_ref *def = *def_rec;
2606 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
2607 {
2608 unsigned int dregno = DF_REF_REGNO (def);
2609 unsigned int start = problem_data->regno_start[dregno];
2610 unsigned int len = problem_data->regno_len[dregno];
2611 bitmap_set_range (bb_info->def, start, len);
2612 bitmap_clear_range (bb_info->use, start, len);
2613 }
2614 }
2615
2616 /* Process the hardware registers that are always live. */
2617 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
2618 {
2619 struct df_ref *use = *use_rec;
2620 /* Add use to set of uses in this BB. */
2621 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
2622 {
2623 unsigned int uregno = DF_REF_REGNO (use);
2624 unsigned int start = problem_data->regno_start[uregno];
2625 unsigned int len = problem_data->regno_len[uregno];
2626 bitmap_set_range (bb_info->use, start, len);
2627 }
2628 }
2629
2630 FOR_BB_INSNS_REVERSE (bb, insn)
2631 {
2632 unsigned int uid = INSN_UID (insn);
2633
2634 if (!INSN_P (insn))
2635 continue;
2636
2637 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
2638 {
2639 struct df_ref *def = *def_rec;
2640 /* If the def is to only part of the reg, it does
2641 not kill the other defs that reach here. */
2642 if (!(DF_REF_FLAGS (def) & (DF_REF_CONDITIONAL)))
2643 {
2644 unsigned int dregno = DF_REF_REGNO (def);
2645 unsigned int start = problem_data->regno_start[dregno];
2646 unsigned int len = problem_data->regno_len[dregno];
2647 unsigned int sb;
2648 unsigned int lb;
2649 if (!df_compute_accessed_bytes (def, DF_MM_MUST, &sb, &lb))
2650 {
2651 start += sb;
2652 len = lb - sb;
2653 }
2654 if (len)
2655 {
2656 bitmap_set_range (bb_info->def, start, len);
2657 bitmap_clear_range (bb_info->use, start, len);
2658 }
2659 }
2660 }
2661
2662 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
2663 {
2664 struct df_ref *use = *use_rec;
2665 unsigned int uregno = DF_REF_REGNO (use);
2666 unsigned int start = problem_data->regno_start[uregno];
2667 unsigned int len = problem_data->regno_len[uregno];
2668 unsigned int sb;
2669 unsigned int lb;
2670 if (!df_compute_accessed_bytes (use, DF_MM_MAY, &sb, &lb))
2671 {
2672 start += sb;
2673 len = lb - sb;
2674 }
2675 /* Add use to set of uses in this BB. */
2676 if (len)
2677 bitmap_set_range (bb_info->use, start, len);
2678 }
2679 }
2680
2681 /* Process the registers set in an exception handler or the hard
2682 frame pointer if this block is the target of a non local
2683 goto. */
2684 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
2685 {
2686 struct df_ref *def = *def_rec;
2687 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
2688 {
2689 unsigned int dregno = DF_REF_REGNO (def);
2690 unsigned int start = problem_data->regno_start[dregno];
2691 unsigned int len = problem_data->regno_len[dregno];
2692 bitmap_set_range (bb_info->def, start, len);
2693 bitmap_clear_range (bb_info->use, start, len);
2694 }
2695 }
2696
2697 #ifdef EH_USES
2698 /* Process the uses that are live into an exception handler. */
2699 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
2700 {
2701 struct df_ref *use = *use_rec;
2702 /* Add use to set of uses in this BB. */
2703 if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
2704 {
2705 unsigned int uregno = DF_REF_REGNO (use);
2706 unsigned int start = problem_data->regno_start[uregno];
2707 unsigned int len = problem_data->regno_len[uregno];
2708 bitmap_set_range (bb_info->use, start, len);
2709 }
2710 }
2711 #endif
2712 }
2713
2714
2715 /* Compute local live register info for each basic block within BLOCKS. */
2716
2717 static void
2718 df_byte_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
2719 {
2720 unsigned int bb_index;
2721 bitmap_iterator bi;
2722
2723 EXECUTE_IF_SET_IN_BITMAP (df_byte_lr->out_of_date_transfer_functions, 0, bb_index, bi)
2724 {
2725 if (bb_index == EXIT_BLOCK)
2726 {
2727 /* The exit block is special for this problem and its bits are
2728 computed from thin air. */
2729 struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (EXIT_BLOCK);
2730 df_byte_lr_expand_bitmap (bb_info->use, df->exit_block_uses);
2731 }
2732 else
2733 df_byte_lr_bb_local_compute (bb_index);
2734 }
2735
2736 bitmap_clear (df_byte_lr->out_of_date_transfer_functions);
2737 }
2738
2739
2740 /* Initialize the solution vectors. */
2741
2742 static void
2743 df_byte_lr_init (bitmap all_blocks)
2744 {
2745 unsigned int bb_index;
2746 bitmap_iterator bi;
2747
2748 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2749 {
2750 struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb_index);
2751 bitmap_copy (bb_info->in, bb_info->use);
2752 bitmap_clear (bb_info->out);
2753 }
2754 }
2755
2756
2757 /* Confluence function that processes infinite loops. This might be a
2758 noreturn function that throws. And even if it isn't, getting the
2759 unwind info right helps debugging. */
2760 static void
2761 df_byte_lr_confluence_0 (basic_block bb)
2762 {
2763 struct df_byte_lr_problem_data *problem_data
2764 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2765 bitmap op1 = df_byte_lr_get_bb_info (bb->index)->out;
2766 if (bb != EXIT_BLOCK_PTR)
2767 bitmap_copy (op1, problem_data->hardware_regs_used);
2768 }
2769
2770
2771 /* Confluence function that ignores fake edges. */
2772
2773 static void
2774 df_byte_lr_confluence_n (edge e)
2775 {
2776 struct df_byte_lr_problem_data *problem_data
2777 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2778 bitmap op1 = df_byte_lr_get_bb_info (e->src->index)->out;
2779 bitmap op2 = df_byte_lr_get_bb_info (e->dest->index)->in;
2780
2781 /* Call-clobbered registers die across exception and call edges. */
2782 /* ??? Abnormal call edges ignored for the moment, as this gets
2783 confused by sibling call edges, which crashes reg-stack. */
2784 if (e->flags & EDGE_EH)
2785 bitmap_ior_and_compl_into (op1, op2, problem_data->invalidated_by_call);
2786 else
2787 bitmap_ior_into (op1, op2);
2788
2789 bitmap_ior_into (op1, problem_data->hardware_regs_used);
2790 }
2791
2792
2793 /* Transfer function. */
2794
2795 static bool
2796 df_byte_lr_transfer_function (int bb_index)
2797 {
2798 struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb_index);
2799 bitmap in = bb_info->in;
2800 bitmap out = bb_info->out;
2801 bitmap use = bb_info->use;
2802 bitmap def = bb_info->def;
2803
2804 return bitmap_ior_and_compl (in, use, out, def);
2805 }
2806
2807
2808 /* Free all storage associated with the problem. */
2809
2810 static void
2811 df_byte_lr_free (void)
2812 {
2813 struct df_byte_lr_problem_data *problem_data
2814 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2815
2816
2817 if (df_byte_lr->block_info)
2818 {
2819 free_alloc_pool (df_byte_lr->block_pool);
2820 df_byte_lr->block_info_size = 0;
2821 free (df_byte_lr->block_info);
2822 }
2823
2824 BITMAP_FREE (df_byte_lr->out_of_date_transfer_functions);
2825 bitmap_obstack_release (&problem_data->byte_lr_bitmaps);
2826 free (problem_data->regno_start);
2827 free (problem_data->regno_len);
2828 free (problem_data);
2829 free (df_byte_lr);
2830 }
2831
2832
2833 /* Debugging info at top of bb. */
2834
2835 static void
2836 df_byte_lr_top_dump (basic_block bb, FILE *file)
2837 {
2838 struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb->index);
2839 if (!bb_info || !bb_info->in)
2840 return;
2841
2842 fprintf (file, ";; blr in \t");
2843 df_print_byte_regset (file, bb_info->in);
2844 fprintf (file, ";; blr use \t");
2845 df_print_byte_regset (file, bb_info->use);
2846 fprintf (file, ";; blr def \t");
2847 df_print_byte_regset (file, bb_info->def);
2848 }
2849
2850
2851 /* Debugging info at bottom of bb. */
2852
2853 static void
2854 df_byte_lr_bottom_dump (basic_block bb, FILE *file)
2855 {
2856 struct df_byte_lr_bb_info *bb_info = df_byte_lr_get_bb_info (bb->index);
2857 if (!bb_info || !bb_info->out)
2858 return;
2859
2860 fprintf (file, ";; blr out \t");
2861 df_print_byte_regset (file, bb_info->out);
2862 }
2863
2864
2865 /* All of the information associated with every instance of the problem. */
2866
2867 static struct df_problem problem_BYTE_LR =
2868 {
2869 DF_BYTE_LR, /* Problem id. */
2870 DF_BACKWARD, /* Direction. */
2871 df_byte_lr_alloc, /* Allocate the problem specific data. */
2872 df_byte_lr_reset, /* Reset global information. */
2873 df_byte_lr_free_bb_info, /* Free basic block info. */
2874 df_byte_lr_local_compute, /* Local compute function. */
2875 df_byte_lr_init, /* Init the solution specific data. */
2876 df_worklist_dataflow, /* Worklist solver. */
2877 df_byte_lr_confluence_0, /* Confluence operator 0. */
2878 df_byte_lr_confluence_n, /* Confluence operator n. */
2879 df_byte_lr_transfer_function, /* Transfer function. */
2880 NULL, /* Finalize function. */
2881 df_byte_lr_free, /* Free all of the problem information. */
2882 df_byte_lr_free, /* Remove this problem from the stack of dataflow problems. */
2883 NULL, /* Debugging. */
2884 df_byte_lr_top_dump, /* Debugging start block. */
2885 df_byte_lr_bottom_dump, /* Debugging end block. */
2886 NULL, /* Incremental solution verify start. */
2887 NULL, /* Incremental solution verify end. */
2888 NULL, /* Dependent problem. */
2889 TV_DF_BYTE_LR, /* Timing variable. */
2890 false /* Reset blocks on dropping out of blocks_to_analyze. */
2891 };
2892
2893
2894 /* Create a new DATAFLOW instance and add it to an existing instance
2895 of DF. The returned structure is what is used to get at the
2896 solution. */
2897
2898 void
2899 df_byte_lr_add_problem (void)
2900 {
2901 df_add_problem (&problem_BYTE_LR);
2902 /* These will be initialized when df_scan_blocks processes each
2903 block. */
2904 df_byte_lr->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
2905 }
2906
2907
2908 /* Simulate the effects of the defs of INSN on LIVE. */
2909
2910 void
2911 df_byte_lr_simulate_defs (rtx insn, bitmap live)
2912 {
2913 struct df_byte_lr_problem_data *problem_data
2914 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2915 struct df_ref **def_rec;
2916 unsigned int uid = INSN_UID (insn);
2917
2918 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
2919 {
2920 struct df_ref *def = *def_rec;
2921
2922 /* If the def is to only part of the reg, it does
2923 not kill the other defs that reach here. */
2924 if (!(DF_REF_FLAGS (def) & DF_REF_CONDITIONAL))
2925 {
2926 unsigned int dregno = DF_REF_REGNO (def);
2927 unsigned int start = problem_data->regno_start[dregno];
2928 unsigned int len = problem_data->regno_len[dregno];
2929 unsigned int sb;
2930 unsigned int lb;
2931 if (!df_compute_accessed_bytes (def, DF_MM_MUST, &sb, &lb))
2932 {
2933 start += sb;
2934 len = lb - sb;
2935 }
2936
2937 if (len)
2938 bitmap_clear_range (live, start, len);
2939 }
2940 }
2941 }
2942
2943
2944 /* Simulate the effects of the uses of INSN on LIVE. */
2945
2946 void
2947 df_byte_lr_simulate_uses (rtx insn, bitmap live)
2948 {
2949 struct df_byte_lr_problem_data *problem_data
2950 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2951 struct df_ref **use_rec;
2952 unsigned int uid = INSN_UID (insn);
2953
2954 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
2955 {
2956 struct df_ref *use = *use_rec;
2957 unsigned int uregno = DF_REF_REGNO (use);
2958 unsigned int start = problem_data->regno_start[uregno];
2959 unsigned int len = problem_data->regno_len[uregno];
2960 unsigned int sb;
2961 unsigned int lb;
2962
2963 if (!df_compute_accessed_bytes (use, DF_MM_MAY, &sb, &lb))
2964 {
2965 start += sb;
2966 len = lb - sb;
2967 }
2968
2969 /* Add use to set of uses in this BB. */
2970 if (len)
2971 bitmap_set_range (live, start, len);
2972 }
2973 }
2974
2975
2976 /* Apply the artificial uses and defs at the top of BB in a forwards
2977 direction. */
2978
2979 void
2980 df_byte_lr_simulate_artificial_refs_at_top (basic_block bb, bitmap live)
2981 {
2982 struct df_byte_lr_problem_data *problem_data
2983 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
2984 struct df_ref **def_rec;
2985 #ifdef EH_USES
2986 struct df_ref **use_rec;
2987 #endif
2988 int bb_index = bb->index;
2989
2990 #ifdef EH_USES
2991 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
2992 {
2993 struct df_ref *use = *use_rec;
2994 if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
2995 {
2996 unsigned int uregno = DF_REF_REGNO (use);
2997 unsigned int start = problem_data->regno_start[uregno];
2998 unsigned int len = problem_data->regno_len[uregno];
2999 bitmap_set_range (live, start, len);
3000 }
3001 }
3002 #endif
3003
3004 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3005 {
3006 struct df_ref *def = *def_rec;
3007 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3008 {
3009 unsigned int dregno = DF_REF_REGNO (def);
3010 unsigned int start = problem_data->regno_start[dregno];
3011 unsigned int len = problem_data->regno_len[dregno];
3012 bitmap_clear_range (live, start, len);
3013 }
3014 }
3015 }
3016
3017
3018 /* Apply the artificial uses and defs at the end of BB in a backwards
3019 direction. */
3020
3021 void
3022 df_byte_lr_simulate_artificial_refs_at_end (basic_block bb, bitmap live)
3023 {
3024 struct df_byte_lr_problem_data *problem_data
3025 = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
3026 struct df_ref **def_rec;
3027 struct df_ref **use_rec;
3028 int bb_index = bb->index;
3029
3030 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3031 {
3032 struct df_ref *def = *def_rec;
3033 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3034 {
3035 unsigned int dregno = DF_REF_REGNO (def);
3036 unsigned int start = problem_data->regno_start[dregno];
3037 unsigned int len = problem_data->regno_len[dregno];
3038 bitmap_clear_range (live, start, len);
3039 }
3040 }
3041
3042 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3043 {
3044 struct df_ref *use = *use_rec;
3045 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3046 {
3047 unsigned int uregno = DF_REF_REGNO (use);
3048 unsigned int start = problem_data->regno_start[uregno];
3049 unsigned int len = problem_data->regno_len[uregno];
3050 bitmap_set_range (live, start, len);
3051 }
3052 }
3053 }
3054
3055
3056 \f
3057 /*----------------------------------------------------------------------------
3058 This problem computes REG_DEAD and REG_UNUSED notes.
3059 ----------------------------------------------------------------------------*/
3060
3061 static void
3062 df_note_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
3063 {
3064 df_note->optional_p = true;
3065 }
3066
3067 #ifdef REG_DEAD_DEBUGGING
3068 static void
3069 df_print_note (const char *prefix, rtx insn, rtx note)
3070 {
3071 if (dump_file)
3072 {
3073 fprintf (dump_file, "%s %d ", prefix, INSN_UID (insn));
3074 print_rtl (dump_file, note);
3075 fprintf (dump_file, "\n");
3076 }
3077 }
3078 #endif
3079
3080
3081 /* After reg-stack, the x86 floating point stack regs are difficult to
3082 analyze because of all of the pushes, pops and rotations. Thus, we
3083 just leave the notes alone. */
3084
3085 #ifdef STACK_REGS
3086 static inline bool
3087 df_ignore_stack_reg (int regno)
3088 {
3089 return regstack_completed
3090 && IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG);
3091 }
3092 #else
3093 static inline bool
3094 df_ignore_stack_reg (int regno ATTRIBUTE_UNUSED)
3095 {
3096 return false;
3097 }
3098 #endif
3099
3100
3101 /* Remove all of the REG_DEAD or REG_UNUSED notes from INSN and add
3102 them to OLD_DEAD_NOTES and OLD_UNUSED_NOTES. */
3103
3104 static void
3105 df_kill_notes (rtx insn, rtx *old_dead_notes, rtx *old_unused_notes)
3106 {
3107 rtx *pprev = &REG_NOTES (insn);
3108 rtx link = *pprev;
3109 rtx dead = NULL;
3110 rtx unused = NULL;
3111
3112 while (link)
3113 {
3114 switch (REG_NOTE_KIND (link))
3115 {
3116 case REG_DEAD:
3117 /* After reg-stack, we need to ignore any unused notes
3118 for the stack registers. */
3119 if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
3120 {
3121 pprev = &XEXP (link, 1);
3122 link = *pprev;
3123 }
3124 else
3125 {
3126 rtx next = XEXP (link, 1);
3127 #ifdef REG_DEAD_DEBUGGING
3128 df_print_note ("deleting: ", insn, link);
3129 #endif
3130 XEXP (link, 1) = dead;
3131 dead = link;
3132 *pprev = link = next;
3133 }
3134 break;
3135
3136 case REG_UNUSED:
3137 /* After reg-stack, we need to ignore any unused notes
3138 for the stack registers. */
3139 if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
3140 {
3141 pprev = &XEXP (link, 1);
3142 link = *pprev;
3143 }
3144 else
3145 {
3146 rtx next = XEXP (link, 1);
3147 #ifdef REG_DEAD_DEBUGGING
3148 df_print_note ("deleting: ", insn, link);
3149 #endif
3150 XEXP (link, 1) = unused;
3151 unused = link;
3152 *pprev = link = next;
3153 }
3154 break;
3155
3156 default:
3157 pprev = &XEXP (link, 1);
3158 link = *pprev;
3159 break;
3160 }
3161 }
3162
3163 *old_dead_notes = dead;
3164 *old_unused_notes = unused;
3165 }
3166
3167
3168 /* Set a NOTE_TYPE note for REG in INSN. Try to pull it from the OLD
3169 list, otherwise create a new one. */
3170
3171 static inline rtx
3172 df_set_note (enum reg_note note_type, rtx insn, rtx old, rtx reg)
3173 {
3174 rtx this = old;
3175 rtx prev = NULL;
3176
3177 while (this)
3178 if (XEXP (this, 0) == reg)
3179 {
3180 if (prev)
3181 XEXP (prev, 1) = XEXP (this, 1);
3182 else
3183 old = XEXP (this, 1);
3184 XEXP (this, 1) = REG_NOTES (insn);
3185 REG_NOTES (insn) = this;
3186 return old;
3187 }
3188 else
3189 {
3190 prev = this;
3191 this = XEXP (this, 1);
3192 }
3193
3194 /* Did not find the note. */
3195 REG_NOTES (insn) = alloc_EXPR_LIST (note_type, reg, REG_NOTES (insn));
3196 return old;
3197 }
3198
3199 /* A subroutine of df_set_unused_notes_for_mw, with a selection of its
3200 arguments. Return true if the register value described by MWS's
3201 mw_reg is known to be completely unused, and if mw_reg can therefore
3202 be used in a REG_UNUSED note. */
3203
3204 static bool
3205 df_whole_mw_reg_unused_p (struct df_mw_hardreg *mws,
3206 bitmap live, bitmap artificial_uses)
3207 {
3208 unsigned int r;
3209
3210 /* If MWS describes a partial reference, create REG_UNUSED notes for
3211 individual hard registers. */
3212 if (mws->flags & DF_REF_PARTIAL)
3213 return false;
3214
3215 /* Likewise if some part of the register is used. */
3216 for (r = mws->start_regno; r <= mws->end_regno; r++)
3217 if (bitmap_bit_p (live, r)
3218 || bitmap_bit_p (artificial_uses, r))
3219 return false;
3220
3221 gcc_assert (REG_P (mws->mw_reg));
3222 return true;
3223 }
3224
3225 /* Set the REG_UNUSED notes for the multiword hardreg defs in INSN
3226 based on the bits in LIVE. Do not generate notes for registers in
3227 artificial uses. DO_NOT_GEN is updated so that REG_DEAD notes are
3228 not generated if the reg is both read and written by the
3229 instruction.
3230 */
3231
3232 static rtx
3233 df_set_unused_notes_for_mw (rtx insn, rtx old, struct df_mw_hardreg *mws,
3234 bitmap live, bitmap do_not_gen,
3235 bitmap artificial_uses)
3236 {
3237 unsigned int r;
3238
3239 #ifdef REG_DEAD_DEBUGGING
3240 if (dump_file)
3241 fprintf (dump_file, "mw_set_unused looking at mws[%d..%d]\n",
3242 mws->start_regno, mws->end_regno);
3243 #endif
3244
3245 if (df_whole_mw_reg_unused_p (mws, live, artificial_uses))
3246 {
3247 unsigned int regno = mws->start_regno;
3248 old = df_set_note (REG_UNUSED, insn, old, mws->mw_reg);
3249
3250 #ifdef REG_DEAD_DEBUGGING
3251 df_print_note ("adding 1: ", insn, REG_NOTES (insn));
3252 #endif
3253 bitmap_set_bit (do_not_gen, regno);
3254 /* Only do this if the value is totally dead. */
3255 }
3256 else
3257 for (r = mws->start_regno; r <= mws->end_regno; r++)
3258 {
3259 if (!bitmap_bit_p (live, r)
3260 && !bitmap_bit_p (artificial_uses, r))
3261 {
3262 old = df_set_note (REG_UNUSED, insn, old, regno_reg_rtx[r]);
3263 #ifdef REG_DEAD_DEBUGGING
3264 df_print_note ("adding 2: ", insn, REG_NOTES (insn));
3265 #endif
3266 }
3267 bitmap_set_bit (do_not_gen, r);
3268 }
3269 return old;
3270 }
3271
3272
3273 /* A subroutine of df_set_dead_notes_for_mw, with a selection of its
3274 arguments. Return true if the register value described by MWS's
3275 mw_reg is known to be completely dead, and if mw_reg can therefore
3276 be used in a REG_DEAD note. */
3277
3278 static bool
3279 df_whole_mw_reg_dead_p (struct df_mw_hardreg *mws,
3280 bitmap live, bitmap artificial_uses,
3281 bitmap do_not_gen)
3282 {
3283 unsigned int r;
3284
3285 /* If MWS describes a partial reference, create REG_DEAD notes for
3286 individual hard registers. */
3287 if (mws->flags & DF_REF_PARTIAL)
3288 return false;
3289
3290 /* Likewise if some part of the register is not dead. */
3291 for (r = mws->start_regno; r <= mws->end_regno; r++)
3292 if (bitmap_bit_p (live, r)
3293 || bitmap_bit_p (artificial_uses, r)
3294 || bitmap_bit_p (do_not_gen, r))
3295 return false;
3296
3297 gcc_assert (REG_P (mws->mw_reg));
3298 return true;
3299 }
3300
3301 /* Set the REG_DEAD notes for the multiword hardreg use in INSN based
3302 on the bits in LIVE. DO_NOT_GEN is used to keep REG_DEAD notes
3303 from being set if the instruction both reads and writes the
3304 register. */
3305
3306 static rtx
3307 df_set_dead_notes_for_mw (rtx insn, rtx old, struct df_mw_hardreg *mws,
3308 bitmap live, bitmap do_not_gen,
3309 bitmap artificial_uses)
3310 {
3311 unsigned int r;
3312
3313 #ifdef REG_DEAD_DEBUGGING
3314 if (dump_file)
3315 {
3316 fprintf (dump_file, "mw_set_dead looking at mws[%d..%d]\n do_not_gen =",
3317 mws->start_regno, mws->end_regno);
3318 df_print_regset (dump_file, do_not_gen);
3319 fprintf (dump_file, " live =");
3320 df_print_regset (dump_file, live);
3321 fprintf (dump_file, " artificial uses =");
3322 df_print_regset (dump_file, artificial_uses);
3323 }
3324 #endif
3325
3326 if (df_whole_mw_reg_dead_p (mws, live, artificial_uses, do_not_gen))
3327 {
3328 /* Add a dead note for the entire multi word register. */
3329 old = df_set_note (REG_DEAD, insn, old, mws->mw_reg);
3330 #ifdef REG_DEAD_DEBUGGING
3331 df_print_note ("adding 1: ", insn, REG_NOTES (insn));
3332 #endif
3333 }
3334 else
3335 {
3336 for (r = mws->start_regno; r <= mws->end_regno; r++)
3337 if (!bitmap_bit_p (live, r)
3338 && !bitmap_bit_p (artificial_uses, r)
3339 && !bitmap_bit_p (do_not_gen, r))
3340 {
3341 old = df_set_note (REG_DEAD, insn, old, regno_reg_rtx[r]);
3342 #ifdef REG_DEAD_DEBUGGING
3343 df_print_note ("adding 2: ", insn, REG_NOTES (insn));
3344 #endif
3345 }
3346 }
3347 return old;
3348 }
3349
3350
3351 /* Create a REG_UNUSED note if necessary for DEF in INSN updating
3352 LIVE. Do not generate notes for registers in ARTIFICIAL_USES. */
3353
3354 static rtx
3355 df_create_unused_note (rtx insn, rtx old, struct df_ref *def,
3356 bitmap live, bitmap artificial_uses)
3357 {
3358 unsigned int dregno = DF_REF_REGNO (def);
3359
3360 #ifdef REG_DEAD_DEBUGGING
3361 if (dump_file)
3362 {
3363 fprintf (dump_file, " regular looking at def ");
3364 df_ref_debug (def, dump_file);
3365 }
3366 #endif
3367
3368 if (!(bitmap_bit_p (live, dregno)
3369 || (DF_REF_FLAGS (def) & DF_REF_MW_HARDREG)
3370 || bitmap_bit_p (artificial_uses, dregno)
3371 || df_ignore_stack_reg (dregno)))
3372 {
3373 rtx reg = (DF_REF_LOC (def))
3374 ? *DF_REF_REAL_LOC (def): DF_REF_REG (def);
3375 old = df_set_note (REG_UNUSED, insn, old, reg);
3376 #ifdef REG_DEAD_DEBUGGING
3377 df_print_note ("adding 3: ", insn, REG_NOTES (insn));
3378 #endif
3379 }
3380
3381 return old;
3382 }
3383
3384
3385 /* Recompute the REG_DEAD and REG_UNUSED notes and compute register
3386 info: lifetime, bb, and number of defs and uses for basic block
3387 BB. The three bitvectors are scratch regs used here. */
3388
3389 static void
3390 df_note_bb_compute (unsigned int bb_index,
3391 bitmap live, bitmap do_not_gen, bitmap artificial_uses)
3392 {
3393 basic_block bb = BASIC_BLOCK (bb_index);
3394 rtx insn;
3395 struct df_ref **def_rec;
3396 struct df_ref **use_rec;
3397
3398 bitmap_copy (live, df_get_live_out (bb));
3399 bitmap_clear (artificial_uses);
3400
3401 #ifdef REG_DEAD_DEBUGGING
3402 if (dump_file)
3403 {
3404 fprintf (dump_file, "live at bottom ");
3405 df_print_regset (dump_file, live);
3406 }
3407 #endif
3408
3409 /* Process the artificial defs and uses at the bottom of the block
3410 to begin processing. */
3411 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3412 {
3413 struct df_ref *def = *def_rec;
3414 #ifdef REG_DEAD_DEBUGGING
3415 if (dump_file)
3416 fprintf (dump_file, "artificial def %d\n", DF_REF_REGNO (def));
3417 #endif
3418
3419 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3420 bitmap_clear_bit (live, DF_REF_REGNO (def));
3421 }
3422
3423 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3424 {
3425 struct df_ref *use = *use_rec;
3426 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3427 {
3428 unsigned int regno = DF_REF_REGNO (use);
3429 bitmap_set_bit (live, regno);
3430
3431 /* Notes are not generated for any of the artificial registers
3432 at the bottom of the block. */
3433 bitmap_set_bit (artificial_uses, regno);
3434 }
3435 }
3436
3437 #ifdef REG_DEAD_DEBUGGING
3438 if (dump_file)
3439 {
3440 fprintf (dump_file, "live before artificials out ");
3441 df_print_regset (dump_file, live);
3442 }
3443 #endif
3444
3445 FOR_BB_INSNS_REVERSE (bb, insn)
3446 {
3447 unsigned int uid = INSN_UID (insn);
3448 struct df_mw_hardreg **mws_rec;
3449 rtx old_dead_notes;
3450 rtx old_unused_notes;
3451
3452 if (!INSN_P (insn))
3453 continue;
3454
3455 bitmap_clear (do_not_gen);
3456 df_kill_notes (insn, &old_dead_notes, &old_unused_notes);
3457
3458 /* Process the defs. */
3459 if (CALL_P (insn))
3460 {
3461 #ifdef REG_DEAD_DEBUGGING
3462 if (dump_file)
3463 {
3464 fprintf (dump_file, "processing call %d\n live =", INSN_UID (insn));
3465 df_print_regset (dump_file, live);
3466 }
3467 #endif
3468 /* We only care about real sets for calls. Clobbers cannot
3469 be depended on to really die. */
3470 mws_rec = DF_INSN_UID_MWS (uid);
3471 while (*mws_rec)
3472 {
3473 struct df_mw_hardreg *mws = *mws_rec;
3474 if ((mws->type == DF_REF_REG_DEF)
3475 && !df_ignore_stack_reg (mws->start_regno))
3476 old_unused_notes
3477 = df_set_unused_notes_for_mw (insn, old_unused_notes,
3478 mws, live, do_not_gen,
3479 artificial_uses);
3480 mws_rec++;
3481 }
3482
3483 /* All of the defs except the return value are some sort of
3484 clobber. This code is for the return. */
3485 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3486 {
3487 struct df_ref *def = *def_rec;
3488 unsigned int dregno = DF_REF_REGNO (def);
3489 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
3490 {
3491 old_unused_notes
3492 = df_create_unused_note (insn, old_unused_notes,
3493 def, live, artificial_uses);
3494 bitmap_set_bit (do_not_gen, dregno);
3495 }
3496
3497 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3498 bitmap_clear_bit (live, dregno);
3499 }
3500 }
3501 else
3502 {
3503 /* Regular insn. */
3504 mws_rec = DF_INSN_UID_MWS (uid);
3505 while (*mws_rec)
3506 {
3507 struct df_mw_hardreg *mws = *mws_rec;
3508 if (mws->type == DF_REF_REG_DEF)
3509 old_unused_notes
3510 = df_set_unused_notes_for_mw (insn, old_unused_notes,
3511 mws, live, do_not_gen,
3512 artificial_uses);
3513 mws_rec++;
3514 }
3515
3516 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3517 {
3518 struct df_ref *def = *def_rec;
3519 unsigned int dregno = DF_REF_REGNO (def);
3520 old_unused_notes
3521 = df_create_unused_note (insn, old_unused_notes,
3522 def, live, artificial_uses);
3523
3524 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
3525 bitmap_set_bit (do_not_gen, dregno);
3526
3527 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3528 bitmap_clear_bit (live, dregno);
3529 }
3530 }
3531
3532 /* Process the uses. */
3533 mws_rec = DF_INSN_UID_MWS (uid);
3534 while (*mws_rec)
3535 {
3536 struct df_mw_hardreg *mws = *mws_rec;
3537 if ((mws->type != DF_REF_REG_DEF)
3538 && !df_ignore_stack_reg (mws->start_regno))
3539 old_dead_notes
3540 = df_set_dead_notes_for_mw (insn, old_dead_notes,
3541 mws, live, do_not_gen,
3542 artificial_uses);
3543 mws_rec++;
3544 }
3545
3546 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
3547 {
3548 struct df_ref *use = *use_rec;
3549 unsigned int uregno = DF_REF_REGNO (use);
3550
3551 #ifdef REG_DEAD_DEBUGGING
3552 if (dump_file)
3553 {
3554 fprintf (dump_file, " regular looking at use ");
3555 df_ref_debug (use, dump_file);
3556 }
3557 #endif
3558 if (!bitmap_bit_p (live, uregno))
3559 {
3560 if ( (!(DF_REF_FLAGS (use) & DF_REF_MW_HARDREG))
3561 && (!bitmap_bit_p (do_not_gen, uregno))
3562 && (!bitmap_bit_p (artificial_uses, uregno))
3563 && (!(DF_REF_FLAGS (use) & DF_REF_READ_WRITE))
3564 && (!df_ignore_stack_reg (uregno)))
3565 {
3566 rtx reg = (DF_REF_LOC (use))
3567 ? *DF_REF_REAL_LOC (use) : DF_REF_REG (use);
3568 old_dead_notes = df_set_note (REG_DEAD, insn, old_dead_notes, reg);
3569
3570 #ifdef REG_DEAD_DEBUGGING
3571 df_print_note ("adding 4: ", insn, REG_NOTES (insn));
3572 #endif
3573 }
3574 /* This register is now live. */
3575 bitmap_set_bit (live, uregno);
3576 }
3577 }
3578
3579 while (old_unused_notes)
3580 {
3581 rtx next = XEXP (old_unused_notes, 1);
3582 free_EXPR_LIST_node (old_unused_notes);
3583 old_unused_notes = next;
3584 }
3585 while (old_dead_notes)
3586 {
3587 rtx next = XEXP (old_dead_notes, 1);
3588 free_EXPR_LIST_node (old_dead_notes);
3589 old_dead_notes = next;
3590 }
3591 }
3592 }
3593
3594
3595 /* Compute register info: lifetime, bb, and number of defs and uses. */
3596 static void
3597 df_note_compute (bitmap all_blocks)
3598 {
3599 unsigned int bb_index;
3600 bitmap_iterator bi;
3601 bitmap live = BITMAP_ALLOC (&df_bitmap_obstack);
3602 bitmap do_not_gen = BITMAP_ALLOC (&df_bitmap_obstack);
3603 bitmap artificial_uses = BITMAP_ALLOC (&df_bitmap_obstack);
3604
3605 #ifdef REG_DEAD_DEBUGGING
3606 if (dump_file)
3607 print_rtl_with_bb (dump_file, get_insns());
3608 #endif
3609
3610 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
3611 {
3612 df_note_bb_compute (bb_index, live, do_not_gen, artificial_uses);
3613 }
3614
3615 BITMAP_FREE (live);
3616 BITMAP_FREE (do_not_gen);
3617 BITMAP_FREE (artificial_uses);
3618 }
3619
3620
3621 /* Free all storage associated with the problem. */
3622
3623 static void
3624 df_note_free (void)
3625 {
3626 free (df_note);
3627 }
3628
3629
3630 /* All of the information associated every instance of the problem. */
3631
3632 static struct df_problem problem_NOTE =
3633 {
3634 DF_NOTE, /* Problem id. */
3635 DF_NONE, /* Direction. */
3636 df_note_alloc, /* Allocate the problem specific data. */
3637 NULL, /* Reset global information. */
3638 NULL, /* Free basic block info. */
3639 df_note_compute, /* Local compute function. */
3640 NULL, /* Init the solution specific data. */
3641 NULL, /* Iterative solver. */
3642 NULL, /* Confluence operator 0. */
3643 NULL, /* Confluence operator n. */
3644 NULL, /* Transfer function. */
3645 NULL, /* Finalize function. */
3646 df_note_free, /* Free all of the problem information. */
3647 df_note_free, /* Remove this problem from the stack of dataflow problems. */
3648 NULL, /* Debugging. */
3649 NULL, /* Debugging start block. */
3650 NULL, /* Debugging end block. */
3651 NULL, /* Incremental solution verify start. */
3652 NULL, /* Incremental solution verify end. */
3653 &problem_LR, /* Dependent problem. */
3654 TV_DF_NOTE, /* Timing variable. */
3655 false /* Reset blocks on dropping out of blocks_to_analyze. */
3656 };
3657
3658
3659 /* Create a new DATAFLOW instance and add it to an existing instance
3660 of DF. The returned structure is what is used to get at the
3661 solution. */
3662
3663 void
3664 df_note_add_problem (void)
3665 {
3666 df_add_problem (&problem_NOTE);
3667 }
3668
3669
3670
3671 \f
3672 /*----------------------------------------------------------------------------
3673 Functions for simulating the effects of single insns.
3674
3675 You can either simulate in the forwards direction, starting from
3676 the top of a block or the backwards direction from the end of the
3677 block. The main difference is that if you go forwards, the uses
3678 are examined first then the defs, and if you go backwards, the defs
3679 are examined first then the uses.
3680
3681 If you start at the top of the block, use one of DF_LIVE_IN or
3682 DF_LR_IN. If you start at the bottom of the block use one of
3683 DF_LIVE_OUT or DF_LR_OUT. BE SURE TO PASS A COPY OF THESE SETS,
3684 THEY WILL BE DESTROYED.
3685 ----------------------------------------------------------------------------*/
3686
3687
3688 /* Find the set of DEFs for INSN. */
3689
3690 void
3691 df_simulate_find_defs (rtx insn, bitmap defs)
3692 {
3693 struct df_ref **def_rec;
3694 unsigned int uid = INSN_UID (insn);
3695
3696 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3697 {
3698 struct df_ref *def = *def_rec;
3699 /* If the def is to only part of the reg, it does
3700 not kill the other defs that reach here. */
3701 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
3702 bitmap_set_bit (defs, DF_REF_REGNO (def));
3703 }
3704 }
3705
3706
3707 /* Simulate the effects of the defs of INSN on LIVE. */
3708
3709 void
3710 df_simulate_defs (rtx insn, bitmap live)
3711 {
3712 struct df_ref **def_rec;
3713 unsigned int uid = INSN_UID (insn);
3714
3715 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3716 {
3717 struct df_ref *def = *def_rec;
3718 unsigned int dregno = DF_REF_REGNO (def);
3719
3720 /* If the def is to only part of the reg, it does
3721 not kill the other defs that reach here. */
3722 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
3723 bitmap_clear_bit (live, dregno);
3724 }
3725 }
3726
3727
3728 /* Simulate the effects of the uses of INSN on LIVE. */
3729
3730 void
3731 df_simulate_uses (rtx insn, bitmap live)
3732 {
3733 struct df_ref **use_rec;
3734 unsigned int uid = INSN_UID (insn);
3735
3736 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
3737 {
3738 struct df_ref *use = *use_rec;
3739 /* Add use to set of uses in this BB. */
3740 bitmap_set_bit (live, DF_REF_REGNO (use));
3741 }
3742 }
3743
3744
3745 /* Add back the always live regs in BB to LIVE. */
3746
3747 static inline void
3748 df_simulate_fixup_sets (basic_block bb, bitmap live)
3749 {
3750 /* These regs are considered always live so if they end up dying
3751 because of some def, we need to bring the back again. */
3752 if (bb_has_eh_pred (bb))
3753 bitmap_ior_into (live, df->eh_block_artificial_uses);
3754 else
3755 bitmap_ior_into (live, df->regular_block_artificial_uses);
3756 }
3757
3758
3759 /*----------------------------------------------------------------------------
3760 The following three functions are used only for BACKWARDS scanning:
3761 i.e. they process the defs before the uses.
3762
3763 df_simulate_artificial_refs_at_end should be called first with a
3764 bitvector copyied from the DF_LIVE_OUT or DF_LR_OUT. Then
3765 df_simulate_one_insn should be called for each insn in the block,
3766 starting with the last on. Finally,
3767 df_simulate_artificial_refs_at_top can be called to get a new value
3768 of the sets at the top of the block (this is rarely used).
3769
3770 It would be not be difficult to define a similar set of functions
3771 that work in the forwards direction. In that case the functions
3772 would ignore the use sets and look for the REG_DEAD and REG_UNUSED
3773 notes.
3774 ----------------------------------------------------------------------------*/
3775
3776 /* Apply the artificial uses and defs at the end of BB in a backwards
3777 direction. */
3778
3779 void
3780 df_simulate_artificial_refs_at_end (basic_block bb, bitmap live)
3781 {
3782 struct df_ref **def_rec;
3783 struct df_ref **use_rec;
3784 int bb_index = bb->index;
3785
3786 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3787 {
3788 struct df_ref *def = *def_rec;
3789 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3790 bitmap_clear_bit (live, DF_REF_REGNO (def));
3791 }
3792
3793 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3794 {
3795 struct df_ref *use = *use_rec;
3796 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3797 bitmap_set_bit (live, DF_REF_REGNO (use));
3798 }
3799 }
3800
3801
3802 /* Simulate the backwards effects of INSN on the bitmap LIVE. */
3803
3804 void
3805 df_simulate_one_insn (basic_block bb, rtx insn, bitmap live)
3806 {
3807 if (! INSN_P (insn))
3808 return;
3809
3810 df_simulate_defs (insn, live);
3811 df_simulate_uses (insn, live);
3812 df_simulate_fixup_sets (bb, live);
3813 }
3814
3815
3816 /* Apply the artificial uses and defs at the top of BB in a backwards
3817 direction. */
3818
3819 void
3820 df_simulate_artificial_refs_at_top (basic_block bb, bitmap live)
3821 {
3822 struct df_ref **def_rec;
3823 #ifdef EH_USES
3824 struct df_ref **use_rec;
3825 #endif
3826 int bb_index = bb->index;
3827
3828 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
3829 {
3830 struct df_ref *def = *def_rec;
3831 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3832 bitmap_clear_bit (live, DF_REF_REGNO (def));
3833 }
3834
3835 #ifdef EH_USES
3836 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
3837 {
3838 struct df_ref *use = *use_rec;
3839 if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
3840 bitmap_set_bit (live, DF_REF_REGNO (use));
3841 }
3842 #endif
3843 }
Mirror of the offical gcc git repository hosted at gcc.gnu.org