1 /* Dataflow support routines.
2 Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004
3 Free Software Foundation, Inc.
4 Contributed by Michael P. Hayes (m.hayes@elec.canterbury.ac.nz,
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 2, or (at your option) any later
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING. If not, write to the Free
21 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
27 This file provides some dataflow routines for computing reaching defs,
28 upward exposed uses, live variables, def-use chains, and use-def
29 chains. The global dataflow is performed using simple iterative
30 methods with a worklist and could be sped up by ordering the blocks
31 with a depth first search order.
33 A `struct ref' data structure (ref) is allocated for every register
34 reference (def or use) and this records the insn and bb the ref is
35 found within. The refs are linked together in chains of uses and defs
36 for each insn and for each register. Each ref also has a chain field
37 that links all the use refs for a def or all the def refs for a use.
38 This is used to create use-def or def-use chains.
43 Here's an example of using the dataflow routines.
49 df_analyze (df, 0, DF_ALL);
51 df_dump (df, DF_ALL, stderr);
56 df_init simply creates a poor man's object (df) that needs to be
57 passed to all the dataflow routines. df_finish destroys this
58 object and frees up any allocated memory. DF_ALL says to analyze
61 df_analyze performs the following:
63 1. Records defs and uses by scanning the insns in each basic block
64 or by scanning the insns queued by df_insn_modify.
65 2. Links defs and uses into insn-def and insn-use chains.
66 3. Links defs and uses into reg-def and reg-use chains.
67 4. Assigns LUIDs to each insn (for modified blocks).
68 5. Calculates local reaching definitions.
69 6. Calculates global reaching definitions.
70 7. Creates use-def chains.
71 8. Calculates local reaching uses (upwards exposed uses).
72 9. Calculates global reaching uses.
73 10. Creates def-use chains.
74 11. Calculates local live registers.
75 12. Calculates global live registers.
76 13. Calculates register lifetimes and determines local registers.
81 Note that the dataflow information is not updated for every newly
82 deleted or created insn. If the dataflow information requires
83 updating then all the changed, new, or deleted insns needs to be
84 marked with df_insn_modify (or df_insns_modify) either directly or
85 indirectly (say through calling df_insn_delete). df_insn_modify
86 marks all the modified insns to get processed the next time df_analyze
89 Beware that tinkering with insns may invalidate the dataflow information.
90 The philosophy behind these routines is that once the dataflow
91 information has been gathered, the user should store what they require
92 before they tinker with any insn. Once a reg is replaced, for example,
93 then the reg-def/reg-use chains will point to the wrong place. Once a
94 whole lot of changes have been made, df_analyze can be called again
95 to update the dataflow information. Currently, this is not very smart
96 with regard to propagating changes to the dataflow so it should not
102 The basic object is a REF (reference) and this may either be a DEF
103 (definition) or a USE of a register.
105 These are linked into a variety of lists; namely reg-def, reg-use,
106 insn-def, insn-use, def-use, and use-def lists. For example,
107 the reg-def lists contain all the refs that define a given register
108 while the insn-use lists contain all the refs used by an insn.
110 Note that the reg-def and reg-use chains are generally short (except for the
111 hard registers) and thus it is much faster to search these chains
112 rather than searching the def or use bitmaps.
114 If the insns are in SSA form then the reg-def and use-def lists
115 should only contain the single defining ref.
120 1) Incremental dataflow analysis.
122 Note that if a loop invariant insn is hoisted (or sunk), we do not
123 need to change the def-use or use-def chains. All we have to do is to
124 change the bb field for all the associated defs and uses and to
125 renumber the LUIDs for the original and new basic blocks of the insn.
127 When shadowing loop mems we create new uses and defs for new pseudos
128 so we do not affect the existing dataflow information.
130 My current strategy is to queue up all modified, created, or deleted
131 insns so when df_analyze is called we can easily determine all the new
132 or deleted refs. Currently the global dataflow information is
133 recomputed from scratch but this could be propagated more efficiently.
135 2) Reduced memory requirements.
137 We could operate a pool of ref structures. When a ref is deleted it
138 gets returned to the pool (say by linking on to a chain of free refs).
139 This will require a pair of bitmaps for defs and uses so that we can
140 tell which ones have been changed. Alternatively, we could
141 periodically squeeze the def and use tables and associated bitmaps and
142 renumber the def and use ids.
144 3) Ordering of reg-def and reg-use lists.
146 Should the first entry in the def list be the first def (within a BB)?
147 Similarly, should the first entry in the use list be the last use
150 4) Working with a sub-CFG.
152 Often the whole CFG does not need to be analyzed, for example,
153 when optimizing a loop, only certain registers are of interest.
154 Perhaps there should be a bitmap argument to df_analyze to specify
155 which registers should be analyzed?
160 Embedded addressing side-effects, such as POST_INC or PRE_INC, generate
161 both a use and a def. These are both marked read/write to show that they
162 are dependent. For example, (set (reg 40) (mem (post_inc (reg 42))))
163 will generate a use of reg 42 followed by a def of reg 42 (both marked
164 read/write). Similarly, (set (reg 40) (mem (pre_dec (reg 41))))
165 generates a use of reg 41 then a def of reg 41 (both marked read/write),
166 even though reg 41 is decremented before it is used for the memory
167 address in this second example.
169 A set to a REG inside a ZERO_EXTRACT, SIGN_EXTRACT, or SUBREG invokes
170 a read-modify write operation. We generate both a use and a def
171 and again mark them read/write.
176 #include "coretypes.h"
180 #include "insn-config.h"
182 #include "function.h"
184 #include "alloc-pool.h"
185 #include "hard-reg-set.h"
186 #include "basic-block.h"
191 #define FOR_EACH_BB_IN_BITMAP(BITMAP, MIN, BB, CODE) \
194 unsigned int node_; \
195 EXECUTE_IF_SET_IN_BITMAP (BITMAP, MIN, node_, \
196 {(BB) = BASIC_BLOCK (node_); CODE;}); \
200 static alloc_pool df_ref_pool
;
201 static alloc_pool df_link_pool
;
202 static struct df
*ddf
;
204 static void df_reg_table_realloc (struct df
*, int);
205 static void df_insn_table_realloc (struct df
*, unsigned int);
206 static void df_bb_table_realloc (struct df
*, unsigned int);
207 static void df_bitmaps_alloc (struct df
*, bitmap
, int);
208 static void df_bitmaps_free (struct df
*, int);
209 static void df_free (struct df
*);
210 static void df_alloc (struct df
*, int);
212 static rtx
df_reg_use_gen (unsigned int);
214 static inline struct df_link
*df_link_create (struct ref
*, struct df_link
*);
215 static struct df_link
*df_ref_unlink (struct df_link
**, struct ref
*);
216 static void df_def_unlink (struct df
*, struct ref
*);
217 static void df_use_unlink (struct df
*, struct ref
*);
218 static void df_insn_refs_unlink (struct df
*, basic_block
, rtx
);
220 static void df_bb_refs_unlink (struct df
*, basic_block
);
221 static void df_refs_unlink (struct df
*, bitmap
);
224 static struct ref
*df_ref_create (struct df
*, rtx
, rtx
*, rtx
,
225 enum df_ref_type
, enum df_ref_flags
);
226 static void df_ref_record_1 (struct df
*, rtx
, rtx
*, rtx
, enum df_ref_type
,
228 static void df_ref_record (struct df
*, rtx
, rtx
*, rtx
, enum df_ref_type
,
230 static void df_def_record_1 (struct df
*, rtx
, basic_block
, rtx
);
231 static void df_defs_record (struct df
*, rtx
, basic_block
, rtx
);
232 static void df_uses_record (struct df
*, rtx
*, enum df_ref_type
,
233 basic_block
, rtx
, enum df_ref_flags
);
234 static void df_insn_refs_record (struct df
*, basic_block
, rtx
);
235 static void df_bb_refs_record (struct df
*, basic_block
);
236 static void df_refs_record (struct df
*, bitmap
);
238 static void df_bb_reg_def_chain_create (struct df
*, basic_block
);
239 static void df_reg_def_chain_create (struct df
*, bitmap
, bool);
240 static void df_bb_reg_use_chain_create (struct df
*, basic_block
);
241 static void df_reg_use_chain_create (struct df
*, bitmap
, bool);
242 static void df_bb_du_chain_create (struct df
*, basic_block
, bitmap
);
243 static void df_du_chain_create (struct df
*, bitmap
);
244 static void df_bb_ud_chain_create (struct df
*, basic_block
);
245 static void df_ud_chain_create (struct df
*, bitmap
);
246 static void df_bb_rd_local_compute (struct df
*, basic_block
, bitmap
);
247 static void df_rd_local_compute (struct df
*, bitmap
);
248 static void df_bb_ru_local_compute (struct df
*, basic_block
);
249 static void df_ru_local_compute (struct df
*, bitmap
);
250 static void df_bb_lr_local_compute (struct df
*, basic_block
);
251 static void df_lr_local_compute (struct df
*, bitmap
);
252 static void df_bb_reg_info_compute (struct df
*, basic_block
, bitmap
);
253 static void df_reg_info_compute (struct df
*, bitmap
);
255 static int df_bb_luids_set (struct df
*df
, basic_block
);
256 static int df_luids_set (struct df
*df
, bitmap
);
258 static int df_modified_p (struct df
*, bitmap
);
259 static int df_refs_queue (struct df
*);
260 static int df_refs_process (struct df
*);
261 static int df_bb_refs_update (struct df
*, basic_block
);
262 static int df_refs_update (struct df
*, bitmap
);
263 static void df_analyze_1 (struct df
*, bitmap
, int, int);
265 static void df_insns_modify (struct df
*, basic_block
, rtx
, rtx
);
266 static int df_rtx_mem_replace (rtx
*, void *);
267 static int df_rtx_reg_replace (rtx
*, void *);
268 void df_refs_reg_replace (struct df
*, bitmap
, struct df_link
*, rtx
, rtx
);
270 static int df_def_dominates_all_uses_p (struct df
*, struct ref
*def
);
271 static int df_def_dominates_uses_p (struct df
*, struct ref
*def
, bitmap
);
272 static struct ref
*df_bb_insn_regno_last_use_find (struct df
*, basic_block
,
274 static struct ref
*df_bb_insn_regno_first_def_find (struct df
*, basic_block
,
277 static void df_chain_dump (struct df_link
*, FILE *file
);
278 static void df_chain_dump_regno (struct df_link
*, FILE *file
);
279 static void df_regno_debug (struct df
*, unsigned int, FILE *);
280 static void df_ref_debug (struct df
*, struct ref
*, FILE *);
281 static void df_rd_transfer_function (int, int *, void *, void *, void *,
283 static void df_ru_transfer_function (int, int *, void *, void *, void *,
285 static void df_lr_transfer_function (int, int *, void *, void *, void *,
287 static void hybrid_search (basic_block
, struct dataflow
*,
288 sbitmap
, sbitmap
, sbitmap
);
291 /* Local memory allocation/deallocation routines. */
294 /* Increase the insn info table to have space for at least SIZE + 1
297 df_insn_table_realloc (struct df
*df
, unsigned int size
)
300 if (size
<= df
->insn_size
)
303 /* Make the table a little larger than requested, so we do not need
304 to enlarge it so often. */
305 size
+= df
->insn_size
/ 4;
307 df
->insns
= xrealloc (df
->insns
, size
* sizeof (struct insn_info
));
309 memset (df
->insns
+ df
->insn_size
, 0,
310 (size
- df
->insn_size
) * sizeof (struct insn_info
));
312 df
->insn_size
= size
;
314 if (! df
->insns_modified
)
316 df
->insns_modified
= BITMAP_XMALLOC ();
317 bitmap_zero (df
->insns_modified
);
321 /* Increase the bb info table to have space for at least SIZE + 1
325 df_bb_table_realloc (struct df
*df
, unsigned int size
)
328 if (size
<= df
->n_bbs
)
331 /* Make the table a little larger than requested, so we do not need
332 to enlarge it so often. */
333 size
+= df
->n_bbs
/ 4;
335 df
->bbs
= xrealloc (df
->bbs
, size
* sizeof (struct bb_info
));
337 memset (df
->bbs
+ df
->n_bbs
, 0, (size
- df
->n_bbs
) * sizeof (struct bb_info
));
342 /* Increase the reg info table by SIZE more elements. */
344 df_reg_table_realloc (struct df
*df
, int size
)
346 /* Make table 25 percent larger by default. */
348 size
= df
->reg_size
/ 4;
350 size
+= df
->reg_size
;
351 if (size
< max_reg_num ())
352 size
= max_reg_num ();
354 df
->regs
= xrealloc (df
->regs
, size
* sizeof (struct reg_info
));
355 df
->reg_def_last
= xrealloc (df
->reg_def_last
,
356 size
* sizeof (struct ref
*));
358 /* Zero the new entries. */
359 memset (df
->regs
+ df
->reg_size
, 0,
360 (size
- df
->reg_size
) * sizeof (struct reg_info
));
366 /* Allocate bitmaps for each basic block. */
369 df_bitmaps_alloc (struct df
*df
, bitmap blocks
, int flags
)
373 df
->n_defs
= df
->def_id
;
374 df
->n_uses
= df
->use_id
;
377 blocks
= df
->all_blocks
;
379 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
381 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
387 /* Allocate bitmaps for reaching definitions. */
388 bb_info
->rd_kill
= BITMAP_XMALLOC ();
389 bb_info
->rd_gen
= BITMAP_XMALLOC ();
390 bb_info
->rd_in
= BITMAP_XMALLOC ();
391 bb_info
->rd_out
= BITMAP_XMALLOC ();
395 bitmap_clear (bb_info
->rd_kill
);
396 bitmap_clear (bb_info
->rd_gen
);
397 bitmap_clear (bb_info
->rd_in
);
398 bitmap_clear (bb_info
->rd_out
);
406 /* Allocate bitmaps for upward exposed uses. */
407 bb_info
->ru_kill
= BITMAP_XMALLOC ();
408 bb_info
->ru_gen
= BITMAP_XMALLOC ();
409 bb_info
->ru_in
= BITMAP_XMALLOC ();
410 bb_info
->ru_out
= BITMAP_XMALLOC ();
414 bitmap_clear (bb_info
->ru_kill
);
415 bitmap_clear (bb_info
->ru_gen
);
416 bitmap_clear (bb_info
->ru_in
);
417 bitmap_clear (bb_info
->ru_out
);
425 /* Allocate bitmaps for live variables. */
426 bb_info
->lr_def
= BITMAP_XMALLOC ();
427 bb_info
->lr_use
= BITMAP_XMALLOC ();
428 bb_info
->lr_in
= BITMAP_XMALLOC ();
429 bb_info
->lr_out
= BITMAP_XMALLOC ();
433 bitmap_clear (bb_info
->lr_def
);
434 bitmap_clear (bb_info
->lr_use
);
435 bitmap_clear (bb_info
->lr_in
);
436 bitmap_clear (bb_info
->lr_out
);
443 /* Free bitmaps for each basic block. */
445 df_bitmaps_free (struct df
*df
, int flags
)
451 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
456 if ((flags
& DF_RD
) && bb_info
->rd_in
)
458 /* Free bitmaps for reaching definitions. */
459 BITMAP_XFREE (bb_info
->rd_kill
);
460 bb_info
->rd_kill
= NULL
;
461 BITMAP_XFREE (bb_info
->rd_gen
);
462 bb_info
->rd_gen
= NULL
;
463 BITMAP_XFREE (bb_info
->rd_in
);
464 bb_info
->rd_in
= NULL
;
465 BITMAP_XFREE (bb_info
->rd_out
);
466 bb_info
->rd_out
= NULL
;
469 if ((flags
& DF_RU
) && bb_info
->ru_in
)
471 /* Free bitmaps for upward exposed uses. */
472 BITMAP_XFREE (bb_info
->ru_kill
);
473 bb_info
->ru_kill
= NULL
;
474 BITMAP_XFREE (bb_info
->ru_gen
);
475 bb_info
->ru_gen
= NULL
;
476 BITMAP_XFREE (bb_info
->ru_in
);
477 bb_info
->ru_in
= NULL
;
478 BITMAP_XFREE (bb_info
->ru_out
);
479 bb_info
->ru_out
= NULL
;
482 if ((flags
& DF_LR
) && bb_info
->lr_in
)
484 /* Free bitmaps for live variables. */
485 BITMAP_XFREE (bb_info
->lr_def
);
486 bb_info
->lr_def
= NULL
;
487 BITMAP_XFREE (bb_info
->lr_use
);
488 bb_info
->lr_use
= NULL
;
489 BITMAP_XFREE (bb_info
->lr_in
);
490 bb_info
->lr_in
= NULL
;
491 BITMAP_XFREE (bb_info
->lr_out
);
492 bb_info
->lr_out
= NULL
;
495 df
->flags
&= ~(flags
& (DF_RD
| DF_RU
| DF_LR
));
499 /* Allocate and initialize dataflow memory. */
501 df_alloc (struct df
*df
, int n_regs
)
506 df_link_pool
= create_alloc_pool ("df_link pool", sizeof (struct df_link
),
508 df_ref_pool
= create_alloc_pool ("df_ref pool", sizeof (struct ref
), 100);
510 /* Perhaps we should use LUIDs to save memory for the insn_refs
511 table. This is only a small saving; a few pointers. */
512 n_insns
= get_max_uid () + 1;
516 /* Approximate number of defs by number of insns. */
517 df
->def_size
= n_insns
;
518 df
->defs
= xmalloc (df
->def_size
* sizeof (*df
->defs
));
522 /* Approximate number of uses by twice number of insns. */
523 df
->use_size
= n_insns
* 2;
524 df
->uses
= xmalloc (df
->use_size
* sizeof (*df
->uses
));
527 df
->n_bbs
= last_basic_block
;
529 /* Allocate temporary working array used during local dataflow analysis. */
530 df_insn_table_realloc (df
, n_insns
);
532 df_reg_table_realloc (df
, df
->n_regs
);
534 df
->bbs_modified
= BITMAP_XMALLOC ();
535 bitmap_zero (df
->bbs_modified
);
539 df
->bbs
= xcalloc (last_basic_block
, sizeof (struct bb_info
));
541 df
->all_blocks
= BITMAP_XMALLOC ();
543 bitmap_set_bit (df
->all_blocks
, bb
->index
);
547 /* Free all the dataflow info. */
549 df_free (struct df
*df
)
551 df_bitmaps_free (df
, DF_ALL
);
579 if (df
->bbs_modified
)
580 BITMAP_XFREE (df
->bbs_modified
);
581 df
->bbs_modified
= 0;
583 if (df
->insns_modified
)
584 BITMAP_XFREE (df
->insns_modified
);
585 df
->insns_modified
= 0;
587 BITMAP_XFREE (df
->all_blocks
);
590 free_alloc_pool (df_ref_pool
);
591 free_alloc_pool (df_link_pool
);
594 /* Local miscellaneous routines. */
596 /* Return a USE for register REGNO. */
597 static rtx
df_reg_use_gen (unsigned int regno
)
602 reg
= regno_reg_rtx
[regno
];
604 use
= gen_rtx_USE (GET_MODE (reg
), reg
);
608 /* Local chain manipulation routines. */
610 /* Create a link in a def-use or use-def chain. */
611 static inline struct df_link
*
612 df_link_create (struct ref
*ref
, struct df_link
*next
)
614 struct df_link
*link
;
616 link
= pool_alloc (df_link_pool
);
622 /* Releases members of the CHAIN. */
625 free_reg_ref_chain (struct df_link
**chain
)
627 struct df_link
*act
, *next
;
629 for (act
= *chain
; act
; act
= next
)
632 pool_free (df_link_pool
, act
);
638 /* Add REF to chain head pointed to by PHEAD. */
639 static struct df_link
*
640 df_ref_unlink (struct df_link
**phead
, struct ref
*ref
)
642 struct df_link
*link
= *phead
;
648 /* Only a single ref. It must be the one we want.
649 If not, the def-use and use-def chains are likely to
651 if (link
->ref
!= ref
)
653 /* Now have an empty chain. */
658 /* Multiple refs. One of them must be us. */
659 if (link
->ref
== ref
)
664 for (; link
->next
; link
= link
->next
)
666 if (link
->next
->ref
== ref
)
668 /* Unlink from list. */
669 link
->next
= link
->next
->next
;
680 /* Unlink REF from all def-use/use-def chains, etc. */
682 df_ref_remove (struct df
*df
, struct ref
*ref
)
684 if (DF_REF_REG_DEF_P (ref
))
686 df_def_unlink (df
, ref
);
687 df_ref_unlink (&df
->insns
[DF_REF_INSN_UID (ref
)].defs
, ref
);
691 df_use_unlink (df
, ref
);
692 df_ref_unlink (&df
->insns
[DF_REF_INSN_UID (ref
)].uses
, ref
);
698 /* Unlink DEF from use-def and reg-def chains. */
700 df_def_unlink (struct df
*df ATTRIBUTE_UNUSED
, struct ref
*def
)
702 struct df_link
*du_link
;
703 unsigned int dregno
= DF_REF_REGNO (def
);
705 /* Follow def-use chain to find all the uses of this def. */
706 for (du_link
= DF_REF_CHAIN (def
); du_link
; du_link
= du_link
->next
)
708 struct ref
*use
= du_link
->ref
;
710 /* Unlink this def from the use-def chain. */
711 df_ref_unlink (&DF_REF_CHAIN (use
), def
);
713 DF_REF_CHAIN (def
) = 0;
715 /* Unlink def from reg-def chain. */
716 df_ref_unlink (&df
->regs
[dregno
].defs
, def
);
718 df
->defs
[DF_REF_ID (def
)] = 0;
722 /* Unlink use from def-use and reg-use chains. */
724 df_use_unlink (struct df
*df ATTRIBUTE_UNUSED
, struct ref
*use
)
726 struct df_link
*ud_link
;
727 unsigned int uregno
= DF_REF_REGNO (use
);
729 /* Follow use-def chain to find all the defs of this use. */
730 for (ud_link
= DF_REF_CHAIN (use
); ud_link
; ud_link
= ud_link
->next
)
732 struct ref
*def
= ud_link
->ref
;
734 /* Unlink this use from the def-use chain. */
735 df_ref_unlink (&DF_REF_CHAIN (def
), use
);
737 DF_REF_CHAIN (use
) = 0;
739 /* Unlink use from reg-use chain. */
740 df_ref_unlink (&df
->regs
[uregno
].uses
, use
);
742 df
->uses
[DF_REF_ID (use
)] = 0;
745 /* Local routines for recording refs. */
748 /* Create a new ref of type DF_REF_TYPE for register REG at address
749 LOC within INSN of BB. */
751 df_ref_create (struct df
*df
, rtx reg
, rtx
*loc
, rtx insn
,
752 enum df_ref_type ref_type
, enum df_ref_flags ref_flags
)
754 struct ref
*this_ref
;
756 this_ref
= pool_alloc (df_ref_pool
);
757 DF_REF_REG (this_ref
) = reg
;
758 DF_REF_LOC (this_ref
) = loc
;
759 DF_REF_INSN (this_ref
) = insn
;
760 DF_REF_CHAIN (this_ref
) = 0;
761 DF_REF_TYPE (this_ref
) = ref_type
;
762 DF_REF_FLAGS (this_ref
) = ref_flags
;
763 DF_REF_DATA (this_ref
) = NULL
;
765 if (ref_type
== DF_REF_REG_DEF
)
767 if (df
->def_id
>= df
->def_size
)
769 /* Make table 25 percent larger. */
770 df
->def_size
+= (df
->def_size
/ 4);
771 df
->defs
= xrealloc (df
->defs
,
772 df
->def_size
* sizeof (*df
->defs
));
774 DF_REF_ID (this_ref
) = df
->def_id
;
775 df
->defs
[df
->def_id
++] = this_ref
;
779 if (df
->use_id
>= df
->use_size
)
781 /* Make table 25 percent larger. */
782 df
->use_size
+= (df
->use_size
/ 4);
783 df
->uses
= xrealloc (df
->uses
,
784 df
->use_size
* sizeof (*df
->uses
));
786 DF_REF_ID (this_ref
) = df
->use_id
;
787 df
->uses
[df
->use_id
++] = this_ref
;
793 /* Create a new reference of type DF_REF_TYPE for a single register REG,
794 used inside the LOC rtx of INSN. */
796 df_ref_record_1 (struct df
*df
, rtx reg
, rtx
*loc
, rtx insn
,
797 enum df_ref_type ref_type
, enum df_ref_flags ref_flags
)
799 df_ref_create (df
, reg
, loc
, insn
, ref_type
, ref_flags
);
803 /* Create new references of type DF_REF_TYPE for each part of register REG
804 at address LOC within INSN of BB. */
806 df_ref_record (struct df
*df
, rtx reg
, rtx
*loc
, rtx insn
,
807 enum df_ref_type ref_type
, enum df_ref_flags ref_flags
)
811 if (!REG_P (reg
) && GET_CODE (reg
) != SUBREG
)
814 /* For the reg allocator we are interested in some SUBREG rtx's, but not
815 all. Notably only those representing a word extraction from a multi-word
816 reg. As written in the docu those should have the form
817 (subreg:SI (reg:M A) N), with size(SImode) > size(Mmode).
818 XXX Is that true? We could also use the global word_mode variable. */
819 if (GET_CODE (reg
) == SUBREG
820 && (GET_MODE_SIZE (GET_MODE (reg
)) < GET_MODE_SIZE (word_mode
)
821 || GET_MODE_SIZE (GET_MODE (reg
))
822 >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (reg
)))))
824 loc
= &SUBREG_REG (reg
);
826 ref_flags
|= DF_REF_STRIPPED
;
829 regno
= REGNO (GET_CODE (reg
) == SUBREG
? SUBREG_REG (reg
) : reg
);
830 if (regno
< FIRST_PSEUDO_REGISTER
)
835 if (! (df
->flags
& DF_HARD_REGS
))
838 /* GET_MODE (reg) is correct here. We do not want to go into a SUBREG
839 for the mode, because we only want to add references to regs, which
840 are really referenced. E.g., a (subreg:SI (reg:DI 0) 0) does _not_
841 reference the whole reg 0 in DI mode (which would also include
842 reg 1, at least, if 0 and 1 are SImode registers). */
843 endregno
= hard_regno_nregs
[regno
][GET_MODE (reg
)];
844 if (GET_CODE (reg
) == SUBREG
)
845 regno
+= subreg_regno_offset (regno
, GET_MODE (SUBREG_REG (reg
)),
846 SUBREG_BYTE (reg
), GET_MODE (reg
));
849 for (i
= regno
; i
< endregno
; i
++)
850 df_ref_record_1 (df
, regno_reg_rtx
[i
],
851 loc
, insn
, ref_type
, ref_flags
);
855 df_ref_record_1 (df
, reg
, loc
, insn
, ref_type
, ref_flags
);
860 /* Return nonzero if writes to paradoxical SUBREGs, or SUBREGs which
861 are too narrow, are read-modify-write. */
863 read_modify_subreg_p (rtx x
)
865 unsigned int isize
, osize
;
866 if (GET_CODE (x
) != SUBREG
)
868 isize
= GET_MODE_SIZE (GET_MODE (SUBREG_REG (x
)));
869 osize
= GET_MODE_SIZE (GET_MODE (x
));
870 /* Paradoxical subreg writes don't leave a trace of the old content. */
871 return (isize
> osize
&& isize
> UNITS_PER_WORD
);
875 /* Process all the registers defined in the rtx, X. */
877 df_def_record_1 (struct df
*df
, rtx x
, basic_block bb
, rtx insn
)
881 enum df_ref_flags flags
= 0;
883 /* We may recursively call ourselves on EXPR_LIST when dealing with PARALLEL
885 if (GET_CODE (x
) == EXPR_LIST
|| GET_CODE (x
) == CLOBBER
)
891 /* Some targets place small structures in registers for
892 return values of functions. */
893 if (GET_CODE (dst
) == PARALLEL
&& GET_MODE (dst
) == BLKmode
)
897 for (i
= XVECLEN (dst
, 0) - 1; i
>= 0; i
--)
899 rtx temp
= XVECEXP (dst
, 0, i
);
900 if (GET_CODE (temp
) == EXPR_LIST
|| GET_CODE (temp
) == CLOBBER
901 || GET_CODE (temp
) == SET
)
902 df_def_record_1 (df
, temp
, bb
, insn
);
907 /* Maybe, we should flag the use of STRICT_LOW_PART somehow. It might
908 be handy for the reg allocator. */
909 while (GET_CODE (dst
) == STRICT_LOW_PART
910 || GET_CODE (dst
) == ZERO_EXTRACT
911 || GET_CODE (dst
) == SIGN_EXTRACT
912 || ((df
->flags
& DF_FOR_REGALLOC
) == 0
913 && read_modify_subreg_p (dst
)))
915 /* Strict low part always contains SUBREG, but we do not want to make
916 it appear outside, as whole register is always considered. */
917 if (GET_CODE (dst
) == STRICT_LOW_PART
)
919 loc
= &XEXP (dst
, 0);
922 loc
= &XEXP (dst
, 0);
924 flags
|= DF_REF_READ_WRITE
;
928 || (GET_CODE (dst
) == SUBREG
&& REG_P (SUBREG_REG (dst
))))
929 df_ref_record (df
, dst
, loc
, insn
, DF_REF_REG_DEF
, flags
);
933 /* Process all the registers defined in the pattern rtx, X. */
935 df_defs_record (struct df
*df
, rtx x
, basic_block bb
, rtx insn
)
937 RTX_CODE code
= GET_CODE (x
);
939 if (code
== SET
|| code
== CLOBBER
)
941 /* Mark the single def within the pattern. */
942 df_def_record_1 (df
, x
, bb
, insn
);
944 else if (code
== PARALLEL
)
948 /* Mark the multiple defs within the pattern. */
949 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
951 code
= GET_CODE (XVECEXP (x
, 0, i
));
952 if (code
== SET
|| code
== CLOBBER
)
953 df_def_record_1 (df
, XVECEXP (x
, 0, i
), bb
, insn
);
959 /* Process all the registers used in the rtx at address LOC. */
961 df_uses_record (struct df
*df
, rtx
*loc
, enum df_ref_type ref_type
,
962 basic_block bb
, rtx insn
, enum df_ref_flags flags
)
986 /* If we are clobbering a MEM, mark any registers inside the address
988 if (GET_CODE (XEXP (x
, 0)) == MEM
)
989 df_uses_record (df
, &XEXP (XEXP (x
, 0), 0),
990 DF_REF_REG_MEM_STORE
, bb
, insn
, flags
);
992 /* If we're clobbering a REG then we have a def so ignore. */
996 df_uses_record (df
, &XEXP (x
, 0), DF_REF_REG_MEM_LOAD
, bb
, insn
, 0);
1000 /* While we're here, optimize this case. */
1002 /* In case the SUBREG is not of a REG, do not optimize. */
1003 if (!REG_P (SUBREG_REG (x
)))
1005 loc
= &SUBREG_REG (x
);
1006 df_uses_record (df
, loc
, ref_type
, bb
, insn
, flags
);
1009 /* ... Fall through ... */
1012 df_ref_record (df
, x
, loc
, insn
, ref_type
, flags
);
1017 rtx dst
= SET_DEST (x
);
1019 df_uses_record (df
, &SET_SRC (x
), DF_REF_REG_USE
, bb
, insn
, 0);
1021 switch (GET_CODE (dst
))
1024 if ((df
->flags
& DF_FOR_REGALLOC
) == 0
1025 && read_modify_subreg_p (dst
))
1027 df_uses_record (df
, &SUBREG_REG (dst
), DF_REF_REG_USE
, bb
,
1028 insn
, DF_REF_READ_WRITE
);
1038 df_uses_record (df
, &XEXP (dst
, 0),
1039 DF_REF_REG_MEM_STORE
,
1042 case STRICT_LOW_PART
:
1043 /* A strict_low_part uses the whole REG and not just the SUBREG. */
1044 dst
= XEXP (dst
, 0);
1045 if (GET_CODE (dst
) != SUBREG
)
1047 df_uses_record (df
, &SUBREG_REG (dst
), DF_REF_REG_USE
, bb
,
1048 insn
, DF_REF_READ_WRITE
);
1052 df_uses_record (df
, &XEXP (dst
, 0), DF_REF_REG_USE
, bb
, insn
,
1054 df_uses_record (df
, &XEXP (dst
, 1), DF_REF_REG_USE
, bb
, insn
, 0);
1055 df_uses_record (df
, &XEXP (dst
, 2), DF_REF_REG_USE
, bb
, insn
, 0);
1056 dst
= XEXP (dst
, 0);
1068 case UNSPEC_VOLATILE
:
1072 /* Traditional and volatile asm instructions must be considered to use
1073 and clobber all hard registers, all pseudo-registers and all of
1074 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
1076 Consider for instance a volatile asm that changes the fpu rounding
1077 mode. An insn should not be moved across this even if it only uses
1078 pseudo-regs because it might give an incorrectly rounded result.
1080 For now, just mark any regs we can find in ASM_OPERANDS as
1083 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
1084 We can not just fall through here since then we would be confused
1085 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
1086 traditional asms unlike their normal usage. */
1087 if (code
== ASM_OPERANDS
)
1091 for (j
= 0; j
< ASM_OPERANDS_INPUT_LENGTH (x
); j
++)
1092 df_uses_record (df
, &ASM_OPERANDS_INPUT (x
, j
),
1093 DF_REF_REG_USE
, bb
, insn
, 0);
1105 /* Catch the def of the register being modified. */
1106 df_ref_record (df
, XEXP (x
, 0), &XEXP (x
, 0), insn
, DF_REF_REG_DEF
, DF_REF_READ_WRITE
);
1108 /* ... Fall through to handle uses ... */
1114 /* Recursively scan the operands of this expression. */
1116 const char *fmt
= GET_RTX_FORMAT (code
);
1119 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1123 /* Tail recursive case: save a function call level. */
1129 df_uses_record (df
, &XEXP (x
, i
), ref_type
, bb
, insn
, flags
);
1131 else if (fmt
[i
] == 'E')
1134 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1135 df_uses_record (df
, &XVECEXP (x
, i
, j
), ref_type
,
1143 /* Record all the df within INSN of basic block BB. */
1145 df_insn_refs_record (struct df
*df
, basic_block bb
, rtx insn
)
1153 /* Record register defs. */
1154 df_defs_record (df
, PATTERN (insn
), bb
, insn
);
1156 if (df
->flags
& DF_EQUIV_NOTES
)
1157 for (note
= REG_NOTES (insn
); note
;
1158 note
= XEXP (note
, 1))
1160 switch (REG_NOTE_KIND (note
))
1164 df_uses_record (df
, &XEXP (note
, 0), DF_REF_REG_USE
,
1171 if (GET_CODE (insn
) == CALL_INSN
)
1176 /* Record the registers used to pass arguments. */
1177 for (note
= CALL_INSN_FUNCTION_USAGE (insn
); note
;
1178 note
= XEXP (note
, 1))
1180 if (GET_CODE (XEXP (note
, 0)) == USE
)
1181 df_uses_record (df
, &XEXP (XEXP (note
, 0), 0), DF_REF_REG_USE
,
1185 /* The stack ptr is used (honorarily) by a CALL insn. */
1186 x
= df_reg_use_gen (STACK_POINTER_REGNUM
);
1187 df_uses_record (df
, &XEXP (x
, 0), DF_REF_REG_USE
, bb
, insn
, 0);
1189 if (df
->flags
& DF_HARD_REGS
)
1191 /* Calls may also reference any of the global registers,
1192 so they are recorded as used. */
1193 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1196 x
= df_reg_use_gen (i
);
1197 df_uses_record (df
, &SET_DEST (x
),
1198 DF_REF_REG_USE
, bb
, insn
, 0);
1203 /* Record the register uses. */
1204 df_uses_record (df
, &PATTERN (insn
),
1205 DF_REF_REG_USE
, bb
, insn
, 0);
1207 if (GET_CODE (insn
) == CALL_INSN
)
1211 /* We do not record hard registers clobbered by the call,
1212 since there are awfully many of them and "defs" created
1213 through them are not interesting (since no use can be legally
1214 reached by them). So we must just make sure we include them when
1215 computing kill bitmaps. */
1217 /* There may be extra registers to be clobbered. */
1218 for (note
= CALL_INSN_FUNCTION_USAGE (insn
);
1220 note
= XEXP (note
, 1))
1221 if (GET_CODE (XEXP (note
, 0)) == CLOBBER
)
1222 df_defs_record (df
, XEXP (note
, 0), bb
, insn
);
1228 /* Record all the refs within the basic block BB. */
1230 df_bb_refs_record (struct df
*df
, basic_block bb
)
1234 /* Scan the block an insn at a time from beginning to end. */
1235 FOR_BB_INSNS (bb
, insn
)
1239 /* Record defs within INSN. */
1240 df_insn_refs_record (df
, bb
, insn
);
1246 /* Record all the refs in the basic blocks specified by BLOCKS. */
1248 df_refs_record (struct df
*df
, bitmap blocks
)
1252 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
1254 df_bb_refs_record (df
, bb
);
1258 /* Dataflow analysis routines. */
1260 /* Create reg-def chains for basic block BB. These are a list of
1261 definitions for each register. */
1264 df_bb_reg_def_chain_create (struct df
*df
, basic_block bb
)
1268 /* Perhaps the defs should be sorted using a depth first search
1269 of the CFG (or possibly a breadth first search). */
1271 FOR_BB_INSNS_REVERSE (bb
, insn
)
1273 struct df_link
*link
;
1274 unsigned int uid
= INSN_UID (insn
);
1276 if (! INSN_P (insn
))
1279 for (link
= df
->insns
[uid
].defs
; link
; link
= link
->next
)
1281 struct ref
*def
= link
->ref
;
1282 unsigned int dregno
= DF_REF_REGNO (def
);
1284 /* Do not add ref's to the chain twice, i.e., only add new
1285 refs. XXX the same could be done by testing if the
1286 current insn is a modified (or a new) one. This would be
1288 if (DF_REF_ID (def
) < df
->def_id_save
)
1291 df
->regs
[dregno
].defs
= df_link_create (def
, df
->regs
[dregno
].defs
);
1297 /* Create reg-def chains for each basic block within BLOCKS. These
1298 are a list of definitions for each register. If REDO is true, add
1299 all defs, otherwise just add the new defs. */
1302 df_reg_def_chain_create (struct df
*df
, bitmap blocks
, bool redo
)
1305 #ifdef ENABLE_CHECKING
1308 unsigned old_def_id_save
= df
->def_id_save
;
1312 #ifdef ENABLE_CHECKING
1313 for (regno
= 0; regno
< df
->n_regs
; regno
++)
1314 if (df
->regs
[regno
].defs
)
1318 /* Pretend that all defs are new. */
1319 df
->def_id_save
= 0;
1322 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
1324 df_bb_reg_def_chain_create (df
, bb
);
1327 df
->def_id_save
= old_def_id_save
;
1330 /* Remove all reg-def chains stored in the dataflow object DF. */
1333 df_reg_def_chain_clean (struct df
*df
)
1337 for (regno
= 0; regno
< df
->n_regs
; regno
++)
1338 free_reg_ref_chain (&df
->regs
[regno
].defs
);
1341 /* Create reg-use chains for basic block BB. These are a list of uses
1342 for each register. */
1345 df_bb_reg_use_chain_create (struct df
*df
, basic_block bb
)
1349 /* Scan in forward order so that the last uses appear at the start
1352 FOR_BB_INSNS (bb
, insn
)
1354 struct df_link
*link
;
1355 unsigned int uid
= INSN_UID (insn
);
1357 if (! INSN_P (insn
))
1360 for (link
= df
->insns
[uid
].uses
; link
; link
= link
->next
)
1362 struct ref
*use
= link
->ref
;
1363 unsigned int uregno
= DF_REF_REGNO (use
);
1365 /* Do not add ref's to the chain twice, i.e., only add new
1366 refs. XXX the same could be done by testing if the
1367 current insn is a modified (or a new) one. This would be
1369 if (DF_REF_ID (use
) < df
->use_id_save
)
1372 df
->regs
[uregno
].uses
1373 = df_link_create (use
, df
->regs
[uregno
].uses
);
1379 /* Create reg-use chains for each basic block within BLOCKS. These
1380 are a list of uses for each register. If REDO is true, remove the
1381 old reg-use chains first, otherwise just add new uses to them. */
1384 df_reg_use_chain_create (struct df
*df
, bitmap blocks
, bool redo
)
1387 #ifdef ENABLE_CHECKING
1390 unsigned old_use_id_save
= df
->use_id_save
;
1394 #ifdef ENABLE_CHECKING
1395 for (regno
= 0; regno
< df
->n_regs
; regno
++)
1396 if (df
->regs
[regno
].uses
)
1400 /* Pretend that all uses are new. */
1401 df
->use_id_save
= 0;
1404 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
1406 df_bb_reg_use_chain_create (df
, bb
);
1409 df
->use_id_save
= old_use_id_save
;
1412 /* Remove all reg-use chains stored in the dataflow object DF. */
1415 df_reg_use_chain_clean (struct df
*df
)
1419 for (regno
= 0; regno
< df
->n_regs
; regno
++)
1420 free_reg_ref_chain (&df
->regs
[regno
].uses
);
1423 /* Create def-use chains from reaching use bitmaps for basic block BB. */
1425 df_bb_du_chain_create (struct df
*df
, basic_block bb
, bitmap ru
)
1427 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
1430 bitmap_copy (ru
, bb_info
->ru_out
);
1432 /* For each def in BB create a linked list (chain) of uses
1433 reached from the def. */
1434 FOR_BB_INSNS_REVERSE (bb
, insn
)
1436 struct df_link
*def_link
;
1437 struct df_link
*use_link
;
1438 unsigned int uid
= INSN_UID (insn
);
1440 if (! INSN_P (insn
))
1443 /* For each def in insn... */
1444 for (def_link
= df
->insns
[uid
].defs
; def_link
; def_link
= def_link
->next
)
1446 struct ref
*def
= def_link
->ref
;
1447 unsigned int dregno
= DF_REF_REGNO (def
);
1449 DF_REF_CHAIN (def
) = 0;
1451 /* While the reg-use chains are not essential, it
1452 is _much_ faster to search these short lists rather
1453 than all the reaching uses, especially for large functions. */
1454 for (use_link
= df
->regs
[dregno
].uses
; use_link
;
1455 use_link
= use_link
->next
)
1457 struct ref
*use
= use_link
->ref
;
1459 if (bitmap_bit_p (ru
, DF_REF_ID (use
)))
1462 = df_link_create (use
, DF_REF_CHAIN (def
));
1464 bitmap_clear_bit (ru
, DF_REF_ID (use
));
1469 /* For each use in insn... */
1470 for (use_link
= df
->insns
[uid
].uses
; use_link
; use_link
= use_link
->next
)
1472 struct ref
*use
= use_link
->ref
;
1473 bitmap_set_bit (ru
, DF_REF_ID (use
));
1479 /* Create def-use chains from reaching use bitmaps for basic blocks
1482 df_du_chain_create (struct df
*df
, bitmap blocks
)
1487 ru
= BITMAP_XMALLOC ();
1489 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
1491 df_bb_du_chain_create (df
, bb
, ru
);
1498 /* Create use-def chains from reaching def bitmaps for basic block BB. */
1500 df_bb_ud_chain_create (struct df
*df
, basic_block bb
)
1502 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
1503 struct ref
**reg_def_last
= df
->reg_def_last
;
1506 memset (reg_def_last
, 0, df
->n_regs
* sizeof (struct ref
*));
1508 /* For each use in BB create a linked list (chain) of defs
1509 that reach the use. */
1510 FOR_BB_INSNS (bb
, insn
)
1512 unsigned int uid
= INSN_UID (insn
);
1513 struct df_link
*use_link
;
1514 struct df_link
*def_link
;
1516 if (! INSN_P (insn
))
1519 /* For each use in insn... */
1520 for (use_link
= df
->insns
[uid
].uses
; use_link
; use_link
= use_link
->next
)
1522 struct ref
*use
= use_link
->ref
;
1523 unsigned int regno
= DF_REF_REGNO (use
);
1525 DF_REF_CHAIN (use
) = 0;
1527 /* Has regno been defined in this BB yet? If so, use
1528 the last def as the single entry for the use-def
1529 chain for this use. Otherwise, we need to add all
1530 the defs using this regno that reach the start of
1532 if (reg_def_last
[regno
])
1535 = df_link_create (reg_def_last
[regno
], 0);
1539 /* While the reg-def chains are not essential, it is
1540 _much_ faster to search these short lists rather than
1541 all the reaching defs, especially for large
1543 for (def_link
= df
->regs
[regno
].defs
; def_link
;
1544 def_link
= def_link
->next
)
1546 struct ref
*def
= def_link
->ref
;
1548 if (bitmap_bit_p (bb_info
->rd_in
, DF_REF_ID (def
)))
1551 = df_link_create (def
, DF_REF_CHAIN (use
));
1558 /* For each def in insn... record the last def of each reg. */
1559 for (def_link
= df
->insns
[uid
].defs
; def_link
; def_link
= def_link
->next
)
1561 struct ref
*def
= def_link
->ref
;
1562 int dregno
= DF_REF_REGNO (def
);
1564 reg_def_last
[dregno
] = def
;
1570 /* Create use-def chains from reaching def bitmaps for basic blocks
1573 df_ud_chain_create (struct df
*df
, bitmap blocks
)
1577 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
1579 df_bb_ud_chain_create (df
, bb
);
1586 df_rd_transfer_function (int bb ATTRIBUTE_UNUSED
, int *changed
, void *in
,
1587 void *out
, void *gen
, void *kill
,
1588 void *data ATTRIBUTE_UNUSED
)
1590 *changed
= bitmap_union_of_diff (out
, gen
, in
, kill
);
1595 df_ru_transfer_function (int bb ATTRIBUTE_UNUSED
, int *changed
, void *in
,
1596 void *out
, void *gen
, void *kill
,
1597 void *data ATTRIBUTE_UNUSED
)
1599 *changed
= bitmap_union_of_diff (in
, gen
, out
, kill
);
1604 df_lr_transfer_function (int bb ATTRIBUTE_UNUSED
, int *changed
, void *in
,
1605 void *out
, void *use
, void *def
,
1606 void *data ATTRIBUTE_UNUSED
)
1608 *changed
= bitmap_union_of_diff (in
, use
, out
, def
);
1612 /* Compute local reaching def info for basic block BB. */
1614 df_bb_rd_local_compute (struct df
*df
, basic_block bb
, bitmap call_killed_defs
)
1616 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
1618 bitmap seen
= BITMAP_XMALLOC ();
1619 bool call_seen
= false;
1621 FOR_BB_INSNS_REVERSE (bb
, insn
)
1623 unsigned int uid
= INSN_UID (insn
);
1624 struct df_link
*def_link
;
1626 if (! INSN_P (insn
))
1629 for (def_link
= df
->insns
[uid
].defs
; def_link
; def_link
= def_link
->next
)
1631 struct ref
*def
= def_link
->ref
;
1632 unsigned int regno
= DF_REF_REGNO (def
);
1633 struct df_link
*def2_link
;
1635 if (bitmap_bit_p (seen
, regno
)
1637 && regno
< FIRST_PSEUDO_REGISTER
1638 && TEST_HARD_REG_BIT (regs_invalidated_by_call
, regno
)))
1641 for (def2_link
= df
->regs
[regno
].defs
; def2_link
;
1642 def2_link
= def2_link
->next
)
1644 struct ref
*def2
= def2_link
->ref
;
1646 /* Add all defs of this reg to the set of kills. This
1647 is greedy since many of these defs will not actually
1648 be killed by this BB but it keeps things a lot
1650 bitmap_set_bit (bb_info
->rd_kill
, DF_REF_ID (def2
));
1653 bitmap_set_bit (bb_info
->rd_gen
, DF_REF_ID (def
));
1654 bitmap_set_bit (seen
, regno
);
1657 if (GET_CODE (insn
) == CALL_INSN
&& (df
->flags
& DF_HARD_REGS
))
1659 bitmap_operation (bb_info
->rd_kill
, bb_info
->rd_kill
,
1660 call_killed_defs
, BITMAP_IOR
);
1665 BITMAP_XFREE (seen
);
1669 /* Compute local reaching def info for each basic block within BLOCKS. */
1671 df_rd_local_compute (struct df
*df
, bitmap blocks
)
1674 bitmap killed_by_call
= NULL
;
1676 struct df_link
*def_link
;
1678 if (df
->flags
& DF_HARD_REGS
)
1680 killed_by_call
= BITMAP_XMALLOC ();
1681 for (regno
= 0; regno
< FIRST_PSEUDO_REGISTER
; regno
++)
1683 if (!TEST_HARD_REG_BIT (regs_invalidated_by_call
, regno
))
1686 for (def_link
= df
->regs
[regno
].defs
;
1688 def_link
= def_link
->next
)
1689 bitmap_set_bit (killed_by_call
, DF_REF_ID (def_link
->ref
));
1693 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
1695 df_bb_rd_local_compute (df
, bb
, killed_by_call
);
1698 if (df
->flags
& DF_HARD_REGS
)
1699 BITMAP_XFREE (killed_by_call
);
1703 /* Compute local reaching use (upward exposed use) info for basic
1706 df_bb_ru_local_compute (struct df
*df
, basic_block bb
)
1708 /* This is much more tricky than computing reaching defs. With
1709 reaching defs, defs get killed by other defs. With upwards
1710 exposed uses, these get killed by defs with the same regno. */
1712 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
1716 FOR_BB_INSNS_REVERSE (bb
, insn
)
1718 unsigned int uid
= INSN_UID (insn
);
1719 struct df_link
*def_link
;
1720 struct df_link
*use_link
;
1722 if (! INSN_P (insn
))
1725 for (def_link
= df
->insns
[uid
].defs
; def_link
; def_link
= def_link
->next
)
1727 struct ref
*def
= def_link
->ref
;
1728 unsigned int dregno
= DF_REF_REGNO (def
);
1730 for (use_link
= df
->regs
[dregno
].uses
; use_link
;
1731 use_link
= use_link
->next
)
1733 struct ref
*use
= use_link
->ref
;
1735 /* Add all uses of this reg to the set of kills. This
1736 is greedy since many of these uses will not actually
1737 be killed by this BB but it keeps things a lot
1739 bitmap_set_bit (bb_info
->ru_kill
, DF_REF_ID (use
));
1741 /* Zap from the set of gens for this BB. */
1742 bitmap_clear_bit (bb_info
->ru_gen
, DF_REF_ID (use
));
1746 for (use_link
= df
->insns
[uid
].uses
; use_link
; use_link
= use_link
->next
)
1748 struct ref
*use
= use_link
->ref
;
1749 /* Add use to set of gens in this BB. */
1750 bitmap_set_bit (bb_info
->ru_gen
, DF_REF_ID (use
));
1756 /* Compute local reaching use (upward exposed use) info for each basic
1757 block within BLOCKS. */
1759 df_ru_local_compute (struct df
*df
, bitmap blocks
)
1763 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
1765 df_bb_ru_local_compute (df
, bb
);
1770 /* Compute local live variable info for basic block BB. */
1772 df_bb_lr_local_compute (struct df
*df
, basic_block bb
)
1774 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
1777 FOR_BB_INSNS_REVERSE (bb
, insn
)
1779 unsigned int uid
= INSN_UID (insn
);
1780 struct df_link
*link
;
1782 if (! INSN_P (insn
))
1785 for (link
= df
->insns
[uid
].defs
; link
; link
= link
->next
)
1787 struct ref
*def
= link
->ref
;
1788 unsigned int dregno
= DF_REF_REGNO (def
);
1790 /* Add def to set of defs in this BB. */
1791 bitmap_set_bit (bb_info
->lr_def
, dregno
);
1793 bitmap_clear_bit (bb_info
->lr_use
, dregno
);
1796 for (link
= df
->insns
[uid
].uses
; link
; link
= link
->next
)
1798 struct ref
*use
= link
->ref
;
1799 /* Add use to set of uses in this BB. */
1800 bitmap_set_bit (bb_info
->lr_use
, DF_REF_REGNO (use
));
1806 /* Compute local live variable info for each basic block within BLOCKS. */
1808 df_lr_local_compute (struct df
*df
, bitmap blocks
)
1812 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
1814 df_bb_lr_local_compute (df
, bb
);
1819 /* Compute register info: lifetime, bb, and number of defs and uses
1820 for basic block BB. */
1822 df_bb_reg_info_compute (struct df
*df
, basic_block bb
, bitmap live
)
1824 struct reg_info
*reg_info
= df
->regs
;
1825 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
1828 bitmap_copy (live
, bb_info
->lr_out
);
1830 FOR_BB_INSNS_REVERSE (bb
, insn
)
1832 unsigned int uid
= INSN_UID (insn
);
1834 struct df_link
*link
;
1836 if (! INSN_P (insn
))
1839 for (link
= df
->insns
[uid
].defs
; link
; link
= link
->next
)
1841 struct ref
*def
= link
->ref
;
1842 unsigned int dregno
= DF_REF_REGNO (def
);
1844 /* Kill this register. */
1845 bitmap_clear_bit (live
, dregno
);
1846 reg_info
[dregno
].n_defs
++;
1849 for (link
= df
->insns
[uid
].uses
; link
; link
= link
->next
)
1851 struct ref
*use
= link
->ref
;
1852 unsigned int uregno
= DF_REF_REGNO (use
);
1854 /* This register is now live. */
1855 bitmap_set_bit (live
, uregno
);
1856 reg_info
[uregno
].n_uses
++;
1859 /* Increment lifetimes of all live registers. */
1860 EXECUTE_IF_SET_IN_BITMAP (live
, 0, regno
,
1862 reg_info
[regno
].lifetime
++;
1868 /* Compute register info: lifetime, bb, and number of defs and uses. */
1870 df_reg_info_compute (struct df
*df
, bitmap blocks
)
1875 live
= BITMAP_XMALLOC ();
1877 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
1879 df_bb_reg_info_compute (df
, bb
, live
);
1882 BITMAP_XFREE (live
);
1886 /* Assign LUIDs for BB. */
1888 df_bb_luids_set (struct df
*df
, basic_block bb
)
1893 /* The LUIDs are monotonically increasing for each basic block. */
1895 FOR_BB_INSNS (bb
, insn
)
1898 DF_INSN_LUID (df
, insn
) = luid
++;
1899 DF_INSN_LUID (df
, insn
) = luid
;
1905 /* Assign LUIDs for each basic block within BLOCKS. */
1907 df_luids_set (struct df
*df
, bitmap blocks
)
1912 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
1914 total
+= df_bb_luids_set (df
, bb
);
1920 /* Perform dataflow analysis using existing DF structure for blocks
1921 within BLOCKS. If BLOCKS is zero, use all basic blocks in the CFG. */
1923 df_analyze_1 (struct df
*df
, bitmap blocks
, int flags
, int update
)
1929 struct dataflow dflow
;
1933 if (flags
& DF_UD_CHAIN
)
1934 aflags
|= DF_RD
| DF_RD_CHAIN
;
1936 if (flags
& DF_DU_CHAIN
)
1940 aflags
|= DF_RU_CHAIN
;
1942 if (flags
& DF_REG_INFO
)
1946 blocks
= df
->all_blocks
;
1951 df_refs_update (df
, NULL
);
1952 /* More fine grained incremental dataflow analysis would be
1953 nice. For now recompute the whole shebang for the
1956 df_refs_unlink (df
, blocks
);
1958 /* All the def-use, use-def chains can be potentially
1959 modified by changes in one block. The size of the
1960 bitmaps can also change. */
1964 /* Scan the function for all register defs and uses. */
1966 df_refs_record (df
, blocks
);
1968 /* Link all the new defs and uses to the insns. */
1969 df_refs_process (df
);
1972 /* Allocate the bitmaps now the total number of defs and uses are
1973 known. If the number of defs or uses have changed, then
1974 these bitmaps need to be reallocated. */
1975 df_bitmaps_alloc (df
, NULL
, aflags
);
1977 /* Set the LUIDs for each specified basic block. */
1978 df_luids_set (df
, blocks
);
1980 /* Recreate reg-def and reg-use chains from scratch so that first
1981 def is at the head of the reg-def chain and the last use is at
1982 the head of the reg-use chain. This is only important for
1983 regs local to a basic block as it speeds up searching. */
1984 if (aflags
& DF_RD_CHAIN
)
1986 df_reg_def_chain_create (df
, blocks
, false);
1989 if (aflags
& DF_RU_CHAIN
)
1991 df_reg_use_chain_create (df
, blocks
, false);
1994 df
->dfs_order
= xmalloc (sizeof (int) * n_basic_blocks
);
1995 df
->rc_order
= xmalloc (sizeof (int) * n_basic_blocks
);
1996 df
->rts_order
= xmalloc (sizeof (int) * n_basic_blocks
);
1997 df
->inverse_dfs_map
= xmalloc (sizeof (int) * last_basic_block
);
1998 df
->inverse_rc_map
= xmalloc (sizeof (int) * last_basic_block
);
1999 df
->inverse_rts_map
= xmalloc (sizeof (int) * last_basic_block
);
2001 flow_depth_first_order_compute (df
->dfs_order
, df
->rc_order
);
2002 flow_reverse_top_sort_order_compute (df
->rts_order
);
2003 for (i
= 0; i
< n_basic_blocks
; i
++)
2005 df
->inverse_dfs_map
[df
->dfs_order
[i
]] = i
;
2006 df
->inverse_rc_map
[df
->rc_order
[i
]] = i
;
2007 df
->inverse_rts_map
[df
->rts_order
[i
]] = i
;
2011 /* Compute the sets of gens and kills for the defs of each bb. */
2012 dflow
.in
= xmalloc (sizeof (bitmap
) * last_basic_block
);
2013 dflow
.out
= xmalloc (sizeof (bitmap
) * last_basic_block
);
2014 dflow
.gen
= xmalloc (sizeof (bitmap
) * last_basic_block
);
2015 dflow
.kill
= xmalloc (sizeof (bitmap
) * last_basic_block
);
2017 df_rd_local_compute (df
, df
->flags
& DF_RD
? blocks
: df
->all_blocks
);
2020 dflow
.in
[bb
->index
] = DF_BB_INFO (df
, bb
)->rd_in
;
2021 dflow
.out
[bb
->index
] = DF_BB_INFO (df
, bb
)->rd_out
;
2022 dflow
.gen
[bb
->index
] = DF_BB_INFO (df
, bb
)->rd_gen
;
2023 dflow
.kill
[bb
->index
] = DF_BB_INFO (df
, bb
)->rd_kill
;
2026 dflow
.repr
= SR_BITMAP
;
2027 dflow
.dir
= DF_FORWARD
;
2028 dflow
.conf_op
= DF_UNION
;
2029 dflow
.transfun
= df_rd_transfer_function
;
2030 dflow
.n_blocks
= n_basic_blocks
;
2031 dflow
.order
= df
->rc_order
;
2034 iterative_dataflow (&dflow
);
2041 if (aflags
& DF_UD_CHAIN
)
2043 /* Create use-def chains. */
2044 df_ud_chain_create (df
, df
->all_blocks
);
2046 if (! (flags
& DF_RD
))
2052 /* Compute the sets of gens and kills for the upwards exposed
2054 dflow
.in
= xmalloc (sizeof (bitmap
) * last_basic_block
);
2055 dflow
.out
= xmalloc (sizeof (bitmap
) * last_basic_block
);
2056 dflow
.gen
= xmalloc (sizeof (bitmap
) * last_basic_block
);
2057 dflow
.kill
= xmalloc (sizeof (bitmap
) * last_basic_block
);
2059 df_ru_local_compute (df
, df
->flags
& DF_RU
? blocks
: df
->all_blocks
);
2063 dflow
.in
[bb
->index
] = DF_BB_INFO (df
, bb
)->ru_in
;
2064 dflow
.out
[bb
->index
] = DF_BB_INFO (df
, bb
)->ru_out
;
2065 dflow
.gen
[bb
->index
] = DF_BB_INFO (df
, bb
)->ru_gen
;
2066 dflow
.kill
[bb
->index
] = DF_BB_INFO (df
, bb
)->ru_kill
;
2069 dflow
.repr
= SR_BITMAP
;
2070 dflow
.dir
= DF_BACKWARD
;
2071 dflow
.conf_op
= DF_UNION
;
2072 dflow
.transfun
= df_ru_transfer_function
;
2073 dflow
.n_blocks
= n_basic_blocks
;
2074 dflow
.order
= df
->rts_order
;
2077 iterative_dataflow (&dflow
);
2084 if (aflags
& DF_DU_CHAIN
)
2086 /* Create def-use chains. */
2087 df_du_chain_create (df
, df
->all_blocks
);
2089 if (! (flags
& DF_RU
))
2093 /* Free up bitmaps that are no longer required. */
2095 df_bitmaps_free (df
, dflags
);
2099 /* Compute the sets of defs and uses of live variables. */
2100 dflow
.in
= xmalloc (sizeof (bitmap
) * last_basic_block
);
2101 dflow
.out
= xmalloc (sizeof (bitmap
) * last_basic_block
);
2102 dflow
.gen
= xmalloc (sizeof (bitmap
) * last_basic_block
);
2103 dflow
.kill
= xmalloc (sizeof (bitmap
) * last_basic_block
);
2105 df_lr_local_compute (df
, df
->flags
& DF_LR
? blocks
: df
->all_blocks
);
2109 dflow
.in
[bb
->index
] = DF_BB_INFO (df
, bb
)->lr_in
;
2110 dflow
.out
[bb
->index
] = DF_BB_INFO (df
, bb
)->lr_out
;
2111 dflow
.gen
[bb
->index
] = DF_BB_INFO (df
, bb
)->lr_use
;
2112 dflow
.kill
[bb
->index
] = DF_BB_INFO (df
, bb
)->lr_def
;
2115 dflow
.repr
= SR_BITMAP
;
2116 dflow
.dir
= DF_BACKWARD
;
2117 dflow
.conf_op
= DF_UNION
;
2118 dflow
.transfun
= df_lr_transfer_function
;
2119 dflow
.n_blocks
= n_basic_blocks
;
2120 dflow
.order
= df
->rts_order
;
2123 iterative_dataflow (&dflow
);
2130 if (aflags
& DF_REG_INFO
)
2132 df_reg_info_compute (df
, df
->all_blocks
);
2135 free (df
->dfs_order
);
2136 free (df
->rc_order
);
2137 free (df
->rts_order
);
2138 free (df
->inverse_rc_map
);
2139 free (df
->inverse_dfs_map
);
2140 free (df
->inverse_rts_map
);
2144 /* Initialize dataflow analysis. */
2150 df
= xcalloc (1, sizeof (struct df
));
2152 /* Squirrel away a global for debugging. */
2159 /* Start queuing refs. */
2161 df_refs_queue (struct df
*df
)
2163 df
->def_id_save
= df
->def_id
;
2164 df
->use_id_save
= df
->use_id
;
2165 /* ???? Perhaps we should save current obstack state so that we can
2171 /* Process queued refs. */
2173 df_refs_process (struct df
*df
)
2177 /* Build new insn-def chains. */
2178 for (i
= df
->def_id_save
; i
!= df
->def_id
; i
++)
2180 struct ref
*def
= df
->defs
[i
];
2181 unsigned int uid
= DF_REF_INSN_UID (def
);
2183 /* Add def to head of def list for INSN. */
2185 = df_link_create (def
, df
->insns
[uid
].defs
);
2188 /* Build new insn-use chains. */
2189 for (i
= df
->use_id_save
; i
!= df
->use_id
; i
++)
2191 struct ref
*use
= df
->uses
[i
];
2192 unsigned int uid
= DF_REF_INSN_UID (use
);
2194 /* Add use to head of use list for INSN. */
2196 = df_link_create (use
, df
->insns
[uid
].uses
);
2202 /* Update refs for basic block BB. */
2204 df_bb_refs_update (struct df
*df
, basic_block bb
)
2209 /* While we have to scan the chain of insns for this BB, we do not
2210 need to allocate and queue a long chain of BB/INSN pairs. Using
2211 a bitmap for insns_modified saves memory and avoids queuing
2214 FOR_BB_INSNS (bb
, insn
)
2218 uid
= INSN_UID (insn
);
2220 if (bitmap_bit_p (df
->insns_modified
, uid
))
2222 /* Delete any allocated refs of this insn. MPH, FIXME. */
2223 df_insn_refs_unlink (df
, bb
, insn
);
2225 /* Scan the insn for refs. */
2226 df_insn_refs_record (df
, bb
, insn
);
2235 /* Process all the modified/deleted insns that were queued. */
2237 df_refs_update (struct df
*df
, bitmap blocks
)
2240 int count
= 0, bbno
;
2242 df
->n_regs
= max_reg_num ();
2243 if (df
->n_regs
>= df
->reg_size
)
2244 df_reg_table_realloc (df
, 0);
2250 FOR_EACH_BB_IN_BITMAP (df
->bbs_modified
, 0, bb
,
2252 count
+= df_bb_refs_update (df
, bb
);
2257 EXECUTE_IF_AND_IN_BITMAP (df
->bbs_modified
, blocks
, 0, bbno
,
2259 count
+= df_bb_refs_update (df
, BASIC_BLOCK (bbno
));
2263 df_refs_process (df
);
2268 /* Return nonzero if any of the requested blocks in the bitmap
2269 BLOCKS have been modified. */
2271 df_modified_p (struct df
*df
, bitmap blocks
)
2280 if (bitmap_bit_p (df
->bbs_modified
, bb
->index
)
2281 && (! blocks
|| (blocks
== (bitmap
) -1) || bitmap_bit_p (blocks
, bb
->index
)))
2290 /* Analyze dataflow info for the basic blocks specified by the bitmap
2291 BLOCKS, or for the whole CFG if BLOCKS is zero, or just for the
2292 modified blocks if BLOCKS is -1. */
2295 df_analyze (struct df
*df
, bitmap blocks
, int flags
)
2299 /* We could deal with additional basic blocks being created by
2300 rescanning everything again. */
2301 if (df
->n_bbs
&& df
->n_bbs
!= (unsigned int) last_basic_block
)
2304 update
= df_modified_p (df
, blocks
);
2305 if (update
|| (flags
!= df
->flags
))
2311 /* Recompute everything from scratch. */
2314 /* Allocate and initialize data structures. */
2315 df_alloc (df
, max_reg_num ());
2316 df_analyze_1 (df
, 0, flags
, 0);
2321 if (blocks
== (bitmap
) -1)
2322 blocks
= df
->bbs_modified
;
2327 df_analyze_1 (df
, blocks
, flags
, 1);
2328 bitmap_zero (df
->bbs_modified
);
2329 bitmap_zero (df
->insns_modified
);
2335 /* Remove the entries not in BLOCKS from the LIST of length LEN, preserving
2336 the order of the remaining entries. Returns the length of the resulting
2340 prune_to_subcfg (int list
[], unsigned len
, bitmap blocks
)
2344 for (act
= 0, last
= 0; act
< len
; act
++)
2345 if (bitmap_bit_p (blocks
, list
[act
]))
2346 list
[last
++] = list
[act
];
2351 /* Alternative entry point to the analysis. Analyse just the part of the cfg
2352 graph induced by BLOCKS.
2354 TODO I am not quite sure how to avoid code duplication with df_analyze_1
2355 here, and simultaneously not make even greater chaos in it. We behave
2356 slightly differently in some details, especially in handling modified
2360 df_analyze_subcfg (struct df
*df
, bitmap blocks
, int flags
)
2364 struct dataflow dflow
;
2367 if (flags
& DF_UD_CHAIN
)
2368 flags
|= DF_RD
| DF_RD_CHAIN
;
2369 if (flags
& DF_DU_CHAIN
)
2372 flags
|= DF_RU_CHAIN
;
2373 if (flags
& DF_REG_INFO
)
2378 df_alloc (df
, max_reg_num ());
2380 /* Mark all insns as modified. */
2384 FOR_BB_INSNS (bb
, insn
)
2386 df_insn_modify (df
, bb
, insn
);
2393 df_reg_def_chain_clean (df
);
2394 df_reg_use_chain_clean (df
);
2396 df_refs_update (df
, blocks
);
2398 /* Clear the updated stuff from ``modified'' bitmaps. */
2399 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
2401 if (bitmap_bit_p (df
->bbs_modified
, bb
->index
))
2403 FOR_BB_INSNS (bb
, insn
)
2405 bitmap_clear_bit (df
->insns_modified
, INSN_UID (insn
));
2408 bitmap_clear_bit (df
->bbs_modified
, bb
->index
);
2412 /* Allocate the bitmaps now the total number of defs and uses are
2413 known. If the number of defs or uses have changed, then
2414 these bitmaps need to be reallocated. */
2415 df_bitmaps_alloc (df
, blocks
, flags
);
2417 /* Set the LUIDs for each specified basic block. */
2418 df_luids_set (df
, blocks
);
2420 /* Recreate reg-def and reg-use chains from scratch so that first
2421 def is at the head of the reg-def chain and the last use is at
2422 the head of the reg-use chain. This is only important for
2423 regs local to a basic block as it speeds up searching. */
2424 if (flags
& DF_RD_CHAIN
)
2426 df_reg_def_chain_create (df
, blocks
, true);
2429 if (flags
& DF_RU_CHAIN
)
2431 df_reg_use_chain_create (df
, blocks
, true);
2434 df
->dfs_order
= xmalloc (sizeof (int) * n_basic_blocks
);
2435 df
->rc_order
= xmalloc (sizeof (int) * n_basic_blocks
);
2436 df
->rts_order
= xmalloc (sizeof (int) * n_basic_blocks
);
2438 flow_depth_first_order_compute (df
->dfs_order
, df
->rc_order
);
2439 flow_reverse_top_sort_order_compute (df
->rts_order
);
2441 n_blocks
= prune_to_subcfg (df
->dfs_order
, n_basic_blocks
, blocks
);
2442 prune_to_subcfg (df
->rc_order
, n_basic_blocks
, blocks
);
2443 prune_to_subcfg (df
->rts_order
, n_basic_blocks
, blocks
);
2445 dflow
.in
= xmalloc (sizeof (bitmap
) * last_basic_block
);
2446 dflow
.out
= xmalloc (sizeof (bitmap
) * last_basic_block
);
2447 dflow
.gen
= xmalloc (sizeof (bitmap
) * last_basic_block
);
2448 dflow
.kill
= xmalloc (sizeof (bitmap
) * last_basic_block
);
2452 /* Compute the sets of gens and kills for the defs of each bb. */
2453 df_rd_local_compute (df
, blocks
);
2455 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
2457 dflow
.in
[bb
->index
] = DF_BB_INFO (df
, bb
)->rd_in
;
2458 dflow
.out
[bb
->index
] = DF_BB_INFO (df
, bb
)->rd_out
;
2459 dflow
.gen
[bb
->index
] = DF_BB_INFO (df
, bb
)->rd_gen
;
2460 dflow
.kill
[bb
->index
] = DF_BB_INFO (df
, bb
)->rd_kill
;
2463 dflow
.repr
= SR_BITMAP
;
2464 dflow
.dir
= DF_FORWARD
;
2465 dflow
.conf_op
= DF_UNION
;
2466 dflow
.transfun
= df_rd_transfer_function
;
2467 dflow
.n_blocks
= n_blocks
;
2468 dflow
.order
= df
->rc_order
;
2471 iterative_dataflow (&dflow
);
2474 if (flags
& DF_UD_CHAIN
)
2476 /* Create use-def chains. */
2477 df_ud_chain_create (df
, blocks
);
2482 /* Compute the sets of gens and kills for the upwards exposed
2484 df_ru_local_compute (df
, blocks
);
2486 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
2488 dflow
.in
[bb
->index
] = DF_BB_INFO (df
, bb
)->ru_in
;
2489 dflow
.out
[bb
->index
] = DF_BB_INFO (df
, bb
)->ru_out
;
2490 dflow
.gen
[bb
->index
] = DF_BB_INFO (df
, bb
)->ru_gen
;
2491 dflow
.kill
[bb
->index
] = DF_BB_INFO (df
, bb
)->ru_kill
;
2494 dflow
.repr
= SR_BITMAP
;
2495 dflow
.dir
= DF_BACKWARD
;
2496 dflow
.conf_op
= DF_UNION
;
2497 dflow
.transfun
= df_ru_transfer_function
;
2498 dflow
.n_blocks
= n_blocks
;
2499 dflow
.order
= df
->rts_order
;
2502 iterative_dataflow (&dflow
);
2505 if (flags
& DF_DU_CHAIN
)
2507 /* Create def-use chains. */
2508 df_du_chain_create (df
, blocks
);
2513 /* Compute the sets of defs and uses of live variables. */
2514 df_lr_local_compute (df
, blocks
);
2518 dflow
.in
[bb
->index
] = DF_BB_INFO (df
, bb
)->lr_in
;
2519 dflow
.out
[bb
->index
] = DF_BB_INFO (df
, bb
)->lr_out
;
2520 dflow
.gen
[bb
->index
] = DF_BB_INFO (df
, bb
)->lr_use
;
2521 dflow
.kill
[bb
->index
] = DF_BB_INFO (df
, bb
)->lr_def
;
2524 dflow
.repr
= SR_BITMAP
;
2525 dflow
.dir
= DF_BACKWARD
;
2526 dflow
.conf_op
= DF_UNION
;
2527 dflow
.transfun
= df_lr_transfer_function
;
2528 dflow
.n_blocks
= n_blocks
;
2529 dflow
.order
= df
->rts_order
;
2532 iterative_dataflow (&dflow
);
2535 if (flags
& DF_REG_INFO
)
2537 df_reg_info_compute (df
, blocks
);
2545 free (df
->dfs_order
);
2546 free (df
->rc_order
);
2547 free (df
->rts_order
);
2550 /* Free all the dataflow info and the DF structure. */
2552 df_finish (struct df
*df
)
2558 /* Unlink INSN from its reference information. */
2560 df_insn_refs_unlink (struct df
*df
, basic_block bb ATTRIBUTE_UNUSED
, rtx insn
)
2562 struct df_link
*link
;
2565 uid
= INSN_UID (insn
);
2567 /* Unlink all refs defined by this insn. */
2568 for (link
= df
->insns
[uid
].defs
; link
; link
= link
->next
)
2569 df_def_unlink (df
, link
->ref
);
2571 /* Unlink all refs used by this insn. */
2572 for (link
= df
->insns
[uid
].uses
; link
; link
= link
->next
)
2573 df_use_unlink (df
, link
->ref
);
2575 df
->insns
[uid
].defs
= 0;
2576 df
->insns
[uid
].uses
= 0;
2581 /* Unlink all the insns within BB from their reference information. */
2583 df_bb_refs_unlink (struct df
*df
, basic_block bb
)
2587 /* Scan the block an insn at a time from beginning to end. */
2588 for (insn
= BB_HEAD (bb
); ; insn
= NEXT_INSN (insn
))
2592 /* Unlink refs for INSN. */
2593 df_insn_refs_unlink (df
, bb
, insn
);
2595 if (insn
== BB_END (bb
))
2601 /* Unlink all the refs in the basic blocks specified by BLOCKS.
2602 Not currently used. */
2604 df_refs_unlink (struct df
*df
, bitmap blocks
)
2610 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
2612 df_bb_refs_unlink (df
, bb
);
2618 df_bb_refs_unlink (df
, bb
);
2623 /* Functions to modify insns. */
2626 /* Delete INSN and all its reference information. */
2628 df_insn_delete (struct df
*df
, basic_block bb ATTRIBUTE_UNUSED
, rtx insn
)
2630 /* If the insn is a jump, we should perhaps call delete_insn to
2631 handle the JUMP_LABEL? */
2633 /* We should not be deleting the NOTE_INSN_BASIC_BLOCK or label. */
2634 if (insn
== BB_HEAD (bb
))
2637 /* Delete the insn. */
2640 df_insn_modify (df
, bb
, insn
);
2642 return NEXT_INSN (insn
);
2645 /* Mark that basic block BB was modified. */
2648 df_bb_modify (struct df
*df
, basic_block bb
)
2650 if ((unsigned) bb
->index
>= df
->n_bbs
)
2651 df_bb_table_realloc (df
, df
->n_bbs
);
2653 bitmap_set_bit (df
->bbs_modified
, bb
->index
);
2656 /* Mark that INSN within BB may have changed (created/modified/deleted).
2657 This may be called multiple times for the same insn. There is no
2658 harm calling this function if the insn wasn't changed; it will just
2659 slow down the rescanning of refs. */
2661 df_insn_modify (struct df
*df
, basic_block bb
, rtx insn
)
2665 uid
= INSN_UID (insn
);
2666 if (uid
>= df
->insn_size
)
2667 df_insn_table_realloc (df
, uid
);
2669 df_bb_modify (df
, bb
);
2670 bitmap_set_bit (df
->insns_modified
, uid
);
2672 /* For incremental updating on the fly, perhaps we could make a copy
2673 of all the refs of the original insn and turn them into
2674 anti-refs. When df_refs_update finds these anti-refs, it annihilates
2675 the original refs. If validate_change fails then these anti-refs
2676 will just get ignored. */
2679 typedef struct replace_args
2688 /* Replace mem pointed to by PX with its associated pseudo register.
2689 DATA is actually a pointer to a structure describing the
2690 instruction currently being scanned and the MEM we are currently
2693 df_rtx_mem_replace (rtx
*px
, void *data
)
2695 replace_args
*args
= (replace_args
*) data
;
2698 if (mem
== NULL_RTX
)
2701 switch (GET_CODE (mem
))
2707 /* We're not interested in the MEM associated with a
2708 CONST_DOUBLE, so there's no need to traverse into one. */
2712 /* This is not a MEM. */
2716 if (!rtx_equal_p (args
->match
, mem
))
2717 /* This is not the MEM we are currently replacing. */
2720 /* Actually replace the MEM. */
2721 validate_change (args
->insn
, px
, args
->replacement
, 1);
2729 df_insn_mem_replace (struct df
*df
, basic_block bb
, rtx insn
, rtx mem
, rtx reg
)
2735 args
.replacement
= reg
;
2738 /* Search and replace all matching mems within insn. */
2739 for_each_rtx (&insn
, df_rtx_mem_replace
, &args
);
2742 df_insn_modify (df
, bb
, insn
);
2744 /* ???? FIXME. We may have a new def or one or more new uses of REG
2745 in INSN. REG should be a new pseudo so it won't affect the
2746 dataflow information that we currently have. We should add
2747 the new uses and defs to INSN and then recreate the chains
2748 when df_analyze is called. */
2749 return args
.modified
;
2753 /* Replace one register with another. Called through for_each_rtx; PX
2754 points to the rtx being scanned. DATA is actually a pointer to a
2755 structure of arguments. */
2757 df_rtx_reg_replace (rtx
*px
, void *data
)
2760 replace_args
*args
= (replace_args
*) data
;
2765 if (x
== args
->match
)
2767 validate_change (args
->insn
, px
, args
->replacement
, 1);
2775 /* Replace the reg within every ref on CHAIN that is within the set
2776 BLOCKS of basic blocks with NEWREG. Also update the regs within
2779 df_refs_reg_replace (struct df
*df
, bitmap blocks
, struct df_link
*chain
, rtx oldreg
, rtx newreg
)
2781 struct df_link
*link
;
2785 blocks
= df
->all_blocks
;
2787 args
.match
= oldreg
;
2788 args
.replacement
= newreg
;
2791 for (link
= chain
; link
; link
= link
->next
)
2793 struct ref
*ref
= link
->ref
;
2794 rtx insn
= DF_REF_INSN (ref
);
2796 if (! INSN_P (insn
))
2799 if (bitmap_bit_p (blocks
, DF_REF_BBNO (ref
)))
2801 df_ref_reg_replace (df
, ref
, oldreg
, newreg
);
2803 /* Replace occurrences of the reg within the REG_NOTES. */
2804 if ((! link
->next
|| DF_REF_INSN (ref
)
2805 != DF_REF_INSN (link
->next
->ref
))
2806 && REG_NOTES (insn
))
2809 for_each_rtx (®_NOTES (insn
), df_rtx_reg_replace
, &args
);
2814 /* Temporary check to ensure that we have a grip on which
2815 regs should be replaced. */
2822 /* Replace all occurrences of register OLDREG with register NEWREG in
2823 blocks defined by bitmap BLOCKS. This also replaces occurrences of
2824 OLDREG in the REG_NOTES but only for insns containing OLDREG. This
2825 routine expects the reg-use and reg-def chains to be valid. */
2827 df_reg_replace (struct df
*df
, bitmap blocks
, rtx oldreg
, rtx newreg
)
2829 unsigned int oldregno
= REGNO (oldreg
);
2831 df_refs_reg_replace (df
, blocks
, df
->regs
[oldregno
].defs
, oldreg
, newreg
);
2832 df_refs_reg_replace (df
, blocks
, df
->regs
[oldregno
].uses
, oldreg
, newreg
);
2837 /* Try replacing the reg within REF with NEWREG. Do not modify
2838 def-use/use-def chains. */
2840 df_ref_reg_replace (struct df
*df
, struct ref
*ref
, rtx oldreg
, rtx newreg
)
2842 /* Check that insn was deleted by being converted into a NOTE. If
2843 so ignore this insn. */
2844 if (! INSN_P (DF_REF_INSN (ref
)))
2847 if (oldreg
&& oldreg
!= DF_REF_REG (ref
))
2850 if (! validate_change (DF_REF_INSN (ref
), DF_REF_LOC (ref
), newreg
, 1))
2853 df_insn_modify (df
, DF_REF_BB (ref
), DF_REF_INSN (ref
));
2859 df_bb_def_use_swap (struct df
*df
, basic_block bb
, rtx def_insn
, rtx use_insn
, unsigned int regno
)
2865 struct df_link
*link
;
2867 def
= df_bb_insn_regno_first_def_find (df
, bb
, def_insn
, regno
);
2871 use
= df_bb_insn_regno_last_use_find (df
, bb
, use_insn
, regno
);
2875 /* The USE no longer exists. */
2876 use_uid
= INSN_UID (use_insn
);
2877 df_use_unlink (df
, use
);
2878 df_ref_unlink (&df
->insns
[use_uid
].uses
, use
);
2880 /* The DEF requires shifting so remove it from DEF_INSN
2881 and add it to USE_INSN by reusing LINK. */
2882 def_uid
= INSN_UID (def_insn
);
2883 link
= df_ref_unlink (&df
->insns
[def_uid
].defs
, def
);
2885 link
->next
= df
->insns
[use_uid
].defs
;
2886 df
->insns
[use_uid
].defs
= link
;
2889 link
= df_ref_unlink (&df
->regs
[regno
].defs
, def
);
2891 link
->next
= df
->regs
[regno
].defs
;
2892 df
->insns
[regno
].defs
= link
;
2895 DF_REF_INSN (def
) = use_insn
;
2900 /* Record df between FIRST_INSN and LAST_INSN inclusive. All new
2901 insns must be processed by this routine. */
2903 df_insns_modify (struct df
*df
, basic_block bb
, rtx first_insn
, rtx last_insn
)
2907 for (insn
= first_insn
; ; insn
= NEXT_INSN (insn
))
2911 /* A non-const call should not have slipped through the net. If
2912 it does, we need to create a new basic block. Ouch. The
2913 same applies for a label. */
2914 if ((GET_CODE (insn
) == CALL_INSN
2915 && ! CONST_OR_PURE_CALL_P (insn
))
2916 || GET_CODE (insn
) == CODE_LABEL
)
2919 uid
= INSN_UID (insn
);
2921 if (uid
>= df
->insn_size
)
2922 df_insn_table_realloc (df
, uid
);
2924 df_insn_modify (df
, bb
, insn
);
2926 if (insn
== last_insn
)
2932 /* Emit PATTERN before INSN within BB. */
2934 df_pattern_emit_before (struct df
*df
, rtx pattern
, basic_block bb
, rtx insn
)
2937 rtx prev_insn
= PREV_INSN (insn
);
2939 /* We should not be inserting before the start of the block. */
2940 if (insn
== BB_HEAD (bb
))
2942 ret_insn
= emit_insn_before (pattern
, insn
);
2943 if (ret_insn
== insn
)
2946 df_insns_modify (df
, bb
, NEXT_INSN (prev_insn
), ret_insn
);
2951 /* Emit PATTERN after INSN within BB. */
2953 df_pattern_emit_after (struct df
*df
, rtx pattern
, basic_block bb
, rtx insn
)
2957 ret_insn
= emit_insn_after (pattern
, insn
);
2958 if (ret_insn
== insn
)
2961 df_insns_modify (df
, bb
, NEXT_INSN (insn
), ret_insn
);
2966 /* Emit jump PATTERN after INSN within BB. */
2968 df_jump_pattern_emit_after (struct df
*df
, rtx pattern
, basic_block bb
, rtx insn
)
2972 ret_insn
= emit_jump_insn_after (pattern
, insn
);
2973 if (ret_insn
== insn
)
2976 df_insns_modify (df
, bb
, NEXT_INSN (insn
), ret_insn
);
2981 /* Move INSN within BB before BEFORE_INSN within BEFORE_BB.
2983 This function should only be used to move loop invariant insns
2984 out of a loop where it has been proven that the def-use info
2985 will still be valid. */
2987 df_insn_move_before (struct df
*df
, basic_block bb
, rtx insn
, basic_block before_bb
, rtx before_insn
)
2989 struct df_link
*link
;
2993 return df_pattern_emit_before (df
, insn
, before_bb
, before_insn
);
2995 uid
= INSN_UID (insn
);
2997 /* Change bb for all df defined and used by this insn. */
2998 for (link
= df
->insns
[uid
].defs
; link
; link
= link
->next
)
2999 DF_REF_BB (link
->ref
) = before_bb
;
3000 for (link
= df
->insns
[uid
].uses
; link
; link
= link
->next
)
3001 DF_REF_BB (link
->ref
) = before_bb
;
3003 /* The lifetimes of the registers used in this insn will be reduced
3004 while the lifetimes of the registers defined in this insn
3005 are likely to be increased. */
3007 /* ???? Perhaps all the insns moved should be stored on a list
3008 which df_analyze removes when it recalculates data flow. */
3010 return emit_insn_before (insn
, before_insn
);
3013 /* Functions to query dataflow information. */
3017 df_insn_regno_def_p (struct df
*df
, basic_block bb ATTRIBUTE_UNUSED
,
3018 rtx insn
, unsigned int regno
)
3021 struct df_link
*link
;
3023 uid
= INSN_UID (insn
);
3025 for (link
= df
->insns
[uid
].defs
; link
; link
= link
->next
)
3027 struct ref
*def
= link
->ref
;
3029 if (DF_REF_REGNO (def
) == regno
)
3036 /* Finds the reference corresponding to the definition of REG in INSN.
3037 DF is the dataflow object. */
3040 df_find_def (struct df
*df
, rtx insn
, rtx reg
)
3042 struct df_link
*defs
;
3044 for (defs
= DF_INSN_DEFS (df
, insn
); defs
; defs
= defs
->next
)
3045 if (rtx_equal_p (DF_REF_REG (defs
->ref
), reg
))
3051 /* Return 1 if REG is referenced in INSN, zero otherwise. */
3054 df_reg_used (struct df
*df
, rtx insn
, rtx reg
)
3056 struct df_link
*uses
;
3058 for (uses
= DF_INSN_USES (df
, insn
); uses
; uses
= uses
->next
)
3059 if (rtx_equal_p (DF_REF_REG (uses
->ref
), reg
))
3066 df_def_dominates_all_uses_p (struct df
*df ATTRIBUTE_UNUSED
, struct ref
*def
)
3068 struct df_link
*du_link
;
3070 /* Follow def-use chain to find all the uses of this def. */
3071 for (du_link
= DF_REF_CHAIN (def
); du_link
; du_link
= du_link
->next
)
3073 struct ref
*use
= du_link
->ref
;
3074 struct df_link
*ud_link
;
3076 /* Follow use-def chain to check all the defs for this use. */
3077 for (ud_link
= DF_REF_CHAIN (use
); ud_link
; ud_link
= ud_link
->next
)
3078 if (ud_link
->ref
!= def
)
3086 df_insn_dominates_all_uses_p (struct df
*df
, basic_block bb ATTRIBUTE_UNUSED
,
3090 struct df_link
*link
;
3092 uid
= INSN_UID (insn
);
3094 for (link
= df
->insns
[uid
].defs
; link
; link
= link
->next
)
3096 struct ref
*def
= link
->ref
;
3098 if (! df_def_dominates_all_uses_p (df
, def
))
3106 /* Return nonzero if all DF dominates all the uses within the bitmap
3109 df_def_dominates_uses_p (struct df
*df ATTRIBUTE_UNUSED
, struct ref
*def
,
3112 struct df_link
*du_link
;
3114 /* Follow def-use chain to find all the uses of this def. */
3115 for (du_link
= DF_REF_CHAIN (def
); du_link
; du_link
= du_link
->next
)
3117 struct ref
*use
= du_link
->ref
;
3118 struct df_link
*ud_link
;
3120 /* Only worry about the uses within BLOCKS. For example,
3121 consider a register defined within a loop that is live at the
3123 if (bitmap_bit_p (blocks
, DF_REF_BBNO (use
)))
3125 /* Follow use-def chain to check all the defs for this use. */
3126 for (ud_link
= DF_REF_CHAIN (use
); ud_link
; ud_link
= ud_link
->next
)
3127 if (ud_link
->ref
!= def
)
3135 /* Return nonzero if all the defs of INSN within BB dominates
3136 all the corresponding uses. */
3138 df_insn_dominates_uses_p (struct df
*df
, basic_block bb ATTRIBUTE_UNUSED
,
3139 rtx insn
, bitmap blocks
)
3142 struct df_link
*link
;
3144 uid
= INSN_UID (insn
);
3146 for (link
= df
->insns
[uid
].defs
; link
; link
= link
->next
)
3148 struct ref
*def
= link
->ref
;
3150 /* Only consider the defs within BLOCKS. */
3151 if (bitmap_bit_p (blocks
, DF_REF_BBNO (def
))
3152 && ! df_def_dominates_uses_p (df
, def
, blocks
))
3159 /* Return the basic block that REG referenced in or NULL if referenced
3160 in multiple basic blocks. */
3162 df_regno_bb (struct df
*df
, unsigned int regno
)
3164 struct df_link
*defs
= df
->regs
[regno
].defs
;
3165 struct df_link
*uses
= df
->regs
[regno
].uses
;
3166 struct ref
*def
= defs
? defs
->ref
: 0;
3167 struct ref
*use
= uses
? uses
->ref
: 0;
3168 basic_block bb_def
= def
? DF_REF_BB (def
) : 0;
3169 basic_block bb_use
= use
? DF_REF_BB (use
) : 0;
3171 /* Compare blocks of first def and last use. ???? FIXME. What if
3172 the reg-def and reg-use lists are not correctly ordered. */
3173 return bb_def
== bb_use
? bb_def
: 0;
3177 /* Return nonzero if REG used in multiple basic blocks. */
3179 df_reg_global_p (struct df
*df
, rtx reg
)
3181 return df_regno_bb (df
, REGNO (reg
)) != 0;
3185 /* Return total lifetime (in insns) of REG. */
3187 df_reg_lifetime (struct df
*df
, rtx reg
)
3189 return df
->regs
[REGNO (reg
)].lifetime
;
3193 /* Return nonzero if REG live at start of BB. */
3195 df_bb_reg_live_start_p (struct df
*df
, basic_block bb
, rtx reg
)
3197 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
3199 #ifdef ENABLE_CHECKING
3200 if (! bb_info
->lr_in
)
3204 return bitmap_bit_p (bb_info
->lr_in
, REGNO (reg
));
3208 /* Return nonzero if REG live at end of BB. */
3210 df_bb_reg_live_end_p (struct df
*df
, basic_block bb
, rtx reg
)
3212 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
3214 #ifdef ENABLE_CHECKING
3215 if (! bb_info
->lr_in
)
3219 return bitmap_bit_p (bb_info
->lr_out
, REGNO (reg
));
3223 /* Return -1 if life of REG1 before life of REG2, 1 if life of REG1
3224 after life of REG2, or 0, if the lives overlap. */
3226 df_bb_regs_lives_compare (struct df
*df
, basic_block bb
, rtx reg1
, rtx reg2
)
3228 unsigned int regno1
= REGNO (reg1
);
3229 unsigned int regno2
= REGNO (reg2
);
3236 /* The regs must be local to BB. */
3237 if (df_regno_bb (df
, regno1
) != bb
3238 || df_regno_bb (df
, regno2
) != bb
)
3241 def2
= df_bb_regno_first_def_find (df
, bb
, regno2
);
3242 use1
= df_bb_regno_last_use_find (df
, bb
, regno1
);
3244 if (DF_INSN_LUID (df
, DF_REF_INSN (def2
))
3245 > DF_INSN_LUID (df
, DF_REF_INSN (use1
)))
3248 def1
= df_bb_regno_first_def_find (df
, bb
, regno1
);
3249 use2
= df_bb_regno_last_use_find (df
, bb
, regno2
);
3251 if (DF_INSN_LUID (df
, DF_REF_INSN (def1
))
3252 > DF_INSN_LUID (df
, DF_REF_INSN (use2
)))
3259 /* Return last use of REGNO within BB. */
3261 df_bb_regno_last_use_find (struct df
*df
, basic_block bb
, unsigned int regno
)
3263 struct df_link
*link
;
3265 /* This assumes that the reg-use list is ordered such that for any
3266 BB, the last use is found first. However, since the BBs are not
3267 ordered, the first use in the chain is not necessarily the last
3268 use in the function. */
3269 for (link
= df
->regs
[regno
].uses
; link
; link
= link
->next
)
3271 struct ref
*use
= link
->ref
;
3273 if (DF_REF_BB (use
) == bb
)
3280 /* Return first def of REGNO within BB. */
3282 df_bb_regno_first_def_find (struct df
*df
, basic_block bb
, unsigned int regno
)
3284 struct df_link
*link
;
3286 /* This assumes that the reg-def list is ordered such that for any
3287 BB, the first def is found first. However, since the BBs are not
3288 ordered, the first def in the chain is not necessarily the first
3289 def in the function. */
3290 for (link
= df
->regs
[regno
].defs
; link
; link
= link
->next
)
3292 struct ref
*def
= link
->ref
;
3294 if (DF_REF_BB (def
) == bb
)
3300 /* Return last def of REGNO within BB. */
3302 df_bb_regno_last_def_find (struct df
*df
, basic_block bb
, unsigned int regno
)
3304 struct df_link
*link
;
3305 struct ref
*last_def
= NULL
;
3308 /* This assumes that the reg-def list is ordered such that for any
3309 BB, the first def is found first. However, since the BBs are not
3310 ordered, the first def in the chain is not necessarily the first
3311 def in the function. */
3312 for (link
= df
->regs
[regno
].defs
; link
; link
= link
->next
)
3314 struct ref
*def
= link
->ref
;
3315 /* The first time in the desired block. */
3316 if (DF_REF_BB (def
) == bb
)
3318 /* The last def in the desired block. */
3326 /* Return first use of REGNO inside INSN within BB. */
3328 df_bb_insn_regno_last_use_find (struct df
*df
,
3329 basic_block bb ATTRIBUTE_UNUSED
, rtx insn
,
3333 struct df_link
*link
;
3335 uid
= INSN_UID (insn
);
3337 for (link
= df
->insns
[uid
].uses
; link
; link
= link
->next
)
3339 struct ref
*use
= link
->ref
;
3341 if (DF_REF_REGNO (use
) == regno
)
3349 /* Return first def of REGNO inside INSN within BB. */
3351 df_bb_insn_regno_first_def_find (struct df
*df
,
3352 basic_block bb ATTRIBUTE_UNUSED
, rtx insn
,
3356 struct df_link
*link
;
3358 uid
= INSN_UID (insn
);
3360 for (link
= df
->insns
[uid
].defs
; link
; link
= link
->next
)
3362 struct ref
*def
= link
->ref
;
3364 if (DF_REF_REGNO (def
) == regno
)
3372 /* Return insn using REG if the BB contains only a single
3373 use and def of REG. */
3375 df_bb_single_def_use_insn_find (struct df
*df
, basic_block bb
, rtx insn
, rtx reg
)
3379 struct df_link
*du_link
;
3381 def
= df_bb_insn_regno_first_def_find (df
, bb
, insn
, REGNO (reg
));
3386 du_link
= DF_REF_CHAIN (def
);
3393 /* Check if def is dead. */
3397 /* Check for multiple uses. */
3401 return DF_REF_INSN (use
);
3404 /* Functions for debugging/dumping dataflow information. */
3407 /* Dump a def-use or use-def chain for REF to FILE. */
3409 df_chain_dump (struct df_link
*link
, FILE *file
)
3411 fprintf (file
, "{ ");
3412 for (; link
; link
= link
->next
)
3414 fprintf (file
, "%c%d ",
3415 DF_REF_REG_DEF_P (link
->ref
) ? 'd' : 'u',
3416 DF_REF_ID (link
->ref
));
3418 fprintf (file
, "}");
3422 /* Dump a chain of refs with the associated regno. */
3424 df_chain_dump_regno (struct df_link
*link
, FILE *file
)
3426 fprintf (file
, "{ ");
3427 for (; link
; link
= link
->next
)
3429 fprintf (file
, "%c%d(%d) ",
3430 DF_REF_REG_DEF_P (link
->ref
) ? 'd' : 'u',
3431 DF_REF_ID (link
->ref
),
3432 DF_REF_REGNO (link
->ref
));
3434 fprintf (file
, "}");
3438 /* Dump dataflow info. */
3440 df_dump (struct df
*df
, int flags
, FILE *file
)
3448 fprintf (file
, "\nDataflow summary:\n");
3449 fprintf (file
, "n_regs = %d, n_defs = %d, n_uses = %d, n_bbs = %d\n",
3450 df
->n_regs
, df
->n_defs
, df
->n_uses
, df
->n_bbs
);
3456 fprintf (file
, "Reaching defs:\n");
3459 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
3461 if (! bb_info
->rd_in
)
3464 fprintf (file
, "bb %d in \t", bb
->index
);
3465 dump_bitmap (file
, bb_info
->rd_in
);
3466 fprintf (file
, "bb %d gen \t", bb
->index
);
3467 dump_bitmap (file
, bb_info
->rd_gen
);
3468 fprintf (file
, "bb %d kill\t", bb
->index
);
3469 dump_bitmap (file
, bb_info
->rd_kill
);
3470 fprintf (file
, "bb %d out \t", bb
->index
);
3471 dump_bitmap (file
, bb_info
->rd_out
);
3475 if (flags
& DF_UD_CHAIN
)
3477 fprintf (file
, "Use-def chains:\n");
3478 for (j
= 0; j
< df
->n_defs
; j
++)
3482 fprintf (file
, "d%d bb %d luid %d insn %d reg %d ",
3483 j
, DF_REF_BBNO (df
->defs
[j
]),
3484 DF_INSN_LUID (df
, DF_REF_INSN (df
->defs
[j
])),
3485 DF_REF_INSN_UID (df
->defs
[j
]),
3486 DF_REF_REGNO (df
->defs
[j
]));
3487 if (df
->defs
[j
]->flags
& DF_REF_READ_WRITE
)
3488 fprintf (file
, "read/write ");
3489 df_chain_dump (DF_REF_CHAIN (df
->defs
[j
]), file
);
3490 fprintf (file
, "\n");
3497 fprintf (file
, "Reaching uses:\n");
3500 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
3502 if (! bb_info
->ru_in
)
3505 fprintf (file
, "bb %d in \t", bb
->index
);
3506 dump_bitmap (file
, bb_info
->ru_in
);
3507 fprintf (file
, "bb %d gen \t", bb
->index
);
3508 dump_bitmap (file
, bb_info
->ru_gen
);
3509 fprintf (file
, "bb %d kill\t", bb
->index
);
3510 dump_bitmap (file
, bb_info
->ru_kill
);
3511 fprintf (file
, "bb %d out \t", bb
->index
);
3512 dump_bitmap (file
, bb_info
->ru_out
);
3516 if (flags
& DF_DU_CHAIN
)
3518 fprintf (file
, "Def-use chains:\n");
3519 for (j
= 0; j
< df
->n_uses
; j
++)
3523 fprintf (file
, "u%d bb %d luid %d insn %d reg %d ",
3524 j
, DF_REF_BBNO (df
->uses
[j
]),
3525 DF_INSN_LUID (df
, DF_REF_INSN (df
->uses
[j
])),
3526 DF_REF_INSN_UID (df
->uses
[j
]),
3527 DF_REF_REGNO (df
->uses
[j
]));
3528 if (df
->uses
[j
]->flags
& DF_REF_READ_WRITE
)
3529 fprintf (file
, "read/write ");
3530 df_chain_dump (DF_REF_CHAIN (df
->uses
[j
]), file
);
3531 fprintf (file
, "\n");
3538 fprintf (file
, "Live regs:\n");
3541 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
3543 if (! bb_info
->lr_in
)
3546 fprintf (file
, "bb %d in \t", bb
->index
);
3547 dump_bitmap (file
, bb_info
->lr_in
);
3548 fprintf (file
, "bb %d use \t", bb
->index
);
3549 dump_bitmap (file
, bb_info
->lr_use
);
3550 fprintf (file
, "bb %d def \t", bb
->index
);
3551 dump_bitmap (file
, bb_info
->lr_def
);
3552 fprintf (file
, "bb %d out \t", bb
->index
);
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 (struct df
*df
, rtx insn
, FILE *file
)
3616 uid
= INSN_UID (insn
);
3617 if (uid
>= df
->insn_size
)
3620 if (df
->insns
[uid
].defs
)
3621 bbi
= DF_REF_BBNO (df
->insns
[uid
].defs
->ref
);
3622 else if (df
->insns
[uid
].uses
)
3623 bbi
= DF_REF_BBNO (df
->insns
[uid
].uses
->ref
);
3627 fprintf (file
, "insn %d bb %d luid %d defs ",
3628 uid
, bbi
, DF_INSN_LUID (df
, insn
));
3629 df_chain_dump (df
->insns
[uid
].defs
, file
);
3630 fprintf (file
, " uses ");
3631 df_chain_dump (df
->insns
[uid
].uses
, file
);
3632 fprintf (file
, "\n");
3637 df_insn_debug_regno (struct df
*df
, rtx insn
, FILE *file
)
3642 uid
= INSN_UID (insn
);
3643 if (uid
>= df
->insn_size
)
3646 if (df
->insns
[uid
].defs
)
3647 bbi
= DF_REF_BBNO (df
->insns
[uid
].defs
->ref
);
3648 else if (df
->insns
[uid
].uses
)
3649 bbi
= DF_REF_BBNO (df
->insns
[uid
].uses
->ref
);
3653 fprintf (file
, "insn %d bb %d luid %d defs ",
3654 uid
, bbi
, DF_INSN_LUID (df
, insn
));
3655 df_chain_dump_regno (df
->insns
[uid
].defs
, file
);
3656 fprintf (file
, " uses ");
3657 df_chain_dump_regno (df
->insns
[uid
].uses
, file
);
3658 fprintf (file
, "\n");
3663 df_regno_debug (struct df
*df
, unsigned int regno
, FILE *file
)
3665 if (regno
>= df
->reg_size
)
3668 fprintf (file
, "reg %d life %d defs ",
3669 regno
, df
->regs
[regno
].lifetime
);
3670 df_chain_dump (df
->regs
[regno
].defs
, file
);
3671 fprintf (file
, " uses ");
3672 df_chain_dump (df
->regs
[regno
].uses
, file
);
3673 fprintf (file
, "\n");
3678 df_ref_debug (struct df
*df
, struct ref
*ref
, FILE *file
)
3680 fprintf (file
, "%c%d ",
3681 DF_REF_REG_DEF_P (ref
) ? 'd' : 'u',
3683 fprintf (file
, "reg %d bb %d luid %d insn %d chain ",
3686 DF_INSN_LUID (df
, DF_REF_INSN (ref
)),
3687 INSN_UID (DF_REF_INSN (ref
)));
3688 df_chain_dump (DF_REF_CHAIN (ref
), file
);
3689 fprintf (file
, "\n");
3692 /* Functions for debugging from GDB. */
3695 debug_df_insn (rtx insn
)
3697 df_insn_debug (ddf
, insn
, stderr
);
3703 debug_df_reg (rtx reg
)
3705 df_regno_debug (ddf
, REGNO (reg
), stderr
);
3710 debug_df_regno (unsigned int regno
)
3712 df_regno_debug (ddf
, regno
, stderr
);
3717 debug_df_ref (struct ref
*ref
)
3719 df_ref_debug (ddf
, ref
, stderr
);
3724 debug_df_defno (unsigned int defno
)
3726 df_ref_debug (ddf
, ddf
->defs
[defno
], stderr
);
3731 debug_df_useno (unsigned int defno
)
3733 df_ref_debug (ddf
, ddf
->uses
[defno
], stderr
);
3738 debug_df_chain (struct df_link
*link
)
3740 df_chain_dump (link
, stderr
);
3741 fputc ('\n', stderr
);
3746 dataflow_set_a_op_b (enum set_representation repr
,
3747 enum df_confluence_op op
,
3748 void *rslt
, void *op1
, void *op2
)
3756 sbitmap_a_or_b (rslt
, op1
, op2
);
3759 case DF_INTERSECTION
:
3760 sbitmap_a_and_b (rslt
, op1
, op2
);
3772 bitmap_a_or_b (rslt
, op1
, op2
);
3775 case DF_INTERSECTION
:
3776 bitmap_a_and_b (rslt
, op1
, op2
);
3790 dataflow_set_copy (enum set_representation repr
, void *dest
, void *src
)
3795 sbitmap_copy (dest
, src
);
3799 bitmap_copy (dest
, src
);
3807 /* Hybrid search algorithm from "Implementation Techniques for
3808 Efficient Data-Flow Analysis of Large Programs". */
3811 hybrid_search (basic_block bb
, struct dataflow
*dataflow
,
3812 sbitmap visited
, sbitmap pending
, sbitmap considered
)
3818 SET_BIT (visited
, bb
->index
);
3819 if (!TEST_BIT (pending
, bb
->index
))
3821 RESET_BIT (pending
, i
);
3823 #define HS(E_ANTI, E_ANTI_NEXT, E_ANTI_BB, E_ANTI_START_BB, IN_SET, \
3824 E, E_NEXT, E_BB, E_START_BB, OUT_SET) \
3827 /* Calculate <conf_op> of predecessor_outs. */ \
3828 bitmap_zero (IN_SET[i]); \
3829 for (e = bb->E_ANTI; e; e = e->E_ANTI_NEXT) \
3831 if (e->E_ANTI_BB == E_ANTI_START_BB) \
3833 if (!TEST_BIT (considered, e->E_ANTI_BB->index)) \
3836 dataflow_set_a_op_b (dataflow->repr, dataflow->conf_op, \
3837 IN_SET[i], IN_SET[i], \
3838 OUT_SET[e->E_ANTI_BB->index]); \
3841 (*dataflow->transfun)(i, &changed, \
3842 dataflow->in[i], dataflow->out[i], \
3843 dataflow->gen[i], dataflow->kill[i], \
3849 for (e = bb->E; e; e = e->E_NEXT) \
3851 if (e->E_BB == E_START_BB || e->E_BB->index == i) \
3854 if (!TEST_BIT (considered, e->E_BB->index)) \
3857 SET_BIT (pending, e->E_BB->index); \
3860 for (e = bb->E; e; e = e->E_NEXT) \
3862 if (e->E_BB == E_START_BB || e->E_BB->index == i) \
3865 if (!TEST_BIT (considered, e->E_BB->index)) \
3868 if (!TEST_BIT (visited, e->E_BB->index)) \
3869 hybrid_search (e->E_BB, dataflow, visited, pending, considered); \
3873 if (dataflow
->dir
== DF_FORWARD
)
3874 HS (pred
, pred_next
, src
, ENTRY_BLOCK_PTR
, dataflow
->in
,
3875 succ
, succ_next
, dest
, EXIT_BLOCK_PTR
, dataflow
->out
);
3877 HS (succ
, succ_next
, dest
, EXIT_BLOCK_PTR
, dataflow
->out
,
3878 pred
, pred_next
, src
, ENTRY_BLOCK_PTR
, dataflow
->in
);
3881 /* This function will perform iterative bitvector dataflow described by
3882 DATAFLOW, producing the in and out sets. Only the part of the cfg
3883 induced by blocks in DATAFLOW->order is taken into account.
3885 For forward problems, you probably want to pass in a mapping of
3886 block number to rc_order (like df->inverse_rc_map). */
3889 iterative_dataflow (struct dataflow
*dataflow
)
3892 sbitmap visited
, pending
, considered
;
3894 pending
= sbitmap_alloc (last_basic_block
);
3895 visited
= sbitmap_alloc (last_basic_block
);
3896 considered
= sbitmap_alloc (last_basic_block
);
3897 sbitmap_zero (pending
);
3898 sbitmap_zero (visited
);
3899 sbitmap_zero (considered
);
3901 for (i
= 0; i
< dataflow
->n_blocks
; i
++)
3903 idx
= dataflow
->order
[i
];
3904 SET_BIT (pending
, idx
);
3905 SET_BIT (considered
, idx
);
3906 if (dataflow
->dir
== DF_FORWARD
)
3907 dataflow_set_copy (dataflow
->repr
,
3908 dataflow
->out
[idx
], dataflow
->gen
[idx
]);
3910 dataflow_set_copy (dataflow
->repr
,
3911 dataflow
->in
[idx
], dataflow
->gen
[idx
]);
3916 for (i
= 0; i
< dataflow
->n_blocks
; i
++)
3918 idx
= dataflow
->order
[i
];
3920 if (TEST_BIT (pending
, idx
) && !TEST_BIT (visited
, idx
))
3921 hybrid_search (BASIC_BLOCK (idx
), dataflow
,
3922 visited
, pending
, considered
);
3925 if (sbitmap_first_set_bit (pending
) == -1)
3928 sbitmap_zero (visited
);
3931 sbitmap_free (pending
);
3932 sbitmap_free (visited
);
3933 sbitmap_free (considered
);