1 /* Dataflow support routines.
2 Copyright (C) 1999, 2000, 2001 Free Software Foundation, Inc.
3 Contributed by Michael P. Hayes (m.hayes@elec.canterbury.ac.nz,
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 2, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING. If not, write to the Free
20 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
26 This file provides some dataflow routines for computing reaching defs,
27 upward exposed uses, live variables, def-use chains, and use-def
28 chains. The global dataflow is performed using simple iterative
29 methods with a worklist and could be sped up by ordering the blocks
30 with a depth first search order.
32 A `struct ref' data structure (ref) is allocated for every register
33 reference (def or use) and this records the insn and bb the ref is
34 found within. The refs are linked together in chains of uses and defs
35 for each insn and for each register. Each ref also has a chain field
36 that links all the use refs for a def or all the def refs for a use.
37 This is used to create use-def or def-use chains.
42 Here's an example of using the dataflow routines.
48 df_analyse (df, 0, DF_ALL);
50 df_dump (df, DF_ALL, stderr);
55 df_init simply creates a poor man's object (df) that needs to be
56 passed to all the dataflow routines. df_finish destroys this
57 object and frees up any allocated memory.
59 df_analyse performs the following:
61 1. Records defs and uses by scanning the insns in each basic block
62 or by scanning the insns queued by df_insn_modify.
63 2. Links defs and uses into insn-def and insn-use chains.
64 3. Links defs and uses into reg-def and reg-use chains.
65 4. Assigns LUIDs to each insn (for modified blocks).
66 5. Calculates local reaching definitions.
67 6. Calculates global reaching definitions.
68 7. Creates use-def chains.
69 8. Calculates local reaching uses (upwards exposed uses).
70 9. Calculates global reaching uses.
71 10. Creates def-use chains.
72 11. Calculates local live registers.
73 12. Calculates global live registers.
74 13. Calculates register lifetimes and determines local registers.
79 Note that the dataflow information is not updated for every newly
80 deleted or created insn. If the dataflow information requires
81 updating then all the changed, new, or deleted insns needs to be
82 marked with df_insn_modify (or df_insns_modify) either directly or
83 indirectly (say through calling df_insn_delete). df_insn_modify
84 marks all the modified insns to get processed the next time df_analyse
87 Beware that tinkering with insns may invalidate the dataflow information.
88 The philosophy behind these routines is that once the dataflow
89 information has been gathered, the user should store what they require
90 before they tinker with any insn. Once a reg is replaced, for example,
91 then the reg-def/reg-use chains will point to the wrong place. Once a
92 whole lot of changes have been made, df_analyse can be called again
93 to update the dataflow information. Currently, this is not very smart
94 with regard to propagating changes to the dataflow so it should not
100 The basic object is a REF (reference) and this may either be a DEF
101 (definition) or a USE of a register.
103 These are linked into a variety of lists; namely reg-def, reg-use,
104 insn-def, insn-use, def-use, and use-def lists. For example,
105 the reg-def lists contain all the refs that define a given register
106 while the insn-use lists contain all the refs used by an insn.
108 Note that the reg-def and reg-use chains are generally short (except for the
109 hard registers) and thus it is much faster to search these chains
110 rather than searching the def or use bitmaps.
112 If the insns are in SSA form then the reg-def and use-def lists
113 should only contain the single defining ref.
117 1) Incremental dataflow analysis.
119 Note that if a loop invariant insn is hoisted (or sunk), we do not
120 need to change the def-use or use-def chains. All we have to do is to
121 change the bb field for all the associated defs and uses and to
122 renumber the LUIDs for the original and new basic blocks of the insn.
124 When shadowing loop mems we create new uses and defs for new pseudos
125 so we do not affect the existing dataflow information.
127 My current strategy is to queue up all modified, created, or deleted
128 insns so when df_analyse is called we can easily determine all the new
129 or deleted refs. Currently the global dataflow information is
130 recomputed from scratch but this could be propagated more efficiently.
132 2) Improved global data flow computation using depth first search.
134 3) Reduced memory requirements.
136 We could operate a pool of ref structures. When a ref is deleted it
137 gets returned to the pool (say by linking on to a chain of free refs).
138 This will require a pair of bitmaps for defs and uses so that we can
139 tell which ones have been changed. Alternatively, we could
140 periodically squeeze the def and use tables and associated bitmaps and
141 renumber the def and use ids.
143 4) Ordering of reg-def and reg-use lists.
145 Should the first entry in the def list be the first def (within a BB)?
146 Similarly, should the first entry in the use list be the last use
149 5) Working with a sub-CFG.
151 Often the whole CFG does not need to be analysed, for example,
152 when optimising a loop, only certain registers are of interest.
153 Perhaps there should be a bitmap argument to df_analyse to specify
154 which registers should be analysed? */
156 #define HANDLE_SUBREG
161 #include "insn-config.h"
163 #include "function.h"
166 #include "hard-reg-set.h"
167 #include "basic-block.h"
172 #define FOR_ALL_BBS(BB, CODE) \
175 for (node_ = 0; node_ < n_basic_blocks; node_++) \
176 {(BB) = BASIC_BLOCK (node_); CODE;};} while (0)
178 #define FOR_EACH_BB_IN_BITMAP(BITMAP, MIN, BB, CODE) \
180 unsigned int node_; \
181 EXECUTE_IF_SET_IN_BITMAP (BITMAP, MIN, node_, \
182 {(BB) = BASIC_BLOCK (node_); CODE;});} while (0)
184 #define FOR_EACH_BB_IN_BITMAP_REV(BITMAP, MIN, BB, CODE) \
186 unsigned int node_; \
187 EXECUTE_IF_SET_IN_BITMAP_REV (BITMAP, node_, \
188 {(BB) = BASIC_BLOCK (node_); CODE;});} while (0)
190 #define FOR_EACH_BB_IN_SBITMAP(BITMAP, MIN, BB, CODE) \
192 unsigned int node_; \
193 EXECUTE_IF_SET_IN_SBITMAP (BITMAP, MIN, node_, \
194 {(BB) = BASIC_BLOCK (node_); CODE;});} while (0)
196 #define obstack_chunk_alloc xmalloc
197 #define obstack_chunk_free free
199 static struct obstack df_ref_obstack
;
200 static struct df
*ddf
;
202 static void df_reg_table_realloc
PARAMS((struct df
*, int));
204 static void df_def_table_realloc
PARAMS((struct df
*, int));
206 static void df_insn_table_realloc
PARAMS((struct df
*, int));
207 static void df_bitmaps_alloc
PARAMS((struct df
*, int));
208 static void df_bitmaps_free
PARAMS((struct df
*, int));
209 static void df_free
PARAMS((struct df
*));
210 static void df_alloc
PARAMS((struct df
*, int));
212 static rtx df_reg_clobber_gen
PARAMS((unsigned int));
213 static rtx df_reg_use_gen
PARAMS((unsigned int));
215 static inline struct df_link
*df_link_create
PARAMS((struct ref
*,
217 static struct df_link
*df_ref_unlink
PARAMS((struct df_link
**, struct ref
*));
218 static void df_def_unlink
PARAMS((struct df
*, struct ref
*));
219 static void df_use_unlink
PARAMS((struct df
*, struct ref
*));
220 static void df_insn_refs_unlink
PARAMS ((struct df
*, basic_block
, rtx
));
222 static void df_bb_refs_unlink
PARAMS ((struct df
*, basic_block
));
223 static void df_refs_unlink
PARAMS ((struct df
*, bitmap
));
226 static struct ref
*df_ref_create
PARAMS((struct df
*,
227 rtx
, rtx
*, basic_block
, rtx
,
229 static void df_ref_record_1
PARAMS((struct df
*, rtx
, rtx
*,
230 basic_block
, rtx
, enum df_ref_type
));
231 static void df_ref_record
PARAMS((struct df
*, rtx
, rtx
*,
232 basic_block bb
, rtx
, enum df_ref_type
));
233 static void df_def_record_1
PARAMS((struct df
*, rtx
, basic_block
, rtx
));
234 static void df_defs_record
PARAMS((struct df
*, rtx
, basic_block
, rtx
));
235 static void df_uses_record
PARAMS((struct df
*, rtx
*,
236 enum df_ref_type
, basic_block
, rtx
));
237 static void df_insn_refs_record
PARAMS((struct df
*, basic_block
, rtx
));
238 static void df_bb_refs_record
PARAMS((struct df
*, basic_block
));
239 static void df_refs_record
PARAMS((struct df
*, bitmap
));
241 static int df_visit_next_rc
PARAMS ((struct df
*, sbitmap
));
242 static int df_visit_next_rts
PARAMS ((struct df
*, sbitmap
));
243 static void df_bb_reg_def_chain_create
PARAMS((struct df
*, basic_block
));
244 static void df_reg_def_chain_create
PARAMS((struct df
*, bitmap
));
245 static void df_bb_reg_use_chain_create
PARAMS((struct df
*, basic_block
));
246 static void df_reg_use_chain_create
PARAMS((struct df
*, bitmap
));
247 static void df_bb_du_chain_create
PARAMS((struct df
*, basic_block
, bitmap
));
248 static void df_du_chain_create
PARAMS((struct df
*, bitmap
));
249 static void df_bb_ud_chain_create
PARAMS((struct df
*, basic_block
));
250 static void df_ud_chain_create
PARAMS((struct df
*, bitmap
));
251 static void df_rd_global_compute
PARAMS((struct df
*, bitmap
));
252 static void df_ru_global_compute
PARAMS((struct df
*, bitmap
));
253 static void df_lr_global_compute
PARAMS((struct df
*, bitmap
));
254 static void df_bb_rd_local_compute
PARAMS((struct df
*, basic_block
));
255 static void df_rd_local_compute
PARAMS((struct df
*, bitmap
));
256 static void df_bb_ru_local_compute
PARAMS((struct df
*, basic_block
));
257 static void df_ru_local_compute
PARAMS((struct df
*, bitmap
));
258 static void df_bb_lr_local_compute
PARAMS((struct df
*, basic_block
));
259 static void df_lr_local_compute
PARAMS((struct df
*, bitmap
));
260 static void df_bb_reg_info_compute
PARAMS((struct df
*, basic_block
, bitmap
));
261 static void df_reg_info_compute
PARAMS((struct df
*, bitmap
));
263 static int df_bb_luids_set
PARAMS((struct df
*df
, basic_block
));
264 static int df_luids_set
PARAMS((struct df
*df
, bitmap
));
266 static int df_modified_p
PARAMS ((struct df
*, bitmap
));
267 static int df_refs_queue
PARAMS ((struct df
*));
268 static int df_refs_process
PARAMS ((struct df
*));
269 static int df_bb_refs_update
PARAMS ((struct df
*, basic_block
));
270 static int df_refs_update
PARAMS ((struct df
*));
271 static void df_analyse_1
PARAMS((struct df
*, bitmap
, int, int));
273 static void df_insns_modify
PARAMS((struct df
*, basic_block
,
275 static int df_rtx_mem_replace
PARAMS ((rtx
*, void *));
276 static int df_rtx_reg_replace
PARAMS ((rtx
*, void *));
277 void df_refs_reg_replace
PARAMS ((struct df
*, bitmap
,
278 struct df_link
*, rtx
, rtx
));
280 static int df_def_dominates_all_uses_p
PARAMS((struct df
*, struct ref
*def
));
281 static int df_def_dominates_uses_p
PARAMS((struct df
*,
282 struct ref
*def
, bitmap
));
283 static struct ref
*df_bb_regno_last_use_find
PARAMS((struct df
*, basic_block
,
285 static struct ref
*df_bb_regno_first_def_find
PARAMS((struct df
*, basic_block
,
287 static struct ref
*df_bb_insn_regno_last_use_find
PARAMS((struct df
*,
290 static struct ref
*df_bb_insn_regno_first_def_find
PARAMS((struct df
*,
294 static void df_chain_dump
PARAMS((struct df_link
*, FILE *file
));
295 static void df_chain_dump_regno
PARAMS((struct df_link
*, FILE *file
));
296 static void df_regno_debug
PARAMS ((struct df
*, unsigned int, FILE *));
297 static void df_ref_debug
PARAMS ((struct df
*, struct ref
*, FILE *));
300 /* Local memory allocation/deallocation routines. */
303 /* Increase the insn info table by SIZE more elements. */
305 df_insn_table_realloc (df
, size
)
309 /* Make table 25 percent larger by default. */
311 size
= df
->insn_size
/ 4;
313 size
+= df
->insn_size
;
315 df
->insns
= (struct insn_info
*)
316 xrealloc (df
->insns
, size
* sizeof (struct insn_info
));
318 memset (df
->insns
+ df
->insn_size
, 0,
319 (size
- df
->insn_size
) * sizeof (struct insn_info
));
321 df
->insn_size
= size
;
323 if (! df
->insns_modified
)
325 df
->insns_modified
= BITMAP_XMALLOC ();
326 bitmap_zero (df
->insns_modified
);
331 /* Increase the reg info table by SIZE more elements. */
333 df_reg_table_realloc (df
, size
)
337 /* Make table 25 percent larger by default. */
339 size
= df
->reg_size
/ 4;
341 size
+= df
->reg_size
;
343 df
->regs
= (struct reg_info
*)
344 xrealloc (df
->regs
, size
* sizeof (struct reg_info
));
346 /* Zero the new entries. */
347 memset (df
->regs
+ df
->reg_size
, 0,
348 (size
- df
->reg_size
) * sizeof (struct reg_info
));
355 /* Not currently used. */
357 df_def_table_realloc (df
, size
)
364 /* Make table 25 percent larger by default. */
366 size
= df
->def_size
/ 4;
368 df
->def_size
+= size
;
369 df
->defs
= xrealloc (df
->defs
,
370 df
->def_size
* sizeof (*df
->defs
));
372 /* Allocate a new block of memory and link into list of blocks
373 that will need to be freed later. */
375 refs
= xmalloc (size
* sizeof (*refs
));
377 /* Link all the new refs together, overloading the chain field. */
378 for (i
= 0; i
< size
- 1; i
++)
379 refs
[i
].chain
= (struct df_link
*)(refs
+ i
+ 1);
380 refs
[size
- 1].chain
= 0;
386 /* Allocate bitmaps for each basic block. */
388 df_bitmaps_alloc (df
, flags
)
395 /* Free the bitmaps if they need resizing. */
396 if ((flags
& DF_LR
) && df
->n_regs
< (unsigned int)max_reg_num ())
397 dflags
|= DF_LR
| DF_RU
;
398 if ((flags
& DF_RU
) && df
->n_uses
< df
->use_id
)
400 if ((flags
& DF_RD
) && df
->n_defs
< df
->def_id
)
404 df_bitmaps_free (df
, dflags
);
406 df
->n_defs
= df
->def_id
;
407 df
->n_uses
= df
->use_id
;
409 for (i
= 0; i
< df
->n_bbs
; i
++)
411 basic_block bb
= BASIC_BLOCK (i
);
412 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
414 if (flags
& DF_RD
&& ! bb_info
->rd_in
)
416 /* Allocate bitmaps for reaching definitions. */
417 bb_info
->rd_kill
= BITMAP_XMALLOC ();
418 bitmap_zero (bb_info
->rd_kill
);
419 bb_info
->rd_gen
= BITMAP_XMALLOC ();
420 bitmap_zero (bb_info
->rd_gen
);
421 bb_info
->rd_in
= BITMAP_XMALLOC ();
422 bb_info
->rd_out
= BITMAP_XMALLOC ();
423 bb_info
->rd_valid
= 0;
426 if (flags
& DF_RU
&& ! bb_info
->ru_in
)
428 /* Allocate bitmaps for upward exposed uses. */
429 bb_info
->ru_kill
= BITMAP_XMALLOC ();
430 bitmap_zero (bb_info
->ru_kill
);
431 /* Note the lack of symmetry. */
432 bb_info
->ru_gen
= BITMAP_XMALLOC ();
433 bitmap_zero (bb_info
->ru_gen
);
434 bb_info
->ru_in
= BITMAP_XMALLOC ();
435 bb_info
->ru_out
= BITMAP_XMALLOC ();
436 bb_info
->ru_valid
= 0;
439 if (flags
& DF_LR
&& ! bb_info
->lr_in
)
441 /* Allocate bitmaps for live variables. */
442 bb_info
->lr_def
= BITMAP_XMALLOC ();
443 bitmap_zero (bb_info
->lr_def
);
444 bb_info
->lr_use
= BITMAP_XMALLOC ();
445 bitmap_zero (bb_info
->lr_use
);
446 bb_info
->lr_in
= BITMAP_XMALLOC ();
447 bb_info
->lr_out
= BITMAP_XMALLOC ();
448 bb_info
->lr_valid
= 0;
454 /* Free bitmaps for each basic block. */
456 df_bitmaps_free (df
, flags
)
457 struct df
*df ATTRIBUTE_UNUSED
;
462 for (i
= 0; i
< df
->n_bbs
; i
++)
464 basic_block bb
= BASIC_BLOCK (i
);
465 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
470 if ((flags
& DF_RD
) && bb_info
->rd_in
)
472 /* Free bitmaps for reaching definitions. */
473 BITMAP_XFREE (bb_info
->rd_kill
);
474 bb_info
->rd_kill
= NULL
;
475 BITMAP_XFREE (bb_info
->rd_gen
);
476 bb_info
->rd_gen
= NULL
;
477 BITMAP_XFREE (bb_info
->rd_in
);
478 bb_info
->rd_in
= NULL
;
479 BITMAP_XFREE (bb_info
->rd_out
);
480 bb_info
->rd_out
= NULL
;
483 if ((flags
& DF_RU
) && bb_info
->ru_in
)
485 /* Free bitmaps for upward exposed uses. */
486 BITMAP_XFREE (bb_info
->ru_kill
);
487 bb_info
->ru_kill
= NULL
;
488 BITMAP_XFREE (bb_info
->ru_gen
);
489 bb_info
->ru_gen
= NULL
;
490 BITMAP_XFREE (bb_info
->ru_in
);
491 bb_info
->ru_in
= NULL
;
492 BITMAP_XFREE (bb_info
->ru_out
);
493 bb_info
->ru_out
= NULL
;
496 if ((flags
& DF_LR
) && bb_info
->lr_in
)
498 /* Free bitmaps for live variables. */
499 BITMAP_XFREE (bb_info
->lr_def
);
500 bb_info
->lr_def
= NULL
;
501 BITMAP_XFREE (bb_info
->lr_use
);
502 bb_info
->lr_use
= NULL
;
503 BITMAP_XFREE (bb_info
->lr_in
);
504 bb_info
->lr_in
= NULL
;
505 BITMAP_XFREE (bb_info
->lr_out
);
506 bb_info
->lr_out
= NULL
;
509 df
->flags
&= ~(flags
& (DF_RD
| DF_RU
| DF_LR
));
513 /* Allocate and initialise dataflow memory. */
515 df_alloc (df
, n_regs
)
522 gcc_obstack_init (&df_ref_obstack
);
524 /* Perhaps we should use LUIDs to save memory for the insn_refs
525 table. This is only a small saving; a few pointers. */
526 n_insns
= get_max_uid () + 1;
530 /* Approximate number of defs by number of insns. */
531 df
->def_size
= n_insns
;
532 df
->defs
= xmalloc (df
->def_size
* sizeof (*df
->defs
));
536 /* Approximate number of uses by twice number of insns. */
537 df
->use_size
= n_insns
* 2;
538 df
->uses
= xmalloc (df
->use_size
* sizeof (*df
->uses
));
541 df
->n_bbs
= n_basic_blocks
;
543 /* Allocate temporary working array used during local dataflow analysis. */
544 df
->reg_def_last
= xmalloc (df
->n_regs
* sizeof (struct ref
*));
546 df_insn_table_realloc (df
, n_insns
);
548 df_reg_table_realloc (df
, df
->n_regs
);
550 df
->bbs_modified
= BITMAP_XMALLOC ();
551 bitmap_zero (df
->bbs_modified
);
555 df
->bbs
= xcalloc (df
->n_bbs
, sizeof (struct bb_info
));
557 df
->all_blocks
= BITMAP_XMALLOC ();
558 for (i
= 0; i
< n_basic_blocks
; i
++)
559 bitmap_set_bit (df
->all_blocks
, i
);
563 /* Free all the dataflow info. */
568 df_bitmaps_free (df
, DF_ALL
);
596 if (df
->bbs_modified
)
597 BITMAP_XFREE (df
->bbs_modified
);
598 df
->bbs_modified
= 0;
600 if (df
->insns_modified
)
601 BITMAP_XFREE (df
->insns_modified
);
602 df
->insns_modified
= 0;
604 BITMAP_XFREE (df
->all_blocks
);
607 obstack_free (&df_ref_obstack
, NULL
);
610 /* Local miscellaneous routines. */
612 /* Return a USE for register REGNO. */
613 static rtx
df_reg_use_gen (regno
)
619 reg
= regno
>= FIRST_PSEUDO_REGISTER
620 ? regno_reg_rtx
[regno
] : gen_rtx_REG (reg_raw_mode
[regno
], regno
);
622 use
= gen_rtx_USE (GET_MODE (reg
), reg
);
627 /* Return a CLOBBER for register REGNO. */
628 static rtx
df_reg_clobber_gen (regno
)
634 reg
= regno
>= FIRST_PSEUDO_REGISTER
635 ? regno_reg_rtx
[regno
] : gen_rtx_REG (reg_raw_mode
[regno
], regno
);
637 use
= gen_rtx_CLOBBER (GET_MODE (reg
), reg
);
641 /* Local chain manipulation routines. */
643 /* Create a link in a def-use or use-def chain. */
644 static inline struct df_link
*
645 df_link_create (ref
, next
)
647 struct df_link
*next
;
649 struct df_link
*link
;
651 link
= (struct df_link
*) obstack_alloc (&df_ref_obstack
,
659 /* Add REF to chain head pointed to by PHEAD. */
660 static struct df_link
*
661 df_ref_unlink (phead
, ref
)
662 struct df_link
**phead
;
665 struct df_link
*link
= *phead
;
671 /* Only a single ref. It must be the one we want.
672 If not, the def-use and use-def chains are likely to
674 if (link
->ref
!= ref
)
676 /* Now have an empty chain. */
681 /* Multiple refs. One of them must be us. */
682 if (link
->ref
== ref
)
687 for (; link
->next
; link
= link
->next
)
689 if (link
->next
->ref
== ref
)
691 /* Unlink from list. */
692 link
->next
= link
->next
->next
;
703 /* Unlink REF from all def-use/use-def chains, etc. */
705 df_ref_remove (df
, ref
)
709 if (DF_REF_REG_DEF_P (ref
))
711 df_def_unlink (df
, ref
);
712 df_ref_unlink (&df
->insns
[DF_REF_INSN_UID (ref
)].defs
, ref
);
716 df_use_unlink (df
, ref
);
717 df_ref_unlink (&df
->insns
[DF_REF_INSN_UID (ref
)].uses
, ref
);
723 /* Unlink DEF from use-def and reg-def chains. */
725 df_def_unlink (df
, def
)
726 struct df
*df ATTRIBUTE_UNUSED
;
729 struct df_link
*du_link
;
730 unsigned int dregno
= DF_REF_REGNO (def
);
732 /* Follow def-use chain to find all the uses of this def. */
733 for (du_link
= DF_REF_CHAIN (def
); du_link
; du_link
= du_link
->next
)
735 struct ref
*use
= du_link
->ref
;
737 /* Unlink this def from the use-def chain. */
738 df_ref_unlink (&DF_REF_CHAIN (use
), def
);
740 DF_REF_CHAIN (def
) = 0;
742 /* Unlink def from reg-def chain. */
743 df_ref_unlink (&df
->regs
[dregno
].defs
, def
);
745 df
->defs
[DF_REF_ID (def
)] = 0;
749 /* Unlink use from def-use and reg-use chains. */
751 df_use_unlink (df
, use
)
752 struct df
*df ATTRIBUTE_UNUSED
;
755 struct df_link
*ud_link
;
756 unsigned int uregno
= DF_REF_REGNO (use
);
758 /* Follow use-def chain to find all the defs of this use. */
759 for (ud_link
= DF_REF_CHAIN (use
); ud_link
; ud_link
= ud_link
->next
)
761 struct ref
*def
= ud_link
->ref
;
763 /* Unlink this use from the def-use chain. */
764 df_ref_unlink (&DF_REF_CHAIN (def
), use
);
766 DF_REF_CHAIN (use
) = 0;
768 /* Unlink use from reg-use chain. */
769 df_ref_unlink (&df
->regs
[uregno
].uses
, use
);
771 df
->uses
[DF_REF_ID (use
)] = 0;
774 /* Local routines for recording refs. */
777 /* Create a new ref of type DF_REF_TYPE for register REG at address
778 LOC within INSN of BB. */
780 df_ref_create (df
, reg
, loc
, bb
, insn
, ref_type
)
786 enum df_ref_type ref_type
;
788 struct ref
*this_ref
;
791 this_ref
= (struct ref
*) obstack_alloc (&df_ref_obstack
,
793 DF_REF_REG (this_ref
) = reg
;
794 DF_REF_LOC (this_ref
) = loc
;
795 DF_REF_BB (this_ref
) = bb
;
796 DF_REF_INSN (this_ref
) = insn
;
797 DF_REF_CHAIN (this_ref
) = 0;
798 DF_REF_TYPE (this_ref
) = ref_type
;
799 uid
= INSN_UID (insn
);
801 if (ref_type
== DF_REF_REG_DEF
)
803 if (df
->def_id
>= df
->def_size
)
805 /* Make table 25 percent larger. */
806 df
->def_size
+= (df
->def_size
/ 4);
807 df
->defs
= xrealloc (df
->defs
,
808 df
->def_size
* sizeof (*df
->defs
));
810 DF_REF_ID (this_ref
) = df
->def_id
;
811 df
->defs
[df
->def_id
++] = this_ref
;
815 if (df
->use_id
>= df
->use_size
)
817 /* Make table 25 percent larger. */
818 df
->use_size
+= (df
->use_size
/ 4);
819 df
->uses
= xrealloc (df
->uses
,
820 df
->use_size
* sizeof (*df
->uses
));
822 DF_REF_ID (this_ref
) = df
->use_id
;
823 df
->uses
[df
->use_id
++] = this_ref
;
829 /* Create a new reference of type DF_REF_TYPE for a single register REG,
830 used inside the LOC rtx of INSN. */
832 df_ref_record_1 (df
, reg
, loc
, bb
, insn
, ref_type
)
838 enum df_ref_type ref_type
;
840 df_ref_create (df
, reg
, loc
, bb
, insn
, ref_type
);
844 /* Create new references of type DF_REF_TYPE for each part of register REG
845 at address LOC within INSN of BB. */
847 df_ref_record (df
, reg
, loc
, bb
, insn
, ref_type
)
853 enum df_ref_type ref_type
;
857 if (GET_CODE (reg
) != REG
&& GET_CODE (reg
) != SUBREG
)
860 /* For the reg allocator we are interested in some SUBREG rtx's, but not
861 all. Notably only those representing a word extraction from a multi-word
862 reg. As written in the docu those should have the form
863 (subreg:SI (reg:M A) N), with size(SImode) > size(Mmode).
864 XXX Is that true? We could also use the global word_mode variable. */
865 if (GET_CODE (reg
) == SUBREG
866 && (GET_MODE_SIZE (GET_MODE (reg
)) < GET_MODE_SIZE (word_mode
)
867 || GET_MODE_SIZE (GET_MODE (reg
))
868 >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (reg
)))))
870 loc
= &SUBREG_REG (reg
);
874 regno
= REGNO (GET_CODE (reg
) == SUBREG
? SUBREG_REG (reg
) : reg
);
875 if (regno
< FIRST_PSEUDO_REGISTER
)
880 if (! (df
->flags
& DF_HARD_REGS
))
883 /* GET_MODE (reg) is correct here. We don't want to go into a SUBREG
884 for the mode, because we only want to add references to regs, which
885 are really referenced. E.g. a (subreg:SI (reg:DI 0) 0) does _not_
886 reference the whole reg 0 in DI mode (which would also include
887 reg 1, at least, if 0 and 1 are SImode registers). */
888 endregno
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
890 for (i
= regno
; i
< endregno
; i
++)
891 df_ref_record_1 (df
, gen_rtx_REG (reg_raw_mode
[i
], i
),
892 loc
, bb
, insn
, ref_type
);
896 df_ref_record_1 (df
, reg
, loc
, bb
, insn
, ref_type
);
901 /* Process all the registers defined in the rtx, X. */
903 df_def_record_1 (df
, x
, bb
, insn
)
909 rtx
*loc
= &SET_DEST (x
);
912 /* Some targets place small structures in registers for
913 return values of functions. */
914 if (GET_CODE (dst
) == PARALLEL
&& GET_MODE (dst
) == BLKmode
)
918 for (i
= XVECLEN (dst
, 0) - 1; i
>= 0; i
--)
919 df_def_record_1 (df
, XVECEXP (dst
, 0, i
), bb
, insn
);
923 /* May be, we should flag the use of strict_low_part somehow. Might be
924 handy for the reg allocator. */
926 while (GET_CODE (dst
) == STRICT_LOW_PART
927 || GET_CODE (dst
) == ZERO_EXTRACT
928 || GET_CODE (dst
) == SIGN_EXTRACT
)
930 loc
= &XEXP (dst
, 0);
933 /* For the reg allocator we are interested in exact register references.
934 This means, we want to know, if only a part of a register is
937 if (GET_CODE (dst) == SUBREG)
939 loc = &XEXP (dst, 0);
944 while (GET_CODE (dst
) == SUBREG
945 || GET_CODE (dst
) == ZERO_EXTRACT
946 || GET_CODE (dst
) == SIGN_EXTRACT
947 || GET_CODE (dst
) == STRICT_LOW_PART
)
949 loc
= &XEXP (dst
, 0);
954 if (GET_CODE (dst
) == REG
955 || (GET_CODE (dst
) == SUBREG
&& GET_CODE (SUBREG_REG (dst
)) == REG
))
956 df_ref_record (df
, dst
, loc
, bb
, insn
, DF_REF_REG_DEF
);
960 /* Process all the registers defined in the pattern rtx, X. */
962 df_defs_record (df
, x
, bb
, insn
)
968 RTX_CODE code
= GET_CODE (x
);
970 if (code
== SET
|| code
== CLOBBER
)
972 /* Mark the single def within the pattern. */
973 df_def_record_1 (df
, x
, bb
, insn
);
975 else if (code
== PARALLEL
)
979 /* Mark the multiple defs within the pattern. */
980 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
982 code
= GET_CODE (XVECEXP (x
, 0, i
));
983 if (code
== SET
|| code
== CLOBBER
)
984 df_def_record_1 (df
, XVECEXP (x
, 0, i
), bb
, insn
);
990 /* Process all the registers used in the rtx at address LOC. */
992 df_uses_record (df
, loc
, ref_type
, bb
, insn
)
995 enum df_ref_type ref_type
;
1004 code
= GET_CODE (x
);
1018 /* If we are clobbering a MEM, mark any registers inside the address
1020 if (GET_CODE (XEXP (x
, 0)) == MEM
)
1021 df_uses_record (df
, &XEXP (XEXP (x
, 0), 0),
1022 DF_REF_REG_MEM_STORE
, bb
, insn
);
1024 /* If we're clobbering a REG then we have a def so ignore. */
1028 df_uses_record (df
, &XEXP (x
, 0), DF_REF_REG_MEM_LOAD
, bb
, insn
);
1032 /* While we're here, optimize this case. */
1033 #if defined(HANDLE_SUBREG)
1035 /* In case the SUBREG is not of a register, don't optimize. */
1036 if (GET_CODE (SUBREG_REG (x
)) != REG
)
1038 loc
= &SUBREG_REG (x
);
1039 df_uses_record (df
, loc
, ref_type
, bb
, insn
);
1043 loc
= &SUBREG_REG (x
);
1045 if (GET_CODE (x
) != REG
)
1047 df_uses_record (df
, loc
, ref_type
, bb
, insn
);
1052 /* ... Fall through ... */
1055 /* See a register (or subreg) other than being set. */
1056 df_ref_record (df
, x
, loc
, bb
, insn
, ref_type
);
1061 rtx dst
= SET_DEST (x
);
1064 /* If storing into MEM, don't show it as being used. But do
1065 show the address as being used. */
1066 if (GET_CODE (dst
) == MEM
)
1068 df_uses_record (df
, &XEXP (dst
, 0),
1069 DF_REF_REG_MEM_STORE
,
1071 df_uses_record (df
, &SET_SRC (x
), DF_REF_REG_USE
, bb
, insn
);
1075 #if 1 && defined(HANDLE_SUBREG)
1076 /* Look for sets that perform a read-modify-write. */
1077 while (GET_CODE (dst
) == STRICT_LOW_PART
1078 || GET_CODE (dst
) == ZERO_EXTRACT
1079 || GET_CODE (dst
) == SIGN_EXTRACT
)
1081 if (GET_CODE (dst
) == STRICT_LOW_PART
)
1083 dst
= XEXP (dst
, 0);
1084 if (GET_CODE (dst
) != SUBREG
)
1086 /* A strict_low_part uses the whole reg not only the subreg. */
1087 df_uses_record (df
, &SUBREG_REG (dst
), DF_REF_REG_USE
, bb
, insn
);
1091 df_uses_record (df
, &XEXP (dst
, 0), DF_REF_REG_USE
, bb
, insn
);
1092 dst
= XEXP (dst
, 0);
1095 if (GET_CODE (dst
) == SUBREG
)
1097 /* Paradoxical or too small subreg's are read-mod-write. */
1098 if (GET_MODE_SIZE (GET_MODE (dst
)) < GET_MODE_SIZE (word_mode
)
1099 || GET_MODE_SIZE (GET_MODE (dst
))
1100 >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (dst
))))
1103 /* In the original code also some SUBREG rtx's were considered
1104 read-modify-write (those with
1105 REG_SIZE(SUBREG_REG(dst)) > REG_SIZE(dst) )
1106 e.g. a (subreg:QI (reg:SI A) 0). I can't see this. The only
1107 reason for a read cycle for reg A would be to somehow preserve
1108 the bits outside of the subreg:QI. But for this a strict_low_part
1109 was necessary anyway, and this we handled already. */
1111 while (GET_CODE (dst
) == STRICT_LOW_PART
1112 || GET_CODE (dst
) == ZERO_EXTRACT
1113 || GET_CODE (dst
) == SIGN_EXTRACT
1114 || GET_CODE (dst
) == SUBREG
)
1116 /* A SUBREG of a smaller size does not use the old value. */
1117 if (GET_CODE (dst
) != SUBREG
1118 || (REG_SIZE (SUBREG_REG (dst
)) > REG_SIZE (dst
)))
1120 dst
= XEXP (dst
, 0);
1124 if ((GET_CODE (dst
) == PARALLEL
&& GET_MODE (dst
) == BLKmode
)
1125 || GET_CODE (dst
) == REG
|| GET_CODE (dst
) == SUBREG
)
1127 #if 1 || !defined(HANDLE_SUBREG)
1129 df_uses_record (df
, &SET_DEST (x
), DF_REF_REG_USE
, bb
, insn
);
1131 df_uses_record (df
, &SET_SRC (x
), DF_REF_REG_USE
, bb
, insn
);
1141 case UNSPEC_VOLATILE
:
1145 /* Traditional and volatile asm instructions must be considered to use
1146 and clobber all hard registers, all pseudo-registers and all of
1147 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
1149 Consider for instance a volatile asm that changes the fpu rounding
1150 mode. An insn should not be moved across this even if it only uses
1151 pseudo-regs because it might give an incorrectly rounded result.
1153 For now, just mark any regs we can find in ASM_OPERANDS as
1156 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
1157 We can not just fall through here since then we would be confused
1158 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
1159 traditional asms unlike their normal usage. */
1160 if (code
== ASM_OPERANDS
)
1164 for (j
= 0; j
< ASM_OPERANDS_INPUT_LENGTH (x
); j
++)
1165 df_uses_record (df
, &ASM_OPERANDS_INPUT (x
, j
),
1166 DF_REF_REG_USE
, bb
, insn
);
1178 /* Catch the def of the register being modified. */
1179 df_ref_record (df
, XEXP (x
, 0), &XEXP (x
, 0), bb
, insn
, DF_REF_REG_DEF
);
1181 /* ... Fall through to handle uses ... */
1187 /* Recursively scan the operands of this expression. */
1189 register const char *fmt
= GET_RTX_FORMAT (code
);
1192 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1196 /* Tail recursive case: save a function call level. */
1202 df_uses_record (df
, &XEXP (x
, i
), ref_type
, bb
, insn
);
1204 else if (fmt
[i
] == 'E')
1207 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1208 df_uses_record (df
, &XVECEXP (x
, i
, j
), ref_type
,
1216 /* Record all the df within INSN of basic block BB. */
1218 df_insn_refs_record (df
, bb
, insn
)
1227 /* Record register defs */
1228 df_defs_record (df
, PATTERN (insn
), bb
, insn
);
1230 if (GET_CODE (insn
) == CALL_INSN
)
1235 /* Record the registers used to pass arguments. */
1236 for (note
= CALL_INSN_FUNCTION_USAGE (insn
); note
;
1237 note
= XEXP (note
, 1))
1239 if (GET_CODE (XEXP (note
, 0)) == USE
)
1240 df_uses_record (df
, &SET_DEST (XEXP (note
, 0)), DF_REF_REG_USE
,
1244 /* The stack ptr is used (honorarily) by a CALL insn. */
1245 x
= df_reg_use_gen (STACK_POINTER_REGNUM
);
1246 df_uses_record (df
, &SET_DEST (x
), DF_REF_REG_USE
, bb
, insn
);
1248 if (df
->flags
& DF_HARD_REGS
)
1250 /* Calls may also reference any of the global registers,
1251 so they are recorded as used. */
1252 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1255 x
= df_reg_use_gen (i
);
1256 df_uses_record (df
, &SET_DEST (x
),
1257 DF_REF_REG_USE
, bb
, insn
);
1262 /* Record the register uses. */
1263 df_uses_record (df
, &PATTERN (insn
),
1264 DF_REF_REG_USE
, bb
, insn
);
1267 if (GET_CODE (insn
) == CALL_INSN
)
1271 if (df
->flags
& DF_HARD_REGS
)
1273 /* Kill all registers invalidated by a call. */
1274 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1275 if (TEST_HARD_REG_BIT (regs_invalidated_by_call
, i
))
1277 rtx reg_clob
= df_reg_clobber_gen (i
);
1278 df_defs_record (df
, reg_clob
, bb
, insn
);
1282 /* There may be extra registers to be clobbered. */
1283 for (note
= CALL_INSN_FUNCTION_USAGE (insn
);
1285 note
= XEXP (note
, 1))
1286 if (GET_CODE (XEXP (note
, 0)) == CLOBBER
)
1287 df_defs_record (df
, XEXP (note
, 0), bb
, insn
);
1293 /* Record all the refs within the basic block BB. */
1295 df_bb_refs_record (df
, bb
)
1301 /* Scan the block an insn at a time from beginning to end. */
1302 for (insn
= bb
->head
; ; insn
= NEXT_INSN (insn
))
1306 /* Record defs within INSN. */
1307 df_insn_refs_record (df
, bb
, insn
);
1309 if (insn
== bb
->end
)
1315 /* Record all the refs in the basic blocks specified by BLOCKS. */
1317 df_refs_record (df
, blocks
)
1323 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
1325 df_bb_refs_record (df
, bb
);
1329 /* Dataflow analysis routines. */
1332 /* Create reg-def chains for basic block BB. These are a list of
1333 definitions for each register. */
1335 df_bb_reg_def_chain_create (df
, bb
)
1341 /* Perhaps the defs should be sorted using a depth first search
1342 of the CFG (or possibly a breadth first search). We currently
1343 scan the basic blocks in reverse order so that the first defs
1344 apprear at the start of the chain. */
1346 for (insn
= bb
->end
; insn
&& insn
!= PREV_INSN (bb
->head
);
1347 insn
= PREV_INSN (insn
))
1349 struct df_link
*link
;
1350 unsigned int uid
= INSN_UID (insn
);
1352 if (! INSN_P (insn
))
1355 for (link
= df
->insns
[uid
].defs
; link
; link
= link
->next
)
1357 struct ref
*def
= link
->ref
;
1358 unsigned int dregno
= DF_REF_REGNO (def
);
1360 df
->regs
[dregno
].defs
1361 = df_link_create (def
, df
->regs
[dregno
].defs
);
1367 /* Create reg-def chains for each basic block within BLOCKS. These
1368 are a list of definitions for each register. */
1370 df_reg_def_chain_create (df
, blocks
)
1376 FOR_EACH_BB_IN_BITMAP
/*_REV*/ (blocks
, 0, bb
,
1378 df_bb_reg_def_chain_create (df
, bb
);
1383 /* Create reg-use chains for basic block BB. These are a list of uses
1384 for each register. */
1386 df_bb_reg_use_chain_create (df
, bb
)
1392 /* Scan in forward order so that the last uses appear at the
1393 start of the chain. */
1395 for (insn
= bb
->head
; insn
&& insn
!= NEXT_INSN (bb
->end
);
1396 insn
= NEXT_INSN (insn
))
1398 struct df_link
*link
;
1399 unsigned int uid
= INSN_UID (insn
);
1401 if (! INSN_P (insn
))
1404 for (link
= df
->insns
[uid
].uses
; link
; link
= link
->next
)
1406 struct ref
*use
= link
->ref
;
1407 unsigned int uregno
= DF_REF_REGNO (use
);
1409 df
->regs
[uregno
].uses
1410 = df_link_create (use
, df
->regs
[uregno
].uses
);
1416 /* Create reg-use chains for each basic block within BLOCKS. These
1417 are a list of uses for each register. */
1419 df_reg_use_chain_create (df
, blocks
)
1425 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
1427 df_bb_reg_use_chain_create (df
, bb
);
1432 /* Create def-use chains from reaching use bitmaps for basic block BB. */
1434 df_bb_du_chain_create (df
, bb
, ru
)
1439 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
1442 bitmap_copy (ru
, bb_info
->ru_out
);
1444 /* For each def in BB create a linked list (chain) of uses
1445 reached from the def. */
1446 for (insn
= bb
->end
; insn
&& insn
!= PREV_INSN (bb
->head
);
1447 insn
= PREV_INSN (insn
))
1449 struct df_link
*def_link
;
1450 struct df_link
*use_link
;
1451 unsigned int uid
= INSN_UID (insn
);
1453 if (! INSN_P (insn
))
1456 /* For each def in insn... */
1457 for (def_link
= df
->insns
[uid
].defs
; def_link
; def_link
= def_link
->next
)
1459 struct ref
*def
= def_link
->ref
;
1460 unsigned int dregno
= DF_REF_REGNO (def
);
1462 DF_REF_CHAIN (def
) = 0;
1464 /* While the reg-use chains are not essential, it
1465 is _much_ faster to search these short lists rather
1466 than all the reaching uses, especially for large functions. */
1467 for (use_link
= df
->regs
[dregno
].uses
; use_link
;
1468 use_link
= use_link
->next
)
1470 struct ref
*use
= use_link
->ref
;
1472 if (bitmap_bit_p (ru
, DF_REF_ID (use
)))
1475 = df_link_create (use
, DF_REF_CHAIN (def
));
1477 bitmap_clear_bit (ru
, DF_REF_ID (use
));
1482 /* For each use in insn... */
1483 for (use_link
= df
->insns
[uid
].uses
; use_link
; use_link
= use_link
->next
)
1485 struct ref
*use
= use_link
->ref
;
1486 bitmap_set_bit (ru
, DF_REF_ID (use
));
1492 /* Create def-use chains from reaching use bitmaps for basic blocks
1495 df_du_chain_create (df
, blocks
)
1502 ru
= BITMAP_XMALLOC ();
1504 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
1506 df_bb_du_chain_create (df
, bb
, ru
);
1513 /* Create use-def chains from reaching def bitmaps for basic block BB. */
1515 df_bb_ud_chain_create (df
, bb
)
1519 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
1520 struct ref
**reg_def_last
= df
->reg_def_last
;
1523 memset (reg_def_last
, 0, df
->n_regs
* sizeof (struct ref
*));
1525 /* For each use in BB create a linked list (chain) of defs
1526 that reach the use. */
1527 for (insn
= bb
->head
; insn
&& insn
!= NEXT_INSN (bb
->end
);
1528 insn
= NEXT_INSN (insn
))
1530 unsigned int uid
= INSN_UID (insn
);
1531 struct df_link
*use_link
;
1532 struct df_link
*def_link
;
1534 if (! INSN_P (insn
))
1537 /* For each use in insn... */
1538 for (use_link
= df
->insns
[uid
].uses
; use_link
; use_link
= use_link
->next
)
1540 struct ref
*use
= use_link
->ref
;
1541 unsigned int regno
= DF_REF_REGNO (use
);
1543 DF_REF_CHAIN (use
) = 0;
1545 /* Has regno been defined in this BB yet? If so, use
1546 the last def as the single entry for the use-def
1547 chain for this use. Otherwise, we need to add all
1548 the defs using this regno that reach the start of
1550 if (reg_def_last
[regno
])
1553 = df_link_create (reg_def_last
[regno
], 0);
1557 /* While the reg-def chains are not essential, it is
1558 _much_ faster to search these short lists rather than
1559 all the reaching defs, especially for large
1561 for (def_link
= df
->regs
[regno
].defs
; def_link
;
1562 def_link
= def_link
->next
)
1564 struct ref
*def
= def_link
->ref
;
1566 if (bitmap_bit_p (bb_info
->rd_in
, DF_REF_ID (def
)))
1569 = df_link_create (def
, DF_REF_CHAIN (use
));
1576 /* For each def in insn...record the last def of each reg. */
1577 for (def_link
= df
->insns
[uid
].defs
; def_link
; def_link
= def_link
->next
)
1579 struct ref
*def
= def_link
->ref
;
1580 int dregno
= DF_REF_REGNO (def
);
1582 reg_def_last
[dregno
] = def
;
1588 /* Create use-def chains from reaching def bitmaps for basic blocks
1591 df_ud_chain_create (df
, blocks
)
1597 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
1599 df_bb_ud_chain_create (df
, bb
);
1604 /* Use reverse completion order, and the worklist, to figure out what block
1608 df_visit_next_rc (df
, blocks
)
1609 struct df
*df ATTRIBUTE_UNUSED
;
1613 for (i
= 0; i
< n_basic_blocks
; i
++)
1614 if (TEST_BIT (blocks
, df
->rc_order
[i
]))
1615 return df
->rc_order
[i
];
1616 return sbitmap_first_set_bit (blocks
);
1619 /* Use reverse topsort order, and the worklist, to figure out what block
1623 df_visit_next_rts (df
, blocks
)
1624 struct df
*df ATTRIBUTE_UNUSED
;
1628 for (i
= 0; i
< n_basic_blocks
; i
++)
1629 if (TEST_BIT (blocks
, df
->rts_order
[i
]))
1630 return df
->rts_order
[i
];
1631 return sbitmap_first_set_bit (blocks
);
1635 /* Calculate reaching defs for each basic block in BLOCKS, i.e., the
1636 defs that are live at the start of a basic block. */
1638 df_rd_global_compute (df
, blocks
)
1639 struct df
*df ATTRIBUTE_UNUSED
;
1646 worklist
= sbitmap_alloc (n_basic_blocks
);
1647 sbitmap_zero (worklist
);
1649 /* Copy the blocklist to the worklist */
1650 EXECUTE_IF_SET_IN_BITMAP (blocks
, 0, i
,
1652 SET_BIT (worklist
, i
);
1655 /* We assume that only the basic blocks in WORKLIST have been
1657 FOR_EACH_BB_IN_SBITMAP (worklist
, 0, bb
,
1659 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
1661 bitmap_copy (bb_info
->rd_out
, bb_info
->rd_gen
);
1664 while ((i
= df_visit_next_rc (df
, worklist
)) >= 0)
1666 struct bb_info
*bb_info
;
1670 /* Remove this block from the worklist. */
1671 RESET_BIT (worklist
, i
);
1674 bb
= BASIC_BLOCK (i
);
1675 bb_info
= DF_BB_INFO (df
, bb
);
1677 /* Calculate union of predecessor outs. */
1678 bitmap_zero (bb_info
->rd_in
);
1679 for (e
= bb
->pred
; e
!= 0; e
= e
->pred_next
)
1681 struct bb_info
*pred_refs
= DF_BB_INFO (df
, e
->src
);
1683 if (e
->src
== ENTRY_BLOCK_PTR
)
1686 bitmap_a_or_b (bb_info
->rd_in
, bb_info
->rd_in
,
1690 /* RD_OUT is the set of defs that are live at the end of the
1691 BB. These are the defs that are either generated by defs
1692 (RD_GEN) within the BB or are live at the start (RD_IN)
1693 and are not killed by other defs (RD_KILL). */
1694 changed
= bitmap_union_of_diff (bb_info
->rd_out
, bb_info
->rd_gen
,
1695 bb_info
->rd_in
, bb_info
->rd_kill
);
1699 /* Add each of this block's successors to the worklist. */
1700 for (e
= bb
->succ
; e
!= 0; e
= e
->succ_next
)
1702 if (e
->dest
== EXIT_BLOCK_PTR
)
1705 SET_BIT (worklist
, e
->dest
->index
);
1709 sbitmap_free (worklist
);
1713 /* Calculate reaching uses for each basic block within BLOCKS, i.e.,
1714 the uses that are live at the start of a basic block. */
1716 df_ru_global_compute (df
, blocks
)
1717 struct df
*df ATTRIBUTE_UNUSED
;
1724 worklist
= sbitmap_alloc (n_basic_blocks
);
1725 sbitmap_zero (worklist
);
1727 EXECUTE_IF_SET_IN_BITMAP (blocks
, 0, i
,
1729 SET_BIT (worklist
, i
);
1732 /* We assume that only the basic blocks in WORKLIST have been
1734 FOR_EACH_BB_IN_SBITMAP (worklist
, 0, bb
,
1736 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
1738 bitmap_copy (bb_info
->ru_in
, bb_info
->ru_gen
);
1742 while ((i
= df_visit_next_rts (df
, worklist
)) >= 0)
1744 struct bb_info
*bb_info
;
1748 /* Remove this block from the worklist. */
1749 RESET_BIT (worklist
, i
);
1751 bb
= BASIC_BLOCK (i
);
1752 bb_info
= DF_BB_INFO (df
, bb
);
1754 /* Calculate union of successor ins. */
1755 bitmap_zero (bb_info
->ru_out
);
1756 for (e
= bb
->succ
; e
!= 0; e
= e
->succ_next
)
1758 struct bb_info
*succ_refs
= DF_BB_INFO (df
, e
->dest
);
1760 if (e
->dest
== EXIT_BLOCK_PTR
)
1763 bitmap_a_or_b (bb_info
->ru_out
, bb_info
->ru_out
,
1767 /* RU_IN is the set of uses that are live at the start of the
1768 BB. These are the uses that are either generated within the
1769 BB (RU_GEN) or are live at the end (RU_OUT) and are not uses
1770 killed by defs within the BB (RU_KILL). */
1771 changed
= bitmap_union_of_diff (bb_info
->ru_in
, bb_info
->ru_gen
,
1772 bb_info
->ru_out
, bb_info
->ru_kill
);
1776 /* Add each of this block's predecessors to the worklist. */
1777 for (e
= bb
->pred
; e
!= 0; e
= e
->pred_next
)
1779 if (e
->src
== ENTRY_BLOCK_PTR
)
1782 SET_BIT (worklist
, e
->src
->index
);
1787 sbitmap_free (worklist
);
1791 /* Calculate live registers for each basic block within BLOCKS. */
1793 df_lr_global_compute (df
, blocks
)
1794 struct df
*df ATTRIBUTE_UNUSED
;
1801 worklist
= BITMAP_XMALLOC ();
1802 bitmap_copy (worklist
, blocks
);
1804 /* We assume that only the basic blocks in WORKLIST have been
1806 FOR_EACH_BB_IN_BITMAP (worklist
, 0, bb
,
1808 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
1810 bitmap_copy (bb_info
->lr_in
, bb_info
->lr_use
);
1813 while ((i
= bitmap_last_set_bit (worklist
)) >= 0)
1815 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
1819 /* Remove this block from the worklist. */
1820 bitmap_clear_bit (worklist
, i
);
1822 bb
= BASIC_BLOCK (i
);
1823 bb_info
= DF_BB_INFO (df
, bb
);
1825 /* Calculate union of successor ins. */
1826 bitmap_zero (bb_info
->lr_out
);
1827 for (e
= bb
->succ
; e
!= 0; e
= e
->succ_next
)
1829 struct bb_info
*succ_refs
= DF_BB_INFO (df
, e
->dest
);
1831 if (e
->dest
== EXIT_BLOCK_PTR
)
1834 bitmap_a_or_b (bb_info
->lr_out
, bb_info
->lr_out
,
1838 /* LR_IN is the set of uses that are live at the start of the
1839 BB. These are the uses that are either generated by uses
1840 (LR_USE) within the BB or are live at the end (LR_OUT)
1841 and are not killed by other uses (LR_DEF). */
1842 changed
= bitmap_union_of_diff (bb_info
->lr_in
, bb_info
->lr_use
,
1843 bb_info
->lr_out
, bb_info
->lr_def
);
1847 /* Add each of this block's predecessors to the worklist. */
1848 for (e
= bb
->pred
; e
!= 0; e
= e
->pred_next
)
1850 if (e
->src
== ENTRY_BLOCK_PTR
)
1853 bitmap_set_bit (worklist
, e
->src
->index
);
1857 BITMAP_XFREE (worklist
);
1861 /* Compute local reaching def info for basic block BB. */
1863 df_bb_rd_local_compute (df
, bb
)
1867 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
1870 for (insn
= bb
->head
; insn
&& insn
!= NEXT_INSN (bb
->end
);
1871 insn
= NEXT_INSN (insn
))
1873 unsigned int uid
= INSN_UID (insn
);
1874 struct df_link
*def_link
;
1876 if (! INSN_P (insn
))
1879 for (def_link
= df
->insns
[uid
].defs
; def_link
; def_link
= def_link
->next
)
1881 struct ref
*def
= def_link
->ref
;
1882 unsigned int regno
= DF_REF_REGNO (def
);
1883 struct df_link
*def2_link
;
1885 for (def2_link
= df
->regs
[regno
].defs
; def2_link
;
1886 def2_link
= def2_link
->next
)
1888 struct ref
*def2
= def2_link
->ref
;
1890 /* Add all defs of this reg to the set of kills. This
1891 is greedy since many of these defs will not actually
1892 be killed by this BB but it keeps things a lot
1894 bitmap_set_bit (bb_info
->rd_kill
, DF_REF_ID (def2
));
1896 /* Zap from the set of gens for this BB. */
1897 bitmap_clear_bit (bb_info
->rd_gen
, DF_REF_ID (def2
));
1900 bitmap_set_bit (bb_info
->rd_gen
, DF_REF_ID (def
));
1904 bb_info
->rd_valid
= 1;
1908 /* Compute local reaching def info for each basic block within BLOCKS. */
1910 df_rd_local_compute (df
, blocks
)
1916 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
1918 df_bb_rd_local_compute (df
, bb
);
1923 /* Compute local reaching use (upward exposed use) info for basic
1926 df_bb_ru_local_compute (df
, bb
)
1930 /* This is much more tricky than computing reaching defs. With
1931 reaching defs, defs get killed by other defs. With upwards
1932 exposed uses, these get killed by defs with the same regno. */
1934 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
1937 for (insn
= bb
->end
; insn
&& insn
!= PREV_INSN (bb
->head
);
1938 insn
= PREV_INSN (insn
))
1940 unsigned int uid
= INSN_UID (insn
);
1941 struct df_link
*def_link
;
1942 struct df_link
*use_link
;
1944 if (! INSN_P (insn
))
1947 for (def_link
= df
->insns
[uid
].defs
; def_link
; def_link
= def_link
->next
)
1949 struct ref
*def
= def_link
->ref
;
1950 unsigned int dregno
= DF_REF_REGNO (def
);
1952 for (use_link
= df
->regs
[dregno
].uses
; use_link
;
1953 use_link
= use_link
->next
)
1955 struct ref
*use
= use_link
->ref
;
1957 /* Add all uses of this reg to the set of kills. This
1958 is greedy since many of these uses will not actually
1959 be killed by this BB but it keeps things a lot
1961 bitmap_set_bit (bb_info
->ru_kill
, DF_REF_ID (use
));
1963 /* Zap from the set of gens for this BB. */
1964 bitmap_clear_bit (bb_info
->ru_gen
, DF_REF_ID (use
));
1968 for (use_link
= df
->insns
[uid
].uses
; use_link
; use_link
= use_link
->next
)
1970 struct ref
*use
= use_link
->ref
;
1971 /* Add use to set of gens in this BB. */
1972 bitmap_set_bit (bb_info
->ru_gen
, DF_REF_ID (use
));
1975 bb_info
->ru_valid
= 1;
1979 /* Compute local reaching use (upward exposed use) info for each basic
1980 block within BLOCKS. */
1982 df_ru_local_compute (df
, blocks
)
1988 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
1990 df_bb_ru_local_compute (df
, bb
);
1995 /* Compute local live variable info for basic block BB. */
1997 df_bb_lr_local_compute (df
, bb
)
2001 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
2004 for (insn
= bb
->end
; insn
&& insn
!= PREV_INSN (bb
->head
);
2005 insn
= PREV_INSN (insn
))
2007 unsigned int uid
= INSN_UID (insn
);
2008 struct df_link
*link
;
2010 if (! INSN_P (insn
))
2013 for (link
= df
->insns
[uid
].defs
; link
; link
= link
->next
)
2015 struct ref
*def
= link
->ref
;
2016 unsigned int dregno
= DF_REF_REGNO (def
);
2018 /* Add def to set of defs in this BB. */
2019 bitmap_set_bit (bb_info
->lr_def
, dregno
);
2021 bitmap_clear_bit (bb_info
->lr_use
, dregno
);
2024 for (link
= df
->insns
[uid
].uses
; link
; link
= link
->next
)
2026 struct ref
*use
= link
->ref
;
2027 /* Add use to set of uses in this BB. */
2028 bitmap_set_bit (bb_info
->lr_use
, DF_REF_REGNO (use
));
2031 bb_info
->lr_valid
= 1;
2035 /* Compute local live variable info for each basic block within BLOCKS. */
2037 df_lr_local_compute (df
, blocks
)
2043 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
2045 df_bb_lr_local_compute (df
, bb
);
2050 /* Compute register info: lifetime, bb, and number of defs and uses
2051 for basic block BB. */
2053 df_bb_reg_info_compute (df
, bb
, live
)
2058 struct reg_info
*reg_info
= df
->regs
;
2059 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
2062 bitmap_copy (live
, bb_info
->lr_out
);
2064 for (insn
= bb
->end
; insn
&& insn
!= PREV_INSN (bb
->head
);
2065 insn
= PREV_INSN (insn
))
2067 unsigned int uid
= INSN_UID (insn
);
2069 struct df_link
*link
;
2071 if (! INSN_P (insn
))
2074 for (link
= df
->insns
[uid
].defs
; link
; link
= link
->next
)
2076 struct ref
*def
= link
->ref
;
2077 unsigned int dregno
= DF_REF_REGNO (def
);
2079 /* Kill this register. */
2080 bitmap_clear_bit (live
, dregno
);
2081 reg_info
[dregno
].n_defs
++;
2084 for (link
= df
->insns
[uid
].uses
; link
; link
= link
->next
)
2086 struct ref
*use
= link
->ref
;
2087 unsigned int uregno
= DF_REF_REGNO (use
);
2089 /* This register is now live. */
2090 bitmap_set_bit (live
, uregno
);
2091 reg_info
[uregno
].n_uses
++;
2094 /* Increment lifetimes of all live registers. */
2095 EXECUTE_IF_SET_IN_BITMAP (live
, 0, regno
,
2097 reg_info
[regno
].lifetime
++;
2103 /* Compute register info: lifetime, bb, and number of defs and uses. */
2105 df_reg_info_compute (df
, blocks
)
2112 live
= BITMAP_XMALLOC ();
2114 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
2116 df_bb_reg_info_compute (df
, bb
, live
);
2119 BITMAP_XFREE (live
);
2123 /* Assign LUIDs for BB. */
2125 df_bb_luids_set (df
, bb
)
2132 /* The LUIDs are monotonically increasing for each basic block. */
2134 for (insn
= bb
->head
; ; insn
= NEXT_INSN (insn
))
2137 DF_INSN_LUID (df
, insn
) = luid
++;
2138 DF_INSN_LUID (df
, insn
) = luid
;
2140 if (insn
== bb
->end
)
2147 /* Assign LUIDs for each basic block within BLOCKS. */
2149 df_luids_set (df
, blocks
)
2156 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
2158 total
+= df_bb_luids_set (df
, bb
);
2164 /* Perform dataflow analysis using existing DF structure for blocks
2165 within BLOCKS. If BLOCKS is zero, use all basic blocks in the CFG. */
2167 df_analyse_1 (df
, blocks
, flags
, update
)
2178 if (flags
& DF_UD_CHAIN
)
2179 aflags
|= DF_RD
| DF_RD_CHAIN
;
2181 if (flags
& DF_DU_CHAIN
)
2185 aflags
|= DF_RU_CHAIN
;
2187 if (flags
& DF_REG_INFO
)
2191 blocks
= df
->all_blocks
;
2196 df_refs_update (df
);
2197 /* More fine grained incremental dataflow analysis would be
2198 nice. For now recompute the whole shebang for the
2201 df_refs_unlink (df
, blocks
);
2203 /* All the def-use, use-def chains can be potentially
2204 modified by changes in one block. The size of the
2205 bitmaps can also change. */
2209 /* Scan the function for all register defs and uses. */
2211 df_refs_record (df
, blocks
);
2213 /* Link all the new defs and uses to the insns. */
2214 df_refs_process (df
);
2217 /* Allocate the bitmaps now the total number of defs and uses are
2218 known. If the number of defs or uses have changed, then
2219 these bitmaps need to be reallocated. */
2220 df_bitmaps_alloc (df
, aflags
);
2222 /* Set the LUIDs for each specified basic block. */
2223 df_luids_set (df
, blocks
);
2225 /* Recreate reg-def and reg-use chains from scratch so that first
2226 def is at the head of the reg-def chain and the last use is at
2227 the head of the reg-use chain. This is only important for
2228 regs local to a basic block as it speeds up searching. */
2229 if (aflags
& DF_RD_CHAIN
)
2231 df_reg_def_chain_create (df
, blocks
);
2234 if (aflags
& DF_RU_CHAIN
)
2236 df_reg_use_chain_create (df
, blocks
);
2239 df
->dfs_order
= xmalloc (sizeof(int) * n_basic_blocks
);
2240 df
->rc_order
= xmalloc (sizeof(int) * n_basic_blocks
);
2241 df
->rts_order
= xmalloc (sizeof(int) * n_basic_blocks
);
2243 flow_depth_first_order_compute (df
->dfs_order
, df
->rc_order
);
2244 flow_reverse_top_sort_order_compute (df
->rts_order
);
2247 /* Compute the sets of gens and kills for the defs of each bb. */
2248 df_rd_local_compute (df
, df
->flags
& DF_RD
? blocks
: df
->all_blocks
);
2250 /* Compute the global reaching definitions. */
2251 df_rd_global_compute (df
, df
->all_blocks
);
2254 if (aflags
& DF_UD_CHAIN
)
2256 /* Create use-def chains. */
2257 df_ud_chain_create (df
, df
->all_blocks
);
2259 if (! (flags
& DF_RD
))
2265 /* Compute the sets of gens and kills for the upwards exposed
2267 df_ru_local_compute (df
, df
->flags
& DF_RU
? blocks
: df
->all_blocks
);
2269 /* Compute the global reaching uses. */
2270 df_ru_global_compute (df
, df
->all_blocks
);
2273 if (aflags
& DF_DU_CHAIN
)
2275 /* Create def-use chains. */
2276 df_du_chain_create (df
, df
->all_blocks
);
2278 if (! (flags
& DF_RU
))
2282 /* Free up bitmaps that are no longer required. */
2284 df_bitmaps_free (df
, dflags
);
2288 /* Compute the sets of defs and uses of live variables. */
2289 df_lr_local_compute (df
, df
->flags
& DF_LR
? blocks
: df
->all_blocks
);
2291 /* Compute the global live variables. */
2292 df_lr_global_compute (df
, df
->all_blocks
);
2295 if (aflags
& DF_REG_INFO
)
2297 df_reg_info_compute (df
, df
->all_blocks
);
2299 free (df
->dfs_order
);
2300 free (df
->rc_order
);
2301 free (df
->rts_order
);
2305 /* Initialise dataflow analysis. */
2311 df
= xcalloc (1, sizeof (struct df
));
2313 /* Squirrel away a global for debugging. */
2320 /* Start queuing refs. */
2325 df
->def_id_save
= df
->def_id
;
2326 df
->use_id_save
= df
->use_id
;
2327 /* ???? Perhaps we should save current obstack state so that we can
2333 /* Process queued refs. */
2335 df_refs_process (df
)
2340 /* Build new insn-def chains. */
2341 for (i
= df
->def_id_save
; i
!= df
->def_id
; i
++)
2343 struct ref
*def
= df
->defs
[i
];
2344 unsigned int uid
= DF_REF_INSN_UID (def
);
2346 /* Add def to head of def list for INSN. */
2348 = df_link_create (def
, df
->insns
[uid
].defs
);
2351 /* Build new insn-use chains. */
2352 for (i
= df
->use_id_save
; i
!= df
->use_id
; i
++)
2354 struct ref
*use
= df
->uses
[i
];
2355 unsigned int uid
= DF_REF_INSN_UID (use
);
2357 /* Add use to head of use list for INSN. */
2359 = df_link_create (use
, df
->insns
[uid
].uses
);
2365 /* Update refs for basic block BB. */
2367 df_bb_refs_update (df
, bb
)
2374 /* While we have to scan the chain of insns for this BB, we don't
2375 need to allocate and queue a long chain of BB/INSN pairs. Using
2376 a bitmap for insns_modified saves memory and avoids queuing
2379 for (insn
= bb
->head
; ; insn
= NEXT_INSN (insn
))
2383 uid
= INSN_UID (insn
);
2385 if (bitmap_bit_p (df
->insns_modified
, uid
))
2387 /* Delete any allocated refs of this insn. MPH, FIXME. */
2388 df_insn_refs_unlink (df
, bb
, insn
);
2390 /* Scan the insn for refs. */
2391 df_insn_refs_record (df
, bb
, insn
);
2394 bitmap_clear_bit (df
->insns_modified
, uid
);
2397 if (insn
== bb
->end
)
2404 /* Process all the modified/deleted insns that were queued. */
2412 if ((unsigned int)max_reg_num () >= df
->reg_size
)
2413 df_reg_table_realloc (df
, 0);
2417 FOR_EACH_BB_IN_BITMAP (df
->bbs_modified
, 0, bb
,
2419 count
+= df_bb_refs_update (df
, bb
);
2422 df_refs_process (df
);
2427 /* Return non-zero if any of the requested blocks in the bitmap
2428 BLOCKS have been modified. */
2430 df_modified_p (df
, blocks
)
2437 for (j
= 0; j
< df
->n_bbs
; j
++)
2438 if (bitmap_bit_p (df
->bbs_modified
, j
)
2439 && (! blocks
|| (blocks
== (bitmap
) -1) || bitmap_bit_p (blocks
, j
)))
2449 /* Analyse dataflow info for the basic blocks specified by the bitmap
2450 BLOCKS, or for the whole CFG if BLOCKS is zero, or just for the
2451 modified blocks if BLOCKS is -1. */
2453 df_analyse (df
, blocks
, flags
)
2460 /* We could deal with additional basic blocks being created by
2461 rescanning everything again. */
2462 if (df
->n_bbs
&& df
->n_bbs
!= (unsigned int)n_basic_blocks
)
2465 update
= df_modified_p (df
, blocks
);
2466 if (update
|| (flags
!= df
->flags
))
2472 /* Recompute everything from scratch. */
2475 /* Allocate and initialise data structures. */
2476 df_alloc (df
, max_reg_num ());
2477 df_analyse_1 (df
, 0, flags
, 0);
2482 if (blocks
== (bitmap
) -1)
2483 blocks
= df
->bbs_modified
;
2488 df_analyse_1 (df
, blocks
, flags
, 1);
2489 bitmap_zero (df
->bbs_modified
);
2496 /* Free all the dataflow info and the DF structure. */
2506 /* Unlink INSN from its reference information. */
2508 df_insn_refs_unlink (df
, bb
, insn
)
2510 basic_block bb ATTRIBUTE_UNUSED
;
2513 struct df_link
*link
;
2516 uid
= INSN_UID (insn
);
2518 /* Unlink all refs defined by this insn. */
2519 for (link
= df
->insns
[uid
].defs
; link
; link
= link
->next
)
2520 df_def_unlink (df
, link
->ref
);
2522 /* Unlink all refs used by this insn. */
2523 for (link
= df
->insns
[uid
].uses
; link
; link
= link
->next
)
2524 df_use_unlink (df
, link
->ref
);
2526 df
->insns
[uid
].defs
= 0;
2527 df
->insns
[uid
].uses
= 0;
2532 /* Unlink all the insns within BB from their reference information. */
2534 df_bb_refs_unlink (df
, bb
)
2540 /* Scan the block an insn at a time from beginning to end. */
2541 for (insn
= bb
->head
; ; insn
= NEXT_INSN (insn
))
2545 /* Unlink refs for INSN. */
2546 df_insn_refs_unlink (df
, bb
, insn
);
2548 if (insn
== bb
->end
)
2554 /* Unlink all the refs in the basic blocks specified by BLOCKS.
2555 Not currently used. */
2557 df_refs_unlink (df
, blocks
)
2565 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
2567 df_bb_refs_unlink (df
, bb
);
2574 df_bb_refs_unlink (df
, bb
);
2580 /* Functions to modify insns. */
2583 /* Delete INSN and all its reference information. */
2585 df_insn_delete (df
, bb
, insn
)
2587 basic_block bb ATTRIBUTE_UNUSED
;
2590 /* If the insn is a jump, we should perhaps call delete_insn to
2591 handle the JUMP_LABEL? */
2593 /* We should not be deleting the NOTE_INSN_BASIC_BLOCK or label. */
2594 if (insn
== bb
->head
)
2596 if (insn
== bb
->end
)
2597 bb
->end
= PREV_INSN (insn
);
2599 /* Delete the insn. */
2600 PUT_CODE (insn
, NOTE
);
2601 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED
;
2602 NOTE_SOURCE_FILE (insn
) = 0;
2604 df_insn_modify (df
, bb
, insn
);
2606 return NEXT_INSN (insn
);
2610 /* Mark that INSN within BB may have changed (created/modified/deleted).
2611 This may be called multiple times for the same insn. There is no
2612 harm calling this function if the insn wasn't changed; it will just
2613 slow down the rescanning of refs. */
2615 df_insn_modify (df
, bb
, insn
)
2622 uid
= INSN_UID (insn
);
2624 if (uid
>= df
->insn_size
)
2625 df_insn_table_realloc (df
, 0);
2627 bitmap_set_bit (df
->bbs_modified
, bb
->index
);
2628 bitmap_set_bit (df
->insns_modified
, uid
);
2631 /* For incremental updating on the fly, perhaps we could make a copy
2632 of all the refs of the original insn and turn them into
2633 anti-refs. When df_refs_update finds these anti-refs, it annihilates
2634 the original refs. If validate_change fails then these anti-refs
2635 will just get ignored. */
2641 typedef struct replace_args
2650 /* Replace mem pointed to by PX with its associated pseudo register.
2651 DATA is actually a pointer to a structure describing the
2652 instruction currently being scanned and the MEM we are currently
2655 df_rtx_mem_replace (px
, data
)
2659 replace_args
*args
= (replace_args
*) data
;
2662 if (mem
== NULL_RTX
)
2665 switch (GET_CODE (mem
))
2671 /* We're not interested in the MEM associated with a
2672 CONST_DOUBLE, so there's no need to traverse into one. */
2676 /* This is not a MEM. */
2680 if (!rtx_equal_p (args
->match
, mem
))
2681 /* This is not the MEM we are currently replacing. */
2684 /* Actually replace the MEM. */
2685 validate_change (args
->insn
, px
, args
->replacement
, 1);
2693 df_insn_mem_replace (df
, bb
, insn
, mem
, reg
)
2704 args
.replacement
= reg
;
2707 /* Seach and replace all matching mems within insn. */
2708 for_each_rtx (&insn
, df_rtx_mem_replace
, &args
);
2711 df_insn_modify (df
, bb
, insn
);
2713 /* ???? FIXME. We may have a new def or one or more new uses of REG
2714 in INSN. REG should be a new pseudo so it won't affect the
2715 dataflow information that we currently have. We should add
2716 the new uses and defs to INSN and then recreate the chains
2717 when df_analyse is called. */
2718 return args
.modified
;
2722 /* Replace one register with another. Called through for_each_rtx; PX
2723 points to the rtx being scanned. DATA is actually a pointer to a
2724 structure of arguments. */
2726 df_rtx_reg_replace (px
, data
)
2731 replace_args
*args
= (replace_args
*) data
;
2736 if (x
== args
->match
)
2738 validate_change (args
->insn
, px
, args
->replacement
, 1);
2746 /* Replace the reg within every ref on CHAIN that is within the set
2747 BLOCKS of basic blocks with NEWREG. Also update the regs within
2750 df_refs_reg_replace (df
, blocks
, chain
, oldreg
, newreg
)
2753 struct df_link
*chain
;
2757 struct df_link
*link
;
2761 blocks
= df
->all_blocks
;
2763 args
.match
= oldreg
;
2764 args
.replacement
= newreg
;
2767 for (link
= chain
; link
; link
= link
->next
)
2769 struct ref
*ref
= link
->ref
;
2770 rtx insn
= DF_REF_INSN (ref
);
2772 if (! INSN_P (insn
))
2775 if (bitmap_bit_p (blocks
, DF_REF_BBNO (ref
)))
2777 df_ref_reg_replace (df
, ref
, oldreg
, newreg
);
2779 /* Replace occurrences of the reg within the REG_NOTES. */
2780 if ((! link
->next
|| DF_REF_INSN (ref
)
2781 != DF_REF_INSN (link
->next
->ref
))
2782 && REG_NOTES (insn
))
2785 for_each_rtx (®_NOTES (insn
), df_rtx_reg_replace
, &args
);
2790 /* Temporary check to ensure that we have a grip on which
2791 regs should be replaced. */
2798 /* Replace all occurrences of register OLDREG with register NEWREG in
2799 blocks defined by bitmap BLOCKS. This also replaces occurrences of
2800 OLDREG in the REG_NOTES but only for insns containing OLDREG. This
2801 routine expects the reg-use and reg-def chains to be valid. */
2803 df_reg_replace (df
, blocks
, oldreg
, newreg
)
2809 unsigned int oldregno
= REGNO (oldreg
);
2811 df_refs_reg_replace (df
, blocks
, df
->regs
[oldregno
].defs
, oldreg
, newreg
);
2812 df_refs_reg_replace (df
, blocks
, df
->regs
[oldregno
].uses
, oldreg
, newreg
);
2817 /* Try replacing the reg within REF with NEWREG. Do not modify
2818 def-use/use-def chains. */
2820 df_ref_reg_replace (df
, ref
, oldreg
, newreg
)
2826 /* Check that insn was deleted by being converted into a NOTE. If
2827 so ignore this insn. */
2828 if (! INSN_P (DF_REF_INSN (ref
)))
2831 if (oldreg
&& oldreg
!= DF_REF_REG (ref
))
2834 if (! validate_change (DF_REF_INSN (ref
), DF_REF_LOC (ref
), newreg
, 1))
2837 df_insn_modify (df
, DF_REF_BB (ref
), DF_REF_INSN (ref
));
2843 df_bb_def_use_swap (df
, bb
, def_insn
, use_insn
, regno
)
2854 struct df_link
*link
;
2856 def
= df_bb_insn_regno_first_def_find (df
, bb
, def_insn
, regno
);
2860 use
= df_bb_insn_regno_last_use_find (df
, bb
, use_insn
, regno
);
2864 /* The USE no longer exists. */
2865 use_uid
= INSN_UID (use_insn
);
2866 df_use_unlink (df
, use
);
2867 df_ref_unlink (&df
->insns
[use_uid
].uses
, use
);
2869 /* The DEF requires shifting so remove it from DEF_INSN
2870 and add it to USE_INSN by reusing LINK. */
2871 def_uid
= INSN_UID (def_insn
);
2872 link
= df_ref_unlink (&df
->insns
[def_uid
].defs
, def
);
2874 link
->next
= df
->insns
[use_uid
].defs
;
2875 df
->insns
[use_uid
].defs
= link
;
2878 link
= df_ref_unlink (&df
->regs
[regno
].defs
, def
);
2880 link
->next
= df
->regs
[regno
].defs
;
2881 df
->insns
[regno
].defs
= link
;
2884 DF_REF_INSN (def
) = use_insn
;
2889 /* Record df between FIRST_INSN and LAST_INSN inclusive. All new
2890 insns must be processed by this routine. */
2892 df_insns_modify (df
, bb
, first_insn
, last_insn
)
2900 for (insn
= first_insn
; ; insn
= NEXT_INSN (insn
))
2904 /* A non-const call should not have slipped through the net. If
2905 it does, we need to create a new basic block. Ouch. The
2906 same applies for a label. */
2907 if ((GET_CODE (insn
) == CALL_INSN
2908 && ! CONST_OR_PURE_CALL_P (insn
))
2909 || GET_CODE (insn
) == CODE_LABEL
)
2912 uid
= INSN_UID (insn
);
2914 if (uid
>= df
->insn_size
)
2915 df_insn_table_realloc (df
, 0);
2917 df_insn_modify (df
, bb
, insn
);
2919 if (insn
== last_insn
)
2925 /* Emit PATTERN before INSN within BB. */
2927 df_pattern_emit_before (df
, pattern
, bb
, insn
)
2928 struct df
*df ATTRIBUTE_UNUSED
;
2934 rtx prev_insn
= PREV_INSN (insn
);
2936 /* We should not be inserting before the start of the block. */
2937 if (insn
== bb
->head
)
2939 ret_insn
= emit_insn_before (pattern
, insn
);
2940 if (ret_insn
== insn
)
2943 df_insns_modify (df
, bb
, NEXT_INSN (prev_insn
), ret_insn
);
2948 /* Emit PATTERN after INSN within BB. */
2950 df_pattern_emit_after (df
, pattern
, bb
, insn
)
2958 ret_insn
= emit_insn_after (pattern
, insn
);
2959 if (ret_insn
== insn
)
2962 df_insns_modify (df
, bb
, NEXT_INSN (insn
), ret_insn
);
2967 /* Emit jump PATTERN after INSN within BB. */
2969 df_jump_pattern_emit_after (df
, pattern
, bb
, insn
)
2977 ret_insn
= emit_jump_insn_after (pattern
, insn
);
2978 if (ret_insn
== insn
)
2981 df_insns_modify (df
, bb
, NEXT_INSN (insn
), ret_insn
);
2986 /* Move INSN within BB before BEFORE_INSN within BEFORE_BB.
2988 This function should only be used to move loop invariant insns
2989 out of a loop where it has been proven that the def-use info
2990 will still be valid. */
2992 df_insn_move_before (df
, bb
, insn
, before_bb
, before_insn
)
2996 basic_block before_bb
;
2999 struct df_link
*link
;
3003 return df_pattern_emit_before (df
, insn
, before_bb
, before_insn
);
3005 uid
= INSN_UID (insn
);
3007 /* Change bb for all df defined and used by this insn. */
3008 for (link
= df
->insns
[uid
].defs
; link
; link
= link
->next
)
3009 DF_REF_BB (link
->ref
) = before_bb
;
3010 for (link
= df
->insns
[uid
].uses
; link
; link
= link
->next
)
3011 DF_REF_BB (link
->ref
) = before_bb
;
3013 /* The lifetimes of the registers used in this insn will be reduced
3014 while the lifetimes of the registers defined in this insn
3015 are likely to be increased. */
3017 /* ???? Perhaps all the insns moved should be stored on a list
3018 which df_analyse removes when it recalculates data flow. */
3020 return emit_insn_before (insn
, before_insn
);
3023 /* Functions to query dataflow information. */
3027 df_insn_regno_def_p (df
, bb
, insn
, regno
)
3029 basic_block bb ATTRIBUTE_UNUSED
;
3034 struct df_link
*link
;
3036 uid
= INSN_UID (insn
);
3038 for (link
= df
->insns
[uid
].defs
; link
; link
= link
->next
)
3040 struct ref
*def
= link
->ref
;
3042 if (DF_REF_REGNO (def
) == regno
)
3051 df_def_dominates_all_uses_p (df
, def
)
3052 struct df
*df ATTRIBUTE_UNUSED
;
3055 struct df_link
*du_link
;
3057 /* Follow def-use chain to find all the uses of this def. */
3058 for (du_link
= DF_REF_CHAIN (def
); du_link
; du_link
= du_link
->next
)
3060 struct ref
*use
= du_link
->ref
;
3061 struct df_link
*ud_link
;
3063 /* Follow use-def chain to check all the defs for this use. */
3064 for (ud_link
= DF_REF_CHAIN (use
); ud_link
; ud_link
= ud_link
->next
)
3065 if (ud_link
->ref
!= def
)
3073 df_insn_dominates_all_uses_p (df
, bb
, insn
)
3075 basic_block bb ATTRIBUTE_UNUSED
;
3079 struct df_link
*link
;
3081 uid
= INSN_UID (insn
);
3083 for (link
= df
->insns
[uid
].defs
; link
; link
= link
->next
)
3085 struct ref
*def
= link
->ref
;
3087 if (! df_def_dominates_all_uses_p (df
, def
))
3095 /* Return non-zero if all DF dominates all the uses within the bitmap
3098 df_def_dominates_uses_p (df
, def
, blocks
)
3099 struct df
*df ATTRIBUTE_UNUSED
;
3103 struct df_link
*du_link
;
3105 /* Follow def-use chain to find all the uses of this def. */
3106 for (du_link
= DF_REF_CHAIN (def
); du_link
; du_link
= du_link
->next
)
3108 struct ref
*use
= du_link
->ref
;
3109 struct df_link
*ud_link
;
3111 /* Only worry about the uses within BLOCKS. For example,
3112 consider a register defined within a loop that is live at the
3114 if (bitmap_bit_p (blocks
, DF_REF_BBNO (use
)))
3116 /* Follow use-def chain to check all the defs for this use. */
3117 for (ud_link
= DF_REF_CHAIN (use
); ud_link
; ud_link
= ud_link
->next
)
3118 if (ud_link
->ref
!= def
)
3126 /* Return non-zero if all the defs of INSN within BB dominates
3127 all the corresponding uses. */
3129 df_insn_dominates_uses_p (df
, bb
, insn
, blocks
)
3131 basic_block bb ATTRIBUTE_UNUSED
;
3136 struct df_link
*link
;
3138 uid
= INSN_UID (insn
);
3140 for (link
= df
->insns
[uid
].defs
; link
; link
= link
->next
)
3142 struct ref
*def
= link
->ref
;
3144 /* Only consider the defs within BLOCKS. */
3145 if (bitmap_bit_p (blocks
, DF_REF_BBNO (def
))
3146 && ! df_def_dominates_uses_p (df
, def
, blocks
))
3153 /* Return the basic block that REG referenced in or NULL if referenced
3154 in multiple basic blocks. */
3156 df_regno_bb (df
, regno
)
3160 struct df_link
*defs
= df
->regs
[regno
].defs
;
3161 struct df_link
*uses
= df
->regs
[regno
].uses
;
3162 struct ref
*def
= defs
? defs
->ref
: 0;
3163 struct ref
*use
= uses
? uses
->ref
: 0;
3164 basic_block bb_def
= def
? DF_REF_BB (def
) : 0;
3165 basic_block bb_use
= use
? DF_REF_BB (use
) : 0;
3167 /* Compare blocks of first def and last use. ???? FIXME. What if
3168 the reg-def and reg-use lists are not correctly ordered. */
3169 return bb_def
== bb_use
? bb_def
: 0;
3173 /* Return non-zero if REG used in multiple basic blocks. */
3175 df_reg_global_p (df
, reg
)
3179 return df_regno_bb (df
, REGNO (reg
)) != 0;
3183 /* Return total lifetime (in insns) of REG. */
3185 df_reg_lifetime (df
, reg
)
3189 return df
->regs
[REGNO (reg
)].lifetime
;
3193 /* Return non-zero if REG live at start of BB. */
3195 df_bb_reg_live_start_p (df
, bb
, reg
)
3196 struct df
*df ATTRIBUTE_UNUSED
;
3200 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
3202 #ifdef ENABLE_CHECKING
3203 if (! bb_info
->lr_in
)
3207 return bitmap_bit_p (bb_info
->lr_in
, REGNO (reg
));
3211 /* Return non-zero if REG live at end of BB. */
3213 df_bb_reg_live_end_p (df
, bb
, reg
)
3214 struct df
*df ATTRIBUTE_UNUSED
;
3218 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
3220 #ifdef ENABLE_CHECKING
3221 if (! bb_info
->lr_in
)
3225 return bitmap_bit_p (bb_info
->lr_out
, REGNO (reg
));
3229 /* Return -1 if life of REG1 before life of REG2, 1 if life of REG1
3230 after life of REG2, or 0, if the lives overlap. */
3232 df_bb_regs_lives_compare (df
, bb
, reg1
, reg2
)
3238 unsigned int regno1
= REGNO (reg1
);
3239 unsigned int regno2
= REGNO (reg2
);
3246 /* The regs must be local to BB. */
3247 if (df_regno_bb (df
, regno1
) != bb
3248 || df_regno_bb (df
, regno2
) != bb
)
3251 def2
= df_bb_regno_first_def_find (df
, bb
, regno2
);
3252 use1
= df_bb_regno_last_use_find (df
, bb
, regno1
);
3254 if (DF_INSN_LUID (df
, DF_REF_INSN (def2
))
3255 > DF_INSN_LUID (df
, DF_REF_INSN (use1
)))
3258 def1
= df_bb_regno_first_def_find (df
, bb
, regno1
);
3259 use2
= df_bb_regno_last_use_find (df
, bb
, regno2
);
3261 if (DF_INSN_LUID (df
, DF_REF_INSN (def1
))
3262 > DF_INSN_LUID (df
, DF_REF_INSN (use2
)))
3269 /* Return last use of REGNO within BB. */
3271 df_bb_regno_last_use_find (df
, bb
, regno
)
3273 basic_block bb ATTRIBUTE_UNUSED
;
3276 struct df_link
*link
;
3278 /* This assumes that the reg-use list is ordered such that for any
3279 BB, the last use is found first. However, since the BBs are not
3280 ordered, the first use in the chain is not necessarily the last
3281 use in the function. */
3282 for (link
= df
->regs
[regno
].uses
; link
; link
= link
->next
)
3284 struct ref
*use
= link
->ref
;
3286 if (DF_REF_BB (use
) == bb
)
3293 /* Return first def of REGNO within BB. */
3295 df_bb_regno_first_def_find (df
, bb
, regno
)
3297 basic_block bb ATTRIBUTE_UNUSED
;
3300 struct df_link
*link
;
3302 /* This assumes that the reg-def list is ordered such that for any
3303 BB, the first def is found first. However, since the BBs are not
3304 ordered, the first def in the chain is not necessarily the first
3305 def in the function. */
3306 for (link
= df
->regs
[regno
].defs
; link
; link
= link
->next
)
3308 struct ref
*def
= link
->ref
;
3310 if (DF_REF_BB (def
) == bb
)
3317 /* Return first use of REGNO inside INSN within BB. */
3319 df_bb_insn_regno_last_use_find (df
, bb
, insn
, regno
)
3321 basic_block bb ATTRIBUTE_UNUSED
;
3326 struct df_link
*link
;
3328 uid
= INSN_UID (insn
);
3330 for (link
= df
->insns
[uid
].uses
; link
; link
= link
->next
)
3332 struct ref
*use
= link
->ref
;
3334 if (DF_REF_REGNO (use
) == regno
)
3342 /* Return first def of REGNO inside INSN within BB. */
3344 df_bb_insn_regno_first_def_find (df
, bb
, insn
, regno
)
3346 basic_block bb ATTRIBUTE_UNUSED
;
3351 struct df_link
*link
;
3353 uid
= INSN_UID (insn
);
3355 for (link
= df
->insns
[uid
].defs
; link
; link
= link
->next
)
3357 struct ref
*def
= link
->ref
;
3359 if (DF_REF_REGNO (def
) == regno
)
3367 /* Return insn using REG if the BB contains only a single
3368 use and def of REG. */
3370 df_bb_single_def_use_insn_find (df
, bb
, insn
, reg
)
3378 struct df_link
*du_link
;
3380 def
= df_bb_insn_regno_first_def_find (df
, bb
, insn
, REGNO (reg
));
3385 du_link
= DF_REF_CHAIN (def
);
3392 /* Check if def is dead. */
3396 /* Check for multiple uses. */
3400 return DF_REF_INSN (use
);
3403 /* Functions for debugging/dumping dataflow information. */
3406 /* Dump a def-use or use-def chain for REF to FILE. */
3408 df_chain_dump (link
, file
)
3409 struct df_link
*link
;
3412 fprintf (file
, "{ ");
3413 for (; link
; link
= link
->next
)
3415 fprintf (file
, "%c%d ",
3416 DF_REF_REG_DEF_P (link
->ref
) ? 'd' : 'u',
3417 DF_REF_ID (link
->ref
));
3419 fprintf (file
, "}");
3423 df_chain_dump_regno (link
, file
)
3424 struct df_link
*link
;
3427 fprintf (file
, "{ ");
3428 for (; link
; link
= link
->next
)
3430 fprintf (file
, "%c%d(%d) ",
3431 DF_REF_REG_DEF_P (link
->ref
) ? 'd' : 'u',
3432 DF_REF_ID (link
->ref
),
3433 DF_REF_REGNO (link
->ref
));
3435 fprintf (file
, "}");
3438 /* Dump dataflow info. */
3440 df_dump (df
, flags
, file
)
3451 fprintf (file
, "\nDataflow summary:\n");
3452 fprintf (file
, "n_regs = %d, n_defs = %d, n_uses = %d, n_bbs = %d\n",
3453 df
->n_regs
, df
->n_defs
, df
->n_uses
, df
->n_bbs
);
3457 fprintf (file
, "Reaching defs:\n");
3458 for (i
= 0; i
< df
->n_bbs
; i
++)
3460 basic_block bb
= BASIC_BLOCK (i
);
3461 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
3463 if (! bb_info
->rd_in
)
3466 fprintf (file
, "bb %d in \t", i
);
3467 dump_bitmap (file
, bb_info
->rd_in
);
3468 fprintf (file
, "bb %d gen \t", i
);
3469 dump_bitmap (file
, bb_info
->rd_gen
);
3470 fprintf (file
, "bb %d kill\t", i
);
3471 dump_bitmap (file
, bb_info
->rd_kill
);
3472 fprintf (file
, "bb %d out \t", i
);
3473 dump_bitmap (file
, bb_info
->rd_out
);
3477 if (flags
& DF_UD_CHAIN
)
3479 fprintf (file
, "Use-def chains:\n");
3480 for (j
= 0; j
< df
->n_defs
; j
++)
3484 fprintf (file
, "d%d bb %d luid %d insn %d reg %d ",
3485 j
, DF_REF_BBNO (df
->defs
[j
]),
3486 DF_INSN_LUID (df
, DF_REF_INSN (df
->defs
[j
])),
3487 DF_REF_INSN_UID (df
->defs
[j
]),
3488 DF_REF_REGNO (df
->defs
[j
]));
3489 df_chain_dump (DF_REF_CHAIN (df
->defs
[j
]), file
);
3490 fprintf (file
, "\n");
3497 fprintf (file
, "Reaching uses:\n");
3498 for (i
= 0; i
< df
->n_bbs
; i
++)
3500 basic_block bb
= BASIC_BLOCK (i
);
3501 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
3503 if (! bb_info
->ru_in
)
3506 fprintf (file
, "bb %d in \t", i
);
3507 dump_bitmap (file
, bb_info
->ru_in
);
3508 fprintf (file
, "bb %d gen \t", i
);
3509 dump_bitmap (file
, bb_info
->ru_gen
);
3510 fprintf (file
, "bb %d kill\t", i
);
3511 dump_bitmap (file
, bb_info
->ru_kill
);
3512 fprintf (file
, "bb %d out \t", i
);
3513 dump_bitmap (file
, bb_info
->ru_out
);
3517 if (flags
& DF_DU_CHAIN
)
3519 fprintf (file
, "Def-use chains:\n");
3520 for (j
= 0; j
< df
->n_uses
; j
++)
3524 fprintf (file
, "u%d bb %d luid %d insn %d reg %d ",
3525 j
, DF_REF_BBNO (df
->uses
[j
]),
3526 DF_INSN_LUID (df
, DF_REF_INSN (df
->uses
[j
])),
3527 DF_REF_INSN_UID (df
->uses
[j
]),
3528 DF_REF_REGNO (df
->uses
[j
]));
3529 df_chain_dump (DF_REF_CHAIN (df
->uses
[j
]), file
);
3530 fprintf (file
, "\n");
3537 fprintf (file
, "Live regs:\n");
3538 for (i
= 0; i
< df
->n_bbs
; i
++)
3540 basic_block bb
= BASIC_BLOCK (i
);
3541 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
3543 if (! bb_info
->lr_in
)
3546 fprintf (file
, "bb %d in \t", i
);
3547 dump_bitmap (file
, bb_info
->lr_in
);
3548 fprintf (file
, "bb %d use \t", i
);
3549 dump_bitmap (file
, bb_info
->lr_use
);
3550 fprintf (file
, "bb %d def \t", i
);
3551 dump_bitmap (file
, bb_info
->lr_def
);
3552 fprintf (file
, "bb %d out \t", i
);
3553 dump_bitmap (file
, bb_info
->lr_out
);
3557 if (flags
& (DF_REG_INFO
| DF_RD_CHAIN
| DF_RU_CHAIN
))
3559 struct reg_info
*reg_info
= df
->regs
;
3561 fprintf (file
, "Register info:\n");
3562 for (j
= 0; j
< df
->n_regs
; j
++)
3564 if (((flags
& DF_REG_INFO
)
3565 && (reg_info
[j
].n_uses
|| reg_info
[j
].n_defs
))
3566 || ((flags
& DF_RD_CHAIN
) && reg_info
[j
].defs
)
3567 || ((flags
& DF_RU_CHAIN
) && reg_info
[j
].uses
))
3569 fprintf (file
, "reg %d", j
);
3570 if ((flags
& DF_RD_CHAIN
) && (flags
& DF_RU_CHAIN
))
3572 basic_block bb
= df_regno_bb (df
, j
);
3575 fprintf (file
, " bb %d", bb
->index
);
3577 fprintf (file
, " bb ?");
3579 if (flags
& DF_REG_INFO
)
3581 fprintf (file
, " life %d", reg_info
[j
].lifetime
);
3584 if ((flags
& DF_REG_INFO
) || (flags
& DF_RD_CHAIN
))
3586 fprintf (file
, " defs ");
3587 if (flags
& DF_REG_INFO
)
3588 fprintf (file
, "%d ", reg_info
[j
].n_defs
);
3589 if (flags
& DF_RD_CHAIN
)
3590 df_chain_dump (reg_info
[j
].defs
, file
);
3593 if ((flags
& DF_REG_INFO
) || (flags
& DF_RU_CHAIN
))
3595 fprintf (file
, " uses ");
3596 if (flags
& DF_REG_INFO
)
3597 fprintf (file
, "%d ", reg_info
[j
].n_uses
);
3598 if (flags
& DF_RU_CHAIN
)
3599 df_chain_dump (reg_info
[j
].uses
, file
);
3602 fprintf (file
, "\n");
3606 fprintf (file
, "\n");
3611 df_insn_debug (df
, insn
, file
)
3619 uid
= INSN_UID (insn
);
3620 if (uid
>= df
->insn_size
)
3623 if (df
->insns
[uid
].defs
)
3624 bbi
= DF_REF_BBNO (df
->insns
[uid
].defs
->ref
);
3625 else if (df
->insns
[uid
].uses
)
3626 bbi
= DF_REF_BBNO (df
->insns
[uid
].uses
->ref
);
3630 fprintf (file
, "insn %d bb %d luid %d defs ",
3631 uid
, bbi
, DF_INSN_LUID (df
, insn
));
3632 df_chain_dump (df
->insns
[uid
].defs
, file
);
3633 fprintf (file
, " uses ");
3634 df_chain_dump (df
->insns
[uid
].uses
, file
);
3635 fprintf (file
, "\n");
3639 df_insn_debug_regno (df
, insn
, file
)
3647 uid
= INSN_UID (insn
);
3648 if (uid
>= df
->insn_size
)
3651 if (df
->insns
[uid
].defs
)
3652 bbi
= DF_REF_BBNO (df
->insns
[uid
].defs
->ref
);
3653 else if (df
->insns
[uid
].uses
)
3654 bbi
= DF_REF_BBNO (df
->insns
[uid
].uses
->ref
);
3658 fprintf (file
, "insn %d bb %d luid %d defs ",
3659 uid
, bbi
, DF_INSN_LUID (df
, insn
));
3660 df_chain_dump_regno (df
->insns
[uid
].defs
, file
);
3661 fprintf (file
, " uses ");
3662 df_chain_dump_regno (df
->insns
[uid
].uses
, file
);
3663 fprintf (file
, "\n");
3667 df_regno_debug (df
, regno
, file
)
3672 if (regno
>= df
->reg_size
)
3675 fprintf (file
, "reg %d life %d defs ",
3676 regno
, df
->regs
[regno
].lifetime
);
3677 df_chain_dump (df
->regs
[regno
].defs
, file
);
3678 fprintf (file
, " uses ");
3679 df_chain_dump (df
->regs
[regno
].uses
, file
);
3680 fprintf (file
, "\n");
3685 df_ref_debug (df
, ref
, file
)
3690 fprintf (file
, "%c%d ",
3691 DF_REF_REG_DEF_P (ref
) ? 'd' : 'u',
3693 fprintf (file
, "reg %d bb %d luid %d insn %d chain ",
3696 DF_INSN_LUID (df
, DF_REF_INSN (ref
)),
3697 INSN_UID (DF_REF_INSN (ref
)));
3698 df_chain_dump (DF_REF_CHAIN (ref
), file
);
3699 fprintf (file
, "\n");
3704 debug_df_insn (insn
)
3707 df_insn_debug (ddf
, insn
, stderr
);
3716 df_regno_debug (ddf
, REGNO (reg
), stderr
);
3721 debug_df_regno (regno
)
3724 df_regno_debug (ddf
, regno
, stderr
);
3732 df_ref_debug (ddf
, ref
, stderr
);
3737 debug_df_defno (defno
)
3740 df_ref_debug (ddf
, ddf
->defs
[defno
], stderr
);
3745 debug_df_useno (defno
)
3748 df_ref_debug (ddf
, ddf
->uses
[defno
], stderr
);
3753 debug_df_chain (link
)
3754 struct df_link
*link
;
3756 df_chain_dump (link
, stderr
);
3757 fputc ('\n', stderr
);