?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Merge from mainline
[official-gcc.git] / gcc / df-problems.c
blob257baad5b86c043db8be1f939b29d9abb0a26a0c
1 /* Standard problems for dataflow support routines.
2 Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006
3 Free Software Foundation, Inc.
4 Originally contributed by Michael P. Hayes
5 (m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com)
6 Major rewrite contributed by Danny Berlin (dberlin@dberlin.org)
7 and Kenneth Zadeck (zadeck@naturalbridge.com).
8
9 This file is part of GCC.
10
11 GCC is free software; you can redistribute it and/or modify it under
12 the terms of the GNU General Public License as published by the Free
13 Software Foundation; either version 2, or (at your option) any later
14 version.
15
16 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
17 WARRANTY; without even the implied warranty of MERCHANTABILITY or
18 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 for more details.
20
21 You should have received a copy of the GNU General Public License
22 along with GCC; see the file COPYING. If not, write to the Free
23 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
24 02110-1301, USA. */
25
26 #include "config.h"
27 #include "system.h"
28 #include "coretypes.h"
29 #include "tm.h"
30 #include "rtl.h"
31 #include "tm_p.h"
32 #include "insn-config.h"
33 #include "recog.h"
34 #include "function.h"
35 #include "regs.h"
36 #include "output.h"
37 #include "alloc-pool.h"
38 #include "flags.h"
39 #include "hard-reg-set.h"
40 #include "basic-block.h"
41 #include "sbitmap.h"
42 #include "bitmap.h"
43 #include "timevar.h"
44 #include "df.h"
45
46 #define DF_SPARSE_THRESHOLD 32
47
48 static bitmap seen_in_block = NULL;
49 static bitmap seen_in_insn = NULL;
50
51 \f
52 /*----------------------------------------------------------------------------
53 Public functions access functions for the dataflow problems.
54 ----------------------------------------------------------------------------*/
55
56 /* Get the instance of the problem that DFLOW is dependent on. */
57
58 struct dataflow *
59 df_get_dependent_problem (struct dataflow *dflow)
60 {
61 struct df *df = dflow->df;
62 struct df_problem *dependent_problem = dflow->problem->dependent_problem;
63
64 gcc_assert (dependent_problem);
65 return df->problems_by_index[dependent_problem->id];
66 }
67
68
69 /* Create a du or ud chain from SRC to DST and link it into SRC. */
70
71 struct df_link *
72 df_chain_create (struct dataflow *dflow, struct df_ref *src, struct df_ref *dst)
73 {
74 struct df_link *head = DF_REF_CHAIN (src);
75 struct df_link *link = pool_alloc (dflow->block_pool);;
76
77 DF_REF_CHAIN (src) = link;
78 link->next = head;
79 link->ref = dst;
80 return link;
81 }
82
83
84 /* Delete a du or ud chain for REF. If LINK is NULL, delete all
85 chains for ref and check to see if the reverse chains can also be
86 deleted. If LINK is not NULL it must be a link off of ref. In
87 this case, the other end is not deleted. */
88
89 void
90 df_chain_unlink (struct dataflow *dflow, struct df_ref *ref, struct df_link *link)
91 {
92 struct df_link *chain = DF_REF_CHAIN (ref);
93 if (link)
94 {
95 /* Link was the first element in the chain. */
96 if (chain == link)
97 DF_REF_CHAIN (ref) = link->next;
98 else
99 {
100 /* Link is an internal element in the chain. */
101 struct df_link *prev = chain;
102 while (chain)
103 {
104 if (chain == link)
105 {
106 prev->next = chain->next;
107 break;
108 }
109 prev = chain;
110 chain = chain->next;
111 }
112 }
113 pool_free (dflow->block_pool, link);
114 }
115 else
116 {
117 /* If chain is NULL here, it was because of a recursive call
118 when the other flavor of chains was not built. Just run thru
119 the entire chain calling the other side and then deleting the
120 link. */
121 while (chain)
122 {
123 struct df_link *next = chain->next;
124 /* Delete the other side if it exists. */
125 df_chain_unlink (dflow, chain->ref, chain);
126 chain = next;
127 }
128 }
129 }
130
131
132 /* Copy the du or ud chain starting at FROM_REF and attach it to
133 TO_REF. */
134
135 void
136 df_chain_copy (struct dataflow *dflow,
137 struct df_ref *to_ref,
138 struct df_link *from_ref)
139 {
140 while (from_ref)
141 {
142 df_chain_create (dflow, to_ref, from_ref->ref);
143 from_ref = from_ref->next;
144 }
145 }
146
147
148 /* Get the live in set for BB no matter what problem happens to be
149 defined. */
150
151 bitmap
152 df_get_live_in (struct df *df, basic_block bb)
153 {
154 gcc_assert (df->problems_by_index[DF_LR]);
155
156 if (df->problems_by_index[DF_UREC])
157 return DF_RA_LIVE_IN (df, bb);
158 else if (df->problems_by_index[DF_UR])
159 return DF_LIVE_IN (df, bb);
160 else
161 return DF_UPWARD_LIVE_IN (df, bb);
162 }
163
164
165 /* Get the live out set for BB no matter what problem happens to be
166 defined. */
167
168 bitmap
169 df_get_live_out (struct df *df, basic_block bb)
170 {
171 gcc_assert (df->problems_by_index[DF_LR]);
172
173 if (df->problems_by_index[DF_UREC])
174 return DF_RA_LIVE_OUT (df, bb);
175 else if (df->problems_by_index[DF_UR])
176 return DF_LIVE_OUT (df, bb);
177 else
178 return DF_UPWARD_LIVE_OUT (df, bb);
179 }
180
181
182 /*----------------------------------------------------------------------------
183 Utility functions.
184 ----------------------------------------------------------------------------*/
185
186 /* Generic versions to get the void* version of the block info. Only
187 used inside the problem instace vectors. */
188
189 /* Grow the bb_info array. */
190
191 void
192 df_grow_bb_info (struct dataflow *dflow)
193 {
194 unsigned int new_size = last_basic_block + 1;
195 if (dflow->block_info_size < new_size)
196 {
197 new_size += new_size / 4;
198 dflow->block_info = xrealloc (dflow->block_info,
199 new_size *sizeof (void*));
200 memset (dflow->block_info + dflow->block_info_size, 0,
201 (new_size - dflow->block_info_size) *sizeof (void *));
202 dflow->block_info_size = new_size;
203 }
204 }
205
206 /* Dump a def-use or use-def chain for REF to FILE. */
207
208 void
209 df_chain_dump (struct df *df ATTRIBUTE_UNUSED, struct df_link *link, FILE *file)
210 {
211 fprintf (file, "{ ");
212 for (; link; link = link->next)
213 {
214 fprintf (file, "%c%d(bb %d insn %d) ",
215 DF_REF_REG_DEF_P (link->ref) ? 'd' : 'u',
216 DF_REF_ID (link->ref),
217 DF_REF_BBNO (link->ref),
218 DF_REF_INSN (link->ref) ? DF_REF_INSN_UID (link->ref) : -1);
219 }
220 fprintf (file, "}");
221 }
222
223
224 /* Print some basic block info as part of df_dump. */
225
226 void
227 df_print_bb_index (basic_block bb, FILE *file)
228 {
229 edge e;
230 edge_iterator ei;
231
232 fprintf (file, "( ");
233 FOR_EACH_EDGE (e, ei, bb->preds)
234 {
235 basic_block pred = e->src;
236 fprintf (file, "%d ", pred->index);
237 }
238 fprintf (file, ")->[%d]->( ", bb->index);
239 FOR_EACH_EDGE (e, ei, bb->succs)
240 {
241 basic_block succ = e->dest;
242 fprintf (file, "%d ", succ->index);
243 }
244 fprintf (file, ")\n");
245 }
246
247
248 /* Return the set of reference ids in CHAIN, caching the result in *BMAP. */
249
250 static inline bitmap
251 df_ref_bitmap (bitmap *maps, unsigned int regno, int start, int count)
252 {
253 bitmap ids = maps[regno];
254 if (!ids)
255 {
256 unsigned int i;
257 unsigned int end = start + count;;
258 ids = BITMAP_ALLOC (NULL);
259 maps[regno] = ids;
260 for (i = start; i < end; i++)
261 bitmap_set_bit (ids, i);
262 }
263 return ids;
264 }
265
266
267 /* Make sure that the seen_in_insn and seen_in_block sbitmaps are set
268 up correctly. */
269
270 static void
271 df_set_seen (void)
272 {
273 seen_in_block = BITMAP_ALLOC (NULL);
274 seen_in_insn = BITMAP_ALLOC (NULL);
275 }
276
277
278 static void
279 df_unset_seen (void)
280 {
281 BITMAP_FREE (seen_in_block);
282 BITMAP_FREE (seen_in_insn);
283 }
284
285
286 \f
287 /*----------------------------------------------------------------------------
288 REACHING USES
289
290 Find the locations in the function where each use site for a pseudo
291 can reach backwards.
292
293 ----------------------------------------------------------------------------*/
294
295 struct df_ru_problem_data
296 {
297 bitmap *use_sites; /* Bitmap of uses for each pseudo. */
298 unsigned int use_sites_size; /* Size of use_sites. */
299 /* The set of defs to regs invalidated by call. */
300 bitmap sparse_invalidated_by_call;
301 /* The set of defs to regs invalidated by call for ru. */
302 bitmap dense_invalidated_by_call;
303 };
304
305 /* Get basic block info. */
306
307 struct df_ru_bb_info *
308 df_ru_get_bb_info (struct dataflow *dflow, unsigned int index)
309 {
310 return (struct df_ru_bb_info *) dflow->block_info[index];
311 }
312
313
314 /* Set basic block info. */
315
316 static void
317 df_ru_set_bb_info (struct dataflow *dflow, unsigned int index,
318 struct df_ru_bb_info *bb_info)
319 {
320 dflow->block_info[index] = bb_info;
321 }
322
323
324 /* Free basic block info. */
325
326 static void
327 df_ru_free_bb_info (struct dataflow *dflow,
328 basic_block bb ATTRIBUTE_UNUSED,
329 void *vbb_info)
330 {
331 struct df_ru_bb_info *bb_info = (struct df_ru_bb_info *) vbb_info;
332 if (bb_info)
333 {
334 BITMAP_FREE (bb_info->kill);
335 BITMAP_FREE (bb_info->sparse_kill);
336 BITMAP_FREE (bb_info->gen);
337 BITMAP_FREE (bb_info->in);
338 BITMAP_FREE (bb_info->out);
339 pool_free (dflow->block_pool, bb_info);
340 }
341 }
342
343
344 /* Allocate or reset bitmaps for DFLOW blocks. The solution bits are
345 not touched unless the block is new. */
346
347 static void
348 df_ru_alloc (struct dataflow *dflow, bitmap blocks_to_rescan)
349 {
350 unsigned int bb_index;
351 bitmap_iterator bi;
352 unsigned int reg_size = max_reg_num ();
353
354 if (! dflow->block_pool)
355 dflow->block_pool = create_alloc_pool ("df_ru_block pool",
356 sizeof (struct df_ru_bb_info), 50);
357
358 if (dflow->problem_data)
359 {
360 unsigned int i;
361 struct df_ru_problem_data *problem_data =
362 (struct df_ru_problem_data *) dflow->problem_data;
363
364 for (i = 0; i < problem_data->use_sites_size; i++)
365 {
366 bitmap bm = problem_data->use_sites[i];
367 if (bm)
368 {
369 BITMAP_FREE (bm);
370 problem_data->use_sites[i] = NULL;
371 }
372 }
373
374 if (problem_data->use_sites_size < reg_size)
375 {
376 problem_data->use_sites
377 = xrealloc (problem_data->use_sites, reg_size * sizeof (bitmap));
378 memset (problem_data->use_sites + problem_data->use_sites_size, 0,
379 (reg_size - problem_data->use_sites_size) * sizeof (bitmap));
380 problem_data->use_sites_size = reg_size;
381 }
382
383 bitmap_clear (problem_data->sparse_invalidated_by_call);
384 bitmap_clear (problem_data->dense_invalidated_by_call);
385 }
386 else
387 {
388 struct df_ru_problem_data *problem_data = XNEW (struct df_ru_problem_data);
389 dflow->problem_data = problem_data;
390
391 problem_data->use_sites = XCNEWVEC (bitmap, reg_size);
392 problem_data->use_sites_size = reg_size;
393 problem_data->sparse_invalidated_by_call = BITMAP_ALLOC (NULL);
394 problem_data->dense_invalidated_by_call = BITMAP_ALLOC (NULL);
395 }
396
397 df_grow_bb_info (dflow);
398
399 /* Because of the clustering of all def sites for the same pseudo,
400 we have to process all of the blocks before doing the
401 analysis. */
402
403 EXECUTE_IF_SET_IN_BITMAP (blocks_to_rescan, 0, bb_index, bi)
404 {
405 struct df_ru_bb_info *bb_info = df_ru_get_bb_info (dflow, bb_index);
406 if (bb_info)
407 {
408 bitmap_clear (bb_info->kill);
409 bitmap_clear (bb_info->sparse_kill);
410 bitmap_clear (bb_info->gen);
411 }
412 else
413 {
414 bb_info = (struct df_ru_bb_info *) pool_alloc (dflow->block_pool);
415 df_ru_set_bb_info (dflow, bb_index, bb_info);
416 bb_info->kill = BITMAP_ALLOC (NULL);
417 bb_info->sparse_kill = BITMAP_ALLOC (NULL);
418 bb_info->gen = BITMAP_ALLOC (NULL);
419 bb_info->in = BITMAP_ALLOC (NULL);
420 bb_info->out = BITMAP_ALLOC (NULL);
421 }
422 }
423 }
424
425
426 /* Process a list of DEFs for df_ru_bb_local_compute. */
427
428 static void
429 df_ru_bb_local_compute_process_def (struct dataflow *dflow,
430 struct df_ru_bb_info *bb_info,
431 struct df_ref *def,
432 enum df_ref_flags top_flag)
433 {
434 struct df *df = dflow->df;
435 while (def)
436 {
437 if (top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
438 {
439 unsigned int regno = DF_REF_REGNO (def);
440 unsigned int begin = DF_REG_USE_GET (df, regno)->begin;
441 unsigned int n_uses = DF_REG_USE_GET (df, regno)->n_refs;
442 if (!bitmap_bit_p (seen_in_block, regno))
443 {
444 /* The first def for regno, causes the kill info to be
445 generated and the gen information to cleared. */
446 if (!bitmap_bit_p (seen_in_insn, regno))
447 {
448 if (n_uses > DF_SPARSE_THRESHOLD)
449 {
450 bitmap_set_bit (bb_info->sparse_kill, regno);
451 bitmap_clear_range (bb_info->gen, begin, n_uses);
452 }
453 else
454 {
455 struct df_ru_problem_data * problem_data =
456 (struct df_ru_problem_data *)dflow->problem_data;
457 bitmap uses =
458 df_ref_bitmap (problem_data->use_sites, regno,
459 begin, n_uses);
460 bitmap_ior_into (bb_info->kill, uses);
461 bitmap_and_compl_into (bb_info->gen, uses);
462 }
463 }
464 bitmap_set_bit (seen_in_insn, regno);
465 }
466 }
467 def = def->next_ref;
468 }
469 }
470
471
472 /* Process a list of USEs for df_ru_bb_local_compute. */
473
474 static void
475 df_ru_bb_local_compute_process_use (struct df_ru_bb_info *bb_info,
476 struct df_ref *use,
477 enum df_ref_flags top_flag)
478 {
479 while (use)
480 {
481 if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
482 {
483 /* Add use to set of gens in this BB unless we have seen a
484 def in a previous instruction. */
485 unsigned int regno = DF_REF_REGNO (use);
486 if (!bitmap_bit_p (seen_in_block, regno))
487 bitmap_set_bit (bb_info->gen, DF_REF_ID (use));
488 }
489 use = use->next_ref;
490 }
491 }
492
493 /* Compute local reaching use (upward exposed use) info for basic
494 block BB. USE_INFO->REGS[R] caches the set of uses for register R. */
495 static void
496 df_ru_bb_local_compute (struct dataflow *dflow, unsigned int bb_index)
497 {
498 struct df *df = dflow->df;
499 basic_block bb = BASIC_BLOCK (bb_index);
500 struct df_ru_bb_info *bb_info = df_ru_get_bb_info (dflow, bb_index);
501 rtx insn;
502
503 /* Set when a def for regno is seen. */
504 bitmap_clear (seen_in_block);
505 bitmap_clear (seen_in_insn);
506
507 #ifdef EH_USES
508 /* Variables defined in the prolog that are used by the exception
509 handler. */
510 df_ru_bb_local_compute_process_use (bb_info,
511 df_get_artificial_uses (df, bb_index),
512 DF_REF_AT_TOP);
513 #endif
514 df_ru_bb_local_compute_process_def (dflow, bb_info,
515 df_get_artificial_defs (df, bb_index),
516 DF_REF_AT_TOP);
517
518 FOR_BB_INSNS (bb, insn)
519 {
520 unsigned int uid = INSN_UID (insn);
521 if (! INSN_P (insn))
522 continue;
523
524 df_ru_bb_local_compute_process_def (dflow, bb_info,
525 DF_INSN_UID_GET (df, uid)->defs, 0);
526
527 /* The use processing must happen after the defs processing even
528 though the uses logically happen first since the defs clear
529 the gen set. Otherwise, a use for regno occuring in the same
530 instruction as a def for regno would be cleared. */
531 df_ru_bb_local_compute_process_use (bb_info,
532 DF_INSN_UID_GET (df, uid)->uses, 0);
533
534 bitmap_ior_into (seen_in_block, seen_in_insn);
535 bitmap_clear (seen_in_insn);
536 }
537
538 /* Process the hardware registers that are always live. */
539 df_ru_bb_local_compute_process_use (bb_info,
540 df_get_artificial_uses (df, bb_index), 0);
541
542 df_ru_bb_local_compute_process_def (dflow, bb_info,
543 df_get_artificial_defs (df, bb_index), 0);
544 }
545
546
547 /* Compute local reaching use (upward exposed use) info for each basic
548 block within BLOCKS. */
549 static void
550 df_ru_local_compute (struct dataflow *dflow,
551 bitmap all_blocks,
552 bitmap rescan_blocks ATTRIBUTE_UNUSED)
553 {
554 struct df *df = dflow->df;
555 unsigned int bb_index;
556 bitmap_iterator bi;
557 unsigned int regno;
558 struct df_ru_problem_data *problem_data =
559 (struct df_ru_problem_data *) dflow->problem_data;
560 bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
561 bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
562
563 df_set_seen ();
564
565 if (!df->use_info.refs_organized)
566 df_reorganize_refs (&df->use_info);
567
568 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
569 {
570 df_ru_bb_local_compute (dflow, bb_index);
571 }
572
573 /* Set up the knockout bit vectors to be applied across EH_EDGES. */
574 EXECUTE_IF_SET_IN_BITMAP (df_invalidated_by_call, 0, regno, bi)
575 {
576 struct df_reg_info *reg_info = DF_REG_USE_GET (df, regno);
577 if (reg_info->n_refs > DF_SPARSE_THRESHOLD)
578 bitmap_set_bit (sparse_invalidated, regno);
579 else
580 {
581 bitmap defs = df_ref_bitmap (problem_data->use_sites, regno,
582 reg_info->begin, reg_info->n_refs);
583 bitmap_ior_into (dense_invalidated, defs);
584 }
585 }
586
587 df_unset_seen ();
588 }
589
590
591 /* Initialize the solution bit vectors for problem. */
592
593 static void
594 df_ru_init_solution (struct dataflow *dflow, bitmap all_blocks)
595 {
596 unsigned int bb_index;
597 bitmap_iterator bi;
598
599 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
600 {
601 struct df_ru_bb_info *bb_info = df_ru_get_bb_info (dflow, bb_index);
602 bitmap_copy (bb_info->in, bb_info->gen);
603 bitmap_clear (bb_info->out);
604 }
605 }
606
607
608 /* Out of target gets or of in of source. */
609
610 static void
611 df_ru_confluence_n (struct dataflow *dflow, edge e)
612 {
613 bitmap op1 = df_ru_get_bb_info (dflow, e->src->index)->out;
614 bitmap op2 = df_ru_get_bb_info (dflow, e->dest->index)->in;
615
616 if (e->flags & EDGE_EH)
617 {
618 struct df_ru_problem_data *problem_data =
619 (struct df_ru_problem_data *) dflow->problem_data;
620 bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
621 bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
622 struct df *df = dflow->df;
623 bitmap_iterator bi;
624 unsigned int regno;
625 bitmap tmp = BITMAP_ALLOC (NULL);
626
627 bitmap_copy (tmp, op2);
628 bitmap_and_compl_into (tmp, dense_invalidated);
629
630 EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi)
631 {
632 bitmap_clear_range (tmp,
633 DF_REG_USE_GET (df, regno)->begin,
634 DF_REG_USE_GET (df, regno)->n_refs);
635 }
636 bitmap_ior_into (op1, tmp);
637 BITMAP_FREE (tmp);
638 }
639 else
640 bitmap_ior_into (op1, op2);
641 }
642
643
644 /* Transfer function. */
645
646 static bool
647 df_ru_transfer_function (struct dataflow *dflow, int bb_index)
648 {
649 struct df_ru_bb_info *bb_info = df_ru_get_bb_info (dflow, bb_index);
650 unsigned int regno;
651 bitmap_iterator bi;
652 bitmap in = bb_info->in;
653 bitmap out = bb_info->out;
654 bitmap gen = bb_info->gen;
655 bitmap kill = bb_info->kill;
656 bitmap sparse_kill = bb_info->sparse_kill;
657
658 if (bitmap_empty_p (sparse_kill))
659 return bitmap_ior_and_compl (in, gen, out, kill);
660 else
661 {
662 struct df *df = dflow->df;
663 bool changed = false;
664 bitmap tmp = BITMAP_ALLOC (NULL);
665 bitmap_copy (tmp, in);
666 EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi)
667 {
668 bitmap_clear_range (tmp,
669 DF_REG_USE_GET (df, regno)->begin,
670 DF_REG_USE_GET (df, regno)->n_refs);
671 }
672 bitmap_and_compl_into (tmp, kill);
673 bitmap_ior_into (tmp, gen);
674 changed = !bitmap_equal_p (tmp, in);
675 if (changed)
676 {
677 BITMAP_FREE (out);
678 bb_info->in = tmp;
679 }
680 else
681 BITMAP_FREE (tmp);
682 return changed;
683 }
684 }
685
686
687 /* Free all storage associated with the problem. */
688
689 static void
690 df_ru_free (struct dataflow *dflow)
691 {
692 unsigned int i;
693 struct df_ru_problem_data *problem_data =
694 (struct df_ru_problem_data *) dflow->problem_data;
695
696 if (problem_data)
697 {
698 for (i = 0; i < dflow->block_info_size; i++)
699 {
700 struct df_ru_bb_info *bb_info = df_ru_get_bb_info (dflow, i);
701 if (bb_info)
702 {
703 BITMAP_FREE (bb_info->kill);
704 BITMAP_FREE (bb_info->sparse_kill);
705 BITMAP_FREE (bb_info->gen);
706 BITMAP_FREE (bb_info->in);
707 BITMAP_FREE (bb_info->out);
708 }
709 }
710
711 free_alloc_pool (dflow->block_pool);
712
713 for (i = 0; i < problem_data->use_sites_size; i++)
714 {
715 bitmap bm = problem_data->use_sites[i];
716 if (bm)
717 BITMAP_FREE (bm);
718 }
719
720 free (problem_data->use_sites);
721 BITMAP_FREE (problem_data->sparse_invalidated_by_call);
722 BITMAP_FREE (problem_data->dense_invalidated_by_call);
723
724 dflow->block_info_size = 0;
725 free (dflow->block_info);
726 free (dflow->problem_data);
727 }
728 free (dflow);
729 }
730
731
732 /* Debugging info. */
733
734 static void
735 df_ru_dump (struct dataflow *dflow, FILE *file)
736 {
737 basic_block bb;
738 struct df *df = dflow->df;
739 struct df_ru_problem_data *problem_data =
740 (struct df_ru_problem_data *) dflow->problem_data;
741 unsigned int m = max_reg_num ();
742 unsigned int regno;
743
744 fprintf (file, "Reaching uses:\n");
745
746 fprintf (file, " sparse invalidated \t");
747 dump_bitmap (file, problem_data->sparse_invalidated_by_call);
748 fprintf (file, " dense invalidated \t");
749 dump_bitmap (file, problem_data->dense_invalidated_by_call);
750
751 for (regno = 0; regno < m; regno++)
752 if (DF_REG_USE_GET (df, regno)->n_refs)
753 fprintf (file, "%d[%d,%d] ", regno,
754 DF_REG_USE_GET (df, regno)->begin,
755 DF_REG_USE_GET (df, regno)->n_refs);
756 fprintf (file, "\n");
757
758 FOR_ALL_BB (bb)
759 {
760 struct df_ru_bb_info *bb_info = df_ru_get_bb_info (dflow, bb->index);
761 df_print_bb_index (bb, file);
762
763 if (! bb_info->in)
764 continue;
765
766 fprintf (file, " in \t");
767 dump_bitmap (file, bb_info->in);
768 fprintf (file, " gen \t");
769 dump_bitmap (file, bb_info->gen);
770 fprintf (file, " kill\t");
771 dump_bitmap (file, bb_info->kill);
772 fprintf (file, " out \t");
773 dump_bitmap (file, bb_info->out);
774 }
775 }
776
777 /* All of the information associated with every instance of the problem. */
778
779 static struct df_problem problem_RU =
780 {
781 DF_RU, /* Problem id. */
782 DF_BACKWARD, /* Direction. */
783 df_ru_alloc, /* Allocate the problem specific data. */
784 NULL, /* Reset global information. */
785 df_ru_free_bb_info, /* Free basic block info. */
786 df_ru_local_compute, /* Local compute function. */
787 df_ru_init_solution, /* Init the solution specific data. */
788 df_iterative_dataflow, /* Iterative solver. */
789 NULL, /* Confluence operator 0. */
790 df_ru_confluence_n, /* Confluence operator n. */
791 df_ru_transfer_function, /* Transfer function. */
792 NULL, /* Finalize function. */
793 df_ru_free, /* Free all of the problem information. */
794 df_ru_dump, /* Debugging. */
795 NULL /* Dependent problem. */
796 };
797
798
799
800 /* Create a new DATAFLOW instance and add it to an existing instance
801 of DF. The returned structure is what is used to get at the
802 solution. */
803
804 struct dataflow *
805 df_ru_add_problem (struct df *df)
806 {
807 return df_add_problem (df, &problem_RU);
808 }
809
810 \f
811 /*----------------------------------------------------------------------------
812 REACHING DEFINITIONS
813
814 Find the locations in the function where each definition site for a
815 pseudo reaches.
816 ----------------------------------------------------------------------------*/
817
818 struct df_rd_problem_data
819 {
820 bitmap *def_sites; /* Bitmap of defs for each pseudo. */
821 unsigned int def_sites_size; /* Size of def_sites. */
822 /* The set of defs to regs invalidated by call. */
823 bitmap sparse_invalidated_by_call;
824 /* The set of defs to regs invalidate by call for ru. */
825 bitmap dense_invalidated_by_call;
826 };
827
828 /* Get basic block info. */
829
830 struct df_rd_bb_info *
831 df_rd_get_bb_info (struct dataflow *dflow, unsigned int index)
832 {
833 return (struct df_rd_bb_info *) dflow->block_info[index];
834 }
835
836
837 /* Set basic block info. */
838
839 static void
840 df_rd_set_bb_info (struct dataflow *dflow, unsigned int index,
841 struct df_rd_bb_info *bb_info)
842 {
843 dflow->block_info[index] = bb_info;
844 }
845
846
847 /* Free basic block info. */
848
849 static void
850 df_rd_free_bb_info (struct dataflow *dflow,
851 basic_block bb ATTRIBUTE_UNUSED,
852 void *vbb_info)
853 {
854 struct df_rd_bb_info *bb_info = (struct df_rd_bb_info *) vbb_info;
855 if (bb_info)
856 {
857 BITMAP_FREE (bb_info->kill);
858 BITMAP_FREE (bb_info->sparse_kill);
859 BITMAP_FREE (bb_info->gen);
860 BITMAP_FREE (bb_info->in);
861 BITMAP_FREE (bb_info->out);
862 pool_free (dflow->block_pool, bb_info);
863 }
864 }
865
866
867 /* Allocate or reset bitmaps for DFLOW blocks. The solution bits are
868 not touched unless the block is new. */
869
870 static void
871 df_rd_alloc (struct dataflow *dflow, bitmap blocks_to_rescan)
872 {
873 unsigned int bb_index;
874 bitmap_iterator bi;
875 unsigned int reg_size = max_reg_num ();
876
877 if (! dflow->block_pool)
878 dflow->block_pool = create_alloc_pool ("df_rd_block pool",
879 sizeof (struct df_rd_bb_info), 50);
880
881 if (dflow->problem_data)
882 {
883 unsigned int i;
884 struct df_rd_problem_data *problem_data =
885 (struct df_rd_problem_data *) dflow->problem_data;
886
887 for (i = 0; i < problem_data->def_sites_size; i++)
888 {
889 bitmap bm = problem_data->def_sites[i];
890 if (bm)
891 {
892 BITMAP_FREE (bm);
893 problem_data->def_sites[i] = NULL;
894 }
895 }
896
897 if (problem_data->def_sites_size < reg_size)
898 {
899 problem_data->def_sites
900 = xrealloc (problem_data->def_sites, reg_size *sizeof (bitmap));
901 memset (problem_data->def_sites + problem_data->def_sites_size, 0,
902 (reg_size - problem_data->def_sites_size) *sizeof (bitmap));
903 problem_data->def_sites_size = reg_size;
904 }
905
906 bitmap_clear (problem_data->sparse_invalidated_by_call);
907 bitmap_clear (problem_data->dense_invalidated_by_call);
908 }
909 else
910 {
911 struct df_rd_problem_data *problem_data = XNEW (struct df_rd_problem_data);
912 dflow->problem_data = problem_data;
913
914 problem_data->def_sites = XCNEWVEC (bitmap, reg_size);
915 problem_data->def_sites_size = reg_size;
916 problem_data->sparse_invalidated_by_call = BITMAP_ALLOC (NULL);
917 problem_data->dense_invalidated_by_call = BITMAP_ALLOC (NULL);
918 }
919
920 df_grow_bb_info (dflow);
921
922 /* Because of the clustering of all def sites for the same pseudo,
923 we have to process all of the blocks before doing the
924 analysis. */
925
926 EXECUTE_IF_SET_IN_BITMAP (blocks_to_rescan, 0, bb_index, bi)
927 {
928 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (dflow, bb_index);
929 if (bb_info)
930 {
931 bitmap_clear (bb_info->kill);
932 bitmap_clear (bb_info->sparse_kill);
933 bitmap_clear (bb_info->gen);
934 }
935 else
936 {
937 bb_info = (struct df_rd_bb_info *) pool_alloc (dflow->block_pool);
938 df_rd_set_bb_info (dflow, bb_index, bb_info);
939 bb_info->kill = BITMAP_ALLOC (NULL);
940 bb_info->sparse_kill = BITMAP_ALLOC (NULL);
941 bb_info->gen = BITMAP_ALLOC (NULL);
942 bb_info->in = BITMAP_ALLOC (NULL);
943 bb_info->out = BITMAP_ALLOC (NULL);
944 }
945 }
946 }
947
948
949 /* Process a list of DEFs for df_rd_bb_local_compute. */
950
951 static void
952 df_rd_bb_local_compute_process_def (struct dataflow *dflow,
953 struct df_rd_bb_info *bb_info,
954 struct df_ref *def,
955 enum df_ref_flags top_flag)
956 {
957 struct df *df = dflow->df;
958 while (def)
959 {
960 if (top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
961 {
962 unsigned int regno = DF_REF_REGNO (def);
963 unsigned int begin = DF_REG_DEF_GET (df, regno)->begin;
964 unsigned int n_defs = DF_REG_DEF_GET (df, regno)->n_refs;
965
966 /* Only the last def(s) for a regno in the block has any
967 effect. */
968 if (!bitmap_bit_p (seen_in_block, regno))
969 {
970 /* The first def for regno in insn gets to knock out the
971 defs from other instructions. */
972 if (!bitmap_bit_p (seen_in_insn, regno))
973 {
974 if (n_defs > DF_SPARSE_THRESHOLD)
975 {
976 bitmap_set_bit (bb_info->sparse_kill, regno);
977 bitmap_clear_range(bb_info->gen, begin, n_defs);
978 }
979 else
980 {
981 struct df_rd_problem_data * problem_data =
982 (struct df_rd_problem_data *)dflow->problem_data;
983 bitmap defs =
984 df_ref_bitmap (problem_data->def_sites, regno,
985 begin, n_defs);
986 bitmap_ior_into (bb_info->kill, defs);
987 bitmap_and_compl_into (bb_info->gen, defs);
988 }
989 }
990
991 bitmap_set_bit (seen_in_insn, regno);
992 /* All defs for regno in the instruction may be put into
993 the gen set. */
994 if (! (DF_REF_FLAGS (def) & DF_REF_CLOBBER))
995 bitmap_set_bit (bb_info->gen, DF_REF_ID (def));
996 }
997 }
998 def = def->next_ref;
999 }
1000 }
1001
1002 /* Compute local reaching def info for basic block BB. */
1003
1004 static void
1005 df_rd_bb_local_compute (struct dataflow *dflow, unsigned int bb_index)
1006 {
1007 struct df *df = dflow->df;
1008 basic_block bb = BASIC_BLOCK (bb_index);
1009 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (dflow, bb_index);
1010 rtx insn;
1011
1012 bitmap_clear (seen_in_block);
1013 bitmap_clear (seen_in_insn);
1014
1015 df_rd_bb_local_compute_process_def (dflow, bb_info,
1016 df_get_artificial_defs (df, bb_index), 0);
1017
1018 FOR_BB_INSNS_REVERSE (bb, insn)
1019 {
1020 unsigned int uid = INSN_UID (insn);
1021
1022 if (! INSN_P (insn))
1023 continue;
1024
1025 df_rd_bb_local_compute_process_def (dflow, bb_info,
1026 DF_INSN_UID_GET (df, uid)->defs, 0);
1027
1028 /* This complex dance with the two bitmaps is required because
1029 instructions can assign twice to the same pseudo. This
1030 generally happens with calls that will have one def for the
1031 result and another def for the clobber. If only one vector
1032 is used and the clobber goes first, the result will be
1033 lost. */
1034 bitmap_ior_into (seen_in_block, seen_in_insn);
1035 bitmap_clear (seen_in_insn);
1036 }
1037
1038 /* Process the artificial defs at the top of the block last since we
1039 are going backwards through the block and these are logically at
1040 the start. */
1041 df_rd_bb_local_compute_process_def (dflow, bb_info,
1042 df_get_artificial_defs (df, bb_index),
1043 DF_REF_AT_TOP);
1044 }
1045
1046
1047 /* Compute local reaching def info for each basic block within BLOCKS. */
1048
1049 static void
1050 df_rd_local_compute (struct dataflow *dflow,
1051 bitmap all_blocks,
1052 bitmap rescan_blocks ATTRIBUTE_UNUSED)
1053 {
1054 struct df *df = dflow->df;
1055 unsigned int bb_index;
1056 bitmap_iterator bi;
1057 unsigned int regno;
1058 struct df_rd_problem_data *problem_data =
1059 (struct df_rd_problem_data *) dflow->problem_data;
1060 bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
1061 bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
1062
1063 df_set_seen ();
1064
1065 if (!df->def_info.refs_organized)
1066 df_reorganize_refs (&df->def_info);
1067
1068 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1069 {
1070 df_rd_bb_local_compute (dflow, bb_index);
1071 }
1072
1073 /* Set up the knockout bit vectors to be applied across EH_EDGES. */
1074 EXECUTE_IF_SET_IN_BITMAP (df_invalidated_by_call, 0, regno, bi)
1075 {
1076 struct df_reg_info *reg_info = DF_REG_DEF_GET (df, regno);
1077 if (reg_info->n_refs > DF_SPARSE_THRESHOLD)
1078 {
1079 bitmap_set_bit (sparse_invalidated, regno);
1080 }
1081 else
1082 {
1083 bitmap defs = df_ref_bitmap (problem_data->def_sites, regno,
1084 reg_info->begin, reg_info->n_refs);
1085 bitmap_ior_into (dense_invalidated, defs);
1086 }
1087 }
1088 df_unset_seen ();
1089 }
1090
1091
1092 /* Initialize the solution bit vectors for problem. */
1093
1094 static void
1095 df_rd_init_solution (struct dataflow *dflow, bitmap all_blocks)
1096 {
1097 unsigned int bb_index;
1098 bitmap_iterator bi;
1099
1100 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1101 {
1102 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (dflow, bb_index);
1103
1104 bitmap_copy (bb_info->out, bb_info->gen);
1105 bitmap_clear (bb_info->in);
1106 }
1107 }
1108
1109 /* In of target gets or of out of source. */
1110
1111 static void
1112 df_rd_confluence_n (struct dataflow *dflow, edge e)
1113 {
1114 bitmap op1 = df_rd_get_bb_info (dflow, e->dest->index)->in;
1115 bitmap op2 = df_rd_get_bb_info (dflow, e->src->index)->out;
1116
1117 if (e->flags & EDGE_EH)
1118 {
1119 struct df_rd_problem_data *problem_data =
1120 (struct df_rd_problem_data *) dflow->problem_data;
1121 bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
1122 bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
1123 struct df *df = dflow->df;
1124 bitmap_iterator bi;
1125 unsigned int regno;
1126 bitmap tmp = BITMAP_ALLOC (NULL);
1127
1128 bitmap_copy (tmp, op2);
1129 bitmap_and_compl_into (tmp, dense_invalidated);
1130
1131 EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi)
1132 {
1133 bitmap_clear_range (tmp,
1134 DF_REG_DEF_GET (df, regno)->begin,
1135 DF_REG_DEF_GET (df, regno)->n_refs);
1136 }
1137 bitmap_ior_into (op1, tmp);
1138 BITMAP_FREE (tmp);
1139 }
1140 else
1141 bitmap_ior_into (op1, op2);
1142 }
1143
1144
1145 /* Transfer function. */
1146
1147 static bool
1148 df_rd_transfer_function (struct dataflow *dflow, int bb_index)
1149 {
1150 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (dflow, bb_index);
1151 unsigned int regno;
1152 bitmap_iterator bi;
1153 bitmap in = bb_info->in;
1154 bitmap out = bb_info->out;
1155 bitmap gen = bb_info->gen;
1156 bitmap kill = bb_info->kill;
1157 bitmap sparse_kill = bb_info->sparse_kill;
1158
1159 if (bitmap_empty_p (sparse_kill))
1160 return bitmap_ior_and_compl (out, gen, in, kill);
1161 else
1162 {
1163 struct df *df = dflow->df;
1164 bool changed = false;
1165 bitmap tmp = BITMAP_ALLOC (NULL);
1166 bitmap_copy (tmp, in);
1167 EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi)
1168 {
1169 bitmap_clear_range (tmp,
1170 DF_REG_DEF_GET (df, regno)->begin,
1171 DF_REG_DEF_GET (df, regno)->n_refs);
1172 }
1173 bitmap_and_compl_into (tmp, kill);
1174 bitmap_ior_into (tmp, gen);
1175 changed = !bitmap_equal_p (tmp, out);
1176 if (changed)
1177 {
1178 BITMAP_FREE (out);
1179 bb_info->out = tmp;
1180 }
1181 else
1182 BITMAP_FREE (tmp);
1183 return changed;
1184 }
1185 }
1186
1187
1188 /* Free all storage associated with the problem. */
1189
1190 static void
1191 df_rd_free (struct dataflow *dflow)
1192 {
1193 unsigned int i;
1194 struct df_rd_problem_data *problem_data =
1195 (struct df_rd_problem_data *) dflow->problem_data;
1196
1197 if (problem_data)
1198 {
1199 for (i = 0; i < dflow->block_info_size; i++)
1200 {
1201 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (dflow, i);
1202 if (bb_info)
1203 {
1204 BITMAP_FREE (bb_info->kill);
1205 BITMAP_FREE (bb_info->sparse_kill);
1206 BITMAP_FREE (bb_info->gen);
1207 BITMAP_FREE (bb_info->in);
1208 BITMAP_FREE (bb_info->out);
1209 }
1210 }
1211
1212 free_alloc_pool (dflow->block_pool);
1213
1214 for (i = 0; i < problem_data->def_sites_size; i++)
1215 {
1216 bitmap bm = problem_data->def_sites[i];
1217 if (bm)
1218 BITMAP_FREE (bm);
1219 }
1220
1221 free (problem_data->def_sites);
1222 BITMAP_FREE (problem_data->sparse_invalidated_by_call);
1223 BITMAP_FREE (problem_data->dense_invalidated_by_call);
1224
1225 dflow->block_info_size = 0;
1226 free (dflow->block_info);
1227 free (dflow->problem_data);
1228 }
1229 free (dflow);
1230 }
1231
1232
1233 /* Debugging info. */
1234
1235 static void
1236 df_rd_dump (struct dataflow *dflow, FILE *file)
1237 {
1238 struct df *df = dflow->df;
1239 basic_block bb;
1240 struct df_rd_problem_data *problem_data =
1241 (struct df_rd_problem_data *) dflow->problem_data;
1242 unsigned int m = max_reg_num ();
1243 unsigned int regno;
1244
1245 fprintf (file, "Reaching defs:\n\n");
1246
1247 fprintf (file, " sparse invalidated \t");
1248 dump_bitmap (file, problem_data->sparse_invalidated_by_call);
1249 fprintf (file, " dense invalidated \t");
1250 dump_bitmap (file, problem_data->dense_invalidated_by_call);
1251
1252 for (regno = 0; regno < m; regno++)
1253 if (DF_REG_DEF_GET (df, regno)->n_refs)
1254 fprintf (file, "%d[%d,%d] ", regno,
1255 DF_REG_DEF_GET (df, regno)->begin,
1256 DF_REG_DEF_GET (df, regno)->n_refs);
1257 fprintf (file, "\n");
1258
1259 FOR_ALL_BB (bb)
1260 {
1261 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (dflow, bb->index);
1262 df_print_bb_index (bb, file);
1263
1264 if (! bb_info->in)
1265 continue;
1266
1267 fprintf (file, " in\t(%d)\n", (int) bitmap_count_bits (bb_info->in));
1268 dump_bitmap (file, bb_info->in);
1269 fprintf (file, " gen \t(%d)\n", (int) bitmap_count_bits (bb_info->gen));
1270 dump_bitmap (file, bb_info->gen);
1271 fprintf (file, " kill\t(%d)\n", (int) bitmap_count_bits (bb_info->kill));
1272 dump_bitmap (file, bb_info->kill);
1273 fprintf (file, " out\t(%d)\n", (int) bitmap_count_bits (bb_info->out));
1274 dump_bitmap (file, bb_info->out);
1275 }
1276 }
1277
1278 /* All of the information associated with every instance of the problem. */
1279
1280 static struct df_problem problem_RD =
1281 {
1282 DF_RD, /* Problem id. */
1283 DF_FORWARD, /* Direction. */
1284 df_rd_alloc, /* Allocate the problem specific data. */
1285 NULL, /* Reset global information. */
1286 df_rd_free_bb_info, /* Free basic block info. */
1287 df_rd_local_compute, /* Local compute function. */
1288 df_rd_init_solution, /* Init the solution specific data. */
1289 df_iterative_dataflow, /* Iterative solver. */
1290 NULL, /* Confluence operator 0. */
1291 df_rd_confluence_n, /* Confluence operator n. */
1292 df_rd_transfer_function, /* Transfer function. */
1293 NULL, /* Finalize function. */
1294 df_rd_free, /* Free all of the problem information. */
1295 df_rd_dump, /* Debugging. */
1296 NULL /* Dependent problem. */
1297 };
1298
1299
1300
1301 /* Create a new DATAFLOW instance and add it to an existing instance
1302 of DF. The returned structure is what is used to get at the
1303 solution. */
1304
1305 struct dataflow *
1306 df_rd_add_problem (struct df *df)
1307 {
1308 return df_add_problem (df, &problem_RD);
1309 }
1310
1311
1312 \f
1313 /*----------------------------------------------------------------------------
1314 LIVE REGISTERS
1315
1316 Find the locations in the function where any use of a pseudo can reach
1317 in the backwards direction.
1318 ----------------------------------------------------------------------------*/
1319
1320 /* Get basic block info. */
1321
1322 struct df_lr_bb_info *
1323 df_lr_get_bb_info (struct dataflow *dflow, unsigned int index)
1324 {
1325 return (struct df_lr_bb_info *) dflow->block_info[index];
1326 }
1327
1328
1329 /* Set basic block info. */
1330
1331 static void
1332 df_lr_set_bb_info (struct dataflow *dflow, unsigned int index,
1333 struct df_lr_bb_info *bb_info)
1334 {
1335 dflow->block_info[index] = bb_info;
1336 }
1337
1338
1339 /* Free basic block info. */
1340
1341 static void
1342 df_lr_free_bb_info (struct dataflow *dflow,
1343 basic_block bb ATTRIBUTE_UNUSED,
1344 void *vbb_info)
1345 {
1346 struct df_lr_bb_info *bb_info = (struct df_lr_bb_info *) vbb_info;
1347 if (bb_info)
1348 {
1349 BITMAP_FREE (bb_info->use);
1350 BITMAP_FREE (bb_info->def);
1351 BITMAP_FREE (bb_info->in);
1352 BITMAP_FREE (bb_info->out);
1353 pool_free (dflow->block_pool, bb_info);
1354 }
1355 }
1356
1357
1358 /* Allocate or reset bitmaps for DFLOW blocks. The solution bits are
1359 not touched unless the block is new. */
1360
1361 static void
1362 df_lr_alloc (struct dataflow *dflow, bitmap blocks_to_rescan)
1363 {
1364 unsigned int bb_index;
1365 bitmap_iterator bi;
1366
1367 if (! dflow->block_pool)
1368 dflow->block_pool = create_alloc_pool ("df_lr_block pool",
1369 sizeof (struct df_lr_bb_info), 50);
1370
1371 df_grow_bb_info (dflow);
1372
1373 /* Because of the clustering of all def sites for the same pseudo,
1374 we have to process all of the blocks before doing the
1375 analysis. */
1376
1377 EXECUTE_IF_SET_IN_BITMAP (blocks_to_rescan, 0, bb_index, bi)
1378 {
1379 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (dflow, bb_index);
1380 if (bb_info)
1381 {
1382 bitmap_clear (bb_info->def);
1383 bitmap_clear (bb_info->use);
1384 }
1385 else
1386 {
1387 bb_info = (struct df_lr_bb_info *) pool_alloc (dflow->block_pool);
1388 df_lr_set_bb_info (dflow, bb_index, bb_info);
1389 bb_info->use = BITMAP_ALLOC (NULL);
1390 bb_info->def = BITMAP_ALLOC (NULL);
1391 bb_info->in = BITMAP_ALLOC (NULL);
1392 bb_info->out = BITMAP_ALLOC (NULL);
1393 }
1394 }
1395 }
1396
1397
1398 /* Compute local live register info for basic block BB. */
1399
1400 static void
1401 df_lr_bb_local_compute (struct dataflow *dflow,
1402 struct df *df, unsigned int bb_index)
1403 {
1404 basic_block bb = BASIC_BLOCK (bb_index);
1405 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (dflow, bb_index);
1406 rtx insn;
1407 struct df_ref *def;
1408 struct df_ref *use;
1409
1410 /* Process the registers set in an exception handler. */
1411 for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref)
1412 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
1413 {
1414 unsigned int dregno = DF_REF_REGNO (def);
1415 bitmap_set_bit (bb_info->def, dregno);
1416 bitmap_clear_bit (bb_info->use, dregno);
1417 }
1418
1419 /* Process the hardware registers that are always live. */
1420 for (use = df_get_artificial_uses (df, bb_index); use; use = use->next_ref)
1421 /* Add use to set of uses in this BB. */
1422 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
1423 bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
1424
1425 FOR_BB_INSNS_REVERSE (bb, insn)
1426 {
1427 unsigned int uid = INSN_UID (insn);
1428
1429 if (! INSN_P (insn))
1430 continue;
1431
1432 if (CALL_P (insn))
1433 {
1434 for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
1435 {
1436 unsigned int dregno = DF_REF_REGNO (def);
1437
1438 if (dregno >= FIRST_PSEUDO_REGISTER
1439 || !(SIBLING_CALL_P (insn)
1440 && bitmap_bit_p (df->exit_block_uses, dregno)
1441 && !refers_to_regno_p (dregno, dregno+1,
1442 current_function_return_rtx,
1443 (rtx *)0)))
1444 {
1445 /* Add def to set of defs in this BB. */
1446 bitmap_set_bit (bb_info->def, dregno);
1447 bitmap_clear_bit (bb_info->use, dregno);
1448 }
1449 }
1450 }
1451 else
1452 {
1453 for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
1454 {
1455 unsigned int dregno = DF_REF_REGNO (def);
1456
1457 if (DF_INSN_CONTAINS_ASM (df, insn)
1458 && dregno < FIRST_PSEUDO_REGISTER)
1459 {
1460 unsigned int i;
1461 unsigned int end =
1462 dregno + hard_regno_nregs[dregno][GET_MODE (DF_REF_REG (def))] - 1;
1463 for (i = dregno; i <= end; ++i)
1464 regs_asm_clobbered[i] = 1;
1465 }
1466 /* Add def to set of defs in this BB. */
1467 bitmap_set_bit (bb_info->def, dregno);
1468 bitmap_clear_bit (bb_info->use, dregno);
1469 }
1470 }
1471
1472 for (use = DF_INSN_UID_GET (df, uid)->uses; use; use = use->next_ref)
1473 /* Add use to set of uses in this BB. */
1474 bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
1475 }
1476
1477 /* Process the registers set in an exception handler. */
1478 for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref)
1479 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
1480 {
1481 unsigned int dregno = DF_REF_REGNO (def);
1482 bitmap_set_bit (bb_info->def, dregno);
1483 bitmap_clear_bit (bb_info->use, dregno);
1484 }
1485
1486 #ifdef EH_USES
1487 /* Process the uses that are live into an exception handler. */
1488 for (use = df_get_artificial_uses (df, bb_index); use; use = use->next_ref)
1489 /* Add use to set of uses in this BB. */
1490 if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
1491 bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
1492 #endif
1493 }
1494
1495 /* Compute local live register info for each basic block within BLOCKS. */
1496
1497 static void
1498 df_lr_local_compute (struct dataflow *dflow,
1499 bitmap all_blocks,
1500 bitmap rescan_blocks)
1501 {
1502 struct df *df = dflow->df;
1503 unsigned int bb_index;
1504 bitmap_iterator bi;
1505
1506 /* Assume that the stack pointer is unchanging if alloca hasn't
1507 been used. */
1508 if (bitmap_equal_p (all_blocks, rescan_blocks))
1509 memset (regs_asm_clobbered, 0, sizeof (regs_asm_clobbered));
1510
1511 bitmap_clear (df->hardware_regs_used);
1512
1513 /* The all-important stack pointer must always be live. */
1514 bitmap_set_bit (df->hardware_regs_used, STACK_POINTER_REGNUM);
1515
1516 /* Before reload, there are a few registers that must be forced
1517 live everywhere -- which might not already be the case for
1518 blocks within infinite loops. */
1519 if (! reload_completed)
1520 {
1521 /* Any reference to any pseudo before reload is a potential
1522 reference of the frame pointer. */
1523 bitmap_set_bit (df->hardware_regs_used, FRAME_POINTER_REGNUM);
1524
1525 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
1526 /* Pseudos with argument area equivalences may require
1527 reloading via the argument pointer. */
1528 if (fixed_regs[ARG_POINTER_REGNUM])
1529 bitmap_set_bit (df->hardware_regs_used, ARG_POINTER_REGNUM);
1530 #endif
1531
1532 /* Any constant, or pseudo with constant equivalences, may
1533 require reloading from memory using the pic register. */
1534 if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
1535 && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
1536 bitmap_set_bit (df->hardware_regs_used, PIC_OFFSET_TABLE_REGNUM);
1537 }
1538
1539 if (bitmap_bit_p (rescan_blocks, EXIT_BLOCK))
1540 {
1541 /* The exit block is special for this problem and its bits are
1542 computed from thin air. */
1543 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (dflow, EXIT_BLOCK);
1544 bitmap_copy (bb_info->use, df->exit_block_uses);
1545 }
1546
1547 EXECUTE_IF_SET_IN_BITMAP (rescan_blocks, 0, bb_index, bi)
1548 {
1549 if (bb_index == EXIT_BLOCK)
1550 continue;
1551 df_lr_bb_local_compute (dflow, df, bb_index);
1552 }
1553 }
1554
1555
1556 /* Initialize the solution vectors. */
1557
1558 static void
1559 df_lr_init (struct dataflow *dflow, bitmap all_blocks)
1560 {
1561 unsigned int bb_index;
1562 bitmap_iterator bi;
1563
1564 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1565 {
1566 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (dflow, bb_index);
1567 bitmap_copy (bb_info->in, bb_info->use);
1568 bitmap_clear (bb_info->out);
1569 }
1570 }
1571
1572
1573 /* Confluence function that processes infinite loops. This might be a
1574 noreturn function that throws. And even if it isn't, getting the
1575 unwind info right helps debugging. */
1576 static void
1577 df_lr_confluence_0 (struct dataflow *dflow, basic_block bb)
1578 {
1579 struct df *df = dflow->df;
1580
1581 bitmap op1 = df_lr_get_bb_info (dflow, bb->index)->out;
1582 if (bb != EXIT_BLOCK_PTR)
1583 bitmap_copy (op1, df->hardware_regs_used);
1584 }
1585
1586
1587 /* Confluence function that ignores fake edges. */
1588 static void
1589 df_lr_confluence_n (struct dataflow *dflow, edge e)
1590 {
1591 bitmap op1 = df_lr_get_bb_info (dflow, e->src->index)->out;
1592 bitmap op2 = df_lr_get_bb_info (dflow, e->dest->index)->in;
1593
1594 /* Call-clobbered registers die across exception and call edges. */
1595 /* ??? Abnormal call edges ignored for the moment, as this gets
1596 confused by sibling call edges, which crashes reg-stack. */
1597 if (e->flags & EDGE_EH)
1598 bitmap_ior_and_compl_into (op1, op2, df_invalidated_by_call);
1599 else
1600 bitmap_ior_into (op1, op2);
1601
1602 bitmap_ior_into (op1, dflow->df->hardware_regs_used);
1603 }
1604
1605
1606 /* Transfer function. */
1607 static bool
1608 df_lr_transfer_function (struct dataflow *dflow, int bb_index)
1609 {
1610 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (dflow, bb_index);
1611 bitmap in = bb_info->in;
1612 bitmap out = bb_info->out;
1613 bitmap use = bb_info->use;
1614 bitmap def = bb_info->def;
1615
1616 return bitmap_ior_and_compl (in, use, out, def);
1617 }
1618
1619
1620 /* Free all storage associated with the problem. */
1621
1622 static void
1623 df_lr_free (struct dataflow *dflow)
1624 {
1625 if (dflow->block_info)
1626 {
1627 unsigned int i;
1628 for (i = 0; i < dflow->block_info_size; i++)
1629 {
1630 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (dflow, i);
1631 if (bb_info)
1632 {
1633 BITMAP_FREE (bb_info->use);
1634 BITMAP_FREE (bb_info->def);
1635 BITMAP_FREE (bb_info->in);
1636 BITMAP_FREE (bb_info->out);
1637 }
1638 }
1639 free_alloc_pool (dflow->block_pool);
1640
1641 dflow->block_info_size = 0;
1642 free (dflow->block_info);
1643 }
1644 free (dflow);
1645 }
1646
1647
1648 /* Debugging info. */
1649
1650 static void
1651 df_lr_dump (struct dataflow *dflow, FILE *file)
1652 {
1653 basic_block bb;
1654
1655 fprintf (file, "Live Registers:\n");
1656 FOR_ALL_BB (bb)
1657 {
1658 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (dflow, bb->index);
1659 df_print_bb_index (bb, file);
1660
1661 if (!bb_info->in)
1662 continue;
1663
1664 fprintf (file, " in \t");
1665 dump_bitmap (file, bb_info->in);
1666 fprintf (file, " use \t");
1667 dump_bitmap (file, bb_info->use);
1668 fprintf (file, " def \t");
1669 dump_bitmap (file, bb_info->def);
1670 fprintf (file, " out \t");
1671 dump_bitmap (file, bb_info->out);
1672 }
1673 }
1674
1675 /* All of the information associated with every instance of the problem. */
1676
1677 static struct df_problem problem_LR =
1678 {
1679 DF_LR, /* Problem id. */
1680 DF_BACKWARD, /* Direction. */
1681 df_lr_alloc, /* Allocate the problem specific data. */
1682 NULL, /* Reset global information. */
1683 df_lr_free_bb_info, /* Free basic block info. */
1684 df_lr_local_compute, /* Local compute function. */
1685 df_lr_init, /* Init the solution specific data. */
1686 df_iterative_dataflow, /* Iterative solver. */
1687 df_lr_confluence_0, /* Confluence operator 0. */
1688 df_lr_confluence_n, /* Confluence operator n. */
1689 df_lr_transfer_function, /* Transfer function. */
1690 NULL, /* Finalize function. */
1691 df_lr_free, /* Free all of the problem information. */
1692 df_lr_dump, /* Debugging. */
1693 NULL /* Dependent problem. */
1694 };
1695
1696
1697 /* Create a new DATAFLOW instance and add it to an existing instance
1698 of DF. The returned structure is what is used to get at the
1699 solution. */
1700
1701 struct dataflow *
1702 df_lr_add_problem (struct df *df)
1703 {
1704 return df_add_problem (df, &problem_LR);
1705 }
1706
1707
1708 \f
1709 /*----------------------------------------------------------------------------
1710 UNINITIALIZED REGISTERS
1711
1712 Find the set of uses for registers that are reachable from the entry
1713 block without passing thru a definition.
1714 ----------------------------------------------------------------------------*/
1715
1716 /* Get basic block info. */
1717
1718 struct df_ur_bb_info *
1719 df_ur_get_bb_info (struct dataflow *dflow, unsigned int index)
1720 {
1721 return (struct df_ur_bb_info *) dflow->block_info[index];
1722 }
1723
1724
1725 /* Set basic block info. */
1726
1727 static void
1728 df_ur_set_bb_info (struct dataflow *dflow, unsigned int index,
1729 struct df_ur_bb_info *bb_info)
1730 {
1731 dflow->block_info[index] = bb_info;
1732 }
1733
1734
1735 /* Free basic block info. */
1736
1737 static void
1738 df_ur_free_bb_info (struct dataflow *dflow,
1739 basic_block bb ATTRIBUTE_UNUSED,
1740 void *vbb_info)
1741 {
1742 struct df_ur_bb_info *bb_info = (struct df_ur_bb_info *) vbb_info;
1743 if (bb_info)
1744 {
1745 BITMAP_FREE (bb_info->gen);
1746 BITMAP_FREE (bb_info->kill);
1747 BITMAP_FREE (bb_info->in);
1748 BITMAP_FREE (bb_info->out);
1749 pool_free (dflow->block_pool, bb_info);
1750 }
1751 }
1752
1753
1754 /* Allocate or reset bitmaps for DFLOW blocks. The solution bits are
1755 not touched unless the block is new. */
1756
1757 static void
1758 df_ur_alloc (struct dataflow *dflow, bitmap blocks_to_rescan)
1759 {
1760 unsigned int bb_index;
1761 bitmap_iterator bi;
1762
1763 if (! dflow->block_pool)
1764 dflow->block_pool = create_alloc_pool ("df_ur_block pool",
1765 sizeof (struct df_ur_bb_info), 100);
1766
1767 df_grow_bb_info (dflow);
1768
1769 /* Because of the clustering of all def sites for the same pseudo,
1770 we have to process all of the blocks before doing the
1771 analysis. */
1772
1773 EXECUTE_IF_SET_IN_BITMAP (blocks_to_rescan, 0, bb_index, bi)
1774 {
1775 struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, bb_index);
1776 if (bb_info)
1777 {
1778 bitmap_clear (bb_info->kill);
1779 bitmap_clear (bb_info->gen);
1780 }
1781 else
1782 {
1783 bb_info = (struct df_ur_bb_info *) pool_alloc (dflow->block_pool);
1784 df_ur_set_bb_info (dflow, bb_index, bb_info);
1785 bb_info->kill = BITMAP_ALLOC (NULL);
1786 bb_info->gen = BITMAP_ALLOC (NULL);
1787 bb_info->in = BITMAP_ALLOC (NULL);
1788 bb_info->out = BITMAP_ALLOC (NULL);
1789 }
1790 }
1791 }
1792
1793
1794 /* Compute local uninitialized register info for basic block BB. */
1795
1796 static void
1797 df_ur_bb_local_compute (struct dataflow *dflow, unsigned int bb_index)
1798 {
1799 struct df *df = dflow->df;
1800 basic_block bb = BASIC_BLOCK (bb_index);
1801 struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, bb_index);
1802 rtx insn;
1803 struct df_ref *def;
1804
1805 bitmap_clear (seen_in_block);
1806 bitmap_clear (seen_in_insn);
1807
1808 for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref)
1809 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
1810 {
1811 unsigned int regno = DF_REF_REGNO (def);
1812 if (!bitmap_bit_p (seen_in_block, regno))
1813 {
1814 bitmap_set_bit (seen_in_block, regno);
1815 bitmap_set_bit (bb_info->gen, regno);
1816 }
1817 }
1818
1819 FOR_BB_INSNS_REVERSE (bb, insn)
1820 {
1821 unsigned int uid = INSN_UID (insn);
1822 if (!INSN_P (insn))
1823 continue;
1824
1825 for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
1826 {
1827 unsigned int regno = DF_REF_REGNO (def);
1828 /* Only the last def counts. */
1829 if (!bitmap_bit_p (seen_in_block, regno))
1830 {
1831 bitmap_set_bit (seen_in_insn, regno);
1832
1833 if (DF_REF_FLAGS (def) & DF_REF_CLOBBER)
1834 bitmap_set_bit (bb_info->kill, regno);
1835 else
1836 bitmap_set_bit (bb_info->gen, regno);
1837 }
1838 }
1839 bitmap_ior_into (seen_in_block, seen_in_insn);
1840 bitmap_clear (seen_in_insn);
1841 }
1842
1843 for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref)
1844 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
1845 {
1846 unsigned int regno = DF_REF_REGNO (def);
1847 if (!bitmap_bit_p (seen_in_block, regno))
1848 {
1849 bitmap_set_bit (seen_in_block, regno);
1850 bitmap_set_bit (bb_info->gen, regno);
1851 }
1852 }
1853 }
1854
1855
1856 /* Compute local uninitialized register info. */
1857
1858 static void
1859 df_ur_local_compute (struct dataflow *dflow,
1860 bitmap all_blocks ATTRIBUTE_UNUSED,
1861 bitmap rescan_blocks)
1862 {
1863 unsigned int bb_index;
1864 bitmap_iterator bi;
1865
1866 df_set_seen ();
1867
1868 EXECUTE_IF_SET_IN_BITMAP (rescan_blocks, 0, bb_index, bi)
1869 {
1870 df_ur_bb_local_compute (dflow, bb_index);
1871 }
1872
1873 df_unset_seen ();
1874 }
1875
1876
1877 /* Initialize the solution vectors. */
1878
1879 static void
1880 df_ur_init (struct dataflow *dflow, bitmap all_blocks)
1881 {
1882 unsigned int bb_index;
1883 bitmap_iterator bi;
1884
1885 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1886 {
1887 struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, bb_index);
1888
1889 bitmap_copy (bb_info->out, bb_info->gen);
1890 bitmap_clear (bb_info->in);
1891 }
1892 }
1893
1894
1895 /* Or in the stack regs, hard regs and early clobber regs into the the
1896 ur_in sets of all of the blocks. */
1897
1898 static void
1899 df_ur_local_finalize (struct dataflow *dflow, bitmap all_blocks)
1900 {
1901 struct df *df = dflow->df;
1902 struct dataflow *lr_dflow = df->problems_by_index[DF_LR];
1903 bitmap tmp = BITMAP_ALLOC (NULL);
1904 bitmap_iterator bi;
1905 unsigned int bb_index;
1906
1907 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1908 {
1909 struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, bb_index);
1910 struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (lr_dflow, bb_index);
1911
1912 /* No register may reach a location where it is not used. Thus
1913 we trim the rr result to the places where it is used. */
1914 bitmap_and_into (bb_info->in, bb_lr_info->in);
1915 bitmap_and_into (bb_info->out, bb_lr_info->out);
1916
1917 #if 1
1918 /* Hard registers may still stick in the ur_out set, but not
1919 be in the ur_in set, if their only mention was in a call
1920 in this block. This is because a call kills in the lr
1921 problem but does not kill in the ur problem. To clean
1922 this up, we execute the transfer function on the lr_in
1923 set and then use that to knock bits out of ur_out. */
1924 bitmap_ior_and_compl (tmp, bb_info->gen, bb_lr_info->in,
1925 bb_info->kill);
1926 bitmap_and_into (bb_info->out, tmp);
1927 #endif
1928 }
1929
1930 BITMAP_FREE (tmp);
1931 }
1932
1933
1934 /* Confluence function that ignores fake edges. */
1935
1936 static void
1937 df_ur_confluence_n (struct dataflow *dflow, edge e)
1938 {
1939 bitmap op1 = df_ur_get_bb_info (dflow, e->dest->index)->in;
1940 bitmap op2 = df_ur_get_bb_info (dflow, e->src->index)->out;
1941
1942 if (e->flags & EDGE_FAKE)
1943 return;
1944
1945 bitmap_ior_into (op1, op2);
1946 }
1947
1948
1949 /* Transfer function. */
1950
1951 static bool
1952 df_ur_transfer_function (struct dataflow *dflow, int bb_index)
1953 {
1954 struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, bb_index);
1955 bitmap in = bb_info->in;
1956 bitmap out = bb_info->out;
1957 bitmap gen = bb_info->gen;
1958 bitmap kill = bb_info->kill;
1959
1960 return bitmap_ior_and_compl (out, gen, in, kill);
1961 }
1962
1963
1964 /* Free all storage associated with the problem. */
1965
1966 static void
1967 df_ur_free (struct dataflow *dflow)
1968 {
1969 if (dflow->block_info)
1970 {
1971 unsigned int i;
1972
1973 for (i = 0; i < dflow->block_info_size; i++)
1974 {
1975 struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, i);
1976 if (bb_info)
1977 {
1978 BITMAP_FREE (bb_info->gen);
1979 BITMAP_FREE (bb_info->kill);
1980 BITMAP_FREE (bb_info->in);
1981 BITMAP_FREE (bb_info->out);
1982 }
1983 }
1984
1985 free_alloc_pool (dflow->block_pool);
1986 dflow->block_info_size = 0;
1987 free (dflow->block_info);
1988 }
1989 free (dflow);
1990 }
1991
1992
1993 /* Debugging info. */
1994
1995 static void
1996 df_ur_dump (struct dataflow *dflow, FILE *file)
1997 {
1998 basic_block bb;
1999
2000 fprintf (file, "Undefined regs:\n");
2001
2002 FOR_ALL_BB (bb)
2003 {
2004 struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, bb->index);
2005 df_print_bb_index (bb, file);
2006
2007 if (! bb_info->in)
2008 continue;
2009
2010 fprintf (file, " in \t");
2011 dump_bitmap (file, bb_info->in);
2012 fprintf (file, " gen \t");
2013 dump_bitmap (file, bb_info->gen);
2014 fprintf (file, " kill\t");
2015 dump_bitmap (file, bb_info->kill);
2016 fprintf (file, " out \t");
2017 dump_bitmap (file, bb_info->out);
2018 }
2019 }
2020
2021 /* All of the information associated with every instance of the problem. */
2022
2023 static struct df_problem problem_UR =
2024 {
2025 DF_UR, /* Problem id. */
2026 DF_FORWARD, /* Direction. */
2027 df_ur_alloc, /* Allocate the problem specific data. */
2028 NULL, /* Reset global information. */
2029 df_ur_free_bb_info, /* Free basic block info. */
2030 df_ur_local_compute, /* Local compute function. */
2031 df_ur_init, /* Init the solution specific data. */
2032 df_iterative_dataflow, /* Iterative solver. */
2033 NULL, /* Confluence operator 0. */
2034 df_ur_confluence_n, /* Confluence operator n. */
2035 df_ur_transfer_function, /* Transfer function. */
2036 df_ur_local_finalize, /* Finalize function. */
2037 df_ur_free, /* Free all of the problem information. */
2038 df_ur_dump, /* Debugging. */
2039 &problem_LR /* Dependent problem. */
2040 };
2041
2042
2043 /* Create a new DATAFLOW instance and add it to an existing instance
2044 of DF. The returned structure is what is used to get at the
2045 solution. */
2046
2047 struct dataflow *
2048 df_ur_add_problem (struct df *df)
2049 {
2050 return df_add_problem (df, &problem_UR);
2051 }
2052
2053
2054 \f
2055 /*----------------------------------------------------------------------------
2056 UNINITIALIZED REGISTERS WITH EARLYCLOBBER
2057
2058 Find the set of uses for registers that are reachable from the entry
2059 block without passing thru a definition.
2060
2061 This is a variant of the UR problem above that has a lot of special
2062 features just for the register allocation phase.
2063 ----------------------------------------------------------------------------*/
2064
2065 struct df_urec_problem_data
2066 {
2067 bool earlyclobbers_found; /* True if any instruction contains an
2068 earlyclobber. */
2069 #ifdef STACK_REGS
2070 bitmap stack_regs; /* Registers that may be allocated to a STACK_REGS. */
2071 #endif
2072 };
2073
2074
2075 /* Get basic block info. */
2076
2077 struct df_urec_bb_info *
2078 df_urec_get_bb_info (struct dataflow *dflow, unsigned int index)
2079 {
2080 return (struct df_urec_bb_info *) dflow->block_info[index];
2081 }
2082
2083
2084 /* Set basic block info. */
2085
2086 static void
2087 df_urec_set_bb_info (struct dataflow *dflow, unsigned int index,
2088 struct df_urec_bb_info *bb_info)
2089 {
2090 dflow->block_info[index] = bb_info;
2091 }
2092
2093
2094 /* Free basic block info. */
2095
2096 static void
2097 df_urec_free_bb_info (struct dataflow *dflow,
2098 basic_block bb ATTRIBUTE_UNUSED,
2099 void *vbb_info)
2100 {
2101 struct df_urec_bb_info *bb_info = (struct df_urec_bb_info *) vbb_info;
2102 if (bb_info)
2103 {
2104 BITMAP_FREE (bb_info->gen);
2105 BITMAP_FREE (bb_info->kill);
2106 BITMAP_FREE (bb_info->in);
2107 BITMAP_FREE (bb_info->out);
2108 BITMAP_FREE (bb_info->earlyclobber);
2109 pool_free (dflow->block_pool, bb_info);
2110 }
2111 }
2112
2113
2114 /* Allocate or reset bitmaps for DFLOW blocks. The solution bits are
2115 not touched unless the block is new. */
2116
2117 static void
2118 df_urec_alloc (struct dataflow *dflow, bitmap blocks_to_rescan)
2119 {
2120 unsigned int bb_index;
2121 bitmap_iterator bi;
2122 struct df_urec_problem_data *problem_data =
2123 (struct df_urec_problem_data *) dflow->problem_data;
2124
2125 if (! dflow->block_pool)
2126 dflow->block_pool = create_alloc_pool ("df_urec_block pool",
2127 sizeof (struct df_urec_bb_info), 50);
2128
2129 if (!dflow->problem_data)
2130 {
2131 problem_data = XNEW (struct df_urec_problem_data);
2132 dflow->problem_data = problem_data;
2133 }
2134 problem_data->earlyclobbers_found = false;
2135
2136 df_grow_bb_info (dflow);
2137
2138 /* Because of the clustering of all def sites for the same pseudo,
2139 we have to process all of the blocks before doing the
2140 analysis. */
2141
2142 EXECUTE_IF_SET_IN_BITMAP (blocks_to_rescan, 0, bb_index, bi)
2143 {
2144 struct df_urec_bb_info *bb_info = df_urec_get_bb_info (dflow, bb_index);
2145 if (bb_info)
2146 {
2147 bitmap_clear (bb_info->kill);
2148 bitmap_clear (bb_info->gen);
2149 bitmap_clear (bb_info->earlyclobber);
2150 }
2151 else
2152 {
2153 bb_info = (struct df_urec_bb_info *) pool_alloc (dflow->block_pool);
2154 df_urec_set_bb_info (dflow, bb_index, bb_info);
2155 bb_info->kill = BITMAP_ALLOC (NULL);
2156 bb_info->gen = BITMAP_ALLOC (NULL);
2157 bb_info->in = BITMAP_ALLOC (NULL);
2158 bb_info->out = BITMAP_ALLOC (NULL);
2159 bb_info->earlyclobber = BITMAP_ALLOC (NULL);
2160 }
2161 }
2162 }
2163
2164
2165 /* The function modifies local info for register REG being changed in
2166 SETTER. DATA is used to pass the current basic block info. */
2167
2168 static void
2169 df_urec_mark_reg_change (rtx reg, rtx setter, void *data)
2170 {
2171 int regno;
2172 int endregno;
2173 int i;
2174 struct df_urec_bb_info *bb_info = (struct df_urec_bb_info*) data;
2175
2176 if (GET_CODE (reg) == SUBREG)
2177 reg = SUBREG_REG (reg);
2178
2179 if (!REG_P (reg))
2180 return;
2181
2182
2183 endregno = regno = REGNO (reg);
2184 if (regno < FIRST_PSEUDO_REGISTER)
2185 {
2186 endregno +=hard_regno_nregs[regno][GET_MODE (reg)];
2187
2188 for (i = regno; i < endregno; i++)
2189 {
2190 bitmap_set_bit (bb_info->kill, i);
2191
2192 if (GET_CODE (setter) != CLOBBER)
2193 bitmap_set_bit (bb_info->gen, i);
2194 else
2195 bitmap_clear_bit (bb_info->gen, i);
2196 }
2197 }
2198 else
2199 {
2200 bitmap_set_bit (bb_info->kill, regno);
2201
2202 if (GET_CODE (setter) != CLOBBER)
2203 bitmap_set_bit (bb_info->gen, regno);
2204 else
2205 bitmap_clear_bit (bb_info->gen, regno);
2206 }
2207 }
2208 /* Classes of registers which could be early clobbered in the current
2209 insn. */
2210
2211 DEF_VEC_I(int);
2212 DEF_VEC_ALLOC_I(int,heap);
2213
2214 static VEC(int,heap) *earlyclobber_regclass;
2215
2216 /* This function finds and stores register classes that could be early
2217 clobbered in INSN. If any earlyclobber classes are found, the function
2218 returns TRUE, in all other cases it returns FALSE. */
2219
2220 static bool
2221 df_urec_check_earlyclobber (rtx insn)
2222 {
2223 int opno;
2224 bool found = false;
2225
2226 extract_insn (insn);
2227
2228 VEC_truncate (int, earlyclobber_regclass, 0);
2229 for (opno = 0; opno < recog_data.n_operands; opno++)
2230 {
2231 char c;
2232 bool amp_p;
2233 int i;
2234 enum reg_class class;
2235 const char *p = recog_data.constraints[opno];
2236
2237 class = NO_REGS;
2238 amp_p = false;
2239 for (;;)
2240 {
2241 c = *p;
2242 switch (c)
2243 {
2244 case '=': case '+': case '?':
2245 case '#': case '!':
2246 case '*': case '%':
2247 case 'm': case '<': case '>': case 'V': case 'o':
2248 case 'E': case 'F': case 'G': case 'H':
2249 case 's': case 'i': case 'n':
2250 case 'I': case 'J': case 'K': case 'L':
2251 case 'M': case 'N': case 'O': case 'P':
2252 case 'X':
2253 case '0': case '1': case '2': case '3': case '4':
2254 case '5': case '6': case '7': case '8': case '9':
2255 /* These don't say anything we care about. */
2256 break;
2257
2258 case '&':
2259 amp_p = true;
2260 break;
2261 case '\0':
2262 case ',':
2263 if (amp_p && class != NO_REGS)
2264 {
2265 int rc;
2266
2267 found = true;
2268 for (i = 0;
2269 VEC_iterate (int, earlyclobber_regclass, i, rc);
2270 i++)
2271 {
2272 if (rc == (int) class)
2273 goto found_rc;
2274 }
2275
2276 /* We use VEC_quick_push here because
2277 earlyclobber_regclass holds no more than
2278 N_REG_CLASSES elements. */
2279 VEC_quick_push (int, earlyclobber_regclass, (int) class);
2280 found_rc:
2281 ;
2282 }
2283
2284 amp_p = false;
2285 class = NO_REGS;
2286 break;
2287
2288 case 'r':
2289 class = GENERAL_REGS;
2290 break;
2291
2292 default:
2293 class = REG_CLASS_FROM_CONSTRAINT (c, p);
2294 break;
2295 }
2296 if (c == '\0')
2297 break;
2298 p += CONSTRAINT_LEN (c, p);
2299 }
2300 }
2301
2302 return found;
2303 }
2304
2305 /* The function checks that pseudo-register *X has a class
2306 intersecting with the class of pseudo-register could be early
2307 clobbered in the same insn.
2308
2309 This function is a no-op if earlyclobber_regclass is empty.
2310
2311 Reload can assign the same hard register to uninitialized
2312 pseudo-register and early clobbered pseudo-register in an insn if
2313 the pseudo-register is used first time in given BB and not lived at
2314 the BB start. To prevent this we don't change life information for
2315 such pseudo-registers. */
2316
2317 static int
2318 df_urec_mark_reg_use_for_earlyclobber (rtx *x, void *data)
2319 {
2320 enum reg_class pref_class, alt_class;
2321 int i, regno;
2322 struct df_urec_bb_info *bb_info = (struct df_urec_bb_info*) data;
2323
2324 if (REG_P (*x) && REGNO (*x) >= FIRST_PSEUDO_REGISTER)
2325 {
2326 int rc;
2327
2328 regno = REGNO (*x);
2329 if (bitmap_bit_p (bb_info->kill, regno)
2330 || bitmap_bit_p (bb_info->gen, regno))
2331 return 0;
2332 pref_class = reg_preferred_class (regno);
2333 alt_class = reg_alternate_class (regno);
2334 for (i = 0; VEC_iterate (int, earlyclobber_regclass, i, rc); i++)
2335 {
2336 if (reg_classes_intersect_p (rc, pref_class)
2337 || (rc != NO_REGS
2338 && reg_classes_intersect_p (rc, alt_class)))
2339 {
2340 bitmap_set_bit (bb_info->earlyclobber, regno);
2341 break;
2342 }
2343 }
2344 }
2345 return 0;
2346 }
2347
2348 /* The function processes all pseudo-registers in *X with the aid of
2349 previous function. */
2350
2351 static void
2352 df_urec_mark_reg_use_for_earlyclobber_1 (rtx *x, void *data)
2353 {
2354 for_each_rtx (x, df_urec_mark_reg_use_for_earlyclobber, data);
2355 }
2356
2357
2358 /* Compute local uninitialized register info for basic block BB. */
2359
2360 static void
2361 df_urec_bb_local_compute (struct dataflow *dflow, unsigned int bb_index)
2362 {
2363 struct df *df = dflow->df;
2364 basic_block bb = BASIC_BLOCK (bb_index);
2365 struct df_urec_bb_info *bb_info = df_urec_get_bb_info (dflow, bb_index);
2366 rtx insn;
2367 struct df_ref *def;
2368
2369 for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref)
2370 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
2371 {
2372 unsigned int regno = DF_REF_REGNO (def);
2373 bitmap_set_bit (bb_info->gen, regno);
2374 }
2375
2376 FOR_BB_INSNS (bb, insn)
2377 {
2378 if (INSN_P (insn))
2379 {
2380 note_stores (PATTERN (insn), df_urec_mark_reg_change, bb_info);
2381 if (df_state & (DF_SCAN_GLOBAL | DF_SCAN_POST_ALLOC)
2382 && df_urec_check_earlyclobber (insn))
2383 {
2384 struct df_urec_problem_data *problem_data =
2385 (struct df_urec_problem_data *) dflow->problem_data;
2386 problem_data->earlyclobbers_found = true;
2387 note_uses (&PATTERN (insn),
2388 df_urec_mark_reg_use_for_earlyclobber_1, bb_info);
2389 }
2390 }
2391 }
2392
2393 for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref)
2394 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
2395 {
2396 unsigned int regno = DF_REF_REGNO (def);
2397 bitmap_set_bit (bb_info->gen, regno);
2398 }
2399
2400 }
2401
2402
2403 /* Compute local uninitialized register info. */
2404
2405 static void
2406 df_urec_local_compute (struct dataflow *dflow,
2407 bitmap all_blocks ATTRIBUTE_UNUSED,
2408 bitmap rescan_blocks)
2409 {
2410 unsigned int bb_index;
2411 bitmap_iterator bi;
2412 #ifdef STACK_REGS
2413 int i;
2414 HARD_REG_SET zero, stack_hard_regs, used;
2415 struct df_urec_problem_data *problem_data =
2416 (struct df_urec_problem_data *) dflow->problem_data;
2417
2418 /* Any register that MAY be allocated to a register stack (like the
2419 387) is treated poorly. Each such register is marked as being
2420 live everywhere. This keeps the register allocator and the
2421 subsequent passes from doing anything useful with these values.
2422
2423 FIXME: This seems like an incredibly poor idea. */
2424
2425 CLEAR_HARD_REG_SET (zero);
2426 CLEAR_HARD_REG_SET (stack_hard_regs);
2427 for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++)
2428 SET_HARD_REG_BIT (stack_hard_regs, i);
2429 problem_data->stack_regs = BITMAP_ALLOC (NULL);
2430 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
2431 {
2432 COPY_HARD_REG_SET (used, reg_class_contents[reg_preferred_class (i)]);
2433 IOR_HARD_REG_SET (used, reg_class_contents[reg_alternate_class (i)]);
2434 AND_HARD_REG_SET (used, stack_hard_regs);
2435 GO_IF_HARD_REG_EQUAL (used, zero, skip);
2436 bitmap_set_bit (problem_data->stack_regs, i);
2437 skip:
2438 ;
2439 }
2440 #endif
2441
2442 /* We know that earlyclobber_regclass holds no more than
2443 N_REG_CLASSES elements. See df_urec_check_earlyclobber. */
2444 earlyclobber_regclass = VEC_alloc (int, heap, N_REG_CLASSES);
2445
2446 EXECUTE_IF_SET_IN_BITMAP (rescan_blocks, 0, bb_index, bi)
2447 {
2448 df_urec_bb_local_compute (dflow, bb_index);
2449 }
2450
2451 VEC_free (int, heap, earlyclobber_regclass);
2452 }
2453
2454
2455 /* Initialize the solution vectors. */
2456
2457 static void
2458 df_urec_init (struct dataflow *dflow, bitmap all_blocks)
2459 {
2460 unsigned int bb_index;
2461 bitmap_iterator bi;
2462
2463 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2464 {
2465 struct df_urec_bb_info *bb_info = df_urec_get_bb_info (dflow, bb_index);
2466
2467 bitmap_copy (bb_info->out, bb_info->gen);
2468 bitmap_clear (bb_info->in);
2469 }
2470 }
2471
2472
2473 /* Or in the stack regs, hard regs and early clobber regs into the the
2474 ur_in sets of all of the blocks. */
2475
2476 static void
2477 df_urec_local_finalize (struct dataflow *dflow, bitmap all_blocks)
2478 {
2479 struct df *df = dflow->df;
2480 struct dataflow *lr_dflow = df->problems_by_index[DF_LR];
2481 bitmap tmp = BITMAP_ALLOC (NULL);
2482 bitmap_iterator bi;
2483 unsigned int bb_index;
2484 struct df_urec_problem_data *problem_data =
2485 (struct df_urec_problem_data *) dflow->problem_data;
2486
2487 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2488 {
2489 struct df_urec_bb_info *bb_info = df_urec_get_bb_info (dflow, bb_index);
2490 struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (lr_dflow, bb_index);
2491
2492 if (bb_index != ENTRY_BLOCK && bb_index != EXIT_BLOCK)
2493 {
2494 if (problem_data->earlyclobbers_found)
2495 bitmap_ior_into (bb_info->in, bb_info->earlyclobber);
2496
2497 #ifdef STACK_REGS
2498 /* We can not use the same stack register for uninitialized
2499 pseudo-register and another living pseudo-register
2500 because if the uninitialized pseudo-register dies,
2501 subsequent pass reg-stack will be confused (it will
2502 believe that the other register dies). */
2503 bitmap_ior_into (bb_info->in, problem_data->stack_regs);
2504 bitmap_ior_into (bb_info->out, problem_data->stack_regs);
2505 #endif
2506 }
2507
2508 /* No register may reach a location where it is not used. Thus
2509 we trim the rr result to the places where it is used. */
2510 bitmap_and_into (bb_info->in, bb_lr_info->in);
2511 bitmap_and_into (bb_info->out, bb_lr_info->out);
2512
2513 #if 1
2514 /* Hard registers may still stick in the ur_out set, but not
2515 be in the ur_in set, if their only mention was in a call
2516 in this block. This is because a call kills in the lr
2517 problem but does not kill in the rr problem. To clean
2518 this up, we execute the transfer function on the lr_in
2519 set and then use that to knock bits out of ur_out. */
2520 bitmap_ior_and_compl (tmp, bb_info->gen, bb_lr_info->in,
2521 bb_info->kill);
2522 bitmap_and_into (bb_info->out, tmp);
2523 #endif
2524 }
2525
2526 #ifdef STACK_REGS
2527 BITMAP_FREE (problem_data->stack_regs);
2528 #endif
2529 BITMAP_FREE (tmp);
2530 }
2531
2532
2533 /* Confluence function that ignores fake edges. */
2534
2535 static void
2536 df_urec_confluence_n (struct dataflow *dflow, edge e)
2537 {
2538 bitmap op1 = df_urec_get_bb_info (dflow, e->dest->index)->in;
2539 bitmap op2 = df_urec_get_bb_info (dflow, e->src->index)->out;
2540
2541 if (e->flags & EDGE_FAKE)
2542 return;
2543
2544 bitmap_ior_into (op1, op2);
2545 }
2546
2547
2548 /* Transfer function. */
2549
2550 static bool
2551 df_urec_transfer_function (struct dataflow *dflow, int bb_index)
2552 {
2553 struct df_urec_bb_info *bb_info = df_urec_get_bb_info (dflow, bb_index);
2554 bitmap in = bb_info->in;
2555 bitmap out = bb_info->out;
2556 bitmap gen = bb_info->gen;
2557 bitmap kill = bb_info->kill;
2558
2559 return bitmap_ior_and_compl (out, gen, in, kill);
2560 }
2561
2562
2563 /* Free all storage associated with the problem. */
2564
2565 static void
2566 df_urec_free (struct dataflow *dflow)
2567 {
2568 if (dflow->block_info)
2569 {
2570 unsigned int i;
2571
2572 for (i = 0; i < dflow->block_info_size; i++)
2573 {
2574 struct df_urec_bb_info *bb_info = df_urec_get_bb_info (dflow, i);
2575 if (bb_info)
2576 {
2577 BITMAP_FREE (bb_info->gen);
2578 BITMAP_FREE (bb_info->kill);
2579 BITMAP_FREE (bb_info->in);
2580 BITMAP_FREE (bb_info->out);
2581 BITMAP_FREE (bb_info->earlyclobber);
2582 }
2583 }
2584
2585 free_alloc_pool (dflow->block_pool);
2586
2587 dflow->block_info_size = 0;
2588 free (dflow->block_info);
2589 free (dflow->problem_data);
2590 }
2591 free (dflow);
2592 }
2593
2594
2595 /* Debugging info. */
2596
2597 static void
2598 df_urec_dump (struct dataflow *dflow, FILE *file)
2599 {
2600 basic_block bb;
2601
2602 fprintf (file, "Undefined regs:\n");
2603
2604 FOR_ALL_BB (bb)
2605 {
2606 struct df_urec_bb_info *bb_info = df_urec_get_bb_info (dflow, bb->index);
2607 df_print_bb_index (bb, file);
2608
2609 if (! bb_info->in)
2610 continue;
2611
2612 fprintf (file, " in \t");
2613 dump_bitmap (file, bb_info->in);
2614 fprintf (file, " gen \t");
2615 dump_bitmap (file, bb_info->gen);
2616 fprintf (file, " kill\t");
2617 dump_bitmap (file, bb_info->kill);
2618 fprintf (file, " ec\t");
2619 dump_bitmap (file, bb_info->earlyclobber);
2620 fprintf (file, " out \t");
2621 dump_bitmap (file, bb_info->out);
2622 }
2623 }
2624
2625 /* All of the information associated with every instance of the problem. */
2626
2627 static struct df_problem problem_UREC =
2628 {
2629 DF_UREC, /* Problem id. */
2630 DF_FORWARD, /* Direction. */
2631 df_urec_alloc, /* Allocate the problem specific data. */
2632 NULL, /* Reset global information. */
2633 df_urec_free_bb_info, /* Free basic block info. */
2634 df_urec_local_compute, /* Local compute function. */
2635 df_urec_init, /* Init the solution specific data. */
2636 df_iterative_dataflow, /* Iterative solver. */
2637 NULL, /* Confluence operator 0. */
2638 df_urec_confluence_n, /* Confluence operator n. */
2639 df_urec_transfer_function, /* Transfer function. */
2640 df_urec_local_finalize, /* Finalize function. */
2641 df_urec_free, /* Free all of the problem information. */
2642 df_urec_dump, /* Debugging. */
2643 &problem_LR /* Dependent problem. */
2644 };
2645
2646
2647 /* Create a new DATAFLOW instance and add it to an existing instance
2648 of DF. The returned structure is what is used to get at the
2649 solution. */
2650
2651 struct dataflow *
2652 df_urec_add_problem (struct df *df)
2653 {
2654 return df_add_problem (df, &problem_UREC);
2655 }
2656
2657
2658 \f
2659 /*----------------------------------------------------------------------------
2660 CREATE DEF_USE (DU) and / or USE_DEF (UD) CHAINS
2661
2662 Link either the defs to the uses and / or the uses to the defs.
2663
2664 These problems are set up like the other dataflow problems so that
2665 they nicely fit into the framework. They are much simpler and only
2666 involve a single traversal of instructions and an examination of
2667 the reaching defs information (the dependent problem).
2668 ----------------------------------------------------------------------------*/
2669
2670 struct df_chain_problem_data
2671 {
2672 int flags;
2673 };
2674
2675
2676 /* Create def-use or use-def chains. */
2677
2678 static void
2679 df_chain_alloc (struct dataflow *dflow,
2680 bitmap blocks_to_rescan ATTRIBUTE_UNUSED)
2681 {
2682 struct df *df = dflow->df;
2683 unsigned int i;
2684 struct df_chain_problem_data *problem_data =
2685 (struct df_chain_problem_data *) dflow->problem_data;
2686
2687 /* Wholesale destruction of the old chains. */
2688 if (dflow->block_pool)
2689 free_alloc_pool (dflow->block_pool);
2690
2691 dflow->block_pool = create_alloc_pool ("df_chain_chain_block pool",
2692 sizeof (struct df_link), 100);
2693
2694 if (problem_data->flags & DF_DU_CHAIN)
2695 {
2696 if (!df->def_info.refs_organized)
2697 df_reorganize_refs (&df->def_info);
2698
2699 /* Clear out the pointers from the refs. */
2700 for (i = 0; i < DF_DEFS_SIZE (df); i++)
2701 {
2702 struct df_ref *ref = df->def_info.refs[i];
2703 DF_REF_CHAIN (ref) = NULL;
2704 }
2705 }
2706
2707 if (problem_data->flags & DF_UD_CHAIN)
2708 {
2709 if (!df->use_info.refs_organized)
2710 df_reorganize_refs (&df->use_info);
2711 for (i = 0; i < DF_USES_SIZE (df); i++)
2712 {
2713 struct df_ref *ref = df->use_info.refs[i];
2714 DF_REF_CHAIN (ref) = NULL;
2715 }
2716 }
2717 }
2718
2719
2720 /* Reset all def_use and use_def chains in INSN. */
2721
2722 static void
2723 df_chain_insn_reset (struct dataflow *dflow, rtx insn)
2724 {
2725 struct df *df = dflow->df;
2726 struct df_chain_problem_data *problem_data =
2727 (struct df_chain_problem_data *) dflow->problem_data;
2728 unsigned int uid = INSN_UID (insn);
2729 struct df_insn_info *insn_info = NULL;
2730 struct df_ref *ref;
2731
2732 if (uid < df->insns_size)
2733 insn_info = DF_INSN_UID_GET (df, uid);
2734
2735 if (insn_info)
2736 {
2737 if (problem_data->flags & DF_DU_CHAIN)
2738 {
2739 ref = insn_info->defs;
2740 while (ref)
2741 {
2742 ref->chain = NULL;
2743 ref = ref->next_ref;
2744 }
2745 }
2746
2747 if (problem_data->flags & DF_UD_CHAIN)
2748 {
2749 ref = insn_info->uses;
2750 while (ref)
2751 {
2752 ref->chain = NULL;
2753 ref = ref->next_ref;
2754 }
2755 }
2756 }
2757 }
2758
2759
2760 /* Reset all def_use and use_def chains in basic block. */
2761
2762 static void
2763 df_chain_bb_reset (struct dataflow *dflow, unsigned int bb_index)
2764 {
2765 struct df *df = dflow->df;
2766 struct df_chain_problem_data *problem_data =
2767 (struct df_chain_problem_data *) dflow->problem_data;
2768 rtx insn;
2769 basic_block bb = BASIC_BLOCK (bb_index);
2770
2771 /* Some one deleted the basic block out from under us. */
2772 if (!bb)
2773 return;
2774
2775 FOR_BB_INSNS (bb, insn)
2776 {
2777 if (INSN_P (insn))
2778 {
2779 /* Record defs within INSN. */
2780 df_chain_insn_reset (dflow, insn);
2781 }
2782 }
2783
2784 /* Get rid of any chains in artifical uses or defs. */
2785 if (problem_data->flags & DF_DU_CHAIN)
2786 {
2787 struct df_ref *def;
2788 def = df_get_artificial_defs (df, bb_index);
2789 while (def)
2790 {
2791 def->chain = NULL;
2792 def = def->next_ref;
2793 }
2794 }
2795
2796 if (problem_data->flags & DF_UD_CHAIN)
2797 {
2798 struct df_ref *use;
2799 use = df_get_artificial_uses (df, bb_index);
2800 while (use)
2801 {
2802 use->chain = NULL;
2803 use = use->next_ref;
2804 }
2805 }
2806 }
2807
2808
2809 /* Reset all of the chains when the set of basic blocks changes. */
2810
2811
2812 static void
2813 df_chain_reset (struct dataflow *dflow, bitmap blocks_to_clear)
2814 {
2815 bitmap_iterator bi;
2816 unsigned int bb_index;
2817
2818 EXECUTE_IF_SET_IN_BITMAP (blocks_to_clear, 0, bb_index, bi)
2819 {
2820 df_chain_bb_reset (dflow, bb_index);
2821 }
2822
2823 free_alloc_pool (dflow->block_pool);
2824 dflow->block_pool = NULL;
2825 }
2826
2827
2828 /* Create the chains for a list of USEs. */
2829
2830 static void
2831 df_chain_create_bb_process_use (struct dataflow *dflow,
2832 struct df_chain_problem_data *problem_data,
2833 bitmap local_rd,
2834 struct df_ref *use,
2835 enum df_ref_flags top_flag)
2836 {
2837 struct df *df = dflow->df;
2838 bitmap_iterator bi;
2839 unsigned int def_index;
2840
2841 while (use)
2842 {
2843 /* Do not want to go through this for an uninitialized var. */
2844 unsigned int uregno = DF_REF_REGNO (use);
2845 int count = DF_REG_DEF_GET (df, uregno)->n_refs;
2846 if (count)
2847 {
2848 if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
2849 {
2850 unsigned int first_index = DF_REG_DEF_GET (df, uregno)->begin;
2851 unsigned int last_index = first_index + count - 1;
2852
2853 EXECUTE_IF_SET_IN_BITMAP (local_rd, first_index, def_index, bi)
2854 {
2855 struct df_ref *def;
2856 if (def_index > last_index)
2857 break;
2858
2859 def = DF_DEFS_GET (df, def_index);
2860 if (problem_data->flags & DF_DU_CHAIN)
2861 df_chain_create (dflow, def, use);
2862 if (problem_data->flags & DF_UD_CHAIN)
2863 df_chain_create (dflow, use, def);
2864 }
2865 }
2866 }
2867 use = use->next_ref;
2868 }
2869 }
2870
2871 /* Reset the storage pool that the def-use or use-def chains have been
2872 allocated in. We do not need to re adjust the pointers in the refs,
2873 these have already been clean out.*/
2874
2875 /* Create chains from reaching defs bitmaps for basic block BB. */
2876 static void
2877 df_chain_create_bb (struct dataflow *dflow,
2878 struct dataflow *rd_dflow,
2879 unsigned int bb_index)
2880 {
2881 basic_block bb = BASIC_BLOCK (bb_index);
2882 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (rd_dflow, bb_index);
2883 rtx insn;
2884 bitmap cpy = BITMAP_ALLOC (NULL);
2885 struct df *df = dflow->df;
2886 struct df_chain_problem_data *problem_data =
2887 (struct df_chain_problem_data *) dflow->problem_data;
2888 struct df_ref *def;
2889
2890 bitmap_copy (cpy, bb_info->in);
2891
2892 /* Since we are going forwards, process the artificial uses first
2893 then the artificial defs second. */
2894
2895 #ifdef EH_USES
2896 /* Create the chains for the artificial uses from the EH_USES at the
2897 beginning of the block. */
2898 df_chain_create_bb_process_use (dflow, problem_data, cpy,
2899 df_get_artificial_uses (df, bb->index),
2900 DF_REF_AT_TOP);
2901 #endif
2902
2903 for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref)
2904 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
2905 {
2906 unsigned int dregno = DF_REF_REGNO (def);
2907 bitmap_clear_range (cpy,
2908 DF_REG_DEF_GET (df, dregno)->begin,
2909 DF_REG_DEF_GET (df, dregno)->n_refs);
2910 if (! (DF_REF_FLAGS (def) & DF_REF_CLOBBER))
2911 bitmap_set_bit (cpy, DF_REF_ID (def));
2912 }
2913
2914 /* Process the regular instructions next. */
2915 FOR_BB_INSNS (bb, insn)
2916 {
2917 struct df_ref *def;
2918 unsigned int uid = INSN_UID (insn);
2919
2920 if (! INSN_P (insn))
2921 continue;
2922
2923 /* Now scan the uses and link them up with the defs that remain
2924 in the cpy vector. */
2925
2926 df_chain_create_bb_process_use (dflow, problem_data, cpy,
2927 DF_INSN_UID_GET (df, uid)->uses, 0);
2928
2929 /* Since we are going forwards, process the defs second. This
2930 pass only changes the bits in cpy. */
2931 for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
2932 {
2933 unsigned int dregno = DF_REF_REGNO (def);
2934 bitmap_clear_range (cpy,
2935 DF_REG_DEF_GET (df, dregno)->begin,
2936 DF_REG_DEF_GET (df, dregno)->n_refs);
2937 if (! (DF_REF_FLAGS (def) & DF_REF_CLOBBER))
2938 bitmap_set_bit (cpy, DF_REF_ID (def));
2939 }
2940 }
2941
2942 /* Create the chains for the artificial uses of the hard registers
2943 at the end of the block. */
2944 df_chain_create_bb_process_use (dflow, problem_data, cpy,
2945 df_get_artificial_uses (df, bb->index), 0);
2946 }
2947
2948 /* Create def-use chains from reaching use bitmaps for basic blocks
2949 in BLOCKS. */
2950
2951 static void
2952 df_chain_finalize (struct dataflow *dflow, bitmap all_blocks)
2953 {
2954 unsigned int bb_index;
2955 bitmap_iterator bi;
2956 struct df *df = dflow->df;
2957 struct dataflow *rd_dflow = df->problems_by_index [DF_RD];
2958
2959 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2960 {
2961 df_chain_create_bb (dflow, rd_dflow, bb_index);
2962 }
2963 }
2964
2965
2966 /* Free all storage associated with the problem. */
2967
2968 static void
2969 df_chain_free (struct dataflow *dflow)
2970 {
2971 free_alloc_pool (dflow->block_pool);
2972 free (dflow->problem_data);
2973 free (dflow);
2974 }
2975
2976
2977 /* Debugging info. */
2978
2979 static void
2980 df_chains_dump (struct dataflow *dflow, FILE *file)
2981 {
2982 struct df *df = dflow->df;
2983 unsigned int j;
2984 struct df_chain_problem_data *problem_data =
2985 (struct df_chain_problem_data *) dflow->problem_data;
2986
2987 if (problem_data->flags & DF_DU_CHAIN)
2988 {
2989 fprintf (file, "Def-use chains:\n");
2990 for (j = 0; j < df->def_info.bitmap_size; j++)
2991 {
2992 struct df_ref *def = DF_DEFS_GET (df, j);
2993 if (def)
2994 {
2995 fprintf (file, "d%d bb %d luid %d insn %d reg %d ",
2996 j, DF_REF_BBNO (def),
2997 DF_INSN_LUID (df, DF_REF_INSN (def)),
2998 DF_REF_INSN (def) ? DF_REF_INSN_UID (def) : -1,
2999 DF_REF_REGNO (def));
3000 if (def->flags & DF_REF_READ_WRITE)
3001 fprintf (file, "read/write ");
3002 df_chain_dump (df, DF_REF_CHAIN (def), file);
3003 fprintf (file, "\n");
3004 }
3005 }
3006 }
3007
3008 if (problem_data->flags & DF_UD_CHAIN)
3009 {
3010 fprintf (file, "Use-def chains:\n");
3011 for (j = 0; j < df->use_info.bitmap_size; j++)
3012 {
3013 struct df_ref *use = DF_USES_GET (df, j);
3014 if (use)
3015 {
3016 fprintf (file, "u%d bb %d luid %d insn %d reg %d ",
3017 j, DF_REF_BBNO (use),
3018 DF_REF_INSN (use) ?
3019 DF_INSN_LUID (df, DF_REF_INSN (use))
3020 : -1,
3021 DF_REF_INSN (DF_USES_GET (df, j)) ?
3022 DF_REF_INSN_UID (DF_USES_GET (df,j))
3023 : -1,
3024 DF_REF_REGNO (use));
3025 if (use->flags & DF_REF_READ_WRITE)
3026 fprintf (file, "read/write ");
3027 if (use->flags & DF_REF_STRIPPED)
3028 fprintf (file, "stripped ");
3029 if (use->flags & DF_REF_IN_NOTE)
3030 fprintf (file, "note ");
3031 df_chain_dump (df, DF_REF_CHAIN (use), file);
3032 fprintf (file, "\n");
3033 }
3034 }
3035 }
3036 }
3037
3038
3039 static struct df_problem problem_CHAIN =
3040 {
3041 DF_CHAIN, /* Problem id. */
3042 DF_NONE, /* Direction. */
3043 df_chain_alloc, /* Allocate the problem specific data. */
3044 df_chain_reset, /* Reset global information. */
3045 NULL, /* Free basic block info. */
3046 NULL, /* Local compute function. */
3047 NULL, /* Init the solution specific data. */
3048 NULL, /* Iterative solver. */
3049 NULL, /* Confluence operator 0. */
3050 NULL, /* Confluence operator n. */
3051 NULL, /* Transfer function. */
3052 df_chain_finalize, /* Finalize function. */
3053 df_chain_free, /* Free all of the problem information. */
3054 df_chains_dump, /* Debugging. */
3055 &problem_RD /* Dependent problem. */
3056 };
3057
3058
3059 /* Create a new DATAFLOW instance and add it to an existing instance
3060 of DF. The returned structure is what is used to get at the
3061 solution. */
3062
3063 struct dataflow *
3064 df_chain_add_problem (struct df *df, int flags)
3065 {
3066 struct df_chain_problem_data *problem_data =
3067 XNEW (struct df_chain_problem_data);
3068 struct dataflow *dflow = df_add_problem (df, &problem_CHAIN);
3069
3070 dflow->problem_data = problem_data;
3071 problem_data->flags = flags;
3072
3073 return dflow;
3074 }
3075
3076
3077 /*----------------------------------------------------------------------------
3078 REGISTER INFORMATION
3079
3080 Currently this consists of only lifetime information. But the plan is
3081 to enhance it so that it produces all of the register information needed
3082 by the register allocators.
3083 ----------------------------------------------------------------------------*/
3084
3085
3086 struct df_ri_problem_data
3087 {
3088 int *lifetime;
3089 };
3090
3091
3092 /* Allocate the lifetime information. */
3093
3094 static void
3095 df_ri_alloc (struct dataflow *dflow, bitmap blocks_to_rescan ATTRIBUTE_UNUSED)
3096 {
3097 struct df_ri_problem_data *problem_data =
3098 (struct df_ri_problem_data *) dflow->problem_data;
3099
3100 if (!dflow->problem_data)
3101 {
3102 struct df_ri_problem_data *problem_data = XNEW (struct df_ri_problem_data);
3103 dflow->problem_data = problem_data;
3104 }
3105
3106 problem_data->lifetime = xrealloc (problem_data->lifetime,
3107 max_reg_num () *sizeof (int));
3108 memset (problem_data->lifetime, 0, max_reg_num () *sizeof (int));
3109 }
3110
3111 /* Compute register info: lifetime, bb, and number of defs and uses
3112 for basic block BB. */
3113
3114 static void
3115 df_ri_bb_compute (struct dataflow *dflow, unsigned int bb_index, bitmap live)
3116 {
3117 struct df *df = dflow->df;
3118 struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, bb_index);
3119 struct df_ri_problem_data *problem_data =
3120 (struct df_ri_problem_data *) dflow->problem_data;
3121 basic_block bb = BASIC_BLOCK (bb_index);
3122 rtx insn;
3123
3124 bitmap_copy (live, bb_info->out);
3125
3126 FOR_BB_INSNS_REVERSE (bb, insn)
3127 {
3128 unsigned int uid = INSN_UID (insn);
3129 unsigned int regno;
3130 bitmap_iterator bi;
3131 struct df_ref *def;
3132 struct df_ref *use;
3133
3134 if (! INSN_P (insn))
3135 continue;
3136
3137 for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
3138 {
3139 unsigned int dregno = DF_REF_REGNO (def);
3140
3141 /* Kill this register. */
3142 bitmap_clear_bit (live, dregno);
3143 }
3144
3145 for (use = DF_INSN_UID_GET (df, uid)->uses; use; use = use->next_ref)
3146 {
3147 unsigned int uregno = DF_REF_REGNO (use);
3148
3149 if (!bitmap_bit_p (live, uregno))
3150 {
3151 use->flags |= DF_REF_DIES_AFTER_THIS_USE;
3152 /* This register is now live. */
3153 bitmap_set_bit (live, uregno);
3154 }
3155 else
3156 use->flags &= ~DF_REF_DIES_AFTER_THIS_USE;
3157 }
3158
3159 /* Increment lifetimes of all live registers. */
3160 EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi)
3161 {
3162 problem_data->lifetime[regno]++;
3163 }
3164 }
3165 }
3166
3167
3168 /* Compute register info: lifetime, bb, and number of defs and uses. */
3169 static void
3170 df_ri_compute (struct dataflow *dflow, bitmap all_blocks ATTRIBUTE_UNUSED,
3171 bitmap blocks_to_scan)
3172 {
3173 unsigned int bb_index;
3174 bitmap_iterator bi;
3175 bitmap live;
3176
3177 live = BITMAP_ALLOC (NULL);
3178
3179 EXECUTE_IF_SET_IN_BITMAP (blocks_to_scan, 0, bb_index, bi)
3180 {
3181 df_ri_bb_compute (dflow, bb_index, live);
3182 }
3183
3184 BITMAP_FREE (live);
3185 }
3186
3187
3188 /* Free all storage associated with the problem. */
3189
3190 static void
3191 df_ri_free (struct dataflow *dflow)
3192 {
3193 struct df_ri_problem_data *problem_data =
3194 (struct df_ri_problem_data *) dflow->problem_data;
3195
3196 free (problem_data->lifetime);
3197 free (dflow->problem_data);
3198 free (dflow);
3199 }
3200
3201
3202 /* Debugging info. */
3203
3204 static void
3205 df_ri_dump (struct dataflow *dflow, FILE *file)
3206 {
3207 struct df_ri_problem_data *problem_data =
3208 (struct df_ri_problem_data *) dflow->problem_data;
3209 int j;
3210
3211 fprintf (file, "Register info:\n");
3212 for (j = 0; j < max_reg_num (); j++)
3213 {
3214 fprintf (file, "reg %d life %d\n", j, problem_data->lifetime[j]);
3215 }
3216 }
3217
3218 /* All of the information associated every instance of the problem. */
3219
3220 static struct df_problem problem_RI =
3221 {
3222 DF_RI, /* Problem id. */
3223 DF_NONE, /* Direction. */
3224 df_ri_alloc, /* Allocate the problem specific data. */
3225 NULL, /* Reset global information. */
3226 NULL, /* Free basic block info. */
3227 df_ri_compute, /* Local compute function. */
3228 NULL, /* Init the solution specific data. */
3229 NULL, /* Iterative solver. */
3230 NULL, /* Confluence operator 0. */
3231 NULL, /* Confluence operator n. */
3232 NULL, /* Transfer function. */
3233 NULL, /* Finalize function. */
3234 df_ri_free, /* Free all of the problem information. */
3235 df_ri_dump, /* Debugging. */
3236 &problem_UR /* Dependent problem. */
3237 };
3238
3239
3240 /* Create a new DATAFLOW instance and add it to an existing instance
3241 of DF. The returned structure is what is used to get at the
3242 solution. */
3243
3244 struct dataflow *
3245 df_ri_add_problem (struct df *df)
3246 {
3247 return df_add_problem (df, &problem_RI);
3248 }
3249
3250
3251 /* Return total lifetime (in insns) of REG. */
3252 int
3253 df_reg_lifetime (struct df *df, rtx reg)
3254 {
3255 struct dataflow *dflow = df->problems_by_index[DF_RI];
3256 struct df_ri_problem_data *problem_data =
3257 (struct df_ri_problem_data *) dflow->problem_data;
3258 return problem_data->lifetime[REGNO (reg)];
3259 }
3260
3261
Mirror of the offical gcc git repository hosted at gcc.gnu.org