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