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