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
162 #include "insn-config.h"
164 #include "function.h"
167 #include "hard-reg-set.h"
168 #include "basic-block.h"
174 #define FOR_ALL_BBS(BB, CODE) \
177 for (node_ = 0; node_ < n_basic_blocks; node_++) \
178 {(BB) = BASIC_BLOCK (node_); CODE;};} while (0)
180 #define FOR_EACH_BB_IN_BITMAP(BITMAP, MIN, BB, CODE) \
182 unsigned int node_; \
183 EXECUTE_IF_SET_IN_BITMAP (BITMAP, MIN, node_, \
184 {(BB) = BASIC_BLOCK (node_); CODE;});} while (0)
186 #define FOR_EACH_BB_IN_BITMAP_REV(BITMAP, MIN, BB, CODE) \
188 unsigned int node_; \
189 EXECUTE_IF_SET_IN_BITMAP_REV (BITMAP, node_, \
190 {(BB) = BASIC_BLOCK (node_); CODE;});} while (0)
192 #define FOR_EACH_BB_IN_SBITMAP(BITMAP, MIN, BB, CODE) \
194 unsigned int node_; \
195 EXECUTE_IF_SET_IN_SBITMAP (BITMAP, MIN, node_, \
196 {(BB) = BASIC_BLOCK (node_); CODE;});} while (0)
198 #define obstack_chunk_alloc xmalloc
199 #define obstack_chunk_free free
201 static struct obstack df_ref_obstack
;
202 static struct df
*ddf
;
204 static void df_reg_table_realloc
PARAMS((struct df
*, int));
206 static void df_def_table_realloc
PARAMS((struct df
*, int));
208 static void df_insn_table_realloc
PARAMS((struct df
*, int));
209 static void df_bitmaps_alloc
PARAMS((struct df
*, int));
210 static void df_bitmaps_free
PARAMS((struct df
*, int));
211 static void df_free
PARAMS((struct df
*));
212 static void df_alloc
PARAMS((struct df
*, int));
214 static rtx df_reg_clobber_gen
PARAMS((unsigned int));
215 static rtx df_reg_use_gen
PARAMS((unsigned int));
217 static inline struct df_link
*df_link_create
PARAMS((struct ref
*,
219 static struct df_link
*df_ref_unlink
PARAMS((struct df_link
**, struct ref
*));
220 static void df_def_unlink
PARAMS((struct df
*, struct ref
*));
221 static void df_use_unlink
PARAMS((struct df
*, struct ref
*));
222 static void df_insn_refs_unlink
PARAMS ((struct df
*, basic_block
, rtx
));
224 static void df_bb_refs_unlink
PARAMS ((struct df
*, basic_block
));
225 static void df_refs_unlink
PARAMS ((struct df
*, bitmap
));
228 static struct ref
*df_ref_create
PARAMS((struct df
*,
229 rtx
, rtx
*, basic_block
, rtx
,
230 enum df_ref_type
, enum df_ref_flags
));
231 static void df_ref_record_1
PARAMS((struct df
*, rtx
, rtx
*,
232 basic_block
, rtx
, enum df_ref_type
,
234 static void df_ref_record
PARAMS((struct df
*, rtx
, rtx
*,
235 basic_block bb
, rtx
, enum df_ref_type
,
237 static void df_def_record_1
PARAMS((struct df
*, rtx
, basic_block
, rtx
));
238 static void df_defs_record
PARAMS((struct df
*, rtx
, basic_block
, rtx
));
239 static void df_uses_record
PARAMS((struct df
*, rtx
*,
240 enum df_ref_type
, basic_block
, rtx
,
242 static void df_insn_refs_record
PARAMS((struct df
*, basic_block
, rtx
));
243 static void df_bb_refs_record
PARAMS((struct df
*, basic_block
));
244 static void df_refs_record
PARAMS((struct df
*, bitmap
));
246 static void df_bb_reg_def_chain_create
PARAMS((struct df
*, basic_block
));
247 static void df_reg_def_chain_create
PARAMS((struct df
*, bitmap
));
248 static void df_bb_reg_use_chain_create
PARAMS((struct df
*, basic_block
));
249 static void df_reg_use_chain_create
PARAMS((struct df
*, bitmap
));
250 static void df_bb_du_chain_create
PARAMS((struct df
*, basic_block
, bitmap
));
251 static void df_du_chain_create
PARAMS((struct df
*, bitmap
));
252 static void df_bb_ud_chain_create
PARAMS((struct df
*, basic_block
));
253 static void df_ud_chain_create
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 *));
298 static void df_rd_transfer_function
PARAMS ((int, int *, bitmap
, bitmap
,
299 bitmap
, bitmap
, void *));
300 static void df_ru_transfer_function
PARAMS ((int, int *, bitmap
, bitmap
,
301 bitmap
, bitmap
, void *));
302 static void df_lr_transfer_function
PARAMS ((int, int *, bitmap
, bitmap
,
303 bitmap
, bitmap
, void *));
304 static inline bool read_modify_subreg_p
PARAMS ((rtx
));
307 /* Local memory allocation/deallocation routines. */
310 /* Increase the insn info table by SIZE more elements. */
312 df_insn_table_realloc (df
, size
)
316 /* Make table 25 percent larger by default. */
318 size
= df
->insn_size
/ 4;
320 size
+= df
->insn_size
;
322 df
->insns
= (struct insn_info
*)
323 xrealloc (df
->insns
, size
* sizeof (struct insn_info
));
325 memset (df
->insns
+ df
->insn_size
, 0,
326 (size
- df
->insn_size
) * sizeof (struct insn_info
));
328 df
->insn_size
= size
;
330 if (! df
->insns_modified
)
332 df
->insns_modified
= BITMAP_XMALLOC ();
333 bitmap_zero (df
->insns_modified
);
338 /* Increase the reg info table by SIZE more elements. */
340 df_reg_table_realloc (df
, size
)
344 /* Make table 25 percent larger by default. */
346 size
= df
->reg_size
/ 4;
348 size
+= df
->reg_size
;
350 df
->regs
= (struct reg_info
*)
351 xrealloc (df
->regs
, size
* sizeof (struct reg_info
));
353 /* Zero the new entries. */
354 memset (df
->regs
+ df
->reg_size
, 0,
355 (size
- df
->reg_size
) * sizeof (struct reg_info
));
362 /* Not currently used. */
364 df_def_table_realloc (df
, size
)
371 /* Make table 25 percent larger by default. */
373 size
= df
->def_size
/ 4;
375 df
->def_size
+= size
;
376 df
->defs
= xrealloc (df
->defs
,
377 df
->def_size
* sizeof (*df
->defs
));
379 /* Allocate a new block of memory and link into list of blocks
380 that will need to be freed later. */
382 refs
= xmalloc (size
* sizeof (*refs
));
384 /* Link all the new refs together, overloading the chain field. */
385 for (i
= 0; i
< size
- 1; i
++)
386 refs
[i
].chain
= (struct df_link
*)(refs
+ i
+ 1);
387 refs
[size
- 1].chain
= 0;
393 /* Allocate bitmaps for each basic block. */
395 df_bitmaps_alloc (df
, flags
)
402 /* Free the bitmaps if they need resizing. */
403 if ((flags
& DF_LR
) && df
->n_regs
< (unsigned int)max_reg_num ())
404 dflags
|= DF_LR
| DF_RU
;
405 if ((flags
& DF_RU
) && df
->n_uses
< df
->use_id
)
407 if ((flags
& DF_RD
) && df
->n_defs
< df
->def_id
)
411 df_bitmaps_free (df
, dflags
);
413 df
->n_defs
= df
->def_id
;
414 df
->n_uses
= df
->use_id
;
416 for (i
= 0; i
< df
->n_bbs
; i
++)
418 basic_block bb
= BASIC_BLOCK (i
);
419 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
421 if (flags
& DF_RD
&& ! bb_info
->rd_in
)
423 /* Allocate bitmaps for reaching definitions. */
424 bb_info
->rd_kill
= BITMAP_XMALLOC ();
425 bitmap_zero (bb_info
->rd_kill
);
426 bb_info
->rd_gen
= BITMAP_XMALLOC ();
427 bitmap_zero (bb_info
->rd_gen
);
428 bb_info
->rd_in
= BITMAP_XMALLOC ();
429 bb_info
->rd_out
= BITMAP_XMALLOC ();
430 bb_info
->rd_valid
= 0;
433 if (flags
& DF_RU
&& ! bb_info
->ru_in
)
435 /* Allocate bitmaps for upward exposed uses. */
436 bb_info
->ru_kill
= BITMAP_XMALLOC ();
437 bitmap_zero (bb_info
->ru_kill
);
438 /* Note the lack of symmetry. */
439 bb_info
->ru_gen
= BITMAP_XMALLOC ();
440 bitmap_zero (bb_info
->ru_gen
);
441 bb_info
->ru_in
= BITMAP_XMALLOC ();
442 bb_info
->ru_out
= BITMAP_XMALLOC ();
443 bb_info
->ru_valid
= 0;
446 if (flags
& DF_LR
&& ! bb_info
->lr_in
)
448 /* Allocate bitmaps for live variables. */
449 bb_info
->lr_def
= BITMAP_XMALLOC ();
450 bitmap_zero (bb_info
->lr_def
);
451 bb_info
->lr_use
= BITMAP_XMALLOC ();
452 bitmap_zero (bb_info
->lr_use
);
453 bb_info
->lr_in
= BITMAP_XMALLOC ();
454 bb_info
->lr_out
= BITMAP_XMALLOC ();
455 bb_info
->lr_valid
= 0;
461 /* Free bitmaps for each basic block. */
463 df_bitmaps_free (df
, flags
)
464 struct df
*df ATTRIBUTE_UNUSED
;
469 for (i
= 0; i
< df
->n_bbs
; i
++)
471 basic_block bb
= BASIC_BLOCK (i
);
472 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
477 if ((flags
& DF_RD
) && bb_info
->rd_in
)
479 /* Free bitmaps for reaching definitions. */
480 BITMAP_XFREE (bb_info
->rd_kill
);
481 bb_info
->rd_kill
= NULL
;
482 BITMAP_XFREE (bb_info
->rd_gen
);
483 bb_info
->rd_gen
= NULL
;
484 BITMAP_XFREE (bb_info
->rd_in
);
485 bb_info
->rd_in
= NULL
;
486 BITMAP_XFREE (bb_info
->rd_out
);
487 bb_info
->rd_out
= NULL
;
490 if ((flags
& DF_RU
) && bb_info
->ru_in
)
492 /* Free bitmaps for upward exposed uses. */
493 BITMAP_XFREE (bb_info
->ru_kill
);
494 bb_info
->ru_kill
= NULL
;
495 BITMAP_XFREE (bb_info
->ru_gen
);
496 bb_info
->ru_gen
= NULL
;
497 BITMAP_XFREE (bb_info
->ru_in
);
498 bb_info
->ru_in
= NULL
;
499 BITMAP_XFREE (bb_info
->ru_out
);
500 bb_info
->ru_out
= NULL
;
503 if ((flags
& DF_LR
) && bb_info
->lr_in
)
505 /* Free bitmaps for live variables. */
506 BITMAP_XFREE (bb_info
->lr_def
);
507 bb_info
->lr_def
= NULL
;
508 BITMAP_XFREE (bb_info
->lr_use
);
509 bb_info
->lr_use
= NULL
;
510 BITMAP_XFREE (bb_info
->lr_in
);
511 bb_info
->lr_in
= NULL
;
512 BITMAP_XFREE (bb_info
->lr_out
);
513 bb_info
->lr_out
= NULL
;
516 df
->flags
&= ~(flags
& (DF_RD
| DF_RU
| DF_LR
));
520 /* Allocate and initialise dataflow memory. */
522 df_alloc (df
, n_regs
)
529 gcc_obstack_init (&df_ref_obstack
);
531 /* Perhaps we should use LUIDs to save memory for the insn_refs
532 table. This is only a small saving; a few pointers. */
533 n_insns
= get_max_uid () + 1;
537 /* Approximate number of defs by number of insns. */
538 df
->def_size
= n_insns
;
539 df
->defs
= xmalloc (df
->def_size
* sizeof (*df
->defs
));
543 /* Approximate number of uses by twice number of insns. */
544 df
->use_size
= n_insns
* 2;
545 df
->uses
= xmalloc (df
->use_size
* sizeof (*df
->uses
));
548 df
->n_bbs
= n_basic_blocks
;
550 /* Allocate temporary working array used during local dataflow analysis. */
551 df
->reg_def_last
= xmalloc (df
->n_regs
* sizeof (struct ref
*));
553 df_insn_table_realloc (df
, n_insns
);
555 df_reg_table_realloc (df
, df
->n_regs
);
557 df
->bbs_modified
= BITMAP_XMALLOC ();
558 bitmap_zero (df
->bbs_modified
);
562 df
->bbs
= xcalloc (df
->n_bbs
, sizeof (struct bb_info
));
564 df
->all_blocks
= BITMAP_XMALLOC ();
565 for (i
= 0; i
< n_basic_blocks
; i
++)
566 bitmap_set_bit (df
->all_blocks
, i
);
570 /* Free all the dataflow info. */
575 df_bitmaps_free (df
, DF_ALL
);
603 if (df
->bbs_modified
)
604 BITMAP_XFREE (df
->bbs_modified
);
605 df
->bbs_modified
= 0;
607 if (df
->insns_modified
)
608 BITMAP_XFREE (df
->insns_modified
);
609 df
->insns_modified
= 0;
611 BITMAP_XFREE (df
->all_blocks
);
614 obstack_free (&df_ref_obstack
, NULL
);
617 /* Local miscellaneous routines. */
619 /* Return a USE for register REGNO. */
620 static rtx
df_reg_use_gen (regno
)
626 reg
= regno
>= FIRST_PSEUDO_REGISTER
627 ? regno_reg_rtx
[regno
] : gen_rtx_REG (reg_raw_mode
[regno
], regno
);
629 use
= gen_rtx_USE (GET_MODE (reg
), reg
);
634 /* Return a CLOBBER for register REGNO. */
635 static rtx
df_reg_clobber_gen (regno
)
641 reg
= regno
>= FIRST_PSEUDO_REGISTER
642 ? regno_reg_rtx
[regno
] : gen_rtx_REG (reg_raw_mode
[regno
], regno
);
644 use
= gen_rtx_CLOBBER (GET_MODE (reg
), reg
);
648 /* Local chain manipulation routines. */
650 /* Create a link in a def-use or use-def chain. */
651 static inline struct df_link
*
652 df_link_create (ref
, next
)
654 struct df_link
*next
;
656 struct df_link
*link
;
658 link
= (struct df_link
*) obstack_alloc (&df_ref_obstack
,
666 /* Add REF to chain head pointed to by PHEAD. */
667 static struct df_link
*
668 df_ref_unlink (phead
, ref
)
669 struct df_link
**phead
;
672 struct df_link
*link
= *phead
;
678 /* Only a single ref. It must be the one we want.
679 If not, the def-use and use-def chains are likely to
681 if (link
->ref
!= ref
)
683 /* Now have an empty chain. */
688 /* Multiple refs. One of them must be us. */
689 if (link
->ref
== ref
)
694 for (; link
->next
; link
= link
->next
)
696 if (link
->next
->ref
== ref
)
698 /* Unlink from list. */
699 link
->next
= link
->next
->next
;
710 /* Unlink REF from all def-use/use-def chains, etc. */
712 df_ref_remove (df
, ref
)
716 if (DF_REF_REG_DEF_P (ref
))
718 df_def_unlink (df
, ref
);
719 df_ref_unlink (&df
->insns
[DF_REF_INSN_UID (ref
)].defs
, ref
);
723 df_use_unlink (df
, ref
);
724 df_ref_unlink (&df
->insns
[DF_REF_INSN_UID (ref
)].uses
, ref
);
730 /* Unlink DEF from use-def and reg-def chains. */
732 df_def_unlink (df
, def
)
733 struct df
*df ATTRIBUTE_UNUSED
;
736 struct df_link
*du_link
;
737 unsigned int dregno
= DF_REF_REGNO (def
);
739 /* Follow def-use chain to find all the uses of this def. */
740 for (du_link
= DF_REF_CHAIN (def
); du_link
; du_link
= du_link
->next
)
742 struct ref
*use
= du_link
->ref
;
744 /* Unlink this def from the use-def chain. */
745 df_ref_unlink (&DF_REF_CHAIN (use
), def
);
747 DF_REF_CHAIN (def
) = 0;
749 /* Unlink def from reg-def chain. */
750 df_ref_unlink (&df
->regs
[dregno
].defs
, def
);
752 df
->defs
[DF_REF_ID (def
)] = 0;
756 /* Unlink use from def-use and reg-use chains. */
758 df_use_unlink (df
, use
)
759 struct df
*df ATTRIBUTE_UNUSED
;
762 struct df_link
*ud_link
;
763 unsigned int uregno
= DF_REF_REGNO (use
);
765 /* Follow use-def chain to find all the defs of this use. */
766 for (ud_link
= DF_REF_CHAIN (use
); ud_link
; ud_link
= ud_link
->next
)
768 struct ref
*def
= ud_link
->ref
;
770 /* Unlink this use from the def-use chain. */
771 df_ref_unlink (&DF_REF_CHAIN (def
), use
);
773 DF_REF_CHAIN (use
) = 0;
775 /* Unlink use from reg-use chain. */
776 df_ref_unlink (&df
->regs
[uregno
].uses
, use
);
778 df
->uses
[DF_REF_ID (use
)] = 0;
781 /* Local routines for recording refs. */
784 /* Create a new ref of type DF_REF_TYPE for register REG at address
785 LOC within INSN of BB. */
787 df_ref_create (df
, reg
, loc
, bb
, insn
, ref_type
, ref_flags
)
793 enum df_ref_type ref_type
;
794 enum df_ref_flags ref_flags
;
796 struct ref
*this_ref
;
799 this_ref
= (struct ref
*) obstack_alloc (&df_ref_obstack
,
801 DF_REF_REG (this_ref
) = reg
;
802 DF_REF_LOC (this_ref
) = loc
;
803 DF_REF_BB (this_ref
) = bb
;
804 DF_REF_INSN (this_ref
) = insn
;
805 DF_REF_CHAIN (this_ref
) = 0;
806 DF_REF_TYPE (this_ref
) = ref_type
;
807 DF_REF_FLAGS (this_ref
) = ref_flags
;
808 uid
= INSN_UID (insn
);
810 if (ref_type
== DF_REF_REG_DEF
)
812 if (df
->def_id
>= df
->def_size
)
814 /* Make table 25 percent larger. */
815 df
->def_size
+= (df
->def_size
/ 4);
816 df
->defs
= xrealloc (df
->defs
,
817 df
->def_size
* sizeof (*df
->defs
));
819 DF_REF_ID (this_ref
) = df
->def_id
;
820 df
->defs
[df
->def_id
++] = this_ref
;
824 if (df
->use_id
>= df
->use_size
)
826 /* Make table 25 percent larger. */
827 df
->use_size
+= (df
->use_size
/ 4);
828 df
->uses
= xrealloc (df
->uses
,
829 df
->use_size
* sizeof (*df
->uses
));
831 DF_REF_ID (this_ref
) = df
->use_id
;
832 df
->uses
[df
->use_id
++] = this_ref
;
838 /* Create a new reference of type DF_REF_TYPE for a single register REG,
839 used inside the LOC rtx of INSN. */
841 df_ref_record_1 (df
, reg
, loc
, bb
, insn
, ref_type
, ref_flags
)
847 enum df_ref_type ref_type
;
848 enum df_ref_flags ref_flags
;
850 df_ref_create (df
, reg
, loc
, bb
, insn
, ref_type
, ref_flags
);
854 /* Create new references of type DF_REF_TYPE for each part of register REG
855 at address LOC within INSN of BB. */
857 df_ref_record (df
, reg
, loc
, bb
, insn
, ref_type
, ref_flags
)
863 enum df_ref_type ref_type
;
864 enum df_ref_flags ref_flags
;
868 if (GET_CODE (reg
) != REG
&& GET_CODE (reg
) != SUBREG
)
871 /* For the reg allocator we are interested in some SUBREG rtx's, but not
872 all. Notably only those representing a word extraction from a multi-word
873 reg. As written in the docu those should have the form
874 (subreg:SI (reg:M A) N), with size(SImode) > size(Mmode).
875 XXX Is that true? We could also use the global word_mode variable. */
876 if (GET_CODE (reg
) == SUBREG
877 && (GET_MODE_SIZE (GET_MODE (reg
)) < GET_MODE_SIZE (word_mode
)
878 || GET_MODE_SIZE (GET_MODE (reg
))
879 >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (reg
)))))
881 loc
= &SUBREG_REG (reg
);
885 regno
= REGNO (GET_CODE (reg
) == SUBREG
? SUBREG_REG (reg
) : reg
);
886 if (regno
< FIRST_PSEUDO_REGISTER
)
891 if (! (df
->flags
& DF_HARD_REGS
))
894 /* GET_MODE (reg) is correct here. We don't want to go into a SUBREG
895 for the mode, because we only want to add references to regs, which
896 are really referenced. E.g. a (subreg:SI (reg:DI 0) 0) does _not_
897 reference the whole reg 0 in DI mode (which would also include
898 reg 1, at least, if 0 and 1 are SImode registers). */
899 endregno
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
901 for (i
= regno
; i
< endregno
; i
++)
902 df_ref_record_1 (df
, gen_rtx_REG (reg_raw_mode
[i
], i
),
903 loc
, bb
, insn
, ref_type
, ref_flags
);
907 df_ref_record_1 (df
, reg
, loc
, bb
, insn
, ref_type
, ref_flags
);
911 /* Writes to SUBREG of inndermode wider than word and outermode shorter than
912 word are read-modify-write. */
915 read_modify_subreg_p (x
)
918 if (GET_CODE (x
) != SUBREG
)
920 if (GET_MODE_SIZE (GET_MODE (SUBREG_REG (x
))) <= UNITS_PER_WORD
)
922 if (GET_MODE_SIZE (GET_MODE (x
)) > UNITS_PER_WORD
)
927 /* Process all the registers defined in the rtx, X. */
929 df_def_record_1 (df
, x
, bb
, insn
)
935 rtx
*loc
= &SET_DEST (x
);
937 enum df_ref_flags flags
= 0;
939 /* Some targets place small structures in registers for
940 return values of functions. */
941 if (GET_CODE (dst
) == PARALLEL
&& GET_MODE (dst
) == BLKmode
)
945 for (i
= XVECLEN (dst
, 0) - 1; i
>= 0; i
--)
946 df_def_record_1 (df
, XVECEXP (dst
, 0, i
), bb
, insn
);
950 /* May be, we should flag the use of strict_low_part somehow. Might be
951 handy for the reg allocator. */
952 while (GET_CODE (dst
) == STRICT_LOW_PART
953 || GET_CODE (dst
) == ZERO_EXTRACT
954 || GET_CODE (dst
) == SIGN_EXTRACT
955 || read_modify_subreg_p (dst
))
957 /* Strict low part allways contains SUBREG, but we don't want to make
958 it appear outside, as whole register is allways considered. */
959 if (GET_CODE (dst
) == STRICT_LOW_PART
)
961 loc
= &XEXP (dst
, 0);
964 loc
= &XEXP (dst
, 0);
966 flags
|= DF_REF_READ_WRITE
;
969 if (GET_CODE (dst
) == REG
970 || (GET_CODE (dst
) == SUBREG
&& GET_CODE (SUBREG_REG (dst
)) == REG
))
971 df_ref_record (df
, dst
, loc
, bb
, insn
, DF_REF_REG_DEF
, flags
);
975 /* Process all the registers defined in the pattern rtx, X. */
977 df_defs_record (df
, x
, bb
, insn
)
983 RTX_CODE code
= GET_CODE (x
);
985 if (code
== SET
|| code
== CLOBBER
)
987 /* Mark the single def within the pattern. */
988 df_def_record_1 (df
, x
, bb
, insn
);
990 else if (code
== PARALLEL
)
994 /* Mark the multiple defs within the pattern. */
995 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
997 code
= GET_CODE (XVECEXP (x
, 0, i
));
998 if (code
== SET
|| code
== CLOBBER
)
999 df_def_record_1 (df
, XVECEXP (x
, 0, i
), bb
, insn
);
1005 /* Process all the registers used in the rtx at address LOC. */
1007 df_uses_record (df
, loc
, ref_type
, bb
, insn
, flags
)
1010 enum df_ref_type ref_type
;
1013 enum df_ref_flags flags
;
1022 code
= GET_CODE (x
);
1036 /* If we are clobbering a MEM, mark any registers inside the address
1038 if (GET_CODE (XEXP (x
, 0)) == MEM
)
1039 df_uses_record (df
, &XEXP (XEXP (x
, 0), 0),
1040 DF_REF_REG_MEM_STORE
, bb
, insn
, flags
);
1042 /* If we're clobbering a REG then we have a def so ignore. */
1046 df_uses_record (df
, &XEXP (x
, 0), DF_REF_REG_MEM_LOAD
, bb
, insn
, flags
);
1050 /* While we're here, optimize this case. */
1052 /* In case the SUBREG is not of a register, don't optimize. */
1053 if (GET_CODE (SUBREG_REG (x
)) != REG
)
1055 loc
= &SUBREG_REG (x
);
1056 df_uses_record (df
, loc
, ref_type
, bb
, insn
, flags
);
1060 /* ... Fall through ... */
1063 /* See a register (or subreg) other than being set. */
1064 df_ref_record (df
, x
, loc
, bb
, insn
, ref_type
, flags
);
1069 rtx dst
= SET_DEST (x
);
1071 df_uses_record (df
, &SET_SRC (x
), DF_REF_REG_USE
, bb
, insn
, 0);
1073 switch (GET_CODE (dst
))
1076 if (read_modify_subreg_p (dst
))
1078 df_uses_record (df
, &SUBREG_REG (dst
), DF_REF_REG_USE
, bb
,
1079 insn
, DF_REF_READ_WRITE
);
1082 /* ... FALLTHRU ... */
1087 df_uses_record (df
, &XEXP (dst
, 0),
1088 DF_REF_REG_MEM_STORE
,
1091 case STRICT_LOW_PART
:
1092 /* A strict_low_part uses the whole reg not only the subreg. */
1093 dst
= XEXP (dst
, 0);
1094 if (GET_CODE (dst
) != SUBREG
)
1096 df_uses_record (df
, &SUBREG_REG (dst
), DF_REF_REG_USE
, bb
,
1097 insn
, DF_REF_READ_WRITE
);
1101 df_uses_record (df
, &XEXP (dst
, 0), DF_REF_REG_USE
, bb
, insn
,
1103 df_uses_record (df
, &XEXP (dst
, 1), DF_REF_REG_USE
, bb
, insn
, 0);
1104 df_uses_record (df
, &XEXP (dst
, 2), DF_REF_REG_USE
, bb
, insn
, 0);
1105 dst
= XEXP (dst
, 0);
1117 case UNSPEC_VOLATILE
:
1121 /* Traditional and volatile asm instructions must be considered to use
1122 and clobber all hard registers, all pseudo-registers and all of
1123 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
1125 Consider for instance a volatile asm that changes the fpu rounding
1126 mode. An insn should not be moved across this even if it only uses
1127 pseudo-regs because it might give an incorrectly rounded result.
1129 For now, just mark any regs we can find in ASM_OPERANDS as
1132 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
1133 We can not just fall through here since then we would be confused
1134 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
1135 traditional asms unlike their normal usage. */
1136 if (code
== ASM_OPERANDS
)
1140 for (j
= 0; j
< ASM_OPERANDS_INPUT_LENGTH (x
); j
++)
1141 df_uses_record (df
, &ASM_OPERANDS_INPUT (x
, j
),
1142 DF_REF_REG_USE
, bb
, insn
, 0);
1154 /* Catch the def of the register being modified. */
1155 df_ref_record (df
, XEXP (x
, 0), &XEXP (x
, 0), bb
, insn
, DF_REF_REG_DEF
, DF_REF_READ_WRITE
);
1157 /* ... Fall through to handle uses ... */
1163 /* Recursively scan the operands of this expression. */
1165 const char *fmt
= GET_RTX_FORMAT (code
);
1168 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1172 /* Tail recursive case: save a function call level. */
1178 df_uses_record (df
, &XEXP (x
, i
), ref_type
, bb
, insn
, flags
);
1180 else if (fmt
[i
] == 'E')
1183 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1184 df_uses_record (df
, &XVECEXP (x
, i
, j
), ref_type
,
1192 /* Record all the df within INSN of basic block BB. */
1194 df_insn_refs_record (df
, bb
, insn
)
1205 /* Record register defs */
1206 df_defs_record (df
, PATTERN (insn
), bb
, insn
);
1208 if (df
->flags
& DF_EQUIV_NOTES
)
1209 for (note
= REG_NOTES (insn
); note
;
1210 note
= XEXP (note
, 1))
1212 switch (REG_NOTE_KIND (note
))
1216 df_uses_record (df
, &XEXP (note
, 0), DF_REF_REG_USE
,
1223 if (GET_CODE (insn
) == CALL_INSN
)
1228 /* Record the registers used to pass arguments. */
1229 for (note
= CALL_INSN_FUNCTION_USAGE (insn
); note
;
1230 note
= XEXP (note
, 1))
1232 if (GET_CODE (XEXP (note
, 0)) == USE
)
1233 df_uses_record (df
, &SET_DEST (XEXP (note
, 0)), DF_REF_REG_USE
,
1237 /* The stack ptr is used (honorarily) by a CALL insn. */
1238 x
= df_reg_use_gen (STACK_POINTER_REGNUM
);
1239 df_uses_record (df
, &SET_DEST (x
), DF_REF_REG_USE
, bb
, insn
, 0);
1241 if (df
->flags
& DF_HARD_REGS
)
1243 /* Calls may also reference any of the global registers,
1244 so they are recorded as used. */
1245 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1248 x
= df_reg_use_gen (i
);
1249 df_uses_record (df
, &SET_DEST (x
),
1250 DF_REF_REG_USE
, bb
, insn
, 0);
1255 /* Record the register uses. */
1256 df_uses_record (df
, &PATTERN (insn
),
1257 DF_REF_REG_USE
, bb
, insn
, 0);
1260 if (GET_CODE (insn
) == CALL_INSN
)
1264 if (df
->flags
& DF_HARD_REGS
)
1266 /* Kill all registers invalidated by a call. */
1267 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1268 if (TEST_HARD_REG_BIT (regs_invalidated_by_call
, i
))
1270 rtx reg_clob
= df_reg_clobber_gen (i
);
1271 df_defs_record (df
, reg_clob
, bb
, insn
);
1275 /* There may be extra registers to be clobbered. */
1276 for (note
= CALL_INSN_FUNCTION_USAGE (insn
);
1278 note
= XEXP (note
, 1))
1279 if (GET_CODE (XEXP (note
, 0)) == CLOBBER
)
1280 df_defs_record (df
, XEXP (note
, 0), bb
, insn
);
1286 /* Record all the refs within the basic block BB. */
1288 df_bb_refs_record (df
, bb
)
1294 /* Scan the block an insn at a time from beginning to end. */
1295 for (insn
= bb
->head
; ; insn
= NEXT_INSN (insn
))
1299 /* Record defs within INSN. */
1300 df_insn_refs_record (df
, bb
, insn
);
1302 if (insn
== bb
->end
)
1308 /* Record all the refs in the basic blocks specified by BLOCKS. */
1310 df_refs_record (df
, blocks
)
1316 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
1318 df_bb_refs_record (df
, bb
);
1322 /* Dataflow analysis routines. */
1325 /* Create reg-def chains for basic block BB. These are a list of
1326 definitions for each register. */
1328 df_bb_reg_def_chain_create (df
, bb
)
1334 /* Perhaps the defs should be sorted using a depth first search
1335 of the CFG (or possibly a breadth first search). We currently
1336 scan the basic blocks in reverse order so that the first defs
1337 apprear at the start of the chain. */
1339 for (insn
= bb
->end
; insn
&& insn
!= PREV_INSN (bb
->head
);
1340 insn
= PREV_INSN (insn
))
1342 struct df_link
*link
;
1343 unsigned int uid
= INSN_UID (insn
);
1345 if (! INSN_P (insn
))
1348 for (link
= df
->insns
[uid
].defs
; link
; link
= link
->next
)
1350 struct ref
*def
= link
->ref
;
1351 unsigned int dregno
= DF_REF_REGNO (def
);
1353 df
->regs
[dregno
].defs
1354 = df_link_create (def
, df
->regs
[dregno
].defs
);
1360 /* Create reg-def chains for each basic block within BLOCKS. These
1361 are a list of definitions for each register. */
1363 df_reg_def_chain_create (df
, blocks
)
1369 FOR_EACH_BB_IN_BITMAP
/*_REV*/ (blocks
, 0, bb
,
1371 df_bb_reg_def_chain_create (df
, bb
);
1376 /* Create reg-use chains for basic block BB. These are a list of uses
1377 for each register. */
1379 df_bb_reg_use_chain_create (df
, bb
)
1385 /* Scan in forward order so that the last uses appear at the
1386 start of the chain. */
1388 for (insn
= bb
->head
; insn
&& insn
!= NEXT_INSN (bb
->end
);
1389 insn
= NEXT_INSN (insn
))
1391 struct df_link
*link
;
1392 unsigned int uid
= INSN_UID (insn
);
1394 if (! INSN_P (insn
))
1397 for (link
= df
->insns
[uid
].uses
; link
; link
= link
->next
)
1399 struct ref
*use
= link
->ref
;
1400 unsigned int uregno
= DF_REF_REGNO (use
);
1402 df
->regs
[uregno
].uses
1403 = df_link_create (use
, df
->regs
[uregno
].uses
);
1409 /* Create reg-use chains for each basic block within BLOCKS. These
1410 are a list of uses for each register. */
1412 df_reg_use_chain_create (df
, blocks
)
1418 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
1420 df_bb_reg_use_chain_create (df
, bb
);
1425 /* Create def-use chains from reaching use bitmaps for basic block BB. */
1427 df_bb_du_chain_create (df
, bb
, ru
)
1432 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
1435 bitmap_copy (ru
, bb_info
->ru_out
);
1437 /* For each def in BB create a linked list (chain) of uses
1438 reached from the def. */
1439 for (insn
= bb
->end
; insn
&& insn
!= PREV_INSN (bb
->head
);
1440 insn
= PREV_INSN (insn
))
1442 struct df_link
*def_link
;
1443 struct df_link
*use_link
;
1444 unsigned int uid
= INSN_UID (insn
);
1446 if (! INSN_P (insn
))
1449 /* For each def in insn... */
1450 for (def_link
= df
->insns
[uid
].defs
; def_link
; def_link
= def_link
->next
)
1452 struct ref
*def
= def_link
->ref
;
1453 unsigned int dregno
= DF_REF_REGNO (def
);
1455 DF_REF_CHAIN (def
) = 0;
1457 /* While the reg-use chains are not essential, it
1458 is _much_ faster to search these short lists rather
1459 than all the reaching uses, especially for large functions. */
1460 for (use_link
= df
->regs
[dregno
].uses
; use_link
;
1461 use_link
= use_link
->next
)
1463 struct ref
*use
= use_link
->ref
;
1465 if (bitmap_bit_p (ru
, DF_REF_ID (use
)))
1468 = df_link_create (use
, DF_REF_CHAIN (def
));
1470 bitmap_clear_bit (ru
, DF_REF_ID (use
));
1475 /* For each use in insn... */
1476 for (use_link
= df
->insns
[uid
].uses
; use_link
; use_link
= use_link
->next
)
1478 struct ref
*use
= use_link
->ref
;
1479 bitmap_set_bit (ru
, DF_REF_ID (use
));
1485 /* Create def-use chains from reaching use bitmaps for basic blocks
1488 df_du_chain_create (df
, blocks
)
1495 ru
= BITMAP_XMALLOC ();
1497 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
1499 df_bb_du_chain_create (df
, bb
, ru
);
1506 /* Create use-def chains from reaching def bitmaps for basic block BB. */
1508 df_bb_ud_chain_create (df
, bb
)
1512 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
1513 struct ref
**reg_def_last
= df
->reg_def_last
;
1516 memset (reg_def_last
, 0, df
->n_regs
* sizeof (struct ref
*));
1518 /* For each use in BB create a linked list (chain) of defs
1519 that reach the use. */
1520 for (insn
= bb
->head
; insn
&& insn
!= NEXT_INSN (bb
->end
);
1521 insn
= NEXT_INSN (insn
))
1523 unsigned int uid
= INSN_UID (insn
);
1524 struct df_link
*use_link
;
1525 struct df_link
*def_link
;
1527 if (! INSN_P (insn
))
1530 /* For each use in insn... */
1531 for (use_link
= df
->insns
[uid
].uses
; use_link
; use_link
= use_link
->next
)
1533 struct ref
*use
= use_link
->ref
;
1534 unsigned int regno
= DF_REF_REGNO (use
);
1536 DF_REF_CHAIN (use
) = 0;
1538 /* Has regno been defined in this BB yet? If so, use
1539 the last def as the single entry for the use-def
1540 chain for this use. Otherwise, we need to add all
1541 the defs using this regno that reach the start of
1543 if (reg_def_last
[regno
])
1546 = df_link_create (reg_def_last
[regno
], 0);
1550 /* While the reg-def chains are not essential, it is
1551 _much_ faster to search these short lists rather than
1552 all the reaching defs, especially for large
1554 for (def_link
= df
->regs
[regno
].defs
; def_link
;
1555 def_link
= def_link
->next
)
1557 struct ref
*def
= def_link
->ref
;
1559 if (bitmap_bit_p (bb_info
->rd_in
, DF_REF_ID (def
)))
1562 = df_link_create (def
, DF_REF_CHAIN (use
));
1569 /* For each def in insn...record the last def of each reg. */
1570 for (def_link
= df
->insns
[uid
].defs
; def_link
; def_link
= def_link
->next
)
1572 struct ref
*def
= def_link
->ref
;
1573 int dregno
= DF_REF_REGNO (def
);
1575 reg_def_last
[dregno
] = def
;
1581 /* Create use-def chains from reaching def bitmaps for basic blocks
1584 df_ud_chain_create (df
, blocks
)
1590 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
1592 df_bb_ud_chain_create (df
, bb
);
1599 df_rd_transfer_function (bb
, changed
, in
, out
, gen
, kill
, data
)
1600 int bb ATTRIBUTE_UNUSED
;
1602 bitmap in
, out
, gen
, kill
;
1603 void *data ATTRIBUTE_UNUSED
;
1605 *changed
= bitmap_union_of_diff (out
, gen
, in
, kill
);
1608 df_ru_transfer_function (bb
, changed
, in
, out
, gen
, kill
, data
)
1609 int bb ATTRIBUTE_UNUSED
;
1611 bitmap in
, out
, gen
, kill
;
1612 void *data ATTRIBUTE_UNUSED
;
1614 *changed
= bitmap_union_of_diff (in
, gen
, out
, kill
);
1618 df_lr_transfer_function (bb
, changed
, in
, out
, use
, def
, data
)
1619 int bb ATTRIBUTE_UNUSED
;
1621 bitmap in
, out
, use
, def
;
1622 void *data ATTRIBUTE_UNUSED
;
1624 *changed
= bitmap_union_of_diff (in
, use
, out
, def
);
1628 /* Compute local reaching def info for basic block BB. */
1630 df_bb_rd_local_compute (df
, bb
)
1634 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
1637 for (insn
= bb
->head
; insn
&& insn
!= NEXT_INSN (bb
->end
);
1638 insn
= NEXT_INSN (insn
))
1640 unsigned int uid
= INSN_UID (insn
);
1641 struct df_link
*def_link
;
1643 if (! INSN_P (insn
))
1646 for (def_link
= df
->insns
[uid
].defs
; def_link
; def_link
= def_link
->next
)
1648 struct ref
*def
= def_link
->ref
;
1649 unsigned int regno
= DF_REF_REGNO (def
);
1650 struct df_link
*def2_link
;
1652 for (def2_link
= df
->regs
[regno
].defs
; def2_link
;
1653 def2_link
= def2_link
->next
)
1655 struct ref
*def2
= def2_link
->ref
;
1657 /* Add all defs of this reg to the set of kills. This
1658 is greedy since many of these defs will not actually
1659 be killed by this BB but it keeps things a lot
1661 bitmap_set_bit (bb_info
->rd_kill
, DF_REF_ID (def2
));
1663 /* Zap from the set of gens for this BB. */
1664 bitmap_clear_bit (bb_info
->rd_gen
, DF_REF_ID (def2
));
1667 bitmap_set_bit (bb_info
->rd_gen
, DF_REF_ID (def
));
1671 bb_info
->rd_valid
= 1;
1675 /* Compute local reaching def info for each basic block within BLOCKS. */
1677 df_rd_local_compute (df
, blocks
)
1683 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
1685 df_bb_rd_local_compute (df
, bb
);
1690 /* Compute local reaching use (upward exposed use) info for basic
1693 df_bb_ru_local_compute (df
, bb
)
1697 /* This is much more tricky than computing reaching defs. With
1698 reaching defs, defs get killed by other defs. With upwards
1699 exposed uses, these get killed by defs with the same regno. */
1701 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
1705 for (insn
= bb
->end
; insn
&& insn
!= PREV_INSN (bb
->head
);
1706 insn
= PREV_INSN (insn
))
1708 unsigned int uid
= INSN_UID (insn
);
1709 struct df_link
*def_link
;
1710 struct df_link
*use_link
;
1712 if (! INSN_P (insn
))
1715 for (def_link
= df
->insns
[uid
].defs
; def_link
; def_link
= def_link
->next
)
1717 struct ref
*def
= def_link
->ref
;
1718 unsigned int dregno
= DF_REF_REGNO (def
);
1720 for (use_link
= df
->regs
[dregno
].uses
; use_link
;
1721 use_link
= use_link
->next
)
1723 struct ref
*use
= use_link
->ref
;
1725 /* Add all uses of this reg to the set of kills. This
1726 is greedy since many of these uses will not actually
1727 be killed by this BB but it keeps things a lot
1729 bitmap_set_bit (bb_info
->ru_kill
, DF_REF_ID (use
));
1731 /* Zap from the set of gens for this BB. */
1732 bitmap_clear_bit (bb_info
->ru_gen
, DF_REF_ID (use
));
1736 for (use_link
= df
->insns
[uid
].uses
; use_link
; use_link
= use_link
->next
)
1738 struct ref
*use
= use_link
->ref
;
1739 /* Add use to set of gens in this BB. */
1740 bitmap_set_bit (bb_info
->ru_gen
, DF_REF_ID (use
));
1743 bb_info
->ru_valid
= 1;
1747 /* Compute local reaching use (upward exposed use) info for each basic
1748 block within BLOCKS. */
1750 df_ru_local_compute (df
, blocks
)
1756 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
1758 df_bb_ru_local_compute (df
, bb
);
1763 /* Compute local live variable info for basic block BB. */
1765 df_bb_lr_local_compute (df
, bb
)
1769 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
1772 for (insn
= bb
->end
; insn
&& insn
!= PREV_INSN (bb
->head
);
1773 insn
= PREV_INSN (insn
))
1775 unsigned int uid
= INSN_UID (insn
);
1776 struct df_link
*link
;
1778 if (! INSN_P (insn
))
1781 for (link
= df
->insns
[uid
].defs
; link
; link
= link
->next
)
1783 struct ref
*def
= link
->ref
;
1784 unsigned int dregno
= DF_REF_REGNO (def
);
1786 /* Add def to set of defs in this BB. */
1787 bitmap_set_bit (bb_info
->lr_def
, dregno
);
1789 bitmap_clear_bit (bb_info
->lr_use
, dregno
);
1792 for (link
= df
->insns
[uid
].uses
; link
; link
= link
->next
)
1794 struct ref
*use
= link
->ref
;
1795 /* Add use to set of uses in this BB. */
1796 bitmap_set_bit (bb_info
->lr_use
, DF_REF_REGNO (use
));
1799 bb_info
->lr_valid
= 1;
1803 /* Compute local live variable info for each basic block within BLOCKS. */
1805 df_lr_local_compute (df
, blocks
)
1811 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
1813 df_bb_lr_local_compute (df
, bb
);
1818 /* Compute register info: lifetime, bb, and number of defs and uses
1819 for basic block BB. */
1821 df_bb_reg_info_compute (df
, bb
, live
)
1826 struct reg_info
*reg_info
= df
->regs
;
1827 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
1830 bitmap_copy (live
, bb_info
->lr_out
);
1832 for (insn
= bb
->end
; insn
&& insn
!= PREV_INSN (bb
->head
);
1833 insn
= PREV_INSN (insn
))
1835 unsigned int uid
= INSN_UID (insn
);
1837 struct df_link
*link
;
1839 if (! INSN_P (insn
))
1842 for (link
= df
->insns
[uid
].defs
; link
; link
= link
->next
)
1844 struct ref
*def
= link
->ref
;
1845 unsigned int dregno
= DF_REF_REGNO (def
);
1847 /* Kill this register. */
1848 bitmap_clear_bit (live
, dregno
);
1849 reg_info
[dregno
].n_defs
++;
1852 for (link
= df
->insns
[uid
].uses
; link
; link
= link
->next
)
1854 struct ref
*use
= link
->ref
;
1855 unsigned int uregno
= DF_REF_REGNO (use
);
1857 /* This register is now live. */
1858 bitmap_set_bit (live
, uregno
);
1859 reg_info
[uregno
].n_uses
++;
1862 /* Increment lifetimes of all live registers. */
1863 EXECUTE_IF_SET_IN_BITMAP (live
, 0, regno
,
1865 reg_info
[regno
].lifetime
++;
1871 /* Compute register info: lifetime, bb, and number of defs and uses. */
1873 df_reg_info_compute (df
, blocks
)
1880 live
= BITMAP_XMALLOC ();
1882 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
1884 df_bb_reg_info_compute (df
, bb
, live
);
1887 BITMAP_XFREE (live
);
1891 /* Assign LUIDs for BB. */
1893 df_bb_luids_set (df
, bb
)
1900 /* The LUIDs are monotonically increasing for each basic block. */
1902 for (insn
= bb
->head
; ; insn
= NEXT_INSN (insn
))
1905 DF_INSN_LUID (df
, insn
) = luid
++;
1906 DF_INSN_LUID (df
, insn
) = luid
;
1908 if (insn
== bb
->end
)
1915 /* Assign LUIDs for each basic block within BLOCKS. */
1917 df_luids_set (df
, blocks
)
1924 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
1926 total
+= df_bb_luids_set (df
, bb
);
1932 /* Perform dataflow analysis using existing DF structure for blocks
1933 within BLOCKS. If BLOCKS is zero, use all basic blocks in the CFG. */
1935 df_analyse_1 (df
, blocks
, flags
, update
)
1946 if (flags
& DF_UD_CHAIN
)
1947 aflags
|= DF_RD
| DF_RD_CHAIN
;
1949 if (flags
& DF_DU_CHAIN
)
1953 aflags
|= DF_RU_CHAIN
;
1955 if (flags
& DF_REG_INFO
)
1959 blocks
= df
->all_blocks
;
1964 df_refs_update (df
);
1965 /* More fine grained incremental dataflow analysis would be
1966 nice. For now recompute the whole shebang for the
1969 df_refs_unlink (df
, blocks
);
1971 /* All the def-use, use-def chains can be potentially
1972 modified by changes in one block. The size of the
1973 bitmaps can also change. */
1977 /* Scan the function for all register defs and uses. */
1979 df_refs_record (df
, blocks
);
1981 /* Link all the new defs and uses to the insns. */
1982 df_refs_process (df
);
1985 /* Allocate the bitmaps now the total number of defs and uses are
1986 known. If the number of defs or uses have changed, then
1987 these bitmaps need to be reallocated. */
1988 df_bitmaps_alloc (df
, aflags
);
1990 /* Set the LUIDs for each specified basic block. */
1991 df_luids_set (df
, blocks
);
1993 /* Recreate reg-def and reg-use chains from scratch so that first
1994 def is at the head of the reg-def chain and the last use is at
1995 the head of the reg-use chain. This is only important for
1996 regs local to a basic block as it speeds up searching. */
1997 if (aflags
& DF_RD_CHAIN
)
1999 df_reg_def_chain_create (df
, blocks
);
2002 if (aflags
& DF_RU_CHAIN
)
2004 df_reg_use_chain_create (df
, blocks
);
2007 df
->dfs_order
= xmalloc (sizeof(int) * n_basic_blocks
);
2008 df
->rc_order
= xmalloc (sizeof(int) * n_basic_blocks
);
2009 df
->rts_order
= xmalloc (sizeof(int) * n_basic_blocks
);
2010 df
->inverse_dfs_map
= xmalloc (sizeof(int) * n_basic_blocks
);
2011 df
->inverse_rc_map
= xmalloc (sizeof(int) * n_basic_blocks
);
2012 df
->inverse_rts_map
= xmalloc (sizeof(int) * n_basic_blocks
);
2014 flow_depth_first_order_compute (df
->dfs_order
, df
->rc_order
);
2015 flow_reverse_top_sort_order_compute (df
->rts_order
);
2016 for (i
= 0; i
< n_basic_blocks
; i
++)
2018 df
->inverse_dfs_map
[df
->dfs_order
[i
]] = i
;
2019 df
->inverse_rc_map
[df
->rc_order
[i
]] = i
;
2020 df
->inverse_rts_map
[df
->rts_order
[i
]] = i
;
2024 /* Compute the sets of gens and kills for the defs of each bb. */
2025 df_rd_local_compute (df
, df
->flags
& DF_RD
? blocks
: df
->all_blocks
);
2028 bitmap
*in
= xmalloc (sizeof (bitmap
) * n_basic_blocks
);
2029 bitmap
*out
= xmalloc (sizeof (bitmap
) * n_basic_blocks
);
2030 bitmap
*gen
= xmalloc (sizeof (bitmap
) * n_basic_blocks
);
2031 bitmap
*kill
= xmalloc (sizeof (bitmap
) * n_basic_blocks
);
2032 for (i
= 0; i
< n_basic_blocks
; i
++)
2034 in
[i
] = DF_BB_INFO (df
, BASIC_BLOCK (i
))->rd_in
;
2035 out
[i
] = DF_BB_INFO (df
, BASIC_BLOCK (i
))->rd_out
;
2036 gen
[i
] = DF_BB_INFO (df
, BASIC_BLOCK (i
))->rd_gen
;
2037 kill
[i
] = DF_BB_INFO (df
, BASIC_BLOCK (i
))->rd_kill
;
2039 iterative_dataflow_bitmap (in
, out
, gen
, kill
, df
->all_blocks
,
2040 FORWARD
, UNION
, df_rd_transfer_function
,
2041 df
->inverse_rc_map
, NULL
);
2049 if (aflags
& DF_UD_CHAIN
)
2051 /* Create use-def chains. */
2052 df_ud_chain_create (df
, df
->all_blocks
);
2054 if (! (flags
& DF_RD
))
2060 /* Compute the sets of gens and kills for the upwards exposed
2062 df_ru_local_compute (df
, df
->flags
& DF_RU
? blocks
: df
->all_blocks
);
2065 bitmap
*in
= xmalloc (sizeof (bitmap
) * n_basic_blocks
);
2066 bitmap
*out
= xmalloc (sizeof (bitmap
) * n_basic_blocks
);
2067 bitmap
*gen
= xmalloc (sizeof (bitmap
) * n_basic_blocks
);
2068 bitmap
*kill
= xmalloc (sizeof (bitmap
) * n_basic_blocks
);
2069 for (i
= 0; i
< n_basic_blocks
; i
++)
2071 in
[i
] = DF_BB_INFO (df
, BASIC_BLOCK (i
))->ru_in
;
2072 out
[i
] = DF_BB_INFO (df
, BASIC_BLOCK (i
))->ru_out
;
2073 gen
[i
] = DF_BB_INFO (df
, BASIC_BLOCK (i
))->ru_gen
;
2074 kill
[i
] = DF_BB_INFO (df
, BASIC_BLOCK (i
))->ru_kill
;
2076 iterative_dataflow_bitmap (in
, out
, gen
, kill
, df
->all_blocks
,
2077 BACKWARD
, UNION
, df_ru_transfer_function
,
2078 df
->inverse_rts_map
, NULL
);
2086 if (aflags
& DF_DU_CHAIN
)
2088 /* Create def-use chains. */
2089 df_du_chain_create (df
, df
->all_blocks
);
2091 if (! (flags
& DF_RU
))
2095 /* Free up bitmaps that are no longer required. */
2097 df_bitmaps_free (df
, dflags
);
2101 /* Compute the sets of defs and uses of live variables. */
2102 df_lr_local_compute (df
, df
->flags
& DF_LR
? blocks
: df
->all_blocks
);
2105 bitmap
*in
= xmalloc (sizeof (bitmap
) * n_basic_blocks
);
2106 bitmap
*out
= xmalloc (sizeof (bitmap
) * n_basic_blocks
);
2107 bitmap
*use
= xmalloc (sizeof (bitmap
) * n_basic_blocks
);
2108 bitmap
*def
= xmalloc (sizeof (bitmap
) * n_basic_blocks
);
2109 for (i
= 0; i
< n_basic_blocks
; i
++)
2111 in
[i
] = DF_BB_INFO (df
, BASIC_BLOCK (i
))->lr_in
;
2112 out
[i
] = DF_BB_INFO (df
, BASIC_BLOCK (i
))->lr_out
;
2113 use
[i
] = DF_BB_INFO (df
, BASIC_BLOCK (i
))->lr_use
;
2114 def
[i
] = DF_BB_INFO (df
, BASIC_BLOCK (i
))->lr_def
;
2116 iterative_dataflow_bitmap (in
, out
, use
, def
, df
->all_blocks
,
2117 BACKWARD
, UNION
, df_lr_transfer_function
,
2118 df
->inverse_rts_map
, NULL
);
2126 if (aflags
& DF_REG_INFO
)
2128 df_reg_info_compute (df
, df
->all_blocks
);
2130 free (df
->dfs_order
);
2131 free (df
->rc_order
);
2132 free (df
->rts_order
);
2133 free (df
->inverse_rc_map
);
2134 free (df
->inverse_dfs_map
);
2135 free (df
->inverse_rts_map
);
2139 /* Initialise dataflow analysis. */
2145 df
= xcalloc (1, sizeof (struct df
));
2147 /* Squirrel away a global for debugging. */
2154 /* Start queuing refs. */
2159 df
->def_id_save
= df
->def_id
;
2160 df
->use_id_save
= df
->use_id
;
2161 /* ???? Perhaps we should save current obstack state so that we can
2167 /* Process queued refs. */
2169 df_refs_process (df
)
2174 /* Build new insn-def chains. */
2175 for (i
= df
->def_id_save
; i
!= df
->def_id
; i
++)
2177 struct ref
*def
= df
->defs
[i
];
2178 unsigned int uid
= DF_REF_INSN_UID (def
);
2180 /* Add def to head of def list for INSN. */
2182 = df_link_create (def
, df
->insns
[uid
].defs
);
2185 /* Build new insn-use chains. */
2186 for (i
= df
->use_id_save
; i
!= df
->use_id
; i
++)
2188 struct ref
*use
= df
->uses
[i
];
2189 unsigned int uid
= DF_REF_INSN_UID (use
);
2191 /* Add use to head of use list for INSN. */
2193 = df_link_create (use
, df
->insns
[uid
].uses
);
2199 /* Update refs for basic block BB. */
2201 df_bb_refs_update (df
, bb
)
2208 /* While we have to scan the chain of insns for this BB, we don't
2209 need to allocate and queue a long chain of BB/INSN pairs. Using
2210 a bitmap for insns_modified saves memory and avoids queuing
2213 for (insn
= bb
->head
; ; insn
= NEXT_INSN (insn
))
2217 uid
= INSN_UID (insn
);
2219 if (bitmap_bit_p (df
->insns_modified
, uid
))
2221 /* Delete any allocated refs of this insn. MPH, FIXME. */
2222 df_insn_refs_unlink (df
, bb
, insn
);
2224 /* Scan the insn for refs. */
2225 df_insn_refs_record (df
, bb
, insn
);
2228 bitmap_clear_bit (df
->insns_modified
, uid
);
2231 if (insn
== bb
->end
)
2238 /* Process all the modified/deleted insns that were queued. */
2246 if ((unsigned int)max_reg_num () >= df
->reg_size
)
2247 df_reg_table_realloc (df
, 0);
2251 FOR_EACH_BB_IN_BITMAP (df
->bbs_modified
, 0, bb
,
2253 count
+= df_bb_refs_update (df
, bb
);
2256 df_refs_process (df
);
2261 /* Return non-zero if any of the requested blocks in the bitmap
2262 BLOCKS have been modified. */
2264 df_modified_p (df
, blocks
)
2271 for (j
= 0; j
< df
->n_bbs
; j
++)
2272 if (bitmap_bit_p (df
->bbs_modified
, j
)
2273 && (! blocks
|| (blocks
== (bitmap
) -1) || bitmap_bit_p (blocks
, j
)))
2283 /* Analyse dataflow info for the basic blocks specified by the bitmap
2284 BLOCKS, or for the whole CFG if BLOCKS is zero, or just for the
2285 modified blocks if BLOCKS is -1. */
2287 df_analyse (df
, blocks
, flags
)
2294 /* We could deal with additional basic blocks being created by
2295 rescanning everything again. */
2296 if (df
->n_bbs
&& df
->n_bbs
!= (unsigned int)n_basic_blocks
)
2299 update
= df_modified_p (df
, blocks
);
2300 if (update
|| (flags
!= df
->flags
))
2306 /* Recompute everything from scratch. */
2309 /* Allocate and initialise data structures. */
2310 df_alloc (df
, max_reg_num ());
2311 df_analyse_1 (df
, 0, flags
, 0);
2316 if (blocks
== (bitmap
) -1)
2317 blocks
= df
->bbs_modified
;
2322 df_analyse_1 (df
, blocks
, flags
, 1);
2323 bitmap_zero (df
->bbs_modified
);
2330 /* Free all the dataflow info and the DF structure. */
2340 /* Unlink INSN from its reference information. */
2342 df_insn_refs_unlink (df
, bb
, insn
)
2344 basic_block bb ATTRIBUTE_UNUSED
;
2347 struct df_link
*link
;
2350 uid
= INSN_UID (insn
);
2352 /* Unlink all refs defined by this insn. */
2353 for (link
= df
->insns
[uid
].defs
; link
; link
= link
->next
)
2354 df_def_unlink (df
, link
->ref
);
2356 /* Unlink all refs used by this insn. */
2357 for (link
= df
->insns
[uid
].uses
; link
; link
= link
->next
)
2358 df_use_unlink (df
, link
->ref
);
2360 df
->insns
[uid
].defs
= 0;
2361 df
->insns
[uid
].uses
= 0;
2366 /* Unlink all the insns within BB from their reference information. */
2368 df_bb_refs_unlink (df
, bb
)
2374 /* Scan the block an insn at a time from beginning to end. */
2375 for (insn
= bb
->head
; ; insn
= NEXT_INSN (insn
))
2379 /* Unlink refs for INSN. */
2380 df_insn_refs_unlink (df
, bb
, insn
);
2382 if (insn
== bb
->end
)
2388 /* Unlink all the refs in the basic blocks specified by BLOCKS.
2389 Not currently used. */
2391 df_refs_unlink (df
, blocks
)
2399 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
2401 df_bb_refs_unlink (df
, bb
);
2408 df_bb_refs_unlink (df
, bb
);
2414 /* Functions to modify insns. */
2417 /* Delete INSN and all its reference information. */
2419 df_insn_delete (df
, bb
, insn
)
2421 basic_block bb ATTRIBUTE_UNUSED
;
2424 /* If the insn is a jump, we should perhaps call delete_insn to
2425 handle the JUMP_LABEL? */
2427 /* We should not be deleting the NOTE_INSN_BASIC_BLOCK or label. */
2428 if (insn
== bb
->head
)
2431 /* Delete the insn. */
2434 df_insn_modify (df
, bb
, insn
);
2436 return NEXT_INSN (insn
);
2440 /* Mark that INSN within BB may have changed (created/modified/deleted).
2441 This may be called multiple times for the same insn. There is no
2442 harm calling this function if the insn wasn't changed; it will just
2443 slow down the rescanning of refs. */
2445 df_insn_modify (df
, bb
, insn
)
2452 uid
= INSN_UID (insn
);
2454 if (uid
>= df
->insn_size
)
2455 df_insn_table_realloc (df
, 0);
2457 bitmap_set_bit (df
->bbs_modified
, bb
->index
);
2458 bitmap_set_bit (df
->insns_modified
, uid
);
2460 /* For incremental updating on the fly, perhaps we could make a copy
2461 of all the refs of the original insn and turn them into
2462 anti-refs. When df_refs_update finds these anti-refs, it annihilates
2463 the original refs. If validate_change fails then these anti-refs
2464 will just get ignored. */
2468 typedef struct replace_args
2477 /* Replace mem pointed to by PX with its associated pseudo register.
2478 DATA is actually a pointer to a structure describing the
2479 instruction currently being scanned and the MEM we are currently
2482 df_rtx_mem_replace (px
, data
)
2486 replace_args
*args
= (replace_args
*) data
;
2489 if (mem
== NULL_RTX
)
2492 switch (GET_CODE (mem
))
2498 /* We're not interested in the MEM associated with a
2499 CONST_DOUBLE, so there's no need to traverse into one. */
2503 /* This is not a MEM. */
2507 if (!rtx_equal_p (args
->match
, mem
))
2508 /* This is not the MEM we are currently replacing. */
2511 /* Actually replace the MEM. */
2512 validate_change (args
->insn
, px
, args
->replacement
, 1);
2520 df_insn_mem_replace (df
, bb
, insn
, mem
, reg
)
2531 args
.replacement
= reg
;
2534 /* Seach and replace all matching mems within insn. */
2535 for_each_rtx (&insn
, df_rtx_mem_replace
, &args
);
2538 df_insn_modify (df
, bb
, insn
);
2540 /* ???? FIXME. We may have a new def or one or more new uses of REG
2541 in INSN. REG should be a new pseudo so it won't affect the
2542 dataflow information that we currently have. We should add
2543 the new uses and defs to INSN and then recreate the chains
2544 when df_analyse is called. */
2545 return args
.modified
;
2549 /* Replace one register with another. Called through for_each_rtx; PX
2550 points to the rtx being scanned. DATA is actually a pointer to a
2551 structure of arguments. */
2553 df_rtx_reg_replace (px
, data
)
2558 replace_args
*args
= (replace_args
*) data
;
2563 if (x
== args
->match
)
2565 validate_change (args
->insn
, px
, args
->replacement
, 1);
2573 /* Replace the reg within every ref on CHAIN that is within the set
2574 BLOCKS of basic blocks with NEWREG. Also update the regs within
2577 df_refs_reg_replace (df
, blocks
, chain
, oldreg
, newreg
)
2580 struct df_link
*chain
;
2584 struct df_link
*link
;
2588 blocks
= df
->all_blocks
;
2590 args
.match
= oldreg
;
2591 args
.replacement
= newreg
;
2594 for (link
= chain
; link
; link
= link
->next
)
2596 struct ref
*ref
= link
->ref
;
2597 rtx insn
= DF_REF_INSN (ref
);
2599 if (! INSN_P (insn
))
2602 if (bitmap_bit_p (blocks
, DF_REF_BBNO (ref
)))
2604 df_ref_reg_replace (df
, ref
, oldreg
, newreg
);
2606 /* Replace occurrences of the reg within the REG_NOTES. */
2607 if ((! link
->next
|| DF_REF_INSN (ref
)
2608 != DF_REF_INSN (link
->next
->ref
))
2609 && REG_NOTES (insn
))
2612 for_each_rtx (®_NOTES (insn
), df_rtx_reg_replace
, &args
);
2617 /* Temporary check to ensure that we have a grip on which
2618 regs should be replaced. */
2625 /* Replace all occurrences of register OLDREG with register NEWREG in
2626 blocks defined by bitmap BLOCKS. This also replaces occurrences of
2627 OLDREG in the REG_NOTES but only for insns containing OLDREG. This
2628 routine expects the reg-use and reg-def chains to be valid. */
2630 df_reg_replace (df
, blocks
, oldreg
, newreg
)
2636 unsigned int oldregno
= REGNO (oldreg
);
2638 df_refs_reg_replace (df
, blocks
, df
->regs
[oldregno
].defs
, oldreg
, newreg
);
2639 df_refs_reg_replace (df
, blocks
, df
->regs
[oldregno
].uses
, oldreg
, newreg
);
2644 /* Try replacing the reg within REF with NEWREG. Do not modify
2645 def-use/use-def chains. */
2647 df_ref_reg_replace (df
, ref
, oldreg
, newreg
)
2653 /* Check that insn was deleted by being converted into a NOTE. If
2654 so ignore this insn. */
2655 if (! INSN_P (DF_REF_INSN (ref
)))
2658 if (oldreg
&& oldreg
!= DF_REF_REG (ref
))
2661 if (! validate_change (DF_REF_INSN (ref
), DF_REF_LOC (ref
), newreg
, 1))
2664 df_insn_modify (df
, DF_REF_BB (ref
), DF_REF_INSN (ref
));
2670 df_bb_def_use_swap (df
, bb
, def_insn
, use_insn
, regno
)
2681 struct df_link
*link
;
2683 def
= df_bb_insn_regno_first_def_find (df
, bb
, def_insn
, regno
);
2687 use
= df_bb_insn_regno_last_use_find (df
, bb
, use_insn
, regno
);
2691 /* The USE no longer exists. */
2692 use_uid
= INSN_UID (use_insn
);
2693 df_use_unlink (df
, use
);
2694 df_ref_unlink (&df
->insns
[use_uid
].uses
, use
);
2696 /* The DEF requires shifting so remove it from DEF_INSN
2697 and add it to USE_INSN by reusing LINK. */
2698 def_uid
= INSN_UID (def_insn
);
2699 link
= df_ref_unlink (&df
->insns
[def_uid
].defs
, def
);
2701 link
->next
= df
->insns
[use_uid
].defs
;
2702 df
->insns
[use_uid
].defs
= link
;
2705 link
= df_ref_unlink (&df
->regs
[regno
].defs
, def
);
2707 link
->next
= df
->regs
[regno
].defs
;
2708 df
->insns
[regno
].defs
= link
;
2711 DF_REF_INSN (def
) = use_insn
;
2716 /* Record df between FIRST_INSN and LAST_INSN inclusive. All new
2717 insns must be processed by this routine. */
2719 df_insns_modify (df
, bb
, first_insn
, last_insn
)
2727 for (insn
= first_insn
; ; insn
= NEXT_INSN (insn
))
2731 /* A non-const call should not have slipped through the net. If
2732 it does, we need to create a new basic block. Ouch. The
2733 same applies for a label. */
2734 if ((GET_CODE (insn
) == CALL_INSN
2735 && ! CONST_OR_PURE_CALL_P (insn
))
2736 || GET_CODE (insn
) == CODE_LABEL
)
2739 uid
= INSN_UID (insn
);
2741 if (uid
>= df
->insn_size
)
2742 df_insn_table_realloc (df
, 0);
2744 df_insn_modify (df
, bb
, insn
);
2746 if (insn
== last_insn
)
2752 /* Emit PATTERN before INSN within BB. */
2754 df_pattern_emit_before (df
, pattern
, bb
, insn
)
2755 struct df
*df ATTRIBUTE_UNUSED
;
2761 rtx prev_insn
= PREV_INSN (insn
);
2763 /* We should not be inserting before the start of the block. */
2764 if (insn
== bb
->head
)
2766 ret_insn
= emit_insn_before (pattern
, insn
);
2767 if (ret_insn
== insn
)
2770 df_insns_modify (df
, bb
, NEXT_INSN (prev_insn
), ret_insn
);
2775 /* Emit PATTERN after INSN within BB. */
2777 df_pattern_emit_after (df
, pattern
, bb
, insn
)
2785 ret_insn
= emit_insn_after (pattern
, insn
);
2786 if (ret_insn
== insn
)
2789 df_insns_modify (df
, bb
, NEXT_INSN (insn
), ret_insn
);
2794 /* Emit jump PATTERN after INSN within BB. */
2796 df_jump_pattern_emit_after (df
, pattern
, bb
, insn
)
2804 ret_insn
= emit_jump_insn_after (pattern
, insn
);
2805 if (ret_insn
== insn
)
2808 df_insns_modify (df
, bb
, NEXT_INSN (insn
), ret_insn
);
2813 /* Move INSN within BB before BEFORE_INSN within BEFORE_BB.
2815 This function should only be used to move loop invariant insns
2816 out of a loop where it has been proven that the def-use info
2817 will still be valid. */
2819 df_insn_move_before (df
, bb
, insn
, before_bb
, before_insn
)
2823 basic_block before_bb
;
2826 struct df_link
*link
;
2830 return df_pattern_emit_before (df
, insn
, before_bb
, before_insn
);
2832 uid
= INSN_UID (insn
);
2834 /* Change bb for all df defined and used by this insn. */
2835 for (link
= df
->insns
[uid
].defs
; link
; link
= link
->next
)
2836 DF_REF_BB (link
->ref
) = before_bb
;
2837 for (link
= df
->insns
[uid
].uses
; link
; link
= link
->next
)
2838 DF_REF_BB (link
->ref
) = before_bb
;
2840 /* The lifetimes of the registers used in this insn will be reduced
2841 while the lifetimes of the registers defined in this insn
2842 are likely to be increased. */
2844 /* ???? Perhaps all the insns moved should be stored on a list
2845 which df_analyse removes when it recalculates data flow. */
2847 return emit_insn_before (insn
, before_insn
);
2850 /* Functions to query dataflow information. */
2854 df_insn_regno_def_p (df
, bb
, insn
, regno
)
2856 basic_block bb ATTRIBUTE_UNUSED
;
2861 struct df_link
*link
;
2863 uid
= INSN_UID (insn
);
2865 for (link
= df
->insns
[uid
].defs
; link
; link
= link
->next
)
2867 struct ref
*def
= link
->ref
;
2869 if (DF_REF_REGNO (def
) == regno
)
2878 df_def_dominates_all_uses_p (df
, def
)
2879 struct df
*df ATTRIBUTE_UNUSED
;
2882 struct df_link
*du_link
;
2884 /* Follow def-use chain to find all the uses of this def. */
2885 for (du_link
= DF_REF_CHAIN (def
); du_link
; du_link
= du_link
->next
)
2887 struct ref
*use
= du_link
->ref
;
2888 struct df_link
*ud_link
;
2890 /* Follow use-def chain to check all the defs for this use. */
2891 for (ud_link
= DF_REF_CHAIN (use
); ud_link
; ud_link
= ud_link
->next
)
2892 if (ud_link
->ref
!= def
)
2900 df_insn_dominates_all_uses_p (df
, bb
, insn
)
2902 basic_block bb ATTRIBUTE_UNUSED
;
2906 struct df_link
*link
;
2908 uid
= INSN_UID (insn
);
2910 for (link
= df
->insns
[uid
].defs
; link
; link
= link
->next
)
2912 struct ref
*def
= link
->ref
;
2914 if (! df_def_dominates_all_uses_p (df
, def
))
2922 /* Return non-zero if all DF dominates all the uses within the bitmap
2925 df_def_dominates_uses_p (df
, def
, blocks
)
2926 struct df
*df ATTRIBUTE_UNUSED
;
2930 struct df_link
*du_link
;
2932 /* Follow def-use chain to find all the uses of this def. */
2933 for (du_link
= DF_REF_CHAIN (def
); du_link
; du_link
= du_link
->next
)
2935 struct ref
*use
= du_link
->ref
;
2936 struct df_link
*ud_link
;
2938 /* Only worry about the uses within BLOCKS. For example,
2939 consider a register defined within a loop that is live at the
2941 if (bitmap_bit_p (blocks
, DF_REF_BBNO (use
)))
2943 /* Follow use-def chain to check all the defs for this use. */
2944 for (ud_link
= DF_REF_CHAIN (use
); ud_link
; ud_link
= ud_link
->next
)
2945 if (ud_link
->ref
!= def
)
2953 /* Return non-zero if all the defs of INSN within BB dominates
2954 all the corresponding uses. */
2956 df_insn_dominates_uses_p (df
, bb
, insn
, blocks
)
2958 basic_block bb ATTRIBUTE_UNUSED
;
2963 struct df_link
*link
;
2965 uid
= INSN_UID (insn
);
2967 for (link
= df
->insns
[uid
].defs
; link
; link
= link
->next
)
2969 struct ref
*def
= link
->ref
;
2971 /* Only consider the defs within BLOCKS. */
2972 if (bitmap_bit_p (blocks
, DF_REF_BBNO (def
))
2973 && ! df_def_dominates_uses_p (df
, def
, blocks
))
2980 /* Return the basic block that REG referenced in or NULL if referenced
2981 in multiple basic blocks. */
2983 df_regno_bb (df
, regno
)
2987 struct df_link
*defs
= df
->regs
[regno
].defs
;
2988 struct df_link
*uses
= df
->regs
[regno
].uses
;
2989 struct ref
*def
= defs
? defs
->ref
: 0;
2990 struct ref
*use
= uses
? uses
->ref
: 0;
2991 basic_block bb_def
= def
? DF_REF_BB (def
) : 0;
2992 basic_block bb_use
= use
? DF_REF_BB (use
) : 0;
2994 /* Compare blocks of first def and last use. ???? FIXME. What if
2995 the reg-def and reg-use lists are not correctly ordered. */
2996 return bb_def
== bb_use
? bb_def
: 0;
3000 /* Return non-zero if REG used in multiple basic blocks. */
3002 df_reg_global_p (df
, reg
)
3006 return df_regno_bb (df
, REGNO (reg
)) != 0;
3010 /* Return total lifetime (in insns) of REG. */
3012 df_reg_lifetime (df
, reg
)
3016 return df
->regs
[REGNO (reg
)].lifetime
;
3020 /* Return non-zero if REG live at start of BB. */
3022 df_bb_reg_live_start_p (df
, bb
, reg
)
3023 struct df
*df ATTRIBUTE_UNUSED
;
3027 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
3029 #ifdef ENABLE_CHECKING
3030 if (! bb_info
->lr_in
)
3034 return bitmap_bit_p (bb_info
->lr_in
, REGNO (reg
));
3038 /* Return non-zero if REG live at end of BB. */
3040 df_bb_reg_live_end_p (df
, bb
, reg
)
3041 struct df
*df ATTRIBUTE_UNUSED
;
3045 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
3047 #ifdef ENABLE_CHECKING
3048 if (! bb_info
->lr_in
)
3052 return bitmap_bit_p (bb_info
->lr_out
, REGNO (reg
));
3056 /* Return -1 if life of REG1 before life of REG2, 1 if life of REG1
3057 after life of REG2, or 0, if the lives overlap. */
3059 df_bb_regs_lives_compare (df
, bb
, reg1
, reg2
)
3065 unsigned int regno1
= REGNO (reg1
);
3066 unsigned int regno2
= REGNO (reg2
);
3073 /* The regs must be local to BB. */
3074 if (df_regno_bb (df
, regno1
) != bb
3075 || df_regno_bb (df
, regno2
) != bb
)
3078 def2
= df_bb_regno_first_def_find (df
, bb
, regno2
);
3079 use1
= df_bb_regno_last_use_find (df
, bb
, regno1
);
3081 if (DF_INSN_LUID (df
, DF_REF_INSN (def2
))
3082 > DF_INSN_LUID (df
, DF_REF_INSN (use1
)))
3085 def1
= df_bb_regno_first_def_find (df
, bb
, regno1
);
3086 use2
= df_bb_regno_last_use_find (df
, bb
, regno2
);
3088 if (DF_INSN_LUID (df
, DF_REF_INSN (def1
))
3089 > DF_INSN_LUID (df
, DF_REF_INSN (use2
)))
3096 /* Return last use of REGNO within BB. */
3098 df_bb_regno_last_use_find (df
, bb
, regno
)
3100 basic_block bb ATTRIBUTE_UNUSED
;
3103 struct df_link
*link
;
3105 /* This assumes that the reg-use list is ordered such that for any
3106 BB, the last use is found first. However, since the BBs are not
3107 ordered, the first use in the chain is not necessarily the last
3108 use in the function. */
3109 for (link
= df
->regs
[regno
].uses
; link
; link
= link
->next
)
3111 struct ref
*use
= link
->ref
;
3113 if (DF_REF_BB (use
) == bb
)
3120 /* Return first def of REGNO within BB. */
3122 df_bb_regno_first_def_find (df
, bb
, regno
)
3124 basic_block bb ATTRIBUTE_UNUSED
;
3127 struct df_link
*link
;
3129 /* This assumes that the reg-def list is ordered such that for any
3130 BB, the first def is found first. However, since the BBs are not
3131 ordered, the first def in the chain is not necessarily the first
3132 def in the function. */
3133 for (link
= df
->regs
[regno
].defs
; link
; link
= link
->next
)
3135 struct ref
*def
= link
->ref
;
3137 if (DF_REF_BB (def
) == bb
)
3144 /* Return first use of REGNO inside INSN within BB. */
3146 df_bb_insn_regno_last_use_find (df
, bb
, insn
, regno
)
3148 basic_block bb ATTRIBUTE_UNUSED
;
3153 struct df_link
*link
;
3155 uid
= INSN_UID (insn
);
3157 for (link
= df
->insns
[uid
].uses
; link
; link
= link
->next
)
3159 struct ref
*use
= link
->ref
;
3161 if (DF_REF_REGNO (use
) == regno
)
3169 /* Return first def of REGNO inside INSN within BB. */
3171 df_bb_insn_regno_first_def_find (df
, bb
, insn
, regno
)
3173 basic_block bb ATTRIBUTE_UNUSED
;
3178 struct df_link
*link
;
3180 uid
= INSN_UID (insn
);
3182 for (link
= df
->insns
[uid
].defs
; link
; link
= link
->next
)
3184 struct ref
*def
= link
->ref
;
3186 if (DF_REF_REGNO (def
) == regno
)
3194 /* Return insn using REG if the BB contains only a single
3195 use and def of REG. */
3197 df_bb_single_def_use_insn_find (df
, bb
, insn
, reg
)
3205 struct df_link
*du_link
;
3207 def
= df_bb_insn_regno_first_def_find (df
, bb
, insn
, REGNO (reg
));
3212 du_link
= DF_REF_CHAIN (def
);
3219 /* Check if def is dead. */
3223 /* Check for multiple uses. */
3227 return DF_REF_INSN (use
);
3230 /* Functions for debugging/dumping dataflow information. */
3233 /* Dump a def-use or use-def chain for REF to FILE. */
3235 df_chain_dump (link
, file
)
3236 struct df_link
*link
;
3239 fprintf (file
, "{ ");
3240 for (; link
; link
= link
->next
)
3242 fprintf (file
, "%c%d ",
3243 DF_REF_REG_DEF_P (link
->ref
) ? 'd' : 'u',
3244 DF_REF_ID (link
->ref
));
3246 fprintf (file
, "}");
3250 df_chain_dump_regno (link
, file
)
3251 struct df_link
*link
;
3254 fprintf (file
, "{ ");
3255 for (; link
; link
= link
->next
)
3257 fprintf (file
, "%c%d(%d) ",
3258 DF_REF_REG_DEF_P (link
->ref
) ? 'd' : 'u',
3259 DF_REF_ID (link
->ref
),
3260 DF_REF_REGNO (link
->ref
));
3262 fprintf (file
, "}");
3265 /* Dump dataflow info. */
3267 df_dump (df
, flags
, file
)
3278 fprintf (file
, "\nDataflow summary:\n");
3279 fprintf (file
, "n_regs = %d, n_defs = %d, n_uses = %d, n_bbs = %d\n",
3280 df
->n_regs
, df
->n_defs
, df
->n_uses
, df
->n_bbs
);
3284 fprintf (file
, "Reaching defs:\n");
3285 for (i
= 0; i
< df
->n_bbs
; i
++)
3287 basic_block bb
= BASIC_BLOCK (i
);
3288 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
3290 if (! bb_info
->rd_in
)
3293 fprintf (file
, "bb %d in \t", i
);
3294 dump_bitmap (file
, bb_info
->rd_in
);
3295 fprintf (file
, "bb %d gen \t", i
);
3296 dump_bitmap (file
, bb_info
->rd_gen
);
3297 fprintf (file
, "bb %d kill\t", i
);
3298 dump_bitmap (file
, bb_info
->rd_kill
);
3299 fprintf (file
, "bb %d out \t", i
);
3300 dump_bitmap (file
, bb_info
->rd_out
);
3304 if (flags
& DF_UD_CHAIN
)
3306 fprintf (file
, "Use-def chains:\n");
3307 for (j
= 0; j
< df
->n_defs
; j
++)
3311 fprintf (file
, "d%d bb %d luid %d insn %d reg %d ",
3312 j
, DF_REF_BBNO (df
->defs
[j
]),
3313 DF_INSN_LUID (df
, DF_REF_INSN (df
->defs
[j
])),
3314 DF_REF_INSN_UID (df
->defs
[j
]),
3315 DF_REF_REGNO (df
->defs
[j
]));
3316 if (df
->defs
[j
]->flags
& DF_REF_READ_WRITE
)
3317 fprintf (file
, "read/write ");
3318 df_chain_dump (DF_REF_CHAIN (df
->defs
[j
]), file
);
3319 fprintf (file
, "\n");
3326 fprintf (file
, "Reaching uses:\n");
3327 for (i
= 0; i
< df
->n_bbs
; i
++)
3329 basic_block bb
= BASIC_BLOCK (i
);
3330 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
3332 if (! bb_info
->ru_in
)
3335 fprintf (file
, "bb %d in \t", i
);
3336 dump_bitmap (file
, bb_info
->ru_in
);
3337 fprintf (file
, "bb %d gen \t", i
);
3338 dump_bitmap (file
, bb_info
->ru_gen
);
3339 fprintf (file
, "bb %d kill\t", i
);
3340 dump_bitmap (file
, bb_info
->ru_kill
);
3341 fprintf (file
, "bb %d out \t", i
);
3342 dump_bitmap (file
, bb_info
->ru_out
);
3346 if (flags
& DF_DU_CHAIN
)
3348 fprintf (file
, "Def-use chains:\n");
3349 for (j
= 0; j
< df
->n_uses
; j
++)
3353 fprintf (file
, "u%d bb %d luid %d insn %d reg %d ",
3354 j
, DF_REF_BBNO (df
->uses
[j
]),
3355 DF_INSN_LUID (df
, DF_REF_INSN (df
->uses
[j
])),
3356 DF_REF_INSN_UID (df
->uses
[j
]),
3357 DF_REF_REGNO (df
->uses
[j
]));
3358 if (df
->uses
[j
]->flags
& DF_REF_READ_WRITE
)
3359 fprintf (file
, "read/write ");
3360 df_chain_dump (DF_REF_CHAIN (df
->uses
[j
]), file
);
3361 fprintf (file
, "\n");
3368 fprintf (file
, "Live regs:\n");
3369 for (i
= 0; i
< df
->n_bbs
; i
++)
3371 basic_block bb
= BASIC_BLOCK (i
);
3372 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
3374 if (! bb_info
->lr_in
)
3377 fprintf (file
, "bb %d in \t", i
);
3378 dump_bitmap (file
, bb_info
->lr_in
);
3379 fprintf (file
, "bb %d use \t", i
);
3380 dump_bitmap (file
, bb_info
->lr_use
);
3381 fprintf (file
, "bb %d def \t", i
);
3382 dump_bitmap (file
, bb_info
->lr_def
);
3383 fprintf (file
, "bb %d out \t", i
);
3384 dump_bitmap (file
, bb_info
->lr_out
);
3388 if (flags
& (DF_REG_INFO
| DF_RD_CHAIN
| DF_RU_CHAIN
))
3390 struct reg_info
*reg_info
= df
->regs
;
3392 fprintf (file
, "Register info:\n");
3393 for (j
= 0; j
< df
->n_regs
; j
++)
3395 if (((flags
& DF_REG_INFO
)
3396 && (reg_info
[j
].n_uses
|| reg_info
[j
].n_defs
))
3397 || ((flags
& DF_RD_CHAIN
) && reg_info
[j
].defs
)
3398 || ((flags
& DF_RU_CHAIN
) && reg_info
[j
].uses
))
3400 fprintf (file
, "reg %d", j
);
3401 if ((flags
& DF_RD_CHAIN
) && (flags
& DF_RU_CHAIN
))
3403 basic_block bb
= df_regno_bb (df
, j
);
3406 fprintf (file
, " bb %d", bb
->index
);
3408 fprintf (file
, " bb ?");
3410 if (flags
& DF_REG_INFO
)
3412 fprintf (file
, " life %d", reg_info
[j
].lifetime
);
3415 if ((flags
& DF_REG_INFO
) || (flags
& DF_RD_CHAIN
))
3417 fprintf (file
, " defs ");
3418 if (flags
& DF_REG_INFO
)
3419 fprintf (file
, "%d ", reg_info
[j
].n_defs
);
3420 if (flags
& DF_RD_CHAIN
)
3421 df_chain_dump (reg_info
[j
].defs
, file
);
3424 if ((flags
& DF_REG_INFO
) || (flags
& DF_RU_CHAIN
))
3426 fprintf (file
, " uses ");
3427 if (flags
& DF_REG_INFO
)
3428 fprintf (file
, "%d ", reg_info
[j
].n_uses
);
3429 if (flags
& DF_RU_CHAIN
)
3430 df_chain_dump (reg_info
[j
].uses
, file
);
3433 fprintf (file
, "\n");
3437 fprintf (file
, "\n");
3442 df_insn_debug (df
, insn
, file
)
3450 uid
= INSN_UID (insn
);
3451 if (uid
>= df
->insn_size
)
3454 if (df
->insns
[uid
].defs
)
3455 bbi
= DF_REF_BBNO (df
->insns
[uid
].defs
->ref
);
3456 else if (df
->insns
[uid
].uses
)
3457 bbi
= DF_REF_BBNO (df
->insns
[uid
].uses
->ref
);
3461 fprintf (file
, "insn %d bb %d luid %d defs ",
3462 uid
, bbi
, DF_INSN_LUID (df
, insn
));
3463 df_chain_dump (df
->insns
[uid
].defs
, file
);
3464 fprintf (file
, " uses ");
3465 df_chain_dump (df
->insns
[uid
].uses
, file
);
3466 fprintf (file
, "\n");
3470 df_insn_debug_regno (df
, insn
, file
)
3478 uid
= INSN_UID (insn
);
3479 if (uid
>= df
->insn_size
)
3482 if (df
->insns
[uid
].defs
)
3483 bbi
= DF_REF_BBNO (df
->insns
[uid
].defs
->ref
);
3484 else if (df
->insns
[uid
].uses
)
3485 bbi
= DF_REF_BBNO (df
->insns
[uid
].uses
->ref
);
3489 fprintf (file
, "insn %d bb %d luid %d defs ",
3490 uid
, bbi
, DF_INSN_LUID (df
, insn
));
3491 df_chain_dump_regno (df
->insns
[uid
].defs
, file
);
3492 fprintf (file
, " uses ");
3493 df_chain_dump_regno (df
->insns
[uid
].uses
, file
);
3494 fprintf (file
, "\n");
3498 df_regno_debug (df
, regno
, file
)
3503 if (regno
>= df
->reg_size
)
3506 fprintf (file
, "reg %d life %d defs ",
3507 regno
, df
->regs
[regno
].lifetime
);
3508 df_chain_dump (df
->regs
[regno
].defs
, file
);
3509 fprintf (file
, " uses ");
3510 df_chain_dump (df
->regs
[regno
].uses
, file
);
3511 fprintf (file
, "\n");
3516 df_ref_debug (df
, ref
, file
)
3521 fprintf (file
, "%c%d ",
3522 DF_REF_REG_DEF_P (ref
) ? 'd' : 'u',
3524 fprintf (file
, "reg %d bb %d luid %d insn %d chain ",
3527 DF_INSN_LUID (df
, DF_REF_INSN (ref
)),
3528 INSN_UID (DF_REF_INSN (ref
)));
3529 df_chain_dump (DF_REF_CHAIN (ref
), file
);
3530 fprintf (file
, "\n");
3535 debug_df_insn (insn
)
3538 df_insn_debug (ddf
, insn
, stderr
);
3547 df_regno_debug (ddf
, REGNO (reg
), stderr
);
3552 debug_df_regno (regno
)
3555 df_regno_debug (ddf
, regno
, stderr
);
3563 df_ref_debug (ddf
, ref
, stderr
);
3568 debug_df_defno (defno
)
3571 df_ref_debug (ddf
, ddf
->defs
[defno
], stderr
);
3576 debug_df_useno (defno
)
3579 df_ref_debug (ddf
, ddf
->uses
[defno
], stderr
);
3584 debug_df_chain (link
)
3585 struct df_link
*link
;
3587 df_chain_dump (link
, stderr
);
3588 fputc ('\n', stderr
);
3593 in, out = Filled in by function.
3594 blocks = Blocks to analyze.
3595 dir = Dataflow direction.
3596 conf_op = Confluence operation.
3597 transfun = Transfer function.
3598 order = Order to iterate in. (Should map block numbers -> order)
3599 data = Whatever you want. It's passed to the transfer function.
3601 This function will perform iterative bitvector dataflow, producing
3602 the in and out sets. Even if you only want to perform it for a
3603 small number of blocks, the vectors for in and out must be large
3604 enough for *all* blocks, because changing one block might affect
3605 others. However, it'll only put what you say to analyze on the
3608 For forward problems, you probably want to pass in a mapping of
3609 block number to rc_order (like df->inverse_rc_map).
3613 iterative_dataflow_sbitmap (in
, out
, gen
, kill
, blocks
,
3614 dir
, conf_op
, transfun
, order
, data
)
3615 sbitmap
*in
, *out
, *gen
, *kill
;
3617 enum df_flow_dir dir
;
3618 enum df_confluence_op conf_op
;
3619 transfer_function_sbitmap transfun
;
3628 onqueue
= sbitmap_alloc (n_basic_blocks
);
3629 sbitmap_zero (onqueue
);
3630 worklist
= fibheap_new ();
3631 EXECUTE_IF_SET_IN_BITMAP (blocks
, 0, i
,
3633 fibheap_insert (worklist
, order
[i
], (void *) i
);
3634 SET_BIT (onqueue
, i
);
3637 sbitmap_copy (out
[i
], gen
[i
]);
3641 sbitmap_copy (in
[i
], gen
[i
]);
3645 while (!fibheap_empty (worklist
))
3648 i
= (int) fibheap_extract_min (worklist
);
3650 bb
= BASIC_BLOCK (i
);
3651 RESET_BIT (onqueue
, i
);
3654 /* Calculate <conf_op> of predecessor_outs */
3655 for (e
= bb
->pred
; e
!= 0; e
= e
->pred_next
)
3657 if (e
->src
== ENTRY_BLOCK_PTR
)
3659 sbitmap_zero (in
[i
]);
3662 sbitmap_copy (in
[i
], out
[e
->src
->index
]);
3666 sbitmap_zero (in
[i
]);
3667 for (e
= bb
->pred
; e
!= 0; e
= e
->pred_next
)
3669 if (e
->src
== ENTRY_BLOCK_PTR
)
3674 sbitmap_a_or_b (in
[i
], in
[i
], out
[e
->src
->index
]);
3677 sbitmap_a_and_b (in
[i
], in
[i
], out
[e
->src
->index
]);
3684 /* Calculate <conf_op> of successor ins */
3685 sbitmap_zero (out
[i
]);
3686 for (e
= bb
->succ
; e
!= 0; e
= e
->succ_next
)
3688 if (e
->dest
== EXIT_BLOCK_PTR
)
3693 sbitmap_a_or_b (out
[i
], out
[i
], in
[e
->dest
->index
]);
3696 sbitmap_a_and_b (out
[i
], out
[i
], in
[e
->dest
->index
]);
3702 (*transfun
)(i
, &changed
, in
[i
], out
[i
], gen
[i
], kill
[i
], data
);
3708 for (e
= bb
->succ
; e
!= 0; e
= e
->succ_next
)
3710 if (e
->dest
== EXIT_BLOCK_PTR
)
3712 if (!TEST_BIT (onqueue
, e
->dest
->index
))
3714 SET_BIT (onqueue
, e
->dest
->index
);
3715 fibheap_insert (worklist
,
3716 order
[e
->dest
->index
],
3717 (void *)e
->dest
->index
);
3723 for (e
= bb
->pred
; e
!= 0; e
= e
->pred_next
)
3725 if (e
->src
== ENTRY_BLOCK_PTR
)
3727 if (!TEST_BIT (onqueue
, e
->src
->index
))
3729 SET_BIT (onqueue
, e
->src
->index
);
3730 fibheap_insert (worklist
,
3731 order
[e
->src
->index
],
3732 (void *)e
->src
->index
);
3739 sbitmap_free (onqueue
);
3740 fibheap_delete (worklist
);
3743 /* Exactly the same as iterative_dataflow_sbitmap, except it works on
3746 iterative_dataflow_bitmap (in
, out
, gen
, kill
, blocks
,
3747 dir
, conf_op
, transfun
, order
, data
)
3748 bitmap
*in
, *out
, *gen
, *kill
;
3750 enum df_flow_dir dir
;
3751 enum df_confluence_op conf_op
;
3752 transfer_function_bitmap transfun
;
3762 onqueue
= sbitmap_alloc (n_basic_blocks
);
3763 sbitmap_zero (onqueue
);
3764 worklist
= fibheap_new ();
3765 EXECUTE_IF_SET_IN_BITMAP (blocks
, 0, i
,
3767 fibheap_insert (worklist
, order
[i
], (void *) i
);
3768 SET_BIT (onqueue
, i
);
3771 bitmap_copy (out
[i
], gen
[i
]);
3775 bitmap_copy (in
[i
], gen
[i
]);
3779 while (!fibheap_empty (worklist
))
3782 i
= (int) fibheap_extract_min (worklist
);
3784 bb
= BASIC_BLOCK (i
);
3785 RESET_BIT (onqueue
, i
);
3789 /* Calculate <conf_op> of predecessor_outs */
3790 bitmap_zero (in
[i
]);
3791 for (e
= bb
->pred
; e
!= 0; e
= e
->pred_next
)
3793 if (e
->src
== ENTRY_BLOCK_PTR
)
3798 bitmap_a_or_b (in
[i
], in
[i
], out
[e
->src
->index
]);
3801 bitmap_a_and_b (in
[i
], in
[i
], out
[e
->src
->index
]);
3808 /* Calculate <conf_op> of successor ins */
3809 bitmap_zero(out
[i
]);
3810 for (e
= bb
->succ
; e
!= 0; e
= e
->succ_next
)
3812 if (e
->dest
== EXIT_BLOCK_PTR
)
3817 bitmap_a_or_b (out
[i
], out
[i
], in
[e
->dest
->index
]);
3820 bitmap_a_and_b (out
[i
], out
[i
], in
[e
->dest
->index
]);
3826 (*transfun
)(i
, &changed
, in
[i
], out
[i
], gen
[i
], kill
[i
], data
);
3832 for (e
= bb
->succ
; e
!= 0; e
= e
->succ_next
)
3834 if (e
->dest
== EXIT_BLOCK_PTR
)
3836 if (!TEST_BIT (onqueue
, e
->dest
->index
))
3838 SET_BIT (onqueue
, e
->dest
->index
);
3839 fibheap_insert (worklist
,
3840 order
[e
->dest
->index
],
3841 (void *)e
->dest
->index
);
3847 for (e
= bb
->pred
; e
!= 0; e
= e
->pred_next
)
3849 if (e
->src
== ENTRY_BLOCK_PTR
)
3851 if (!TEST_BIT (onqueue
, e
->src
->index
))
3853 SET_BIT (onqueue
, e
->src
->index
);
3854 fibheap_insert (worklist
,
3855 order
[e
->src
->index
],
3856 (void *)e
->src
->index
);
3863 sbitmap_free (onqueue
);
3864 fibheap_delete (worklist
);