1 /* Dataflow support routines.
2 Copyright (C) 1999, 2000, 2001, 2002 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_EACH_BB_IN_BITMAP(BITMAP, MIN, BB, CODE) \
176 unsigned int node_; \
177 EXECUTE_IF_SET_IN_BITMAP (BITMAP, MIN, node_, \
178 {(BB) = BASIC_BLOCK (node_); CODE;});} while (0)
180 #define FOR_EACH_BB_IN_BITMAP_REV(BITMAP, MIN, BB, CODE) \
182 unsigned int node_; \
183 EXECUTE_IF_SET_IN_BITMAP_REV (BITMAP, node_, \
184 {(BB) = BASIC_BLOCK (node_); CODE;});} while (0)
186 #define FOR_EACH_BB_IN_SBITMAP(BITMAP, MIN, BB, CODE) \
188 unsigned int node_; \
189 EXECUTE_IF_SET_IN_SBITMAP (BITMAP, MIN, node_, \
190 {(BB) = BASIC_BLOCK (node_); CODE;});} while (0)
192 #define obstack_chunk_alloc xmalloc
193 #define obstack_chunk_free free
195 static struct obstack df_ref_obstack
;
196 static struct df
*ddf
;
198 static void df_reg_table_realloc
PARAMS((struct df
*, int));
200 static void df_def_table_realloc
PARAMS((struct df
*, int));
202 static void df_insn_table_realloc
PARAMS((struct df
*, int));
203 static void df_bitmaps_alloc
PARAMS((struct df
*, int));
204 static void df_bitmaps_free
PARAMS((struct df
*, int));
205 static void df_free
PARAMS((struct df
*));
206 static void df_alloc
PARAMS((struct df
*, int));
208 static rtx df_reg_clobber_gen
PARAMS((unsigned int));
209 static rtx df_reg_use_gen
PARAMS((unsigned int));
211 static inline struct df_link
*df_link_create
PARAMS((struct ref
*,
213 static struct df_link
*df_ref_unlink
PARAMS((struct df_link
**, struct ref
*));
214 static void df_def_unlink
PARAMS((struct df
*, struct ref
*));
215 static void df_use_unlink
PARAMS((struct df
*, struct ref
*));
216 static void df_insn_refs_unlink
PARAMS ((struct df
*, basic_block
, rtx
));
218 static void df_bb_refs_unlink
PARAMS ((struct df
*, basic_block
));
219 static void df_refs_unlink
PARAMS ((struct df
*, bitmap
));
222 static struct ref
*df_ref_create
PARAMS((struct df
*,
224 enum df_ref_type
, enum df_ref_flags
));
225 static void df_ref_record_1
PARAMS((struct df
*, rtx
, rtx
*,
226 rtx
, enum df_ref_type
,
228 static void df_ref_record
PARAMS((struct df
*, rtx
, rtx
*,
229 rtx
, enum df_ref_type
,
231 static void df_def_record_1
PARAMS((struct df
*, rtx
, basic_block
, rtx
));
232 static void df_defs_record
PARAMS((struct df
*, rtx
, basic_block
, rtx
));
233 static void df_uses_record
PARAMS((struct df
*, rtx
*,
234 enum df_ref_type
, basic_block
, rtx
,
236 static void df_insn_refs_record
PARAMS((struct df
*, basic_block
, rtx
));
237 static void df_bb_refs_record
PARAMS((struct df
*, basic_block
));
238 static void df_refs_record
PARAMS((struct df
*, bitmap
));
240 static void df_bb_reg_def_chain_create
PARAMS((struct df
*, basic_block
));
241 static void df_reg_def_chain_create
PARAMS((struct df
*, bitmap
));
242 static void df_bb_reg_use_chain_create
PARAMS((struct df
*, basic_block
));
243 static void df_reg_use_chain_create
PARAMS((struct df
*, bitmap
));
244 static void df_bb_du_chain_create
PARAMS((struct df
*, basic_block
, bitmap
));
245 static void df_du_chain_create
PARAMS((struct df
*, bitmap
));
246 static void df_bb_ud_chain_create
PARAMS((struct df
*, basic_block
));
247 static void df_ud_chain_create
PARAMS((struct df
*, bitmap
));
248 static void df_bb_rd_local_compute
PARAMS((struct df
*, basic_block
));
249 static void df_rd_local_compute
PARAMS((struct df
*, bitmap
));
250 static void df_bb_ru_local_compute
PARAMS((struct df
*, basic_block
));
251 static void df_ru_local_compute
PARAMS((struct df
*, bitmap
));
252 static void df_bb_lr_local_compute
PARAMS((struct df
*, basic_block
));
253 static void df_lr_local_compute
PARAMS((struct df
*, bitmap
));
254 static void df_bb_reg_info_compute
PARAMS((struct df
*, basic_block
, bitmap
));
255 static void df_reg_info_compute
PARAMS((struct df
*, bitmap
));
257 static int df_bb_luids_set
PARAMS((struct df
*df
, basic_block
));
258 static int df_luids_set
PARAMS((struct df
*df
, bitmap
));
260 static int df_modified_p
PARAMS ((struct df
*, bitmap
));
261 static int df_refs_queue
PARAMS ((struct df
*));
262 static int df_refs_process
PARAMS ((struct df
*));
263 static int df_bb_refs_update
PARAMS ((struct df
*, basic_block
));
264 static int df_refs_update
PARAMS ((struct df
*));
265 static void df_analyse_1
PARAMS((struct df
*, bitmap
, int, int));
267 static void df_insns_modify
PARAMS((struct df
*, basic_block
,
269 static int df_rtx_mem_replace
PARAMS ((rtx
*, void *));
270 static int df_rtx_reg_replace
PARAMS ((rtx
*, void *));
271 void df_refs_reg_replace
PARAMS ((struct df
*, bitmap
,
272 struct df_link
*, rtx
, rtx
));
274 static int df_def_dominates_all_uses_p
PARAMS((struct df
*, struct ref
*def
));
275 static int df_def_dominates_uses_p
PARAMS((struct df
*,
276 struct ref
*def
, bitmap
));
277 static struct ref
*df_bb_regno_last_use_find
PARAMS((struct df
*, basic_block
,
279 static struct ref
*df_bb_regno_first_def_find
PARAMS((struct df
*, basic_block
,
281 static struct ref
*df_bb_insn_regno_last_use_find
PARAMS((struct df
*,
284 static struct ref
*df_bb_insn_regno_first_def_find
PARAMS((struct df
*,
288 static void df_chain_dump
PARAMS((struct df_link
*, FILE *file
));
289 static void df_chain_dump_regno
PARAMS((struct df_link
*, FILE *file
));
290 static void df_regno_debug
PARAMS ((struct df
*, unsigned int, FILE *));
291 static void df_ref_debug
PARAMS ((struct df
*, struct ref
*, FILE *));
292 static void df_rd_transfer_function
PARAMS ((int, int *, bitmap
, bitmap
,
293 bitmap
, bitmap
, void *));
294 static void df_ru_transfer_function
PARAMS ((int, int *, bitmap
, bitmap
,
295 bitmap
, bitmap
, void *));
296 static void df_lr_transfer_function
PARAMS ((int, int *, bitmap
, bitmap
,
297 bitmap
, bitmap
, void *));
298 static void hybrid_search_bitmap
PARAMS ((basic_block
, bitmap
*, bitmap
*,
299 bitmap
*, bitmap
*, enum df_flow_dir
,
300 enum df_confluence_op
,
301 transfer_function_bitmap
,
302 sbitmap
, sbitmap
, void *));
303 static void hybrid_search_sbitmap
PARAMS ((basic_block
, sbitmap
*, sbitmap
*,
304 sbitmap
*, sbitmap
*, enum df_flow_dir
,
305 enum df_confluence_op
,
306 transfer_function_sbitmap
,
307 sbitmap
, sbitmap
, void *));
308 static inline bool read_modify_subreg_p
PARAMS ((rtx
));
311 /* Local memory allocation/deallocation routines. */
314 /* Increase the insn info table by SIZE more elements. */
316 df_insn_table_realloc (df
, size
)
320 /* Make table 25 percent larger by default. */
322 size
= df
->insn_size
/ 4;
324 size
+= df
->insn_size
;
326 df
->insns
= (struct insn_info
*)
327 xrealloc (df
->insns
, size
* sizeof (struct insn_info
));
329 memset (df
->insns
+ df
->insn_size
, 0,
330 (size
- df
->insn_size
) * sizeof (struct insn_info
));
332 df
->insn_size
= size
;
334 if (! df
->insns_modified
)
336 df
->insns_modified
= BITMAP_XMALLOC ();
337 bitmap_zero (df
->insns_modified
);
342 /* Increase the reg info table by SIZE more elements. */
344 df_reg_table_realloc (df
, size
)
348 /* Make table 25 percent larger by default. */
350 size
= df
->reg_size
/ 4;
352 size
+= df
->reg_size
;
354 df
->regs
= (struct reg_info
*)
355 xrealloc (df
->regs
, size
* sizeof (struct reg_info
));
357 /* Zero the new entries. */
358 memset (df
->regs
+ df
->reg_size
, 0,
359 (size
- df
->reg_size
) * sizeof (struct reg_info
));
366 /* Not currently used. */
368 df_def_table_realloc (df
, size
)
375 /* Make table 25 percent larger by default. */
377 size
= df
->def_size
/ 4;
379 df
->def_size
+= size
;
380 df
->defs
= xrealloc (df
->defs
,
381 df
->def_size
* sizeof (*df
->defs
));
383 /* Allocate a new block of memory and link into list of blocks
384 that will need to be freed later. */
386 refs
= xmalloc (size
* sizeof (*refs
));
388 /* Link all the new refs together, overloading the chain field. */
389 for (i
= 0; i
< size
- 1; i
++)
390 refs
[i
].chain
= (struct df_link
*)(refs
+ i
+ 1);
391 refs
[size
- 1].chain
= 0;
397 /* Allocate bitmaps for each basic block. */
399 df_bitmaps_alloc (df
, flags
)
406 /* Free the bitmaps if they need resizing. */
407 if ((flags
& DF_LR
) && df
->n_regs
< (unsigned int)max_reg_num ())
408 dflags
|= DF_LR
| DF_RU
;
409 if ((flags
& DF_RU
) && df
->n_uses
< df
->use_id
)
411 if ((flags
& DF_RD
) && df
->n_defs
< df
->def_id
)
415 df_bitmaps_free (df
, dflags
);
417 df
->n_defs
= df
->def_id
;
418 df
->n_uses
= df
->use_id
;
422 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
424 if (flags
& DF_RD
&& ! bb_info
->rd_in
)
426 /* Allocate bitmaps for reaching definitions. */
427 bb_info
->rd_kill
= BITMAP_XMALLOC ();
428 bitmap_zero (bb_info
->rd_kill
);
429 bb_info
->rd_gen
= BITMAP_XMALLOC ();
430 bitmap_zero (bb_info
->rd_gen
);
431 bb_info
->rd_in
= BITMAP_XMALLOC ();
432 bb_info
->rd_out
= BITMAP_XMALLOC ();
433 bb_info
->rd_valid
= 0;
436 if (flags
& DF_RU
&& ! bb_info
->ru_in
)
438 /* Allocate bitmaps for upward exposed uses. */
439 bb_info
->ru_kill
= BITMAP_XMALLOC ();
440 bitmap_zero (bb_info
->ru_kill
);
441 /* Note the lack of symmetry. */
442 bb_info
->ru_gen
= BITMAP_XMALLOC ();
443 bitmap_zero (bb_info
->ru_gen
);
444 bb_info
->ru_in
= BITMAP_XMALLOC ();
445 bb_info
->ru_out
= BITMAP_XMALLOC ();
446 bb_info
->ru_valid
= 0;
449 if (flags
& DF_LR
&& ! bb_info
->lr_in
)
451 /* Allocate bitmaps for live variables. */
452 bb_info
->lr_def
= BITMAP_XMALLOC ();
453 bitmap_zero (bb_info
->lr_def
);
454 bb_info
->lr_use
= BITMAP_XMALLOC ();
455 bitmap_zero (bb_info
->lr_use
);
456 bb_info
->lr_in
= BITMAP_XMALLOC ();
457 bb_info
->lr_out
= BITMAP_XMALLOC ();
458 bb_info
->lr_valid
= 0;
464 /* Free bitmaps for each basic block. */
466 df_bitmaps_free (df
, flags
)
467 struct df
*df ATTRIBUTE_UNUSED
;
474 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
479 if ((flags
& DF_RD
) && bb_info
->rd_in
)
481 /* Free bitmaps for reaching definitions. */
482 BITMAP_XFREE (bb_info
->rd_kill
);
483 bb_info
->rd_kill
= NULL
;
484 BITMAP_XFREE (bb_info
->rd_gen
);
485 bb_info
->rd_gen
= NULL
;
486 BITMAP_XFREE (bb_info
->rd_in
);
487 bb_info
->rd_in
= NULL
;
488 BITMAP_XFREE (bb_info
->rd_out
);
489 bb_info
->rd_out
= NULL
;
492 if ((flags
& DF_RU
) && bb_info
->ru_in
)
494 /* Free bitmaps for upward exposed uses. */
495 BITMAP_XFREE (bb_info
->ru_kill
);
496 bb_info
->ru_kill
= NULL
;
497 BITMAP_XFREE (bb_info
->ru_gen
);
498 bb_info
->ru_gen
= NULL
;
499 BITMAP_XFREE (bb_info
->ru_in
);
500 bb_info
->ru_in
= NULL
;
501 BITMAP_XFREE (bb_info
->ru_out
);
502 bb_info
->ru_out
= NULL
;
505 if ((flags
& DF_LR
) && bb_info
->lr_in
)
507 /* Free bitmaps for live variables. */
508 BITMAP_XFREE (bb_info
->lr_def
);
509 bb_info
->lr_def
= NULL
;
510 BITMAP_XFREE (bb_info
->lr_use
);
511 bb_info
->lr_use
= NULL
;
512 BITMAP_XFREE (bb_info
->lr_in
);
513 bb_info
->lr_in
= NULL
;
514 BITMAP_XFREE (bb_info
->lr_out
);
515 bb_info
->lr_out
= NULL
;
518 df
->flags
&= ~(flags
& (DF_RD
| DF_RU
| DF_LR
));
522 /* Allocate and initialise dataflow memory. */
524 df_alloc (df
, n_regs
)
531 gcc_obstack_init (&df_ref_obstack
);
533 /* Perhaps we should use LUIDs to save memory for the insn_refs
534 table. This is only a small saving; a few pointers. */
535 n_insns
= get_max_uid () + 1;
539 /* Approximate number of defs by number of insns. */
540 df
->def_size
= n_insns
;
541 df
->defs
= xmalloc (df
->def_size
* sizeof (*df
->defs
));
545 /* Approximate number of uses by twice number of insns. */
546 df
->use_size
= n_insns
* 2;
547 df
->uses
= xmalloc (df
->use_size
* sizeof (*df
->uses
));
550 df
->n_bbs
= last_basic_block
;
552 /* Allocate temporary working array used during local dataflow analysis. */
553 df
->reg_def_last
= xmalloc (df
->n_regs
* sizeof (struct ref
*));
555 df_insn_table_realloc (df
, n_insns
);
557 df_reg_table_realloc (df
, df
->n_regs
);
559 df
->bbs_modified
= BITMAP_XMALLOC ();
560 bitmap_zero (df
->bbs_modified
);
564 df
->bbs
= xcalloc (last_basic_block
, sizeof (struct bb_info
));
566 df
->all_blocks
= BITMAP_XMALLOC ();
568 bitmap_set_bit (df
->all_blocks
, bb
->index
);
572 /* Free all the dataflow info. */
577 df_bitmaps_free (df
, DF_ALL
);
605 if (df
->bbs_modified
)
606 BITMAP_XFREE (df
->bbs_modified
);
607 df
->bbs_modified
= 0;
609 if (df
->insns_modified
)
610 BITMAP_XFREE (df
->insns_modified
);
611 df
->insns_modified
= 0;
613 BITMAP_XFREE (df
->all_blocks
);
616 obstack_free (&df_ref_obstack
, NULL
);
619 /* Local miscellaneous routines. */
621 /* Return a USE for register REGNO. */
622 static rtx
df_reg_use_gen (regno
)
628 reg
= regno_reg_rtx
[regno
];
630 use
= gen_rtx_USE (GET_MODE (reg
), reg
);
635 /* Return a CLOBBER for register REGNO. */
636 static rtx
df_reg_clobber_gen (regno
)
642 reg
= regno_reg_rtx
[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
, insn
, ref_type
, ref_flags
)
792 enum df_ref_type ref_type
;
793 enum df_ref_flags ref_flags
;
795 struct ref
*this_ref
;
798 this_ref
= (struct ref
*) obstack_alloc (&df_ref_obstack
,
800 DF_REF_REG (this_ref
) = reg
;
801 DF_REF_LOC (this_ref
) = loc
;
802 DF_REF_INSN (this_ref
) = insn
;
803 DF_REF_CHAIN (this_ref
) = 0;
804 DF_REF_TYPE (this_ref
) = ref_type
;
805 DF_REF_FLAGS (this_ref
) = ref_flags
;
806 uid
= INSN_UID (insn
);
808 if (ref_type
== DF_REF_REG_DEF
)
810 if (df
->def_id
>= df
->def_size
)
812 /* Make table 25 percent larger. */
813 df
->def_size
+= (df
->def_size
/ 4);
814 df
->defs
= xrealloc (df
->defs
,
815 df
->def_size
* sizeof (*df
->defs
));
817 DF_REF_ID (this_ref
) = df
->def_id
;
818 df
->defs
[df
->def_id
++] = this_ref
;
822 if (df
->use_id
>= df
->use_size
)
824 /* Make table 25 percent larger. */
825 df
->use_size
+= (df
->use_size
/ 4);
826 df
->uses
= xrealloc (df
->uses
,
827 df
->use_size
* sizeof (*df
->uses
));
829 DF_REF_ID (this_ref
) = df
->use_id
;
830 df
->uses
[df
->use_id
++] = this_ref
;
836 /* Create a new reference of type DF_REF_TYPE for a single register REG,
837 used inside the LOC rtx of INSN. */
839 df_ref_record_1 (df
, reg
, loc
, insn
, ref_type
, ref_flags
)
844 enum df_ref_type ref_type
;
845 enum df_ref_flags ref_flags
;
847 df_ref_create (df
, reg
, loc
, insn
, ref_type
, ref_flags
);
851 /* Create new references of type DF_REF_TYPE for each part of register REG
852 at address LOC within INSN of BB. */
854 df_ref_record (df
, reg
, loc
, insn
, ref_type
, ref_flags
)
859 enum df_ref_type ref_type
;
860 enum df_ref_flags ref_flags
;
864 if (GET_CODE (reg
) != REG
&& GET_CODE (reg
) != SUBREG
)
867 /* For the reg allocator we are interested in some SUBREG rtx's, but not
868 all. Notably only those representing a word extraction from a multi-word
869 reg. As written in the docu those should have the form
870 (subreg:SI (reg:M A) N), with size(SImode) > size(Mmode).
871 XXX Is that true? We could also use the global word_mode variable. */
872 if (GET_CODE (reg
) == SUBREG
873 && (GET_MODE_SIZE (GET_MODE (reg
)) < GET_MODE_SIZE (word_mode
)
874 || GET_MODE_SIZE (GET_MODE (reg
))
875 >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (reg
)))))
877 loc
= &SUBREG_REG (reg
);
881 regno
= REGNO (GET_CODE (reg
) == SUBREG
? SUBREG_REG (reg
) : reg
);
882 if (regno
< FIRST_PSEUDO_REGISTER
)
887 if (! (df
->flags
& DF_HARD_REGS
))
890 /* GET_MODE (reg) is correct here. We don't want to go into a SUBREG
891 for the mode, because we only want to add references to regs, which
892 are really referenced. E.g. a (subreg:SI (reg:DI 0) 0) does _not_
893 reference the whole reg 0 in DI mode (which would also include
894 reg 1, at least, if 0 and 1 are SImode registers). */
895 endregno
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (reg
));
897 for (i
= regno
; i
< endregno
; i
++)
898 df_ref_record_1 (df
, regno_reg_rtx
[i
],
899 loc
, insn
, ref_type
, ref_flags
);
903 df_ref_record_1 (df
, reg
, loc
, insn
, ref_type
, ref_flags
);
907 /* Writes to SUBREG of inndermode wider than word and outermode shorter than
908 word are read-modify-write. */
911 read_modify_subreg_p (x
)
914 if (GET_CODE (x
) != SUBREG
)
916 if (GET_MODE_SIZE (GET_MODE (SUBREG_REG (x
))) <= UNITS_PER_WORD
)
918 if (GET_MODE_SIZE (GET_MODE (x
)) > UNITS_PER_WORD
)
923 /* Process all the registers defined in the rtx, X. */
925 df_def_record_1 (df
, x
, bb
, insn
)
931 rtx
*loc
= &SET_DEST (x
);
933 enum df_ref_flags flags
= 0;
935 /* Some targets place small structures in registers for
936 return values of functions. */
937 if (GET_CODE (dst
) == PARALLEL
&& GET_MODE (dst
) == BLKmode
)
941 for (i
= XVECLEN (dst
, 0) - 1; i
>= 0; i
--)
942 df_def_record_1 (df
, XVECEXP (dst
, 0, i
), bb
, insn
);
946 /* May be, we should flag the use of strict_low_part somehow. Might be
947 handy for the reg allocator. */
948 while (GET_CODE (dst
) == STRICT_LOW_PART
949 || GET_CODE (dst
) == ZERO_EXTRACT
950 || GET_CODE (dst
) == SIGN_EXTRACT
951 || read_modify_subreg_p (dst
))
953 /* Strict low part always contains SUBREG, but we don't want to make
954 it appear outside, as whole register is always considered. */
955 if (GET_CODE (dst
) == STRICT_LOW_PART
)
957 loc
= &XEXP (dst
, 0);
960 loc
= &XEXP (dst
, 0);
962 flags
|= DF_REF_READ_WRITE
;
965 if (GET_CODE (dst
) == REG
966 || (GET_CODE (dst
) == SUBREG
&& GET_CODE (SUBREG_REG (dst
)) == REG
))
967 df_ref_record (df
, dst
, loc
, insn
, DF_REF_REG_DEF
, flags
);
971 /* Process all the registers defined in the pattern rtx, X. */
973 df_defs_record (df
, x
, bb
, insn
)
979 RTX_CODE code
= GET_CODE (x
);
981 if (code
== SET
|| code
== CLOBBER
)
983 /* Mark the single def within the pattern. */
984 df_def_record_1 (df
, x
, bb
, insn
);
986 else if (code
== PARALLEL
)
990 /* Mark the multiple defs within the pattern. */
991 for (i
= XVECLEN (x
, 0) - 1; i
>= 0; i
--)
993 code
= GET_CODE (XVECEXP (x
, 0, i
));
994 if (code
== SET
|| code
== CLOBBER
)
995 df_def_record_1 (df
, XVECEXP (x
, 0, i
), bb
, insn
);
1001 /* Process all the registers used in the rtx at address LOC. */
1003 df_uses_record (df
, loc
, ref_type
, bb
, insn
, flags
)
1006 enum df_ref_type ref_type
;
1009 enum df_ref_flags flags
;
1017 code
= GET_CODE (x
);
1032 /* If we are clobbering a MEM, mark any registers inside the address
1034 if (GET_CODE (XEXP (x
, 0)) == MEM
)
1035 df_uses_record (df
, &XEXP (XEXP (x
, 0), 0),
1036 DF_REF_REG_MEM_STORE
, bb
, insn
, flags
);
1038 /* If we're clobbering a REG then we have a def so ignore. */
1042 df_uses_record (df
, &XEXP (x
, 0), DF_REF_REG_MEM_LOAD
, bb
, insn
, flags
);
1046 /* While we're here, optimize this case. */
1048 /* In case the SUBREG is not of a register, don't optimize. */
1049 if (GET_CODE (SUBREG_REG (x
)) != REG
)
1051 loc
= &SUBREG_REG (x
);
1052 df_uses_record (df
, loc
, ref_type
, bb
, insn
, flags
);
1056 /* ... Fall through ... */
1059 /* See a register (or subreg) other than being set. */
1060 df_ref_record (df
, x
, loc
, insn
, ref_type
, flags
);
1065 rtx dst
= SET_DEST (x
);
1067 df_uses_record (df
, &SET_SRC (x
), DF_REF_REG_USE
, bb
, insn
, 0);
1069 switch (GET_CODE (dst
))
1072 if (read_modify_subreg_p (dst
))
1074 df_uses_record (df
, &SUBREG_REG (dst
), DF_REF_REG_USE
, bb
,
1075 insn
, DF_REF_READ_WRITE
);
1078 /* ... FALLTHRU ... */
1083 df_uses_record (df
, &XEXP (dst
, 0),
1084 DF_REF_REG_MEM_STORE
,
1087 case STRICT_LOW_PART
:
1088 /* A strict_low_part uses the whole reg not only the subreg. */
1089 dst
= XEXP (dst
, 0);
1090 if (GET_CODE (dst
) != SUBREG
)
1092 df_uses_record (df
, &SUBREG_REG (dst
), DF_REF_REG_USE
, bb
,
1093 insn
, DF_REF_READ_WRITE
);
1097 df_uses_record (df
, &XEXP (dst
, 0), DF_REF_REG_USE
, bb
, insn
,
1099 df_uses_record (df
, &XEXP (dst
, 1), DF_REF_REG_USE
, bb
, insn
, 0);
1100 df_uses_record (df
, &XEXP (dst
, 2), DF_REF_REG_USE
, bb
, insn
, 0);
1101 dst
= XEXP (dst
, 0);
1113 case UNSPEC_VOLATILE
:
1117 /* Traditional and volatile asm instructions must be considered to use
1118 and clobber all hard registers, all pseudo-registers and all of
1119 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
1121 Consider for instance a volatile asm that changes the fpu rounding
1122 mode. An insn should not be moved across this even if it only uses
1123 pseudo-regs because it might give an incorrectly rounded result.
1125 For now, just mark any regs we can find in ASM_OPERANDS as
1128 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
1129 We can not just fall through here since then we would be confused
1130 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
1131 traditional asms unlike their normal usage. */
1132 if (code
== ASM_OPERANDS
)
1136 for (j
= 0; j
< ASM_OPERANDS_INPUT_LENGTH (x
); j
++)
1137 df_uses_record (df
, &ASM_OPERANDS_INPUT (x
, j
),
1138 DF_REF_REG_USE
, bb
, insn
, 0);
1150 /* Catch the def of the register being modified. */
1151 df_ref_record (df
, XEXP (x
, 0), &XEXP (x
, 0), insn
, DF_REF_REG_DEF
, DF_REF_READ_WRITE
);
1153 /* ... Fall through to handle uses ... */
1159 /* Recursively scan the operands of this expression. */
1161 const char *fmt
= GET_RTX_FORMAT (code
);
1164 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1168 /* Tail recursive case: save a function call level. */
1174 df_uses_record (df
, &XEXP (x
, i
), ref_type
, bb
, insn
, flags
);
1176 else if (fmt
[i
] == 'E')
1179 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1180 df_uses_record (df
, &XVECEXP (x
, i
, j
), ref_type
,
1188 /* Record all the df within INSN of basic block BB. */
1190 df_insn_refs_record (df
, bb
, insn
)
1201 /* Record register defs */
1202 df_defs_record (df
, PATTERN (insn
), bb
, insn
);
1204 if (df
->flags
& DF_EQUIV_NOTES
)
1205 for (note
= REG_NOTES (insn
); note
;
1206 note
= XEXP (note
, 1))
1208 switch (REG_NOTE_KIND (note
))
1212 df_uses_record (df
, &XEXP (note
, 0), DF_REF_REG_USE
,
1219 if (GET_CODE (insn
) == CALL_INSN
)
1224 /* Record the registers used to pass arguments. */
1225 for (note
= CALL_INSN_FUNCTION_USAGE (insn
); note
;
1226 note
= XEXP (note
, 1))
1228 if (GET_CODE (XEXP (note
, 0)) == USE
)
1229 df_uses_record (df
, &XEXP (XEXP (note
, 0), 0), DF_REF_REG_USE
,
1233 /* The stack ptr is used (honorarily) by a CALL insn. */
1234 x
= df_reg_use_gen (STACK_POINTER_REGNUM
);
1235 df_uses_record (df
, &XEXP (x
, 0), DF_REF_REG_USE
, bb
, insn
, 0);
1237 if (df
->flags
& DF_HARD_REGS
)
1239 /* Calls may also reference any of the global registers,
1240 so they are recorded as used. */
1241 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1244 x
= df_reg_use_gen (i
);
1245 df_uses_record (df
, &SET_DEST (x
),
1246 DF_REF_REG_USE
, bb
, insn
, 0);
1251 /* Record the register uses. */
1252 df_uses_record (df
, &PATTERN (insn
),
1253 DF_REF_REG_USE
, bb
, insn
, 0);
1256 if (GET_CODE (insn
) == CALL_INSN
)
1260 if (df
->flags
& DF_HARD_REGS
)
1262 /* Kill all registers invalidated by a call. */
1263 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1264 if (TEST_HARD_REG_BIT (regs_invalidated_by_call
, i
))
1266 rtx reg_clob
= df_reg_clobber_gen (i
);
1267 df_defs_record (df
, reg_clob
, bb
, insn
);
1271 /* There may be extra registers to be clobbered. */
1272 for (note
= CALL_INSN_FUNCTION_USAGE (insn
);
1274 note
= XEXP (note
, 1))
1275 if (GET_CODE (XEXP (note
, 0)) == CLOBBER
)
1276 df_defs_record (df
, XEXP (note
, 0), bb
, insn
);
1282 /* Record all the refs within the basic block BB. */
1284 df_bb_refs_record (df
, bb
)
1290 /* Scan the block an insn at a time from beginning to end. */
1291 for (insn
= bb
->head
; ; insn
= NEXT_INSN (insn
))
1295 /* Record defs within INSN. */
1296 df_insn_refs_record (df
, bb
, insn
);
1298 if (insn
== bb
->end
)
1304 /* Record all the refs in the basic blocks specified by BLOCKS. */
1306 df_refs_record (df
, blocks
)
1312 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
1314 df_bb_refs_record (df
, bb
);
1318 /* Dataflow analysis routines. */
1321 /* Create reg-def chains for basic block BB. These are a list of
1322 definitions for each register. */
1324 df_bb_reg_def_chain_create (df
, bb
)
1330 /* Perhaps the defs should be sorted using a depth first search
1331 of the CFG (or possibly a breadth first search). We currently
1332 scan the basic blocks in reverse order so that the first defs
1333 appear at the start of the chain. */
1335 for (insn
= bb
->end
; insn
&& insn
!= PREV_INSN (bb
->head
);
1336 insn
= PREV_INSN (insn
))
1338 struct df_link
*link
;
1339 unsigned int uid
= INSN_UID (insn
);
1341 if (! INSN_P (insn
))
1344 for (link
= df
->insns
[uid
].defs
; link
; link
= link
->next
)
1346 struct ref
*def
= link
->ref
;
1347 unsigned int dregno
= DF_REF_REGNO (def
);
1349 df
->regs
[dregno
].defs
1350 = df_link_create (def
, df
->regs
[dregno
].defs
);
1356 /* Create reg-def chains for each basic block within BLOCKS. These
1357 are a list of definitions for each register. */
1359 df_reg_def_chain_create (df
, blocks
)
1365 FOR_EACH_BB_IN_BITMAP
/*_REV*/ (blocks
, 0, bb
,
1367 df_bb_reg_def_chain_create (df
, bb
);
1372 /* Create reg-use chains for basic block BB. These are a list of uses
1373 for each register. */
1375 df_bb_reg_use_chain_create (df
, bb
)
1381 /* Scan in forward order so that the last uses appear at the
1382 start of the chain. */
1384 for (insn
= bb
->head
; insn
&& insn
!= NEXT_INSN (bb
->end
);
1385 insn
= NEXT_INSN (insn
))
1387 struct df_link
*link
;
1388 unsigned int uid
= INSN_UID (insn
);
1390 if (! INSN_P (insn
))
1393 for (link
= df
->insns
[uid
].uses
; link
; link
= link
->next
)
1395 struct ref
*use
= link
->ref
;
1396 unsigned int uregno
= DF_REF_REGNO (use
);
1398 df
->regs
[uregno
].uses
1399 = df_link_create (use
, df
->regs
[uregno
].uses
);
1405 /* Create reg-use chains for each basic block within BLOCKS. These
1406 are a list of uses for each register. */
1408 df_reg_use_chain_create (df
, blocks
)
1414 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
1416 df_bb_reg_use_chain_create (df
, bb
);
1421 /* Create def-use chains from reaching use bitmaps for basic block BB. */
1423 df_bb_du_chain_create (df
, bb
, ru
)
1428 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
1431 bitmap_copy (ru
, bb_info
->ru_out
);
1433 /* For each def in BB create a linked list (chain) of uses
1434 reached from the def. */
1435 for (insn
= bb
->end
; insn
&& insn
!= PREV_INSN (bb
->head
);
1436 insn
= PREV_INSN (insn
))
1438 struct df_link
*def_link
;
1439 struct df_link
*use_link
;
1440 unsigned int uid
= INSN_UID (insn
);
1442 if (! INSN_P (insn
))
1445 /* For each def in insn... */
1446 for (def_link
= df
->insns
[uid
].defs
; def_link
; def_link
= def_link
->next
)
1448 struct ref
*def
= def_link
->ref
;
1449 unsigned int dregno
= DF_REF_REGNO (def
);
1451 DF_REF_CHAIN (def
) = 0;
1453 /* While the reg-use chains are not essential, it
1454 is _much_ faster to search these short lists rather
1455 than all the reaching uses, especially for large functions. */
1456 for (use_link
= df
->regs
[dregno
].uses
; use_link
;
1457 use_link
= use_link
->next
)
1459 struct ref
*use
= use_link
->ref
;
1461 if (bitmap_bit_p (ru
, DF_REF_ID (use
)))
1464 = df_link_create (use
, DF_REF_CHAIN (def
));
1466 bitmap_clear_bit (ru
, DF_REF_ID (use
));
1471 /* For each use in insn... */
1472 for (use_link
= df
->insns
[uid
].uses
; use_link
; use_link
= use_link
->next
)
1474 struct ref
*use
= use_link
->ref
;
1475 bitmap_set_bit (ru
, DF_REF_ID (use
));
1481 /* Create def-use chains from reaching use bitmaps for basic blocks
1484 df_du_chain_create (df
, blocks
)
1491 ru
= BITMAP_XMALLOC ();
1493 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
1495 df_bb_du_chain_create (df
, bb
, ru
);
1502 /* Create use-def chains from reaching def bitmaps for basic block BB. */
1504 df_bb_ud_chain_create (df
, bb
)
1508 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
1509 struct ref
**reg_def_last
= df
->reg_def_last
;
1512 memset (reg_def_last
, 0, df
->n_regs
* sizeof (struct ref
*));
1514 /* For each use in BB create a linked list (chain) of defs
1515 that reach the use. */
1516 for (insn
= bb
->head
; insn
&& insn
!= NEXT_INSN (bb
->end
);
1517 insn
= NEXT_INSN (insn
))
1519 unsigned int uid
= INSN_UID (insn
);
1520 struct df_link
*use_link
;
1521 struct df_link
*def_link
;
1523 if (! INSN_P (insn
))
1526 /* For each use in insn... */
1527 for (use_link
= df
->insns
[uid
].uses
; use_link
; use_link
= use_link
->next
)
1529 struct ref
*use
= use_link
->ref
;
1530 unsigned int regno
= DF_REF_REGNO (use
);
1532 DF_REF_CHAIN (use
) = 0;
1534 /* Has regno been defined in this BB yet? If so, use
1535 the last def as the single entry for the use-def
1536 chain for this use. Otherwise, we need to add all
1537 the defs using this regno that reach the start of
1539 if (reg_def_last
[regno
])
1542 = df_link_create (reg_def_last
[regno
], 0);
1546 /* While the reg-def chains are not essential, it is
1547 _much_ faster to search these short lists rather than
1548 all the reaching defs, especially for large
1550 for (def_link
= df
->regs
[regno
].defs
; def_link
;
1551 def_link
= def_link
->next
)
1553 struct ref
*def
= def_link
->ref
;
1555 if (bitmap_bit_p (bb_info
->rd_in
, DF_REF_ID (def
)))
1558 = df_link_create (def
, DF_REF_CHAIN (use
));
1565 /* For each def in insn...record the last def of each reg. */
1566 for (def_link
= df
->insns
[uid
].defs
; def_link
; def_link
= def_link
->next
)
1568 struct ref
*def
= def_link
->ref
;
1569 int dregno
= DF_REF_REGNO (def
);
1571 reg_def_last
[dregno
] = def
;
1577 /* Create use-def chains from reaching def bitmaps for basic blocks
1580 df_ud_chain_create (df
, blocks
)
1586 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
1588 df_bb_ud_chain_create (df
, bb
);
1595 df_rd_transfer_function (bb
, changed
, in
, out
, gen
, kill
, data
)
1596 int bb ATTRIBUTE_UNUSED
;
1598 bitmap in
, out
, gen
, kill
;
1599 void *data ATTRIBUTE_UNUSED
;
1601 *changed
= bitmap_union_of_diff (out
, gen
, in
, kill
);
1604 df_ru_transfer_function (bb
, changed
, in
, out
, gen
, kill
, data
)
1605 int bb ATTRIBUTE_UNUSED
;
1607 bitmap in
, out
, gen
, kill
;
1608 void *data ATTRIBUTE_UNUSED
;
1610 *changed
= bitmap_union_of_diff (in
, gen
, out
, kill
);
1614 df_lr_transfer_function (bb
, changed
, in
, out
, use
, def
, data
)
1615 int bb ATTRIBUTE_UNUSED
;
1617 bitmap in
, out
, use
, def
;
1618 void *data ATTRIBUTE_UNUSED
;
1620 *changed
= bitmap_union_of_diff (in
, use
, out
, def
);
1624 /* Compute local reaching def info for basic block BB. */
1626 df_bb_rd_local_compute (df
, bb
)
1630 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
1633 for (insn
= bb
->head
; insn
&& insn
!= NEXT_INSN (bb
->end
);
1634 insn
= NEXT_INSN (insn
))
1636 unsigned int uid
= INSN_UID (insn
);
1637 struct df_link
*def_link
;
1639 if (! INSN_P (insn
))
1642 for (def_link
= df
->insns
[uid
].defs
; def_link
; def_link
= def_link
->next
)
1644 struct ref
*def
= def_link
->ref
;
1645 unsigned int regno
= DF_REF_REGNO (def
);
1646 struct df_link
*def2_link
;
1648 for (def2_link
= df
->regs
[regno
].defs
; def2_link
;
1649 def2_link
= def2_link
->next
)
1651 struct ref
*def2
= def2_link
->ref
;
1653 /* Add all defs of this reg to the set of kills. This
1654 is greedy since many of these defs will not actually
1655 be killed by this BB but it keeps things a lot
1657 bitmap_set_bit (bb_info
->rd_kill
, DF_REF_ID (def2
));
1659 /* Zap from the set of gens for this BB. */
1660 bitmap_clear_bit (bb_info
->rd_gen
, DF_REF_ID (def2
));
1663 bitmap_set_bit (bb_info
->rd_gen
, DF_REF_ID (def
));
1667 bb_info
->rd_valid
= 1;
1671 /* Compute local reaching def info for each basic block within BLOCKS. */
1673 df_rd_local_compute (df
, blocks
)
1679 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
1681 df_bb_rd_local_compute (df
, bb
);
1686 /* Compute local reaching use (upward exposed use) info for basic
1689 df_bb_ru_local_compute (df
, bb
)
1693 /* This is much more tricky than computing reaching defs. With
1694 reaching defs, defs get killed by other defs. With upwards
1695 exposed uses, these get killed by defs with the same regno. */
1697 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
1701 for (insn
= bb
->end
; insn
&& insn
!= PREV_INSN (bb
->head
);
1702 insn
= PREV_INSN (insn
))
1704 unsigned int uid
= INSN_UID (insn
);
1705 struct df_link
*def_link
;
1706 struct df_link
*use_link
;
1708 if (! INSN_P (insn
))
1711 for (def_link
= df
->insns
[uid
].defs
; def_link
; def_link
= def_link
->next
)
1713 struct ref
*def
= def_link
->ref
;
1714 unsigned int dregno
= DF_REF_REGNO (def
);
1716 for (use_link
= df
->regs
[dregno
].uses
; use_link
;
1717 use_link
= use_link
->next
)
1719 struct ref
*use
= use_link
->ref
;
1721 /* Add all uses of this reg to the set of kills. This
1722 is greedy since many of these uses will not actually
1723 be killed by this BB but it keeps things a lot
1725 bitmap_set_bit (bb_info
->ru_kill
, DF_REF_ID (use
));
1727 /* Zap from the set of gens for this BB. */
1728 bitmap_clear_bit (bb_info
->ru_gen
, DF_REF_ID (use
));
1732 for (use_link
= df
->insns
[uid
].uses
; use_link
; use_link
= use_link
->next
)
1734 struct ref
*use
= use_link
->ref
;
1735 /* Add use to set of gens in this BB. */
1736 bitmap_set_bit (bb_info
->ru_gen
, DF_REF_ID (use
));
1739 bb_info
->ru_valid
= 1;
1743 /* Compute local reaching use (upward exposed use) info for each basic
1744 block within BLOCKS. */
1746 df_ru_local_compute (df
, blocks
)
1752 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
1754 df_bb_ru_local_compute (df
, bb
);
1759 /* Compute local live variable info for basic block BB. */
1761 df_bb_lr_local_compute (df
, bb
)
1765 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
1768 for (insn
= bb
->end
; insn
&& insn
!= PREV_INSN (bb
->head
);
1769 insn
= PREV_INSN (insn
))
1771 unsigned int uid
= INSN_UID (insn
);
1772 struct df_link
*link
;
1774 if (! INSN_P (insn
))
1777 for (link
= df
->insns
[uid
].defs
; link
; link
= link
->next
)
1779 struct ref
*def
= link
->ref
;
1780 unsigned int dregno
= DF_REF_REGNO (def
);
1782 /* Add def to set of defs in this BB. */
1783 bitmap_set_bit (bb_info
->lr_def
, dregno
);
1785 bitmap_clear_bit (bb_info
->lr_use
, dregno
);
1788 for (link
= df
->insns
[uid
].uses
; link
; link
= link
->next
)
1790 struct ref
*use
= link
->ref
;
1791 /* Add use to set of uses in this BB. */
1792 bitmap_set_bit (bb_info
->lr_use
, DF_REF_REGNO (use
));
1795 bb_info
->lr_valid
= 1;
1799 /* Compute local live variable info for each basic block within BLOCKS. */
1801 df_lr_local_compute (df
, blocks
)
1807 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
1809 df_bb_lr_local_compute (df
, bb
);
1814 /* Compute register info: lifetime, bb, and number of defs and uses
1815 for basic block BB. */
1817 df_bb_reg_info_compute (df
, bb
, live
)
1822 struct reg_info
*reg_info
= df
->regs
;
1823 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
1826 bitmap_copy (live
, bb_info
->lr_out
);
1828 for (insn
= bb
->end
; insn
&& insn
!= PREV_INSN (bb
->head
);
1829 insn
= PREV_INSN (insn
))
1831 unsigned int uid
= INSN_UID (insn
);
1833 struct df_link
*link
;
1835 if (! INSN_P (insn
))
1838 for (link
= df
->insns
[uid
].defs
; link
; link
= link
->next
)
1840 struct ref
*def
= link
->ref
;
1841 unsigned int dregno
= DF_REF_REGNO (def
);
1843 /* Kill this register. */
1844 bitmap_clear_bit (live
, dregno
);
1845 reg_info
[dregno
].n_defs
++;
1848 for (link
= df
->insns
[uid
].uses
; link
; link
= link
->next
)
1850 struct ref
*use
= link
->ref
;
1851 unsigned int uregno
= DF_REF_REGNO (use
);
1853 /* This register is now live. */
1854 bitmap_set_bit (live
, uregno
);
1855 reg_info
[uregno
].n_uses
++;
1858 /* Increment lifetimes of all live registers. */
1859 EXECUTE_IF_SET_IN_BITMAP (live
, 0, regno
,
1861 reg_info
[regno
].lifetime
++;
1867 /* Compute register info: lifetime, bb, and number of defs and uses. */
1869 df_reg_info_compute (df
, blocks
)
1876 live
= BITMAP_XMALLOC ();
1878 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
1880 df_bb_reg_info_compute (df
, bb
, live
);
1883 BITMAP_XFREE (live
);
1887 /* Assign LUIDs for BB. */
1889 df_bb_luids_set (df
, bb
)
1896 /* The LUIDs are monotonically increasing for each basic block. */
1898 for (insn
= bb
->head
; ; insn
= NEXT_INSN (insn
))
1901 DF_INSN_LUID (df
, insn
) = luid
++;
1902 DF_INSN_LUID (df
, insn
) = luid
;
1904 if (insn
== bb
->end
)
1911 /* Assign LUIDs for each basic block within BLOCKS. */
1913 df_luids_set (df
, blocks
)
1920 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
1922 total
+= df_bb_luids_set (df
, bb
);
1927 /* Perform dataflow analysis using existing DF structure for blocks
1928 within BLOCKS. If BLOCKS is zero, use all basic blocks in the CFG. */
1930 df_analyse_1 (df
, blocks
, flags
, update
)
1943 if (flags
& DF_UD_CHAIN
)
1944 aflags
|= DF_RD
| DF_RD_CHAIN
;
1946 if (flags
& DF_DU_CHAIN
)
1950 aflags
|= DF_RU_CHAIN
;
1952 if (flags
& DF_REG_INFO
)
1956 blocks
= df
->all_blocks
;
1961 df_refs_update (df
);
1962 /* More fine grained incremental dataflow analysis would be
1963 nice. For now recompute the whole shebang for the
1966 df_refs_unlink (df
, blocks
);
1968 /* All the def-use, use-def chains can be potentially
1969 modified by changes in one block. The size of the
1970 bitmaps can also change. */
1974 /* Scan the function for all register defs and uses. */
1976 df_refs_record (df
, blocks
);
1978 /* Link all the new defs and uses to the insns. */
1979 df_refs_process (df
);
1982 /* Allocate the bitmaps now the total number of defs and uses are
1983 known. If the number of defs or uses have changed, then
1984 these bitmaps need to be reallocated. */
1985 df_bitmaps_alloc (df
, aflags
);
1987 /* Set the LUIDs for each specified basic block. */
1988 df_luids_set (df
, blocks
);
1990 /* Recreate reg-def and reg-use chains from scratch so that first
1991 def is at the head of the reg-def chain and the last use is at
1992 the head of the reg-use chain. This is only important for
1993 regs local to a basic block as it speeds up searching. */
1994 if (aflags
& DF_RD_CHAIN
)
1996 df_reg_def_chain_create (df
, blocks
);
1999 if (aflags
& DF_RU_CHAIN
)
2001 df_reg_use_chain_create (df
, blocks
);
2004 df
->dfs_order
= xmalloc (sizeof(int) * n_basic_blocks
);
2005 df
->rc_order
= xmalloc (sizeof(int) * n_basic_blocks
);
2006 df
->rts_order
= xmalloc (sizeof(int) * n_basic_blocks
);
2007 df
->inverse_dfs_map
= xmalloc (sizeof(int) * last_basic_block
);
2008 df
->inverse_rc_map
= xmalloc (sizeof(int) * last_basic_block
);
2009 df
->inverse_rts_map
= xmalloc (sizeof(int) * last_basic_block
);
2011 flow_depth_first_order_compute (df
->dfs_order
, df
->rc_order
);
2012 flow_reverse_top_sort_order_compute (df
->rts_order
);
2013 for (i
= 0; i
< n_basic_blocks
; i
++)
2015 df
->inverse_dfs_map
[df
->dfs_order
[i
]] = i
;
2016 df
->inverse_rc_map
[df
->rc_order
[i
]] = i
;
2017 df
->inverse_rts_map
[df
->rts_order
[i
]] = i
;
2021 /* Compute the sets of gens and kills for the defs of each bb. */
2022 df_rd_local_compute (df
, df
->flags
& DF_RD
? blocks
: df
->all_blocks
);
2024 bitmap
*in
= xmalloc (sizeof (bitmap
) * last_basic_block
);
2025 bitmap
*out
= xmalloc (sizeof (bitmap
) * last_basic_block
);
2026 bitmap
*gen
= xmalloc (sizeof (bitmap
) * last_basic_block
);
2027 bitmap
*kill
= xmalloc (sizeof (bitmap
) * last_basic_block
);
2030 in
[bb
->index
] = DF_BB_INFO (df
, bb
)->rd_in
;
2031 out
[bb
->index
] = DF_BB_INFO (df
, bb
)->rd_out
;
2032 gen
[bb
->index
] = DF_BB_INFO (df
, bb
)->rd_gen
;
2033 kill
[bb
->index
] = DF_BB_INFO (df
, bb
)->rd_kill
;
2035 iterative_dataflow_bitmap (in
, out
, gen
, kill
, df
->all_blocks
,
2036 FORWARD
, UNION
, df_rd_transfer_function
,
2037 df
->inverse_rc_map
, NULL
);
2045 if (aflags
& DF_UD_CHAIN
)
2047 /* Create use-def chains. */
2048 df_ud_chain_create (df
, df
->all_blocks
);
2050 if (! (flags
& DF_RD
))
2056 /* Compute the sets of gens and kills for the upwards exposed
2058 df_ru_local_compute (df
, df
->flags
& DF_RU
? blocks
: df
->all_blocks
);
2060 bitmap
*in
= xmalloc (sizeof (bitmap
) * last_basic_block
);
2061 bitmap
*out
= xmalloc (sizeof (bitmap
) * last_basic_block
);
2062 bitmap
*gen
= xmalloc (sizeof (bitmap
) * last_basic_block
);
2063 bitmap
*kill
= xmalloc (sizeof (bitmap
) * last_basic_block
);
2066 in
[bb
->index
] = DF_BB_INFO (df
, bb
)->ru_in
;
2067 out
[bb
->index
] = DF_BB_INFO (df
, bb
)->ru_out
;
2068 gen
[bb
->index
] = DF_BB_INFO (df
, bb
)->ru_gen
;
2069 kill
[bb
->index
] = DF_BB_INFO (df
, bb
)->ru_kill
;
2071 iterative_dataflow_bitmap (in
, out
, gen
, kill
, df
->all_blocks
,
2072 BACKWARD
, UNION
, df_ru_transfer_function
,
2073 df
->inverse_rts_map
, NULL
);
2081 if (aflags
& DF_DU_CHAIN
)
2083 /* Create def-use chains. */
2084 df_du_chain_create (df
, df
->all_blocks
);
2086 if (! (flags
& DF_RU
))
2090 /* Free up bitmaps that are no longer required. */
2092 df_bitmaps_free (df
, dflags
);
2096 /* Compute the sets of defs and uses of live variables. */
2097 df_lr_local_compute (df
, df
->flags
& DF_LR
? blocks
: df
->all_blocks
);
2099 bitmap
*in
= xmalloc (sizeof (bitmap
) * last_basic_block
);
2100 bitmap
*out
= xmalloc (sizeof (bitmap
) * last_basic_block
);
2101 bitmap
*use
= xmalloc (sizeof (bitmap
) * last_basic_block
);
2102 bitmap
*def
= xmalloc (sizeof (bitmap
) * last_basic_block
);
2105 in
[bb
->index
] = DF_BB_INFO (df
, bb
)->lr_in
;
2106 out
[bb
->index
] = DF_BB_INFO (df
, bb
)->lr_out
;
2107 use
[bb
->index
] = DF_BB_INFO (df
, bb
)->lr_use
;
2108 def
[bb
->index
] = DF_BB_INFO (df
, bb
)->lr_def
;
2110 iterative_dataflow_bitmap (in
, out
, use
, def
, df
->all_blocks
,
2111 BACKWARD
, UNION
, df_lr_transfer_function
,
2112 df
->inverse_rts_map
, NULL
);
2120 if (aflags
& DF_REG_INFO
)
2122 df_reg_info_compute (df
, df
->all_blocks
);
2124 free (df
->dfs_order
);
2125 free (df
->rc_order
);
2126 free (df
->rts_order
);
2127 free (df
->inverse_rc_map
);
2128 free (df
->inverse_dfs_map
);
2129 free (df
->inverse_rts_map
);
2133 /* Initialise dataflow analysis. */
2139 df
= xcalloc (1, sizeof (struct df
));
2141 /* Squirrel away a global for debugging. */
2148 /* Start queuing refs. */
2153 df
->def_id_save
= df
->def_id
;
2154 df
->use_id_save
= df
->use_id
;
2155 /* ???? Perhaps we should save current obstack state so that we can
2161 /* Process queued refs. */
2163 df_refs_process (df
)
2168 /* Build new insn-def chains. */
2169 for (i
= df
->def_id_save
; i
!= df
->def_id
; i
++)
2171 struct ref
*def
= df
->defs
[i
];
2172 unsigned int uid
= DF_REF_INSN_UID (def
);
2174 /* Add def to head of def list for INSN. */
2176 = df_link_create (def
, df
->insns
[uid
].defs
);
2179 /* Build new insn-use chains. */
2180 for (i
= df
->use_id_save
; i
!= df
->use_id
; i
++)
2182 struct ref
*use
= df
->uses
[i
];
2183 unsigned int uid
= DF_REF_INSN_UID (use
);
2185 /* Add use to head of use list for INSN. */
2187 = df_link_create (use
, df
->insns
[uid
].uses
);
2193 /* Update refs for basic block BB. */
2195 df_bb_refs_update (df
, bb
)
2202 /* While we have to scan the chain of insns for this BB, we don't
2203 need to allocate and queue a long chain of BB/INSN pairs. Using
2204 a bitmap for insns_modified saves memory and avoids queuing
2207 for (insn
= bb
->head
; ; insn
= NEXT_INSN (insn
))
2211 uid
= INSN_UID (insn
);
2213 if (bitmap_bit_p (df
->insns_modified
, uid
))
2215 /* Delete any allocated refs of this insn. MPH, FIXME. */
2216 df_insn_refs_unlink (df
, bb
, insn
);
2218 /* Scan the insn for refs. */
2219 df_insn_refs_record (df
, bb
, insn
);
2222 bitmap_clear_bit (df
->insns_modified
, uid
);
2225 if (insn
== bb
->end
)
2232 /* Process all the modified/deleted insns that were queued. */
2240 if ((unsigned int)max_reg_num () >= df
->reg_size
)
2241 df_reg_table_realloc (df
, 0);
2245 FOR_EACH_BB_IN_BITMAP (df
->bbs_modified
, 0, bb
,
2247 count
+= df_bb_refs_update (df
, bb
);
2250 df_refs_process (df
);
2255 /* Return non-zero if any of the requested blocks in the bitmap
2256 BLOCKS have been modified. */
2258 df_modified_p (df
, blocks
)
2269 if (bitmap_bit_p (df
->bbs_modified
, bb
->index
)
2270 && (! blocks
|| (blocks
== (bitmap
) -1) || bitmap_bit_p (blocks
, bb
->index
)))
2280 /* Analyse dataflow info for the basic blocks specified by the bitmap
2281 BLOCKS, or for the whole CFG if BLOCKS is zero, or just for the
2282 modified blocks if BLOCKS is -1. */
2284 df_analyse (df
, blocks
, flags
)
2291 /* We could deal with additional basic blocks being created by
2292 rescanning everything again. */
2293 if (df
->n_bbs
&& df
->n_bbs
!= (unsigned int) last_basic_block
)
2296 update
= df_modified_p (df
, blocks
);
2297 if (update
|| (flags
!= df
->flags
))
2303 /* Recompute everything from scratch. */
2306 /* Allocate and initialise data structures. */
2307 df_alloc (df
, max_reg_num ());
2308 df_analyse_1 (df
, 0, flags
, 0);
2313 if (blocks
== (bitmap
) -1)
2314 blocks
= df
->bbs_modified
;
2319 df_analyse_1 (df
, blocks
, flags
, 1);
2320 bitmap_zero (df
->bbs_modified
);
2327 /* Free all the dataflow info and the DF structure. */
2337 /* Unlink INSN from its reference information. */
2339 df_insn_refs_unlink (df
, bb
, insn
)
2341 basic_block bb ATTRIBUTE_UNUSED
;
2344 struct df_link
*link
;
2347 uid
= INSN_UID (insn
);
2349 /* Unlink all refs defined by this insn. */
2350 for (link
= df
->insns
[uid
].defs
; link
; link
= link
->next
)
2351 df_def_unlink (df
, link
->ref
);
2353 /* Unlink all refs used by this insn. */
2354 for (link
= df
->insns
[uid
].uses
; link
; link
= link
->next
)
2355 df_use_unlink (df
, link
->ref
);
2357 df
->insns
[uid
].defs
= 0;
2358 df
->insns
[uid
].uses
= 0;
2363 /* Unlink all the insns within BB from their reference information. */
2365 df_bb_refs_unlink (df
, bb
)
2371 /* Scan the block an insn at a time from beginning to end. */
2372 for (insn
= bb
->head
; ; insn
= NEXT_INSN (insn
))
2376 /* Unlink refs for INSN. */
2377 df_insn_refs_unlink (df
, bb
, insn
);
2379 if (insn
== bb
->end
)
2385 /* Unlink all the refs in the basic blocks specified by BLOCKS.
2386 Not currently used. */
2388 df_refs_unlink (df
, blocks
)
2396 FOR_EACH_BB_IN_BITMAP (blocks
, 0, bb
,
2398 df_bb_refs_unlink (df
, bb
);
2404 df_bb_refs_unlink (df
, bb
);
2409 /* Functions to modify insns. */
2412 /* Delete INSN and all its reference information. */
2414 df_insn_delete (df
, bb
, insn
)
2416 basic_block bb ATTRIBUTE_UNUSED
;
2419 /* If the insn is a jump, we should perhaps call delete_insn to
2420 handle the JUMP_LABEL? */
2422 /* We should not be deleting the NOTE_INSN_BASIC_BLOCK or label. */
2423 if (insn
== bb
->head
)
2426 /* Delete the insn. */
2429 df_insn_modify (df
, bb
, insn
);
2431 return NEXT_INSN (insn
);
2435 /* Mark that INSN within BB may have changed (created/modified/deleted).
2436 This may be called multiple times for the same insn. There is no
2437 harm calling this function if the insn wasn't changed; it will just
2438 slow down the rescanning of refs. */
2440 df_insn_modify (df
, bb
, insn
)
2447 uid
= INSN_UID (insn
);
2449 if (uid
>= df
->insn_size
)
2450 df_insn_table_realloc (df
, 0);
2452 bitmap_set_bit (df
->bbs_modified
, bb
->index
);
2453 bitmap_set_bit (df
->insns_modified
, uid
);
2455 /* For incremental updating on the fly, perhaps we could make a copy
2456 of all the refs of the original insn and turn them into
2457 anti-refs. When df_refs_update finds these anti-refs, it annihilates
2458 the original refs. If validate_change fails then these anti-refs
2459 will just get ignored. */
2463 typedef struct replace_args
2472 /* Replace mem pointed to by PX with its associated pseudo register.
2473 DATA is actually a pointer to a structure describing the
2474 instruction currently being scanned and the MEM we are currently
2477 df_rtx_mem_replace (px
, data
)
2481 replace_args
*args
= (replace_args
*) data
;
2484 if (mem
== NULL_RTX
)
2487 switch (GET_CODE (mem
))
2493 /* We're not interested in the MEM associated with a
2494 CONST_DOUBLE, so there's no need to traverse into one. */
2498 /* This is not a MEM. */
2502 if (!rtx_equal_p (args
->match
, mem
))
2503 /* This is not the MEM we are currently replacing. */
2506 /* Actually replace the MEM. */
2507 validate_change (args
->insn
, px
, args
->replacement
, 1);
2515 df_insn_mem_replace (df
, bb
, insn
, mem
, reg
)
2526 args
.replacement
= reg
;
2529 /* Search and replace all matching mems within insn. */
2530 for_each_rtx (&insn
, df_rtx_mem_replace
, &args
);
2533 df_insn_modify (df
, bb
, insn
);
2535 /* ???? FIXME. We may have a new def or one or more new uses of REG
2536 in INSN. REG should be a new pseudo so it won't affect the
2537 dataflow information that we currently have. We should add
2538 the new uses and defs to INSN and then recreate the chains
2539 when df_analyse is called. */
2540 return args
.modified
;
2544 /* Replace one register with another. Called through for_each_rtx; PX
2545 points to the rtx being scanned. DATA is actually a pointer to a
2546 structure of arguments. */
2548 df_rtx_reg_replace (px
, data
)
2553 replace_args
*args
= (replace_args
*) data
;
2558 if (x
== args
->match
)
2560 validate_change (args
->insn
, px
, args
->replacement
, 1);
2568 /* Replace the reg within every ref on CHAIN that is within the set
2569 BLOCKS of basic blocks with NEWREG. Also update the regs within
2572 df_refs_reg_replace (df
, blocks
, chain
, oldreg
, newreg
)
2575 struct df_link
*chain
;
2579 struct df_link
*link
;
2583 blocks
= df
->all_blocks
;
2585 args
.match
= oldreg
;
2586 args
.replacement
= newreg
;
2589 for (link
= chain
; link
; link
= link
->next
)
2591 struct ref
*ref
= link
->ref
;
2592 rtx insn
= DF_REF_INSN (ref
);
2594 if (! INSN_P (insn
))
2597 if (bitmap_bit_p (blocks
, DF_REF_BBNO (ref
)))
2599 df_ref_reg_replace (df
, ref
, oldreg
, newreg
);
2601 /* Replace occurrences of the reg within the REG_NOTES. */
2602 if ((! link
->next
|| DF_REF_INSN (ref
)
2603 != DF_REF_INSN (link
->next
->ref
))
2604 && REG_NOTES (insn
))
2607 for_each_rtx (®_NOTES (insn
), df_rtx_reg_replace
, &args
);
2612 /* Temporary check to ensure that we have a grip on which
2613 regs should be replaced. */
2620 /* Replace all occurrences of register OLDREG with register NEWREG in
2621 blocks defined by bitmap BLOCKS. This also replaces occurrences of
2622 OLDREG in the REG_NOTES but only for insns containing OLDREG. This
2623 routine expects the reg-use and reg-def chains to be valid. */
2625 df_reg_replace (df
, blocks
, oldreg
, newreg
)
2631 unsigned int oldregno
= REGNO (oldreg
);
2633 df_refs_reg_replace (df
, blocks
, df
->regs
[oldregno
].defs
, oldreg
, newreg
);
2634 df_refs_reg_replace (df
, blocks
, df
->regs
[oldregno
].uses
, oldreg
, newreg
);
2639 /* Try replacing the reg within REF with NEWREG. Do not modify
2640 def-use/use-def chains. */
2642 df_ref_reg_replace (df
, ref
, oldreg
, newreg
)
2648 /* Check that insn was deleted by being converted into a NOTE. If
2649 so ignore this insn. */
2650 if (! INSN_P (DF_REF_INSN (ref
)))
2653 if (oldreg
&& oldreg
!= DF_REF_REG (ref
))
2656 if (! validate_change (DF_REF_INSN (ref
), DF_REF_LOC (ref
), newreg
, 1))
2659 df_insn_modify (df
, DF_REF_BB (ref
), DF_REF_INSN (ref
));
2665 df_bb_def_use_swap (df
, bb
, def_insn
, use_insn
, regno
)
2676 struct df_link
*link
;
2678 def
= df_bb_insn_regno_first_def_find (df
, bb
, def_insn
, regno
);
2682 use
= df_bb_insn_regno_last_use_find (df
, bb
, use_insn
, regno
);
2686 /* The USE no longer exists. */
2687 use_uid
= INSN_UID (use_insn
);
2688 df_use_unlink (df
, use
);
2689 df_ref_unlink (&df
->insns
[use_uid
].uses
, use
);
2691 /* The DEF requires shifting so remove it from DEF_INSN
2692 and add it to USE_INSN by reusing LINK. */
2693 def_uid
= INSN_UID (def_insn
);
2694 link
= df_ref_unlink (&df
->insns
[def_uid
].defs
, def
);
2696 link
->next
= df
->insns
[use_uid
].defs
;
2697 df
->insns
[use_uid
].defs
= link
;
2700 link
= df_ref_unlink (&df
->regs
[regno
].defs
, def
);
2702 link
->next
= df
->regs
[regno
].defs
;
2703 df
->insns
[regno
].defs
= link
;
2706 DF_REF_INSN (def
) = use_insn
;
2711 /* Record df between FIRST_INSN and LAST_INSN inclusive. All new
2712 insns must be processed by this routine. */
2714 df_insns_modify (df
, bb
, first_insn
, last_insn
)
2722 for (insn
= first_insn
; ; insn
= NEXT_INSN (insn
))
2726 /* A non-const call should not have slipped through the net. If
2727 it does, we need to create a new basic block. Ouch. The
2728 same applies for a label. */
2729 if ((GET_CODE (insn
) == CALL_INSN
2730 && ! CONST_OR_PURE_CALL_P (insn
))
2731 || GET_CODE (insn
) == CODE_LABEL
)
2734 uid
= INSN_UID (insn
);
2736 if (uid
>= df
->insn_size
)
2737 df_insn_table_realloc (df
, 0);
2739 df_insn_modify (df
, bb
, insn
);
2741 if (insn
== last_insn
)
2747 /* Emit PATTERN before INSN within BB. */
2749 df_pattern_emit_before (df
, pattern
, bb
, insn
)
2750 struct df
*df ATTRIBUTE_UNUSED
;
2756 rtx prev_insn
= PREV_INSN (insn
);
2758 /* We should not be inserting before the start of the block. */
2759 if (insn
== bb
->head
)
2761 ret_insn
= emit_insn_before (pattern
, insn
);
2762 if (ret_insn
== insn
)
2765 df_insns_modify (df
, bb
, NEXT_INSN (prev_insn
), ret_insn
);
2770 /* Emit PATTERN after INSN within BB. */
2772 df_pattern_emit_after (df
, pattern
, bb
, insn
)
2780 ret_insn
= emit_insn_after (pattern
, insn
);
2781 if (ret_insn
== insn
)
2784 df_insns_modify (df
, bb
, NEXT_INSN (insn
), ret_insn
);
2789 /* Emit jump PATTERN after INSN within BB. */
2791 df_jump_pattern_emit_after (df
, pattern
, bb
, insn
)
2799 ret_insn
= emit_jump_insn_after (pattern
, insn
);
2800 if (ret_insn
== insn
)
2803 df_insns_modify (df
, bb
, NEXT_INSN (insn
), ret_insn
);
2808 /* Move INSN within BB before BEFORE_INSN within BEFORE_BB.
2810 This function should only be used to move loop invariant insns
2811 out of a loop where it has been proven that the def-use info
2812 will still be valid. */
2814 df_insn_move_before (df
, bb
, insn
, before_bb
, before_insn
)
2818 basic_block before_bb
;
2821 struct df_link
*link
;
2825 return df_pattern_emit_before (df
, insn
, before_bb
, before_insn
);
2827 uid
= INSN_UID (insn
);
2829 /* Change bb for all df defined and used by this insn. */
2830 for (link
= df
->insns
[uid
].defs
; link
; link
= link
->next
)
2831 DF_REF_BB (link
->ref
) = before_bb
;
2832 for (link
= df
->insns
[uid
].uses
; link
; link
= link
->next
)
2833 DF_REF_BB (link
->ref
) = before_bb
;
2835 /* The lifetimes of the registers used in this insn will be reduced
2836 while the lifetimes of the registers defined in this insn
2837 are likely to be increased. */
2839 /* ???? Perhaps all the insns moved should be stored on a list
2840 which df_analyse removes when it recalculates data flow. */
2842 return emit_insn_before (insn
, before_insn
);
2845 /* Functions to query dataflow information. */
2849 df_insn_regno_def_p (df
, bb
, insn
, regno
)
2851 basic_block bb ATTRIBUTE_UNUSED
;
2856 struct df_link
*link
;
2858 uid
= INSN_UID (insn
);
2860 for (link
= df
->insns
[uid
].defs
; link
; link
= link
->next
)
2862 struct ref
*def
= link
->ref
;
2864 if (DF_REF_REGNO (def
) == regno
)
2873 df_def_dominates_all_uses_p (df
, def
)
2874 struct df
*df ATTRIBUTE_UNUSED
;
2877 struct df_link
*du_link
;
2879 /* Follow def-use chain to find all the uses of this def. */
2880 for (du_link
= DF_REF_CHAIN (def
); du_link
; du_link
= du_link
->next
)
2882 struct ref
*use
= du_link
->ref
;
2883 struct df_link
*ud_link
;
2885 /* Follow use-def chain to check all the defs for this use. */
2886 for (ud_link
= DF_REF_CHAIN (use
); ud_link
; ud_link
= ud_link
->next
)
2887 if (ud_link
->ref
!= def
)
2895 df_insn_dominates_all_uses_p (df
, bb
, insn
)
2897 basic_block bb ATTRIBUTE_UNUSED
;
2901 struct df_link
*link
;
2903 uid
= INSN_UID (insn
);
2905 for (link
= df
->insns
[uid
].defs
; link
; link
= link
->next
)
2907 struct ref
*def
= link
->ref
;
2909 if (! df_def_dominates_all_uses_p (df
, def
))
2917 /* Return non-zero if all DF dominates all the uses within the bitmap
2920 df_def_dominates_uses_p (df
, def
, blocks
)
2921 struct df
*df ATTRIBUTE_UNUSED
;
2925 struct df_link
*du_link
;
2927 /* Follow def-use chain to find all the uses of this def. */
2928 for (du_link
= DF_REF_CHAIN (def
); du_link
; du_link
= du_link
->next
)
2930 struct ref
*use
= du_link
->ref
;
2931 struct df_link
*ud_link
;
2933 /* Only worry about the uses within BLOCKS. For example,
2934 consider a register defined within a loop that is live at the
2936 if (bitmap_bit_p (blocks
, DF_REF_BBNO (use
)))
2938 /* Follow use-def chain to check all the defs for this use. */
2939 for (ud_link
= DF_REF_CHAIN (use
); ud_link
; ud_link
= ud_link
->next
)
2940 if (ud_link
->ref
!= def
)
2948 /* Return non-zero if all the defs of INSN within BB dominates
2949 all the corresponding uses. */
2951 df_insn_dominates_uses_p (df
, bb
, insn
, blocks
)
2953 basic_block bb ATTRIBUTE_UNUSED
;
2958 struct df_link
*link
;
2960 uid
= INSN_UID (insn
);
2962 for (link
= df
->insns
[uid
].defs
; link
; link
= link
->next
)
2964 struct ref
*def
= link
->ref
;
2966 /* Only consider the defs within BLOCKS. */
2967 if (bitmap_bit_p (blocks
, DF_REF_BBNO (def
))
2968 && ! df_def_dominates_uses_p (df
, def
, blocks
))
2975 /* Return the basic block that REG referenced in or NULL if referenced
2976 in multiple basic blocks. */
2978 df_regno_bb (df
, regno
)
2982 struct df_link
*defs
= df
->regs
[regno
].defs
;
2983 struct df_link
*uses
= df
->regs
[regno
].uses
;
2984 struct ref
*def
= defs
? defs
->ref
: 0;
2985 struct ref
*use
= uses
? uses
->ref
: 0;
2986 basic_block bb_def
= def
? DF_REF_BB (def
) : 0;
2987 basic_block bb_use
= use
? DF_REF_BB (use
) : 0;
2989 /* Compare blocks of first def and last use. ???? FIXME. What if
2990 the reg-def and reg-use lists are not correctly ordered. */
2991 return bb_def
== bb_use
? bb_def
: 0;
2995 /* Return non-zero if REG used in multiple basic blocks. */
2997 df_reg_global_p (df
, reg
)
3001 return df_regno_bb (df
, REGNO (reg
)) != 0;
3005 /* Return total lifetime (in insns) of REG. */
3007 df_reg_lifetime (df
, reg
)
3011 return df
->regs
[REGNO (reg
)].lifetime
;
3015 /* Return non-zero if REG live at start of BB. */
3017 df_bb_reg_live_start_p (df
, bb
, reg
)
3018 struct df
*df ATTRIBUTE_UNUSED
;
3022 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
3024 #ifdef ENABLE_CHECKING
3025 if (! bb_info
->lr_in
)
3029 return bitmap_bit_p (bb_info
->lr_in
, REGNO (reg
));
3033 /* Return non-zero if REG live at end of BB. */
3035 df_bb_reg_live_end_p (df
, bb
, reg
)
3036 struct df
*df ATTRIBUTE_UNUSED
;
3040 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
3042 #ifdef ENABLE_CHECKING
3043 if (! bb_info
->lr_in
)
3047 return bitmap_bit_p (bb_info
->lr_out
, REGNO (reg
));
3051 /* Return -1 if life of REG1 before life of REG2, 1 if life of REG1
3052 after life of REG2, or 0, if the lives overlap. */
3054 df_bb_regs_lives_compare (df
, bb
, reg1
, reg2
)
3060 unsigned int regno1
= REGNO (reg1
);
3061 unsigned int regno2
= REGNO (reg2
);
3068 /* The regs must be local to BB. */
3069 if (df_regno_bb (df
, regno1
) != bb
3070 || df_regno_bb (df
, regno2
) != bb
)
3073 def2
= df_bb_regno_first_def_find (df
, bb
, regno2
);
3074 use1
= df_bb_regno_last_use_find (df
, bb
, regno1
);
3076 if (DF_INSN_LUID (df
, DF_REF_INSN (def2
))
3077 > DF_INSN_LUID (df
, DF_REF_INSN (use1
)))
3080 def1
= df_bb_regno_first_def_find (df
, bb
, regno1
);
3081 use2
= df_bb_regno_last_use_find (df
, bb
, regno2
);
3083 if (DF_INSN_LUID (df
, DF_REF_INSN (def1
))
3084 > DF_INSN_LUID (df
, DF_REF_INSN (use2
)))
3091 /* Return last use of REGNO within BB. */
3093 df_bb_regno_last_use_find (df
, bb
, regno
)
3095 basic_block bb ATTRIBUTE_UNUSED
;
3098 struct df_link
*link
;
3100 /* This assumes that the reg-use list is ordered such that for any
3101 BB, the last use is found first. However, since the BBs are not
3102 ordered, the first use in the chain is not necessarily the last
3103 use in the function. */
3104 for (link
= df
->regs
[regno
].uses
; link
; link
= link
->next
)
3106 struct ref
*use
= link
->ref
;
3108 if (DF_REF_BB (use
) == bb
)
3115 /* Return first def of REGNO within BB. */
3117 df_bb_regno_first_def_find (df
, bb
, regno
)
3119 basic_block bb ATTRIBUTE_UNUSED
;
3122 struct df_link
*link
;
3124 /* This assumes that the reg-def list is ordered such that for any
3125 BB, the first def is found first. However, since the BBs are not
3126 ordered, the first def in the chain is not necessarily the first
3127 def in the function. */
3128 for (link
= df
->regs
[regno
].defs
; link
; link
= link
->next
)
3130 struct ref
*def
= link
->ref
;
3132 if (DF_REF_BB (def
) == bb
)
3139 /* Return first use of REGNO inside INSN within BB. */
3141 df_bb_insn_regno_last_use_find (df
, bb
, insn
, regno
)
3143 basic_block bb ATTRIBUTE_UNUSED
;
3148 struct df_link
*link
;
3150 uid
= INSN_UID (insn
);
3152 for (link
= df
->insns
[uid
].uses
; link
; link
= link
->next
)
3154 struct ref
*use
= link
->ref
;
3156 if (DF_REF_REGNO (use
) == regno
)
3164 /* Return first def of REGNO inside INSN within BB. */
3166 df_bb_insn_regno_first_def_find (df
, bb
, insn
, regno
)
3168 basic_block bb ATTRIBUTE_UNUSED
;
3173 struct df_link
*link
;
3175 uid
= INSN_UID (insn
);
3177 for (link
= df
->insns
[uid
].defs
; link
; link
= link
->next
)
3179 struct ref
*def
= link
->ref
;
3181 if (DF_REF_REGNO (def
) == regno
)
3189 /* Return insn using REG if the BB contains only a single
3190 use and def of REG. */
3192 df_bb_single_def_use_insn_find (df
, bb
, insn
, reg
)
3200 struct df_link
*du_link
;
3202 def
= df_bb_insn_regno_first_def_find (df
, bb
, insn
, REGNO (reg
));
3207 du_link
= DF_REF_CHAIN (def
);
3214 /* Check if def is dead. */
3218 /* Check for multiple uses. */
3222 return DF_REF_INSN (use
);
3225 /* Functions for debugging/dumping dataflow information. */
3228 /* Dump a def-use or use-def chain for REF to FILE. */
3230 df_chain_dump (link
, file
)
3231 struct df_link
*link
;
3234 fprintf (file
, "{ ");
3235 for (; link
; link
= link
->next
)
3237 fprintf (file
, "%c%d ",
3238 DF_REF_REG_DEF_P (link
->ref
) ? 'd' : 'u',
3239 DF_REF_ID (link
->ref
));
3241 fprintf (file
, "}");
3245 df_chain_dump_regno (link
, file
)
3246 struct df_link
*link
;
3249 fprintf (file
, "{ ");
3250 for (; link
; link
= link
->next
)
3252 fprintf (file
, "%c%d(%d) ",
3253 DF_REF_REG_DEF_P (link
->ref
) ? 'd' : 'u',
3254 DF_REF_ID (link
->ref
),
3255 DF_REF_REGNO (link
->ref
));
3257 fprintf (file
, "}");
3260 /* Dump dataflow info. */
3262 df_dump (df
, flags
, file
)
3273 fprintf (file
, "\nDataflow summary:\n");
3274 fprintf (file
, "n_regs = %d, n_defs = %d, n_uses = %d, n_bbs = %d\n",
3275 df
->n_regs
, df
->n_defs
, df
->n_uses
, df
->n_bbs
);
3281 fprintf (file
, "Reaching defs:\n");
3284 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
3286 if (! bb_info
->rd_in
)
3289 fprintf (file
, "bb %d in \t", bb
->index
);
3290 dump_bitmap (file
, bb_info
->rd_in
);
3291 fprintf (file
, "bb %d gen \t", bb
->index
);
3292 dump_bitmap (file
, bb_info
->rd_gen
);
3293 fprintf (file
, "bb %d kill\t", bb
->index
);
3294 dump_bitmap (file
, bb_info
->rd_kill
);
3295 fprintf (file
, "bb %d out \t", bb
->index
);
3296 dump_bitmap (file
, bb_info
->rd_out
);
3300 if (flags
& DF_UD_CHAIN
)
3302 fprintf (file
, "Use-def chains:\n");
3303 for (j
= 0; j
< df
->n_defs
; j
++)
3307 fprintf (file
, "d%d bb %d luid %d insn %d reg %d ",
3308 j
, DF_REF_BBNO (df
->defs
[j
]),
3309 DF_INSN_LUID (df
, DF_REF_INSN (df
->defs
[j
])),
3310 DF_REF_INSN_UID (df
->defs
[j
]),
3311 DF_REF_REGNO (df
->defs
[j
]));
3312 if (df
->defs
[j
]->flags
& DF_REF_READ_WRITE
)
3313 fprintf (file
, "read/write ");
3314 df_chain_dump (DF_REF_CHAIN (df
->defs
[j
]), file
);
3315 fprintf (file
, "\n");
3322 fprintf (file
, "Reaching uses:\n");
3325 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
3327 if (! bb_info
->ru_in
)
3330 fprintf (file
, "bb %d in \t", bb
->index
);
3331 dump_bitmap (file
, bb_info
->ru_in
);
3332 fprintf (file
, "bb %d gen \t", bb
->index
);
3333 dump_bitmap (file
, bb_info
->ru_gen
);
3334 fprintf (file
, "bb %d kill\t", bb
->index
);
3335 dump_bitmap (file
, bb_info
->ru_kill
);
3336 fprintf (file
, "bb %d out \t", bb
->index
);
3337 dump_bitmap (file
, bb_info
->ru_out
);
3341 if (flags
& DF_DU_CHAIN
)
3343 fprintf (file
, "Def-use chains:\n");
3344 for (j
= 0; j
< df
->n_uses
; j
++)
3348 fprintf (file
, "u%d bb %d luid %d insn %d reg %d ",
3349 j
, DF_REF_BBNO (df
->uses
[j
]),
3350 DF_INSN_LUID (df
, DF_REF_INSN (df
->uses
[j
])),
3351 DF_REF_INSN_UID (df
->uses
[j
]),
3352 DF_REF_REGNO (df
->uses
[j
]));
3353 if (df
->uses
[j
]->flags
& DF_REF_READ_WRITE
)
3354 fprintf (file
, "read/write ");
3355 df_chain_dump (DF_REF_CHAIN (df
->uses
[j
]), file
);
3356 fprintf (file
, "\n");
3363 fprintf (file
, "Live regs:\n");
3366 struct bb_info
*bb_info
= DF_BB_INFO (df
, bb
);
3368 if (! bb_info
->lr_in
)
3371 fprintf (file
, "bb %d in \t", bb
->index
);
3372 dump_bitmap (file
, bb_info
->lr_in
);
3373 fprintf (file
, "bb %d use \t", bb
->index
);
3374 dump_bitmap (file
, bb_info
->lr_use
);
3375 fprintf (file
, "bb %d def \t", bb
->index
);
3376 dump_bitmap (file
, bb_info
->lr_def
);
3377 fprintf (file
, "bb %d out \t", bb
->index
);
3378 dump_bitmap (file
, bb_info
->lr_out
);
3382 if (flags
& (DF_REG_INFO
| DF_RD_CHAIN
| DF_RU_CHAIN
))
3384 struct reg_info
*reg_info
= df
->regs
;
3386 fprintf (file
, "Register info:\n");
3387 for (j
= 0; j
< df
->n_regs
; j
++)
3389 if (((flags
& DF_REG_INFO
)
3390 && (reg_info
[j
].n_uses
|| reg_info
[j
].n_defs
))
3391 || ((flags
& DF_RD_CHAIN
) && reg_info
[j
].defs
)
3392 || ((flags
& DF_RU_CHAIN
) && reg_info
[j
].uses
))
3394 fprintf (file
, "reg %d", j
);
3395 if ((flags
& DF_RD_CHAIN
) && (flags
& DF_RU_CHAIN
))
3397 basic_block bb
= df_regno_bb (df
, j
);
3400 fprintf (file
, " bb %d", bb
->index
);
3402 fprintf (file
, " bb ?");
3404 if (flags
& DF_REG_INFO
)
3406 fprintf (file
, " life %d", reg_info
[j
].lifetime
);
3409 if ((flags
& DF_REG_INFO
) || (flags
& DF_RD_CHAIN
))
3411 fprintf (file
, " defs ");
3412 if (flags
& DF_REG_INFO
)
3413 fprintf (file
, "%d ", reg_info
[j
].n_defs
);
3414 if (flags
& DF_RD_CHAIN
)
3415 df_chain_dump (reg_info
[j
].defs
, file
);
3418 if ((flags
& DF_REG_INFO
) || (flags
& DF_RU_CHAIN
))
3420 fprintf (file
, " uses ");
3421 if (flags
& DF_REG_INFO
)
3422 fprintf (file
, "%d ", reg_info
[j
].n_uses
);
3423 if (flags
& DF_RU_CHAIN
)
3424 df_chain_dump (reg_info
[j
].uses
, file
);
3427 fprintf (file
, "\n");
3431 fprintf (file
, "\n");
3436 df_insn_debug (df
, insn
, file
)
3444 uid
= INSN_UID (insn
);
3445 if (uid
>= df
->insn_size
)
3448 if (df
->insns
[uid
].defs
)
3449 bbi
= DF_REF_BBNO (df
->insns
[uid
].defs
->ref
);
3450 else if (df
->insns
[uid
].uses
)
3451 bbi
= DF_REF_BBNO (df
->insns
[uid
].uses
->ref
);
3455 fprintf (file
, "insn %d bb %d luid %d defs ",
3456 uid
, bbi
, DF_INSN_LUID (df
, insn
));
3457 df_chain_dump (df
->insns
[uid
].defs
, file
);
3458 fprintf (file
, " uses ");
3459 df_chain_dump (df
->insns
[uid
].uses
, file
);
3460 fprintf (file
, "\n");
3464 df_insn_debug_regno (df
, insn
, file
)
3472 uid
= INSN_UID (insn
);
3473 if (uid
>= df
->insn_size
)
3476 if (df
->insns
[uid
].defs
)
3477 bbi
= DF_REF_BBNO (df
->insns
[uid
].defs
->ref
);
3478 else if (df
->insns
[uid
].uses
)
3479 bbi
= DF_REF_BBNO (df
->insns
[uid
].uses
->ref
);
3483 fprintf (file
, "insn %d bb %d luid %d defs ",
3484 uid
, bbi
, DF_INSN_LUID (df
, insn
));
3485 df_chain_dump_regno (df
->insns
[uid
].defs
, file
);
3486 fprintf (file
, " uses ");
3487 df_chain_dump_regno (df
->insns
[uid
].uses
, file
);
3488 fprintf (file
, "\n");
3492 df_regno_debug (df
, regno
, file
)
3497 if (regno
>= df
->reg_size
)
3500 fprintf (file
, "reg %d life %d defs ",
3501 regno
, df
->regs
[regno
].lifetime
);
3502 df_chain_dump (df
->regs
[regno
].defs
, file
);
3503 fprintf (file
, " uses ");
3504 df_chain_dump (df
->regs
[regno
].uses
, file
);
3505 fprintf (file
, "\n");
3510 df_ref_debug (df
, ref
, file
)
3515 fprintf (file
, "%c%d ",
3516 DF_REF_REG_DEF_P (ref
) ? 'd' : 'u',
3518 fprintf (file
, "reg %d bb %d luid %d insn %d chain ",
3521 DF_INSN_LUID (df
, DF_REF_INSN (ref
)),
3522 INSN_UID (DF_REF_INSN (ref
)));
3523 df_chain_dump (DF_REF_CHAIN (ref
), file
);
3524 fprintf (file
, "\n");
3529 debug_df_insn (insn
)
3532 df_insn_debug (ddf
, insn
, stderr
);
3541 df_regno_debug (ddf
, REGNO (reg
), stderr
);
3546 debug_df_regno (regno
)
3549 df_regno_debug (ddf
, regno
, stderr
);
3557 df_ref_debug (ddf
, ref
, stderr
);
3562 debug_df_defno (defno
)
3565 df_ref_debug (ddf
, ddf
->defs
[defno
], stderr
);
3570 debug_df_useno (defno
)
3573 df_ref_debug (ddf
, ddf
->uses
[defno
], stderr
);
3578 debug_df_chain (link
)
3579 struct df_link
*link
;
3581 df_chain_dump (link
, stderr
);
3582 fputc ('\n', stderr
);
3585 /* Hybrid search algorithm from "Implementation Techniques for
3586 Efficient Data-Flow Analysis of Large Programs". */
3588 hybrid_search_bitmap (block
, in
, out
, gen
, kill
, dir
,
3589 conf_op
, transfun
, visited
, pending
,
3592 bitmap
*in
, *out
, *gen
, *kill
;
3593 enum df_flow_dir dir
;
3594 enum df_confluence_op conf_op
;
3595 transfer_function_bitmap transfun
;
3601 int i
= block
->index
;
3603 basic_block bb
= block
;
3604 SET_BIT (visited
, block
->index
);
3605 if (TEST_BIT (pending
, block
->index
))
3609 /* Calculate <conf_op> of predecessor_outs */
3610 bitmap_zero (in
[i
]);
3611 for (e
= bb
->pred
; e
!= 0; e
= e
->pred_next
)
3613 if (e
->src
== ENTRY_BLOCK_PTR
)
3618 bitmap_a_or_b (in
[i
], in
[i
], out
[e
->src
->index
]);
3621 bitmap_a_and_b (in
[i
], in
[i
], out
[e
->src
->index
]);
3628 /* Calculate <conf_op> of successor ins */
3629 bitmap_zero(out
[i
]);
3630 for (e
= bb
->succ
; e
!= 0; e
= e
->succ_next
)
3632 if (e
->dest
== EXIT_BLOCK_PTR
)
3637 bitmap_a_or_b (out
[i
], out
[i
], in
[e
->dest
->index
]);
3640 bitmap_a_and_b (out
[i
], out
[i
], in
[e
->dest
->index
]);
3646 (*transfun
)(i
, &changed
, in
[i
], out
[i
], gen
[i
], kill
[i
], data
);
3647 RESET_BIT (pending
, i
);
3652 for (e
= bb
->succ
; e
!= 0; e
= e
->succ_next
)
3654 if (e
->dest
== EXIT_BLOCK_PTR
|| e
->dest
->index
== i
)
3656 SET_BIT (pending
, e
->dest
->index
);
3661 for (e
= bb
->pred
; e
!= 0; e
= e
->pred_next
)
3663 if (e
->src
== ENTRY_BLOCK_PTR
|| e
->dest
->index
== i
)
3665 SET_BIT (pending
, e
->src
->index
);
3672 for (e
= bb
->succ
; e
!= 0; e
= e
->succ_next
)
3674 if (e
->dest
== EXIT_BLOCK_PTR
|| e
->dest
->index
== i
)
3676 if (!TEST_BIT (visited
, e
->dest
->index
))
3677 hybrid_search_bitmap (e
->dest
, in
, out
, gen
, kill
, dir
,
3678 conf_op
, transfun
, visited
, pending
,
3684 for (e
= bb
->pred
; e
!= 0; e
= e
->pred_next
)
3686 if (e
->src
== ENTRY_BLOCK_PTR
|| e
->src
->index
== i
)
3688 if (!TEST_BIT (visited
, e
->src
->index
))
3689 hybrid_search_bitmap (e
->src
, in
, out
, gen
, kill
, dir
,
3690 conf_op
, transfun
, visited
, pending
,
3697 /* Hybrid search for sbitmaps, rather than bitmaps. */
3699 hybrid_search_sbitmap (block
, in
, out
, gen
, kill
, dir
,
3700 conf_op
, transfun
, visited
, pending
,
3703 sbitmap
*in
, *out
, *gen
, *kill
;
3704 enum df_flow_dir dir
;
3705 enum df_confluence_op conf_op
;
3706 transfer_function_sbitmap transfun
;
3712 int i
= block
->index
;
3714 basic_block bb
= block
;
3715 SET_BIT (visited
, block
->index
);
3716 if (TEST_BIT (pending
, block
->index
))
3720 /* Calculate <conf_op> of predecessor_outs */
3721 sbitmap_zero (in
[i
]);
3722 for (e
= bb
->pred
; e
!= 0; e
= e
->pred_next
)
3724 if (e
->src
== ENTRY_BLOCK_PTR
)
3729 sbitmap_a_or_b (in
[i
], in
[i
], out
[e
->src
->index
]);
3732 sbitmap_a_and_b (in
[i
], in
[i
], out
[e
->src
->index
]);
3739 /* Calculate <conf_op> of successor ins */
3740 sbitmap_zero(out
[i
]);
3741 for (e
= bb
->succ
; e
!= 0; e
= e
->succ_next
)
3743 if (e
->dest
== EXIT_BLOCK_PTR
)
3748 sbitmap_a_or_b (out
[i
], out
[i
], in
[e
->dest
->index
]);
3751 sbitmap_a_and_b (out
[i
], out
[i
], in
[e
->dest
->index
]);
3757 (*transfun
)(i
, &changed
, in
[i
], out
[i
], gen
[i
], kill
[i
], data
);
3758 RESET_BIT (pending
, i
);
3763 for (e
= bb
->succ
; e
!= 0; e
= e
->succ_next
)
3765 if (e
->dest
== EXIT_BLOCK_PTR
|| e
->dest
->index
== i
)
3767 SET_BIT (pending
, e
->dest
->index
);
3772 for (e
= bb
->pred
; e
!= 0; e
= e
->pred_next
)
3774 if (e
->src
== ENTRY_BLOCK_PTR
|| e
->dest
->index
== i
)
3776 SET_BIT (pending
, e
->src
->index
);
3783 for (e
= bb
->succ
; e
!= 0; e
= e
->succ_next
)
3785 if (e
->dest
== EXIT_BLOCK_PTR
|| e
->dest
->index
== i
)
3787 if (!TEST_BIT (visited
, e
->dest
->index
))
3788 hybrid_search_sbitmap (e
->dest
, in
, out
, gen
, kill
, dir
,
3789 conf_op
, transfun
, visited
, pending
,
3795 for (e
= bb
->pred
; e
!= 0; e
= e
->pred_next
)
3797 if (e
->src
== ENTRY_BLOCK_PTR
|| e
->src
->index
== i
)
3799 if (!TEST_BIT (visited
, e
->src
->index
))
3800 hybrid_search_sbitmap (e
->src
, in
, out
, gen
, kill
, dir
,
3801 conf_op
, transfun
, visited
, pending
,
3812 in, out = Filled in by function.
3813 blocks = Blocks to analyze.
3814 dir = Dataflow direction.
3815 conf_op = Confluence operation.
3816 transfun = Transfer function.
3817 order = Order to iterate in. (Should map block numbers -> order)
3818 data = Whatever you want. It's passed to the transfer function.
3820 This function will perform iterative bitvector dataflow, producing
3821 the in and out sets. Even if you only want to perform it for a
3822 small number of blocks, the vectors for in and out must be large
3823 enough for *all* blocks, because changing one block might affect
3824 others. However, it'll only put what you say to analyze on the
3827 For forward problems, you probably want to pass in a mapping of
3828 block number to rc_order (like df->inverse_rc_map).
3831 iterative_dataflow_sbitmap (in
, out
, gen
, kill
, blocks
,
3832 dir
, conf_op
, transfun
, order
, data
)
3833 sbitmap
*in
, *out
, *gen
, *kill
;
3835 enum df_flow_dir dir
;
3836 enum df_confluence_op conf_op
;
3837 transfer_function_sbitmap transfun
;
3844 sbitmap visited
, pending
;
3845 pending
= sbitmap_alloc (last_basic_block
);
3846 visited
= sbitmap_alloc (last_basic_block
);
3847 sbitmap_zero (pending
);
3848 sbitmap_zero (visited
);
3849 worklist
= fibheap_new ();
3850 EXECUTE_IF_SET_IN_BITMAP (blocks
, 0, i
,
3852 fibheap_insert (worklist
, order
[i
], (void *) (size_t) i
);
3853 SET_BIT (pending
, i
);
3855 sbitmap_copy (out
[i
], gen
[i
]);
3857 sbitmap_copy (in
[i
], gen
[i
]);
3859 while (sbitmap_first_set_bit (pending
) != -1)
3861 while (!fibheap_empty (worklist
))
3863 i
= (size_t) fibheap_extract_min (worklist
);
3864 bb
= BASIC_BLOCK (i
);
3865 if (!TEST_BIT (visited
, bb
->index
))
3866 hybrid_search_sbitmap (bb
, in
, out
, gen
, kill
, dir
,
3867 conf_op
, transfun
, visited
, pending
, data
);
3869 if (sbitmap_first_set_bit (pending
) != -1)
3871 EXECUTE_IF_SET_IN_BITMAP (blocks
, 0, i
,
3873 fibheap_insert (worklist
, order
[i
], (void *) (size_t) i
);
3875 sbitmap_zero (visited
);
3882 sbitmap_free (pending
);
3883 sbitmap_free (visited
);
3884 fibheap_delete (worklist
);
3887 /* Exactly the same as iterative_dataflow_sbitmap, except it works on
3890 iterative_dataflow_bitmap (in
, out
, gen
, kill
, blocks
,
3891 dir
, conf_op
, transfun
, order
, data
)
3892 bitmap
*in
, *out
, *gen
, *kill
;
3894 enum df_flow_dir dir
;
3895 enum df_confluence_op conf_op
;
3896 transfer_function_bitmap transfun
;
3903 sbitmap visited
, pending
;
3904 pending
= sbitmap_alloc (last_basic_block
);
3905 visited
= sbitmap_alloc (last_basic_block
);
3906 sbitmap_zero (pending
);
3907 sbitmap_zero (visited
);
3908 worklist
= fibheap_new ();
3909 EXECUTE_IF_SET_IN_BITMAP (blocks
, 0, i
,
3911 fibheap_insert (worklist
, order
[i
], (void *) (size_t) i
);
3912 SET_BIT (pending
, i
);
3914 bitmap_copy (out
[i
], gen
[i
]);
3916 bitmap_copy (in
[i
], gen
[i
]);
3918 while (sbitmap_first_set_bit (pending
) != -1)
3920 while (!fibheap_empty (worklist
))
3922 i
= (size_t) fibheap_extract_min (worklist
);
3923 bb
= BASIC_BLOCK (i
);
3924 if (!TEST_BIT (visited
, bb
->index
))
3925 hybrid_search_bitmap (bb
, in
, out
, gen
, kill
, dir
,
3926 conf_op
, transfun
, visited
, pending
, data
);
3928 if (sbitmap_first_set_bit (pending
) != -1)
3930 EXECUTE_IF_SET_IN_BITMAP (blocks
, 0, i
,
3932 fibheap_insert (worklist
, order
[i
], (void *) (size_t) i
);
3934 sbitmap_zero (visited
);
3941 sbitmap_free (pending
);
3942 sbitmap_free (visited
);
3943 fibheap_delete (worklist
);