1 /* Scanning of rtl for dataflow analysis.
2 Copyright (C) 1999-2015 Free Software Foundation, Inc.
3 Originally contributed by Michael P. Hayes
4 (m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com)
5 Major rewrite contributed by Danny Berlin (dberlin@dberlin.org)
6 and Kenneth Zadeck (zadeck@naturalbridge.com).
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 3, or (at your option) any later
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3. If not see
22 <http://www.gnu.org/licenses/>. */
26 #include "coretypes.h"
32 #include "insn-config.h"
36 #include "alloc-pool.h"
40 #include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */
43 typedef struct df_mw_hardreg
*df_mw_hardreg_ptr
;
46 /* The set of hard registers in eliminables[i].from. */
48 static HARD_REG_SET elim_reg_set
;
50 /* Initialize ur_in and ur_out as if all hard registers were partially
53 struct df_collection_rec
55 auto_vec
<df_ref
, 128> def_vec
;
56 auto_vec
<df_ref
, 32> use_vec
;
57 auto_vec
<df_ref
, 32> eq_use_vec
;
58 auto_vec
<df_mw_hardreg_ptr
, 32> mw_vec
;
61 static void df_ref_record (enum df_ref_class
, struct df_collection_rec
*,
63 basic_block
, struct df_insn_info
*,
64 enum df_ref_type
, int ref_flags
);
65 static void df_def_record_1 (struct df_collection_rec
*, rtx
*,
66 basic_block
, struct df_insn_info
*,
68 static void df_defs_record (struct df_collection_rec
*, rtx
,
69 basic_block
, struct df_insn_info
*,
71 static void df_uses_record (struct df_collection_rec
*,
72 rtx
*, enum df_ref_type
,
73 basic_block
, struct df_insn_info
*,
76 static void df_install_ref_incremental (df_ref
);
77 static void df_insn_refs_collect (struct df_collection_rec
*,
78 basic_block
, struct df_insn_info
*);
79 static void df_canonize_collection_rec (struct df_collection_rec
*);
81 static void df_get_regular_block_artificial_uses (bitmap
);
82 static void df_get_eh_block_artificial_uses (bitmap
);
84 static void df_record_entry_block_defs (bitmap
);
85 static void df_record_exit_block_uses (bitmap
);
86 static void df_get_exit_block_use_set (bitmap
);
87 static void df_get_entry_block_def_set (bitmap
);
88 static void df_grow_ref_info (struct df_ref_info
*, unsigned int);
89 static void df_ref_chain_delete_du_chain (df_ref
);
90 static void df_ref_chain_delete (df_ref
);
92 static void df_refs_add_to_chains (struct df_collection_rec
*,
93 basic_block
, rtx_insn
*, unsigned int);
95 static bool df_insn_refs_verify (struct df_collection_rec
*, basic_block
,
97 static void df_entry_block_defs_collect (struct df_collection_rec
*, bitmap
);
98 static void df_exit_block_uses_collect (struct df_collection_rec
*, bitmap
);
99 static void df_install_ref (df_ref
, struct df_reg_info
*,
100 struct df_ref_info
*, bool);
102 static int df_ref_compare (df_ref
, df_ref
);
103 static int df_ref_ptr_compare (const void *, const void *);
104 static int df_mw_compare (const df_mw_hardreg
*, const df_mw_hardreg
*);
105 static int df_mw_ptr_compare (const void *, const void *);
107 static void df_insn_info_delete (unsigned int);
109 /* Indexed by hardware reg number, is true if that register is ever
110 used in the current function.
112 In df-scan.c, this is set up to record the hard regs used
113 explicitly. Reload adds in the hard regs used for holding pseudo
114 regs. Final uses it to generate the code in the function prologue
115 and epilogue to save and restore registers as needed. */
117 static bool regs_ever_live
[FIRST_PSEUDO_REGISTER
];
119 /* Flags used to tell df_refs_add_to_chains() which vectors it should copy. */
120 static const unsigned int copy_defs
= 0x1;
121 static const unsigned int copy_uses
= 0x2;
122 static const unsigned int copy_eq_uses
= 0x4;
123 static const unsigned int copy_mw
= 0x8;
124 static const unsigned int copy_all
= copy_defs
| copy_uses
| copy_eq_uses
127 /*----------------------------------------------------------------------------
128 SCANNING DATAFLOW PROBLEM
130 There are several ways in which scanning looks just like the other
131 dataflow problems. It shares the all the mechanisms for local info
132 as well as basic block info. Where it differs is when and how often
133 it gets run. It also has no need for the iterative solver.
134 ----------------------------------------------------------------------------*/
136 #define SCAN_PROBLEM_DATA_BLOCK_SIZE 512
138 /* Problem data for the scanning dataflow function. */
139 struct df_scan_problem_data
141 object_allocator
<df_base_ref
> *ref_base_pool
;
142 object_allocator
<df_artificial_ref
> *ref_artificial_pool
;
143 object_allocator
<df_regular_ref
> *ref_regular_pool
;
144 object_allocator
<df_insn_info
> *insn_pool
;
145 object_allocator
<df_reg_info
> *reg_pool
;
146 object_allocator
<df_mw_hardreg
> *mw_reg_pool
;
148 bitmap_obstack reg_bitmaps
;
149 bitmap_obstack insn_bitmaps
;
152 typedef struct df_scan_bb_info
*df_scan_bb_info_t
;
155 /* Internal function to shut down the scanning problem. */
157 df_scan_free_internal (void)
159 struct df_scan_problem_data
*problem_data
160 = (struct df_scan_problem_data
*) df_scan
->problem_data
;
162 free (df
->def_info
.refs
);
163 free (df
->def_info
.begin
);
164 free (df
->def_info
.count
);
165 memset (&df
->def_info
, 0, (sizeof (struct df_ref_info
)));
167 free (df
->use_info
.refs
);
168 free (df
->use_info
.begin
);
169 free (df
->use_info
.count
);
170 memset (&df
->use_info
, 0, (sizeof (struct df_ref_info
)));
176 free (df
->eq_use_regs
);
177 df
->eq_use_regs
= NULL
;
179 DF_REG_SIZE (df
) = 0;
185 free (df_scan
->block_info
);
186 df_scan
->block_info
= NULL
;
187 df_scan
->block_info_size
= 0;
189 bitmap_clear (&df
->hardware_regs_used
);
190 bitmap_clear (&df
->regular_block_artificial_uses
);
191 bitmap_clear (&df
->eh_block_artificial_uses
);
192 BITMAP_FREE (df
->entry_block_defs
);
193 BITMAP_FREE (df
->exit_block_uses
);
194 bitmap_clear (&df
->insns_to_delete
);
195 bitmap_clear (&df
->insns_to_rescan
);
196 bitmap_clear (&df
->insns_to_notes_rescan
);
198 delete problem_data
->ref_base_pool
;
199 delete problem_data
->ref_artificial_pool
;
200 delete problem_data
->ref_regular_pool
;
201 delete problem_data
->insn_pool
;
202 delete problem_data
->reg_pool
;
203 delete problem_data
->mw_reg_pool
;
204 bitmap_obstack_release (&problem_data
->reg_bitmaps
);
205 bitmap_obstack_release (&problem_data
->insn_bitmaps
);
206 free (df_scan
->problem_data
);
210 /* Free basic block info. */
213 df_scan_free_bb_info (basic_block bb
, void *vbb_info
)
215 struct df_scan_bb_info
*bb_info
= (struct df_scan_bb_info
*) vbb_info
;
216 unsigned int bb_index
= bb
->index
;
219 FOR_BB_INSNS (bb
, insn
)
221 df_insn_info_delete (INSN_UID (insn
));
223 if (bb_index
< df_scan
->block_info_size
)
224 bb_info
= df_scan_get_bb_info (bb_index
);
226 /* Get rid of any artificial uses or defs. */
227 df_ref_chain_delete_du_chain (bb_info
->artificial_defs
);
228 df_ref_chain_delete_du_chain (bb_info
->artificial_uses
);
229 df_ref_chain_delete (bb_info
->artificial_defs
);
230 df_ref_chain_delete (bb_info
->artificial_uses
);
231 bb_info
->artificial_defs
= NULL
;
232 bb_info
->artificial_uses
= NULL
;
236 /* Allocate the problem data for the scanning problem. This should be
237 called when the problem is created or when the entire function is to
240 df_scan_alloc (bitmap all_blocks ATTRIBUTE_UNUSED
)
242 struct df_scan_problem_data
*problem_data
;
243 unsigned int insn_num
= get_max_uid () + 1;
246 /* Given the number of pools, this is really faster than tearing
248 if (df_scan
->problem_data
)
249 df_scan_free_internal ();
251 problem_data
= XNEW (struct df_scan_problem_data
);
252 df_scan
->problem_data
= problem_data
;
253 df_scan
->computed
= true;
255 problem_data
->ref_base_pool
= new object_allocator
<df_base_ref
>
256 ("df_scan ref base", SCAN_PROBLEM_DATA_BLOCK_SIZE
);
257 problem_data
->ref_artificial_pool
= new object_allocator
<df_artificial_ref
>
258 ("df_scan ref artificial", SCAN_PROBLEM_DATA_BLOCK_SIZE
);
259 problem_data
->ref_regular_pool
= new object_allocator
<df_regular_ref
>
260 ("df_scan ref regular", SCAN_PROBLEM_DATA_BLOCK_SIZE
);
261 problem_data
->insn_pool
= new object_allocator
<df_insn_info
>
262 ("df_scan insn", SCAN_PROBLEM_DATA_BLOCK_SIZE
);
263 problem_data
->reg_pool
= new object_allocator
<df_reg_info
>
264 ("df_scan reg", SCAN_PROBLEM_DATA_BLOCK_SIZE
);
265 problem_data
->mw_reg_pool
= new object_allocator
<df_mw_hardreg
>
266 ("df_scan mw_reg", SCAN_PROBLEM_DATA_BLOCK_SIZE
/ 16);
268 bitmap_obstack_initialize (&problem_data
->reg_bitmaps
);
269 bitmap_obstack_initialize (&problem_data
->insn_bitmaps
);
271 insn_num
+= insn_num
/ 4;
274 df_grow_insn_info ();
275 df_grow_bb_info (df_scan
);
277 FOR_ALL_BB_FN (bb
, cfun
)
279 unsigned int bb_index
= bb
->index
;
280 struct df_scan_bb_info
*bb_info
= df_scan_get_bb_info (bb_index
);
281 bb_info
->artificial_defs
= NULL
;
282 bb_info
->artificial_uses
= NULL
;
285 bitmap_initialize (&df
->hardware_regs_used
, &problem_data
->reg_bitmaps
);
286 bitmap_initialize (&df
->regular_block_artificial_uses
, &problem_data
->reg_bitmaps
);
287 bitmap_initialize (&df
->eh_block_artificial_uses
, &problem_data
->reg_bitmaps
);
288 df
->entry_block_defs
= BITMAP_ALLOC (&problem_data
->reg_bitmaps
);
289 df
->exit_block_uses
= BITMAP_ALLOC (&problem_data
->reg_bitmaps
);
290 bitmap_initialize (&df
->insns_to_delete
, &problem_data
->insn_bitmaps
);
291 bitmap_initialize (&df
->insns_to_rescan
, &problem_data
->insn_bitmaps
);
292 bitmap_initialize (&df
->insns_to_notes_rescan
, &problem_data
->insn_bitmaps
);
293 df_scan
->optional_p
= false;
297 /* Free all of the data associated with the scan problem. */
302 if (df_scan
->problem_data
)
303 df_scan_free_internal ();
305 if (df
->blocks_to_analyze
)
307 BITMAP_FREE (df
->blocks_to_analyze
);
308 df
->blocks_to_analyze
= NULL
;
314 /* Dump the preamble for DF_SCAN dump. */
316 df_scan_start_dump (FILE *file ATTRIBUTE_UNUSED
)
327 fprintf (file
, ";; invalidated by call \t");
328 df_print_regset (file
, regs_invalidated_by_call_regset
);
329 fprintf (file
, ";; hardware regs used \t");
330 df_print_regset (file
, &df
->hardware_regs_used
);
331 fprintf (file
, ";; regular block artificial uses \t");
332 df_print_regset (file
, &df
->regular_block_artificial_uses
);
333 fprintf (file
, ";; eh block artificial uses \t");
334 df_print_regset (file
, &df
->eh_block_artificial_uses
);
335 fprintf (file
, ";; entry block defs \t");
336 df_print_regset (file
, df
->entry_block_defs
);
337 fprintf (file
, ";; exit block uses \t");
338 df_print_regset (file
, df
->exit_block_uses
);
339 fprintf (file
, ";; regs ever live \t");
340 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
341 if (df_regs_ever_live_p (i
))
342 fprintf (file
, " %d [%s]", i
, reg_names
[i
]);
343 fprintf (file
, "\n;; ref usage \t");
345 for (i
= 0; i
< (int)df
->regs_inited
; i
++)
346 if (DF_REG_DEF_COUNT (i
) || DF_REG_USE_COUNT (i
) || DF_REG_EQ_USE_COUNT (i
))
348 const char * sep
= "";
350 fprintf (file
, "r%d={", i
);
351 if (DF_REG_DEF_COUNT (i
))
353 fprintf (file
, "%dd", DF_REG_DEF_COUNT (i
));
355 dcount
+= DF_REG_DEF_COUNT (i
);
357 if (DF_REG_USE_COUNT (i
))
359 fprintf (file
, "%s%du", sep
, DF_REG_USE_COUNT (i
));
361 ucount
+= DF_REG_USE_COUNT (i
);
363 if (DF_REG_EQ_USE_COUNT (i
))
365 fprintf (file
, "%s%de", sep
, DF_REG_EQ_USE_COUNT (i
));
366 ecount
+= DF_REG_EQ_USE_COUNT (i
);
368 fprintf (file
, "} ");
371 FOR_EACH_BB_FN (bb
, cfun
)
372 FOR_BB_INSNS (bb
, insn
)
381 fprintf (file
, "\n;; total ref usage %d{%dd,%du,%de}"
382 " in %d{%d regular + %d call} insns.\n",
383 dcount
+ ucount
+ ecount
, dcount
, ucount
, ecount
,
384 icount
+ ccount
, icount
, ccount
);
387 /* Dump the bb_info for a given basic block. */
389 df_scan_start_block (basic_block bb
, FILE *file
)
391 struct df_scan_bb_info
*bb_info
392 = df_scan_get_bb_info (bb
->index
);
396 fprintf (file
, ";; bb %d artificial_defs: ", bb
->index
);
397 df_refs_chain_dump (bb_info
->artificial_defs
, true, file
);
398 fprintf (file
, "\n;; bb %d artificial_uses: ", bb
->index
);
399 df_refs_chain_dump (bb_info
->artificial_uses
, true, file
);
400 fprintf (file
, "\n");
405 FOR_BB_INSNS (bb
, insn
)
407 df_insn_debug (insn
, false, file
);
412 static struct df_problem problem_SCAN
=
414 DF_SCAN
, /* Problem id. */
415 DF_NONE
, /* Direction. */
416 df_scan_alloc
, /* Allocate the problem specific data. */
417 NULL
, /* Reset global information. */
418 df_scan_free_bb_info
, /* Free basic block info. */
419 NULL
, /* Local compute function. */
420 NULL
, /* Init the solution specific data. */
421 NULL
, /* Iterative solver. */
422 NULL
, /* Confluence operator 0. */
423 NULL
, /* Confluence operator n. */
424 NULL
, /* Transfer function. */
425 NULL
, /* Finalize function. */
426 df_scan_free
, /* Free all of the problem information. */
427 NULL
, /* Remove this problem from the stack of dataflow problems. */
428 df_scan_start_dump
, /* Debugging. */
429 df_scan_start_block
, /* Debugging start block. */
430 NULL
, /* Debugging end block. */
431 NULL
, /* Debugging start insn. */
432 NULL
, /* Debugging end insn. */
433 NULL
, /* Incremental solution verify start. */
434 NULL
, /* Incremental solution verify end. */
435 NULL
, /* Dependent problem. */
436 sizeof (struct df_scan_bb_info
),/* Size of entry of block_info array. */
437 TV_DF_SCAN
, /* Timing variable. */
438 false /* Reset blocks on dropping out of blocks_to_analyze. */
442 /* Create a new DATAFLOW instance and add it to an existing instance
443 of DF. The returned structure is what is used to get at the
447 df_scan_add_problem (void)
449 df_add_problem (&problem_SCAN
);
453 /*----------------------------------------------------------------------------
454 Storage Allocation Utilities
455 ----------------------------------------------------------------------------*/
458 /* First, grow the reg_info information. If the current size is less than
459 the number of pseudos, grow to 25% more than the number of
462 Second, assure that all of the slots up to max_reg_num have been
463 filled with reg_info structures. */
466 df_grow_reg_info (void)
468 unsigned int max_reg
= max_reg_num ();
469 unsigned int new_size
= max_reg
;
470 struct df_scan_problem_data
*problem_data
471 = (struct df_scan_problem_data
*) df_scan
->problem_data
;
474 if (df
->regs_size
< new_size
)
476 new_size
+= new_size
/ 4;
477 df
->def_regs
= XRESIZEVEC (struct df_reg_info
*, df
->def_regs
, new_size
);
478 df
->use_regs
= XRESIZEVEC (struct df_reg_info
*, df
->use_regs
, new_size
);
479 df
->eq_use_regs
= XRESIZEVEC (struct df_reg_info
*, df
->eq_use_regs
,
481 df
->def_info
.begin
= XRESIZEVEC (unsigned, df
->def_info
.begin
, new_size
);
482 df
->def_info
.count
= XRESIZEVEC (unsigned, df
->def_info
.count
, new_size
);
483 df
->use_info
.begin
= XRESIZEVEC (unsigned, df
->use_info
.begin
, new_size
);
484 df
->use_info
.count
= XRESIZEVEC (unsigned, df
->use_info
.count
, new_size
);
485 df
->regs_size
= new_size
;
488 for (i
= df
->regs_inited
; i
< max_reg
; i
++)
490 struct df_reg_info
*reg_info
;
493 reg_info
= problem_data
->reg_pool
->allocate ();
494 memset (reg_info
, 0, sizeof (struct df_reg_info
));
495 df
->def_regs
[i
] = reg_info
;
496 reg_info
= problem_data
->reg_pool
->allocate ();
497 memset (reg_info
, 0, sizeof (struct df_reg_info
));
498 df
->use_regs
[i
] = reg_info
;
499 reg_info
= problem_data
->reg_pool
->allocate ();
500 memset (reg_info
, 0, sizeof (struct df_reg_info
));
501 df
->eq_use_regs
[i
] = reg_info
;
502 df
->def_info
.begin
[i
] = 0;
503 df
->def_info
.count
[i
] = 0;
504 df
->use_info
.begin
[i
] = 0;
505 df
->use_info
.count
[i
] = 0;
508 df
->regs_inited
= max_reg
;
512 /* Grow the ref information. */
515 df_grow_ref_info (struct df_ref_info
*ref_info
, unsigned int new_size
)
517 if (ref_info
->refs_size
< new_size
)
519 ref_info
->refs
= XRESIZEVEC (df_ref
, ref_info
->refs
, new_size
);
520 memset (ref_info
->refs
+ ref_info
->refs_size
, 0,
521 (new_size
- ref_info
->refs_size
) *sizeof (df_ref
));
522 ref_info
->refs_size
= new_size
;
527 /* Check and grow the ref information if necessary. This routine
528 guarantees total_size + BITMAP_ADDEND amount of entries in refs
529 array. It updates ref_info->refs_size only and does not change
530 ref_info->total_size. */
533 df_check_and_grow_ref_info (struct df_ref_info
*ref_info
,
534 unsigned bitmap_addend
)
536 if (ref_info
->refs_size
< ref_info
->total_size
+ bitmap_addend
)
538 int new_size
= ref_info
->total_size
+ bitmap_addend
;
539 new_size
+= ref_info
->total_size
/ 4;
540 df_grow_ref_info (ref_info
, new_size
);
545 /* Grow the ref information. If the current size is less than the
546 number of instructions, grow to 25% more than the number of
550 df_grow_insn_info (void)
552 unsigned int new_size
= get_max_uid () + 1;
553 if (DF_INSN_SIZE () < new_size
)
555 new_size
+= new_size
/ 4;
556 df
->insns
= XRESIZEVEC (struct df_insn_info
*, df
->insns
, new_size
);
557 memset (df
->insns
+ df
->insns_size
, 0,
558 (new_size
- DF_INSN_SIZE ()) *sizeof (struct df_insn_info
*));
559 DF_INSN_SIZE () = new_size
;
566 /*----------------------------------------------------------------------------
567 PUBLIC INTERFACES FOR SMALL GRAIN CHANGES TO SCANNING.
568 ----------------------------------------------------------------------------*/
570 /* Rescan all of the block_to_analyze or all of the blocks in the
571 function if df_set_blocks if blocks_to_analyze is NULL; */
574 df_scan_blocks (void)
578 df
->def_info
.ref_order
= DF_REF_ORDER_NO_TABLE
;
579 df
->use_info
.ref_order
= DF_REF_ORDER_NO_TABLE
;
581 df_get_regular_block_artificial_uses (&df
->regular_block_artificial_uses
);
582 df_get_eh_block_artificial_uses (&df
->eh_block_artificial_uses
);
584 bitmap_ior_into (&df
->eh_block_artificial_uses
,
585 &df
->regular_block_artificial_uses
);
587 /* ENTRY and EXIT blocks have special defs/uses. */
588 df_get_entry_block_def_set (df
->entry_block_defs
);
589 df_record_entry_block_defs (df
->entry_block_defs
);
590 df_get_exit_block_use_set (df
->exit_block_uses
);
591 df_record_exit_block_uses (df
->exit_block_uses
);
592 df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun
, ENTRY_BLOCK
));
593 df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun
, EXIT_BLOCK
));
596 FOR_EACH_BB_FN (bb
, cfun
)
598 unsigned int bb_index
= bb
->index
;
599 df_bb_refs_record (bb_index
, true);
603 /* Create new refs under address LOC within INSN. This function is
604 only used externally. REF_FLAGS must be either 0 or DF_REF_IN_NOTE,
605 depending on whether LOC is inside PATTERN (INSN) or a note. */
608 df_uses_create (rtx
*loc
, rtx_insn
*insn
, int ref_flags
)
610 gcc_assert (!(ref_flags
& ~DF_REF_IN_NOTE
));
611 df_uses_record (NULL
, loc
, DF_REF_REG_USE
,
612 BLOCK_FOR_INSN (insn
),
613 DF_INSN_INFO_GET (insn
),
618 df_install_ref_incremental (df_ref ref
)
620 struct df_reg_info
**reg_info
;
621 struct df_ref_info
*ref_info
;
625 rtx_insn
*insn
= DF_REF_INSN (ref
);
626 basic_block bb
= BLOCK_FOR_INSN (insn
);
628 if (DF_REF_REG_DEF_P (ref
))
630 reg_info
= df
->def_regs
;
631 ref_info
= &df
->def_info
;
632 ref_ptr
= &DF_INSN_DEFS (insn
);
633 add_to_table
= ref_info
->ref_order
!= DF_REF_ORDER_NO_TABLE
;
635 else if (DF_REF_FLAGS (ref
) & DF_REF_IN_NOTE
)
637 reg_info
= df
->eq_use_regs
;
638 ref_info
= &df
->use_info
;
639 ref_ptr
= &DF_INSN_EQ_USES (insn
);
640 switch (ref_info
->ref_order
)
642 case DF_REF_ORDER_UNORDERED_WITH_NOTES
:
643 case DF_REF_ORDER_BY_REG_WITH_NOTES
:
644 case DF_REF_ORDER_BY_INSN_WITH_NOTES
:
648 add_to_table
= false;
654 reg_info
= df
->use_regs
;
655 ref_info
= &df
->use_info
;
656 ref_ptr
= &DF_INSN_USES (insn
);
657 add_to_table
= ref_info
->ref_order
!= DF_REF_ORDER_NO_TABLE
;
660 /* Do not add if ref is not in the right blocks. */
661 if (add_to_table
&& df
->analyze_subset
)
662 add_to_table
= bitmap_bit_p (df
->blocks_to_analyze
, bb
->index
);
664 df_install_ref (ref
, reg_info
[DF_REF_REGNO (ref
)], ref_info
, add_to_table
);
667 switch (ref_info
->ref_order
)
669 case DF_REF_ORDER_UNORDERED_WITH_NOTES
:
670 case DF_REF_ORDER_BY_REG_WITH_NOTES
:
671 case DF_REF_ORDER_BY_INSN_WITH_NOTES
:
672 ref_info
->ref_order
= DF_REF_ORDER_UNORDERED_WITH_NOTES
;
675 ref_info
->ref_order
= DF_REF_ORDER_UNORDERED
;
679 while (*ref_ptr
&& df_ref_compare (*ref_ptr
, ref
) < 0)
680 ref_ptr
= &DF_REF_NEXT_LOC (*ref_ptr
);
682 DF_REF_NEXT_LOC (ref
) = *ref_ptr
;
688 fprintf (dump_file
, "adding ref ");
689 df_ref_debug (ref
, dump_file
);
692 /* By adding the ref directly, df_insn_rescan my not find any
693 differences even though the block will have changed. So we need
694 to mark the block dirty ourselves. */
695 if (!DEBUG_INSN_P (DF_REF_INSN (ref
)))
696 df_set_bb_dirty (bb
);
701 /*----------------------------------------------------------------------------
702 UTILITIES TO CREATE AND DESTROY REFS AND CHAINS.
703 ----------------------------------------------------------------------------*/
706 df_free_ref (df_ref ref
)
708 struct df_scan_problem_data
*problem_data
709 = (struct df_scan_problem_data
*) df_scan
->problem_data
;
711 switch (DF_REF_CLASS (ref
))
714 problem_data
->ref_base_pool
->remove ((df_base_ref
*) (ref
));
717 case DF_REF_ARTIFICIAL
:
718 problem_data
->ref_artificial_pool
->remove
719 ((df_artificial_ref
*) (ref
));
723 problem_data
->ref_regular_pool
->remove
724 ((df_regular_ref
*) (ref
));
730 /* Unlink and delete REF at the reg_use, reg_eq_use or reg_def chain.
731 Also delete the def-use or use-def chain if it exists. */
734 df_reg_chain_unlink (df_ref ref
)
736 df_ref next
= DF_REF_NEXT_REG (ref
);
737 df_ref prev
= DF_REF_PREV_REG (ref
);
738 int id
= DF_REF_ID (ref
);
739 struct df_reg_info
*reg_info
;
742 if (DF_REF_REG_DEF_P (ref
))
744 int regno
= DF_REF_REGNO (ref
);
745 reg_info
= DF_REG_DEF_GET (regno
);
746 refs
= df
->def_info
.refs
;
750 if (DF_REF_FLAGS (ref
) & DF_REF_IN_NOTE
)
752 reg_info
= DF_REG_EQ_USE_GET (DF_REF_REGNO (ref
));
753 switch (df
->use_info
.ref_order
)
755 case DF_REF_ORDER_UNORDERED_WITH_NOTES
:
756 case DF_REF_ORDER_BY_REG_WITH_NOTES
:
757 case DF_REF_ORDER_BY_INSN_WITH_NOTES
:
758 refs
= df
->use_info
.refs
;
766 reg_info
= DF_REG_USE_GET (DF_REF_REGNO (ref
));
767 refs
= df
->use_info
.refs
;
773 if (df
->analyze_subset
)
775 if (bitmap_bit_p (df
->blocks_to_analyze
, DF_REF_BBNO (ref
)))
782 /* Delete any def-use or use-def chains that start here. It is
783 possible that there is trash in this field. This happens for
784 insns that have been deleted when rescanning has been deferred
785 and the chain problem has also been deleted. The chain tear down
786 code skips deleted insns. */
787 if (df_chain
&& DF_REF_CHAIN (ref
))
788 df_chain_unlink (ref
);
791 if (DF_REF_FLAGS_IS_SET (ref
, DF_HARD_REG_LIVE
))
793 gcc_assert (DF_REF_REGNO (ref
) < FIRST_PSEUDO_REGISTER
);
794 df
->hard_regs_live_count
[DF_REF_REGNO (ref
)]--;
797 /* Unlink from the reg chain. If there is no prev, this is the
798 first of the list. If not, just join the next and prev. */
800 DF_REF_NEXT_REG (prev
) = next
;
803 gcc_assert (reg_info
->reg_chain
== ref
);
804 reg_info
->reg_chain
= next
;
807 DF_REF_PREV_REG (next
) = prev
;
812 /* Initialize INSN_INFO to describe INSN. */
815 df_insn_info_init_fields (df_insn_info
*insn_info
, rtx_insn
*insn
)
817 memset (insn_info
, 0, sizeof (struct df_insn_info
));
818 insn_info
->insn
= insn
;
821 /* Create the insn record for INSN. If there was one there, zero it
824 struct df_insn_info
*
825 df_insn_create_insn_record (rtx_insn
*insn
)
827 struct df_scan_problem_data
*problem_data
828 = (struct df_scan_problem_data
*) df_scan
->problem_data
;
829 struct df_insn_info
*insn_rec
;
831 df_grow_insn_info ();
832 insn_rec
= DF_INSN_INFO_GET (insn
);
835 insn_rec
= problem_data
->insn_pool
->allocate ();
836 DF_INSN_INFO_SET (insn
, insn_rec
);
838 df_insn_info_init_fields (insn_rec
, insn
);
843 /* Delete all du chain (DF_REF_CHAIN()) of all refs in the ref chain. */
846 df_ref_chain_delete_du_chain (df_ref ref
)
848 for (; ref
; ref
= DF_REF_NEXT_LOC (ref
))
849 /* CHAIN is allocated by DF_CHAIN. So make sure to
850 pass df_scan instance for the problem. */
851 if (DF_REF_CHAIN (ref
))
852 df_chain_unlink (ref
);
856 /* Delete all refs in the ref chain. */
859 df_ref_chain_delete (df_ref ref
)
862 for (; ref
; ref
= next
)
864 next
= DF_REF_NEXT_LOC (ref
);
865 df_reg_chain_unlink (ref
);
870 /* Delete the hardreg chain. */
873 df_mw_hardreg_chain_delete (struct df_mw_hardreg
*hardregs
)
875 struct df_scan_problem_data
*problem_data
876 = (struct df_scan_problem_data
*) df_scan
->problem_data
;
879 for (; hardregs
; hardregs
= next
)
881 next
= DF_MWS_NEXT (hardregs
);
882 problem_data
->mw_reg_pool
->remove (hardregs
);
886 /* Remove the contents of INSN_INFO (but don't free INSN_INFO itself). */
889 df_insn_info_free_fields (df_insn_info
*insn_info
)
891 /* In general, notes do not have the insn_info fields
892 initialized. However, combine deletes insns by changing them
893 to notes. How clever. So we cannot just check if it is a
894 valid insn before short circuiting this code, we need to see
895 if we actually initialized it. */
896 df_mw_hardreg_chain_delete (insn_info
->mw_hardregs
);
900 df_ref_chain_delete_du_chain (insn_info
->defs
);
901 df_ref_chain_delete_du_chain (insn_info
->uses
);
902 df_ref_chain_delete_du_chain (insn_info
->eq_uses
);
905 df_ref_chain_delete (insn_info
->defs
);
906 df_ref_chain_delete (insn_info
->uses
);
907 df_ref_chain_delete (insn_info
->eq_uses
);
910 /* Delete all of the refs information from the insn with UID.
911 Internal helper for df_insn_delete, df_insn_rescan, and other
912 df-scan routines that don't have to work in deferred mode
913 and do not have to mark basic blocks for re-processing. */
916 df_insn_info_delete (unsigned int uid
)
918 struct df_insn_info
*insn_info
= DF_INSN_UID_SAFE_GET (uid
);
920 bitmap_clear_bit (&df
->insns_to_delete
, uid
);
921 bitmap_clear_bit (&df
->insns_to_rescan
, uid
);
922 bitmap_clear_bit (&df
->insns_to_notes_rescan
, uid
);
925 struct df_scan_problem_data
*problem_data
926 = (struct df_scan_problem_data
*) df_scan
->problem_data
;
928 df_insn_info_free_fields (insn_info
);
929 problem_data
->insn_pool
->remove (insn_info
);
930 DF_INSN_UID_SET (uid
, NULL
);
934 /* Delete all of the refs information from INSN, either right now
935 or marked for later in deferred mode. */
938 df_insn_delete (rtx_insn
*insn
)
943 gcc_checking_assert (INSN_P (insn
));
948 uid
= INSN_UID (insn
);
949 bb
= BLOCK_FOR_INSN (insn
);
951 /* ??? bb can be NULL after pass_free_cfg. At that point, DF should
952 not exist anymore (as mentioned in df-core.c: "The only requirement
953 [for DF] is that there be a correct control flow graph." Clearly
954 that isn't the case after pass_free_cfg. But DF is freed much later
955 because some back-ends want to use DF info even though the CFG is
956 already gone. It's not clear to me whether that is safe, actually.
957 In any case, we expect BB to be non-NULL at least up to register
958 allocation, so disallow a non-NULL BB up to there. Not perfect
959 but better than nothing... */
960 gcc_checking_assert (bb
!= NULL
|| reload_completed
);
962 df_grow_bb_info (df_scan
);
965 /* The block must be marked as dirty now, rather than later as in
966 df_insn_rescan and df_notes_rescan because it may not be there at
967 rescanning time and the mark would blow up.
968 DEBUG_INSNs do not make a block's data flow solution dirty (at
969 worst the LUIDs are no longer contiguous). */
970 if (bb
!= NULL
&& NONDEBUG_INSN_P (insn
))
971 df_set_bb_dirty (bb
);
973 /* The client has deferred rescanning. */
974 if (df
->changeable_flags
& DF_DEFER_INSN_RESCAN
)
976 struct df_insn_info
*insn_info
= DF_INSN_UID_SAFE_GET (uid
);
979 bitmap_clear_bit (&df
->insns_to_rescan
, uid
);
980 bitmap_clear_bit (&df
->insns_to_notes_rescan
, uid
);
981 bitmap_set_bit (&df
->insns_to_delete
, uid
);
984 fprintf (dump_file
, "deferring deletion of insn with uid = %d.\n", uid
);
989 fprintf (dump_file
, "deleting insn with uid = %d.\n", uid
);
991 df_insn_info_delete (uid
);
995 /* Free all of the refs and the mw_hardregs in COLLECTION_REC. */
998 df_free_collection_rec (struct df_collection_rec
*collection_rec
)
1001 struct df_scan_problem_data
*problem_data
1002 = (struct df_scan_problem_data
*) df_scan
->problem_data
;
1004 struct df_mw_hardreg
*mw
;
1006 FOR_EACH_VEC_ELT (collection_rec
->def_vec
, ix
, ref
)
1008 FOR_EACH_VEC_ELT (collection_rec
->use_vec
, ix
, ref
)
1010 FOR_EACH_VEC_ELT (collection_rec
->eq_use_vec
, ix
, ref
)
1012 FOR_EACH_VEC_ELT (collection_rec
->mw_vec
, ix
, mw
)
1013 problem_data
->mw_reg_pool
->remove (mw
);
1015 collection_rec
->def_vec
.release ();
1016 collection_rec
->use_vec
.release ();
1017 collection_rec
->eq_use_vec
.release ();
1018 collection_rec
->mw_vec
.release ();
1021 /* Rescan INSN. Return TRUE if the rescanning produced any changes. */
1024 df_insn_rescan (rtx_insn
*insn
)
1026 unsigned int uid
= INSN_UID (insn
);
1027 struct df_insn_info
*insn_info
= NULL
;
1028 basic_block bb
= BLOCK_FOR_INSN (insn
);
1029 struct df_collection_rec collection_rec
;
1031 if ((!df
) || (!INSN_P (insn
)))
1037 fprintf (dump_file
, "no bb for insn with uid = %d.\n", uid
);
1041 /* The client has disabled rescanning and plans to do it itself. */
1042 if (df
->changeable_flags
& DF_NO_INSN_RESCAN
)
1045 df_grow_bb_info (df_scan
);
1046 df_grow_reg_info ();
1048 insn_info
= DF_INSN_UID_SAFE_GET (uid
);
1050 /* The client has deferred rescanning. */
1051 if (df
->changeable_flags
& DF_DEFER_INSN_RESCAN
)
1055 insn_info
= df_insn_create_insn_record (insn
);
1056 insn_info
->defs
= 0;
1057 insn_info
->uses
= 0;
1058 insn_info
->eq_uses
= 0;
1059 insn_info
->mw_hardregs
= 0;
1062 fprintf (dump_file
, "deferring rescan insn with uid = %d.\n", uid
);
1064 bitmap_clear_bit (&df
->insns_to_delete
, uid
);
1065 bitmap_clear_bit (&df
->insns_to_notes_rescan
, uid
);
1066 bitmap_set_bit (&df
->insns_to_rescan
, INSN_UID (insn
));
1070 bitmap_clear_bit (&df
->insns_to_delete
, uid
);
1071 bitmap_clear_bit (&df
->insns_to_rescan
, uid
);
1072 bitmap_clear_bit (&df
->insns_to_notes_rescan
, uid
);
1076 bool the_same
= df_insn_refs_verify (&collection_rec
, bb
, insn
, false);
1077 /* If there's no change, return false. */
1080 df_free_collection_rec (&collection_rec
);
1082 fprintf (dump_file
, "verify found no changes in insn with uid = %d.\n", uid
);
1086 fprintf (dump_file
, "rescanning insn with uid = %d.\n", uid
);
1088 /* There's change - we need to delete the existing info.
1089 Since the insn isn't moved, we can salvage its LUID. */
1090 luid
= DF_INSN_LUID (insn
);
1091 df_insn_info_free_fields (insn_info
);
1092 df_insn_info_init_fields (insn_info
, insn
);
1093 DF_INSN_LUID (insn
) = luid
;
1097 struct df_insn_info
*insn_info
= df_insn_create_insn_record (insn
);
1098 df_insn_refs_collect (&collection_rec
, bb
, insn_info
);
1100 fprintf (dump_file
, "scanning new insn with uid = %d.\n", uid
);
1103 df_refs_add_to_chains (&collection_rec
, bb
, insn
, copy_all
);
1104 if (!DEBUG_INSN_P (insn
))
1105 df_set_bb_dirty (bb
);
1110 /* Same as df_insn_rescan, but don't mark the basic block as
1114 df_insn_rescan_debug_internal (rtx_insn
*insn
)
1116 unsigned int uid
= INSN_UID (insn
);
1117 struct df_insn_info
*insn_info
;
1119 gcc_assert (DEBUG_INSN_P (insn
)
1120 && VAR_LOC_UNKNOWN_P (INSN_VAR_LOCATION_LOC (insn
)));
1125 insn_info
= DF_INSN_UID_SAFE_GET (INSN_UID (insn
));
1130 fprintf (dump_file
, "deleting debug_insn with uid = %d.\n", uid
);
1132 bitmap_clear_bit (&df
->insns_to_delete
, uid
);
1133 bitmap_clear_bit (&df
->insns_to_rescan
, uid
);
1134 bitmap_clear_bit (&df
->insns_to_notes_rescan
, uid
);
1136 if (insn_info
->defs
== 0
1137 && insn_info
->uses
== 0
1138 && insn_info
->eq_uses
== 0
1139 && insn_info
->mw_hardregs
== 0)
1142 df_mw_hardreg_chain_delete (insn_info
->mw_hardregs
);
1146 df_ref_chain_delete_du_chain (insn_info
->defs
);
1147 df_ref_chain_delete_du_chain (insn_info
->uses
);
1148 df_ref_chain_delete_du_chain (insn_info
->eq_uses
);
1151 df_ref_chain_delete (insn_info
->defs
);
1152 df_ref_chain_delete (insn_info
->uses
);
1153 df_ref_chain_delete (insn_info
->eq_uses
);
1155 insn_info
->defs
= 0;
1156 insn_info
->uses
= 0;
1157 insn_info
->eq_uses
= 0;
1158 insn_info
->mw_hardregs
= 0;
1164 /* Rescan all of the insns in the function. Note that the artificial
1165 uses and defs are not touched. This function will destroy def-use
1166 or use-def chains. */
1169 df_insn_rescan_all (void)
1171 bool no_insn_rescan
= false;
1172 bool defer_insn_rescan
= false;
1178 bitmap_initialize (&tmp
, &df_bitmap_obstack
);
1180 if (df
->changeable_flags
& DF_NO_INSN_RESCAN
)
1182 df_clear_flags (DF_NO_INSN_RESCAN
);
1183 no_insn_rescan
= true;
1186 if (df
->changeable_flags
& DF_DEFER_INSN_RESCAN
)
1188 df_clear_flags (DF_DEFER_INSN_RESCAN
);
1189 defer_insn_rescan
= true;
1192 bitmap_copy (&tmp
, &df
->insns_to_delete
);
1193 EXECUTE_IF_SET_IN_BITMAP (&tmp
, 0, uid
, bi
)
1195 struct df_insn_info
*insn_info
= DF_INSN_UID_SAFE_GET (uid
);
1197 df_insn_info_delete (uid
);
1200 bitmap_clear (&tmp
);
1201 bitmap_clear (&df
->insns_to_delete
);
1202 bitmap_clear (&df
->insns_to_rescan
);
1203 bitmap_clear (&df
->insns_to_notes_rescan
);
1205 FOR_EACH_BB_FN (bb
, cfun
)
1208 FOR_BB_INSNS (bb
, insn
)
1210 df_insn_rescan (insn
);
1215 df_set_flags (DF_NO_INSN_RESCAN
);
1216 if (defer_insn_rescan
)
1217 df_set_flags (DF_DEFER_INSN_RESCAN
);
1221 /* Process all of the deferred rescans or deletions. */
1224 df_process_deferred_rescans (void)
1226 bool no_insn_rescan
= false;
1227 bool defer_insn_rescan
= false;
1232 bitmap_initialize (&tmp
, &df_bitmap_obstack
);
1234 if (df
->changeable_flags
& DF_NO_INSN_RESCAN
)
1236 df_clear_flags (DF_NO_INSN_RESCAN
);
1237 no_insn_rescan
= true;
1240 if (df
->changeable_flags
& DF_DEFER_INSN_RESCAN
)
1242 df_clear_flags (DF_DEFER_INSN_RESCAN
);
1243 defer_insn_rescan
= true;
1247 fprintf (dump_file
, "starting the processing of deferred insns\n");
1249 bitmap_copy (&tmp
, &df
->insns_to_delete
);
1250 EXECUTE_IF_SET_IN_BITMAP (&tmp
, 0, uid
, bi
)
1252 struct df_insn_info
*insn_info
= DF_INSN_UID_SAFE_GET (uid
);
1254 df_insn_info_delete (uid
);
1257 bitmap_copy (&tmp
, &df
->insns_to_rescan
);
1258 EXECUTE_IF_SET_IN_BITMAP (&tmp
, 0, uid
, bi
)
1260 struct df_insn_info
*insn_info
= DF_INSN_UID_SAFE_GET (uid
);
1262 df_insn_rescan (insn_info
->insn
);
1265 bitmap_copy (&tmp
, &df
->insns_to_notes_rescan
);
1266 EXECUTE_IF_SET_IN_BITMAP (&tmp
, 0, uid
, bi
)
1268 struct df_insn_info
*insn_info
= DF_INSN_UID_SAFE_GET (uid
);
1270 df_notes_rescan (insn_info
->insn
);
1274 fprintf (dump_file
, "ending the processing of deferred insns\n");
1276 bitmap_clear (&tmp
);
1277 bitmap_clear (&df
->insns_to_delete
);
1278 bitmap_clear (&df
->insns_to_rescan
);
1279 bitmap_clear (&df
->insns_to_notes_rescan
);
1282 df_set_flags (DF_NO_INSN_RESCAN
);
1283 if (defer_insn_rescan
)
1284 df_set_flags (DF_DEFER_INSN_RESCAN
);
1286 /* If someone changed regs_ever_live during this pass, fix up the
1287 entry and exit blocks. */
1288 if (df
->redo_entry_and_exit
)
1290 df_update_entry_exit_and_calls ();
1291 df
->redo_entry_and_exit
= false;
1296 /* Count the number of refs. Include the defs if INCLUDE_DEFS. Include
1297 the uses if INCLUDE_USES. Include the eq_uses if
1301 df_count_refs (bool include_defs
, bool include_uses
,
1302 bool include_eq_uses
)
1306 unsigned int m
= df
->regs_inited
;
1308 for (regno
= 0; regno
< m
; regno
++)
1311 size
+= DF_REG_DEF_COUNT (regno
);
1313 size
+= DF_REG_USE_COUNT (regno
);
1314 if (include_eq_uses
)
1315 size
+= DF_REG_EQ_USE_COUNT (regno
);
1321 /* Take build ref table for either the uses or defs from the reg-use
1322 or reg-def chains. This version processes the refs in reg order
1323 which is likely to be best if processing the whole function. */
1326 df_reorganize_refs_by_reg_by_reg (struct df_ref_info
*ref_info
,
1329 bool include_eq_uses
)
1331 unsigned int m
= df
->regs_inited
;
1333 unsigned int offset
= 0;
1336 if (df
->changeable_flags
& DF_NO_HARD_REGS
)
1338 start
= FIRST_PSEUDO_REGISTER
;
1339 memset (ref_info
->begin
, 0, sizeof (int) * FIRST_PSEUDO_REGISTER
);
1340 memset (ref_info
->count
, 0, sizeof (int) * FIRST_PSEUDO_REGISTER
);
1345 ref_info
->total_size
1346 = df_count_refs (include_defs
, include_uses
, include_eq_uses
);
1348 df_check_and_grow_ref_info (ref_info
, 1);
1350 for (regno
= start
; regno
< m
; regno
++)
1353 ref_info
->begin
[regno
] = offset
;
1356 df_ref ref
= DF_REG_DEF_CHAIN (regno
);
1359 ref_info
->refs
[offset
] = ref
;
1360 DF_REF_ID (ref
) = offset
++;
1362 ref
= DF_REF_NEXT_REG (ref
);
1363 gcc_checking_assert (offset
< ref_info
->refs_size
);
1368 df_ref ref
= DF_REG_USE_CHAIN (regno
);
1371 ref_info
->refs
[offset
] = ref
;
1372 DF_REF_ID (ref
) = offset
++;
1374 ref
= DF_REF_NEXT_REG (ref
);
1375 gcc_checking_assert (offset
< ref_info
->refs_size
);
1378 if (include_eq_uses
)
1380 df_ref ref
= DF_REG_EQ_USE_CHAIN (regno
);
1383 ref_info
->refs
[offset
] = ref
;
1384 DF_REF_ID (ref
) = offset
++;
1386 ref
= DF_REF_NEXT_REG (ref
);
1387 gcc_checking_assert (offset
< ref_info
->refs_size
);
1390 ref_info
->count
[regno
] = count
;
1393 /* The bitmap size is not decremented when refs are deleted. So
1394 reset it now that we have squished out all of the empty
1396 ref_info
->table_size
= offset
;
1400 /* Take build ref table for either the uses or defs from the reg-use
1401 or reg-def chains. This version processes the refs in insn order
1402 which is likely to be best if processing some segment of the
1406 df_reorganize_refs_by_reg_by_insn (struct df_ref_info
*ref_info
,
1409 bool include_eq_uses
)
1412 unsigned int bb_index
;
1413 unsigned int m
= df
->regs_inited
;
1414 unsigned int offset
= 0;
1417 = (df
->changeable_flags
& DF_NO_HARD_REGS
) ? FIRST_PSEUDO_REGISTER
: 0;
1419 memset (ref_info
->begin
, 0, sizeof (int) * df
->regs_inited
);
1420 memset (ref_info
->count
, 0, sizeof (int) * df
->regs_inited
);
1422 ref_info
->total_size
= df_count_refs (include_defs
, include_uses
, include_eq_uses
);
1423 df_check_and_grow_ref_info (ref_info
, 1);
1425 EXECUTE_IF_SET_IN_BITMAP (df
->blocks_to_analyze
, 0, bb_index
, bi
)
1427 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, bb_index
);
1432 FOR_EACH_ARTIFICIAL_DEF (def
, bb_index
)
1434 unsigned int regno
= DF_REF_REGNO (def
);
1435 ref_info
->count
[regno
]++;
1438 FOR_EACH_ARTIFICIAL_USE (use
, bb_index
)
1440 unsigned int regno
= DF_REF_REGNO (use
);
1441 ref_info
->count
[regno
]++;
1444 FOR_BB_INSNS (bb
, insn
)
1448 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
1451 FOR_EACH_INSN_INFO_DEF (def
, insn_info
)
1453 unsigned int regno
= DF_REF_REGNO (def
);
1454 ref_info
->count
[regno
]++;
1457 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
1459 unsigned int regno
= DF_REF_REGNO (use
);
1460 ref_info
->count
[regno
]++;
1462 if (include_eq_uses
)
1463 FOR_EACH_INSN_INFO_EQ_USE (use
, insn_info
)
1465 unsigned int regno
= DF_REF_REGNO (use
);
1466 ref_info
->count
[regno
]++;
1472 for (r
= start
; r
< m
; r
++)
1474 ref_info
->begin
[r
] = offset
;
1475 offset
+= ref_info
->count
[r
];
1476 ref_info
->count
[r
] = 0;
1479 EXECUTE_IF_SET_IN_BITMAP (df
->blocks_to_analyze
, 0, bb_index
, bi
)
1481 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, bb_index
);
1486 FOR_EACH_ARTIFICIAL_DEF (def
, bb_index
)
1488 unsigned int regno
= DF_REF_REGNO (def
);
1492 = ref_info
->begin
[regno
] + ref_info
->count
[regno
]++;
1493 DF_REF_ID (def
) = id
;
1494 ref_info
->refs
[id
] = def
;
1498 FOR_EACH_ARTIFICIAL_USE (use
, bb_index
)
1500 unsigned int regno
= DF_REF_REGNO (def
);
1504 = ref_info
->begin
[regno
] + ref_info
->count
[regno
]++;
1505 DF_REF_ID (use
) = id
;
1506 ref_info
->refs
[id
] = use
;
1510 FOR_BB_INSNS (bb
, insn
)
1514 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
1517 FOR_EACH_INSN_INFO_DEF (def
, insn_info
)
1519 unsigned int regno
= DF_REF_REGNO (def
);
1523 = ref_info
->begin
[regno
] + ref_info
->count
[regno
]++;
1524 DF_REF_ID (def
) = id
;
1525 ref_info
->refs
[id
] = def
;
1529 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
1531 unsigned int regno
= DF_REF_REGNO (use
);
1535 = ref_info
->begin
[regno
] + ref_info
->count
[regno
]++;
1536 DF_REF_ID (use
) = id
;
1537 ref_info
->refs
[id
] = use
;
1540 if (include_eq_uses
)
1541 FOR_EACH_INSN_INFO_EQ_USE (use
, insn_info
)
1543 unsigned int regno
= DF_REF_REGNO (use
);
1547 = ref_info
->begin
[regno
] + ref_info
->count
[regno
]++;
1548 DF_REF_ID (use
) = id
;
1549 ref_info
->refs
[id
] = use
;
1556 /* The bitmap size is not decremented when refs are deleted. So
1557 reset it now that we have squished out all of the empty
1560 ref_info
->table_size
= offset
;
1563 /* Take build ref table for either the uses or defs from the reg-use
1564 or reg-def chains. */
1567 df_reorganize_refs_by_reg (struct df_ref_info
*ref_info
,
1570 bool include_eq_uses
)
1572 if (df
->analyze_subset
)
1573 df_reorganize_refs_by_reg_by_insn (ref_info
, include_defs
,
1574 include_uses
, include_eq_uses
);
1576 df_reorganize_refs_by_reg_by_reg (ref_info
, include_defs
,
1577 include_uses
, include_eq_uses
);
1581 /* Add the refs in REF_VEC to the table in REF_INFO starting at OFFSET. */
1583 df_add_refs_to_table (unsigned int offset
,
1584 struct df_ref_info
*ref_info
,
1587 for (; ref
; ref
= DF_REF_NEXT_LOC (ref
))
1588 if (!(df
->changeable_flags
& DF_NO_HARD_REGS
)
1589 || (DF_REF_REGNO (ref
) >= FIRST_PSEUDO_REGISTER
))
1591 ref_info
->refs
[offset
] = ref
;
1592 DF_REF_ID (ref
) = offset
++;
1598 /* Count the number of refs in all of the insns of BB. Include the
1599 defs if INCLUDE_DEFS. Include the uses if INCLUDE_USES. Include the
1600 eq_uses if INCLUDE_EQ_USES. */
1603 df_reorganize_refs_by_insn_bb (basic_block bb
, unsigned int offset
,
1604 struct df_ref_info
*ref_info
,
1605 bool include_defs
, bool include_uses
,
1606 bool include_eq_uses
)
1611 offset
= df_add_refs_to_table (offset
, ref_info
,
1612 df_get_artificial_defs (bb
->index
));
1614 offset
= df_add_refs_to_table (offset
, ref_info
,
1615 df_get_artificial_uses (bb
->index
));
1617 FOR_BB_INSNS (bb
, insn
)
1620 unsigned int uid
= INSN_UID (insn
);
1622 offset
= df_add_refs_to_table (offset
, ref_info
,
1623 DF_INSN_UID_DEFS (uid
));
1625 offset
= df_add_refs_to_table (offset
, ref_info
,
1626 DF_INSN_UID_USES (uid
));
1627 if (include_eq_uses
)
1628 offset
= df_add_refs_to_table (offset
, ref_info
,
1629 DF_INSN_UID_EQ_USES (uid
));
1635 /* Organize the refs by insn into the table in REF_INFO. If
1636 blocks_to_analyze is defined, use that set, otherwise the entire
1637 program. Include the defs if INCLUDE_DEFS. Include the uses if
1638 INCLUDE_USES. Include the eq_uses if INCLUDE_EQ_USES. */
1641 df_reorganize_refs_by_insn (struct df_ref_info
*ref_info
,
1642 bool include_defs
, bool include_uses
,
1643 bool include_eq_uses
)
1646 unsigned int offset
= 0;
1648 ref_info
->total_size
= df_count_refs (include_defs
, include_uses
, include_eq_uses
);
1649 df_check_and_grow_ref_info (ref_info
, 1);
1650 if (df
->blocks_to_analyze
)
1655 EXECUTE_IF_SET_IN_BITMAP (df
->blocks_to_analyze
, 0, index
, bi
)
1657 offset
= df_reorganize_refs_by_insn_bb (BASIC_BLOCK_FOR_FN (cfun
,
1660 include_defs
, include_uses
,
1664 ref_info
->table_size
= offset
;
1668 FOR_ALL_BB_FN (bb
, cfun
)
1669 offset
= df_reorganize_refs_by_insn_bb (bb
, offset
, ref_info
,
1670 include_defs
, include_uses
,
1672 ref_info
->table_size
= offset
;
1677 /* If the use refs in DF are not organized, reorganize them. */
1680 df_maybe_reorganize_use_refs (enum df_ref_order order
)
1682 if (order
== df
->use_info
.ref_order
)
1687 case DF_REF_ORDER_BY_REG
:
1688 df_reorganize_refs_by_reg (&df
->use_info
, false, true, false);
1691 case DF_REF_ORDER_BY_REG_WITH_NOTES
:
1692 df_reorganize_refs_by_reg (&df
->use_info
, false, true, true);
1695 case DF_REF_ORDER_BY_INSN
:
1696 df_reorganize_refs_by_insn (&df
->use_info
, false, true, false);
1699 case DF_REF_ORDER_BY_INSN_WITH_NOTES
:
1700 df_reorganize_refs_by_insn (&df
->use_info
, false, true, true);
1703 case DF_REF_ORDER_NO_TABLE
:
1704 free (df
->use_info
.refs
);
1705 df
->use_info
.refs
= NULL
;
1706 df
->use_info
.refs_size
= 0;
1709 case DF_REF_ORDER_UNORDERED
:
1710 case DF_REF_ORDER_UNORDERED_WITH_NOTES
:
1715 df
->use_info
.ref_order
= order
;
1719 /* If the def refs in DF are not organized, reorganize them. */
1722 df_maybe_reorganize_def_refs (enum df_ref_order order
)
1724 if (order
== df
->def_info
.ref_order
)
1729 case DF_REF_ORDER_BY_REG
:
1730 df_reorganize_refs_by_reg (&df
->def_info
, true, false, false);
1733 case DF_REF_ORDER_BY_INSN
:
1734 df_reorganize_refs_by_insn (&df
->def_info
, true, false, false);
1737 case DF_REF_ORDER_NO_TABLE
:
1738 free (df
->def_info
.refs
);
1739 df
->def_info
.refs
= NULL
;
1740 df
->def_info
.refs_size
= 0;
1743 case DF_REF_ORDER_BY_INSN_WITH_NOTES
:
1744 case DF_REF_ORDER_BY_REG_WITH_NOTES
:
1745 case DF_REF_ORDER_UNORDERED
:
1746 case DF_REF_ORDER_UNORDERED_WITH_NOTES
:
1751 df
->def_info
.ref_order
= order
;
1755 /* Change all of the basic block references in INSN to use the insn's
1756 current basic block. This function is called from routines that move
1757 instructions from one block to another. */
1760 df_insn_change_bb (rtx_insn
*insn
, basic_block new_bb
)
1762 basic_block old_bb
= BLOCK_FOR_INSN (insn
);
1763 struct df_insn_info
*insn_info
;
1764 unsigned int uid
= INSN_UID (insn
);
1766 if (old_bb
== new_bb
)
1769 set_block_for_insn (insn
, new_bb
);
1775 fprintf (dump_file
, "changing bb of uid %d\n", uid
);
1777 insn_info
= DF_INSN_UID_SAFE_GET (uid
);
1778 if (insn_info
== NULL
)
1781 fprintf (dump_file
, " unscanned insn\n");
1782 df_insn_rescan (insn
);
1789 df_set_bb_dirty (new_bb
);
1793 fprintf (dump_file
, " from %d to %d\n",
1794 old_bb
->index
, new_bb
->index
);
1795 df_set_bb_dirty (old_bb
);
1799 fprintf (dump_file
, " to %d\n", new_bb
->index
);
1803 /* Helper function for df_ref_change_reg_with_loc. */
1806 df_ref_change_reg_with_loc_1 (struct df_reg_info
*old_df
,
1807 struct df_reg_info
*new_df
,
1808 unsigned int new_regno
, rtx loc
)
1810 df_ref the_ref
= old_df
->reg_chain
;
1814 if ((!DF_REF_IS_ARTIFICIAL (the_ref
))
1815 && DF_REF_LOC (the_ref
)
1816 && (*DF_REF_LOC (the_ref
) == loc
))
1818 df_ref next_ref
= DF_REF_NEXT_REG (the_ref
);
1819 df_ref prev_ref
= DF_REF_PREV_REG (the_ref
);
1821 struct df_insn_info
*insn_info
= DF_REF_INSN_INFO (the_ref
);
1823 DF_REF_REGNO (the_ref
) = new_regno
;
1824 DF_REF_REG (the_ref
) = regno_reg_rtx
[new_regno
];
1826 /* Pull the_ref out of the old regno chain. */
1828 DF_REF_NEXT_REG (prev_ref
) = next_ref
;
1830 old_df
->reg_chain
= next_ref
;
1832 DF_REF_PREV_REG (next_ref
) = prev_ref
;
1835 /* Put the ref into the new regno chain. */
1836 DF_REF_PREV_REG (the_ref
) = NULL
;
1837 DF_REF_NEXT_REG (the_ref
) = new_df
->reg_chain
;
1838 if (new_df
->reg_chain
)
1839 DF_REF_PREV_REG (new_df
->reg_chain
) = the_ref
;
1840 new_df
->reg_chain
= the_ref
;
1842 if (DF_REF_BB (the_ref
))
1843 df_set_bb_dirty (DF_REF_BB (the_ref
));
1845 /* Need to sort the record again that the ref was in because
1846 the regno is a sorting key. First, find the right
1848 if (DF_REF_REG_DEF_P (the_ref
))
1849 ref_ptr
= &insn_info
->defs
;
1850 else if (DF_REF_FLAGS (the_ref
) & DF_REF_IN_NOTE
)
1851 ref_ptr
= &insn_info
->eq_uses
;
1853 ref_ptr
= &insn_info
->uses
;
1855 fprintf (dump_file
, "changing reg in insn %d\n",
1856 DF_REF_INSN_UID (the_ref
));
1858 /* Stop if we find the current reference or where the reference
1860 while (*ref_ptr
!= the_ref
&& df_ref_compare (*ref_ptr
, the_ref
) < 0)
1861 ref_ptr
= &DF_REF_NEXT_LOC (*ref_ptr
);
1862 if (*ref_ptr
!= the_ref
)
1864 /* The reference needs to be promoted up the list. */
1865 df_ref next
= DF_REF_NEXT_LOC (the_ref
);
1866 DF_REF_NEXT_LOC (the_ref
) = *ref_ptr
;
1869 ref_ptr
= &DF_REF_NEXT_LOC (*ref_ptr
);
1870 while (*ref_ptr
!= the_ref
);
1873 else if (DF_REF_NEXT_LOC (the_ref
)
1874 && df_ref_compare (the_ref
, DF_REF_NEXT_LOC (the_ref
)) > 0)
1876 /* The reference needs to be demoted down the list. */
1877 *ref_ptr
= DF_REF_NEXT_LOC (the_ref
);
1879 ref_ptr
= &DF_REF_NEXT_LOC (*ref_ptr
);
1880 while (*ref_ptr
&& df_ref_compare (the_ref
, *ref_ptr
) > 0);
1881 DF_REF_NEXT_LOC (the_ref
) = *ref_ptr
;
1888 the_ref
= DF_REF_NEXT_REG (the_ref
);
1893 /* Change the regno of register LOC to NEW_REGNO and update the df
1894 information accordingly. Refs that do not match LOC are not changed
1895 which means that artificial refs are not changed since they have no loc.
1896 This call is to support the SET_REGNO macro. */
1899 df_ref_change_reg_with_loc (rtx loc
, unsigned int new_regno
)
1901 unsigned int old_regno
= REGNO (loc
);
1902 if (old_regno
== new_regno
)
1907 df_grow_reg_info ();
1909 df_ref_change_reg_with_loc_1 (DF_REG_DEF_GET (old_regno
),
1910 DF_REG_DEF_GET (new_regno
),
1912 df_ref_change_reg_with_loc_1 (DF_REG_USE_GET (old_regno
),
1913 DF_REG_USE_GET (new_regno
),
1915 df_ref_change_reg_with_loc_1 (DF_REG_EQ_USE_GET (old_regno
),
1916 DF_REG_EQ_USE_GET (new_regno
),
1919 set_mode_and_regno (loc
, GET_MODE (loc
), new_regno
);
1923 /* Delete the mw_hardregs that point into the eq_notes. */
1926 df_mw_hardreg_chain_delete_eq_uses (struct df_insn_info
*insn_info
)
1928 struct df_mw_hardreg
**mw_ptr
= &insn_info
->mw_hardregs
;
1929 struct df_scan_problem_data
*problem_data
1930 = (struct df_scan_problem_data
*) df_scan
->problem_data
;
1934 df_mw_hardreg
*mw
= *mw_ptr
;
1935 if (mw
->flags
& DF_REF_IN_NOTE
)
1937 *mw_ptr
= DF_MWS_NEXT (mw
);
1938 problem_data
->mw_reg_pool
->remove (mw
);
1941 mw_ptr
= &DF_MWS_NEXT (mw
);
1946 /* Rescan only the REG_EQUIV/REG_EQUAL notes part of INSN. */
1949 df_notes_rescan (rtx_insn
*insn
)
1951 struct df_insn_info
*insn_info
;
1952 unsigned int uid
= INSN_UID (insn
);
1957 /* The client has disabled rescanning and plans to do it itself. */
1958 if (df
->changeable_flags
& DF_NO_INSN_RESCAN
)
1961 /* Do nothing if the insn hasn't been emitted yet. */
1962 if (!BLOCK_FOR_INSN (insn
))
1965 df_grow_bb_info (df_scan
);
1966 df_grow_reg_info ();
1968 insn_info
= DF_INSN_UID_SAFE_GET (INSN_UID (insn
));
1970 /* The client has deferred rescanning. */
1971 if (df
->changeable_flags
& DF_DEFER_INSN_RESCAN
)
1975 insn_info
= df_insn_create_insn_record (insn
);
1976 insn_info
->defs
= 0;
1977 insn_info
->uses
= 0;
1978 insn_info
->eq_uses
= 0;
1979 insn_info
->mw_hardregs
= 0;
1982 bitmap_clear_bit (&df
->insns_to_delete
, uid
);
1983 /* If the insn is set to be rescanned, it does not need to also
1984 be notes rescanned. */
1985 if (!bitmap_bit_p (&df
->insns_to_rescan
, uid
))
1986 bitmap_set_bit (&df
->insns_to_notes_rescan
, INSN_UID (insn
));
1990 bitmap_clear_bit (&df
->insns_to_delete
, uid
);
1991 bitmap_clear_bit (&df
->insns_to_notes_rescan
, uid
);
1995 basic_block bb
= BLOCK_FOR_INSN (insn
);
1997 struct df_collection_rec collection_rec
;
2000 df_mw_hardreg_chain_delete_eq_uses (insn_info
);
2001 df_ref_chain_delete (insn_info
->eq_uses
);
2002 insn_info
->eq_uses
= NULL
;
2004 /* Process REG_EQUIV/REG_EQUAL notes */
2005 for (note
= REG_NOTES (insn
); note
;
2006 note
= XEXP (note
, 1))
2008 switch (REG_NOTE_KIND (note
))
2012 df_uses_record (&collection_rec
,
2013 &XEXP (note
, 0), DF_REF_REG_USE
,
2014 bb
, insn_info
, DF_REF_IN_NOTE
);
2020 /* Find some place to put any new mw_hardregs. */
2021 df_canonize_collection_rec (&collection_rec
);
2022 struct df_mw_hardreg
**mw_ptr
= &insn_info
->mw_hardregs
, *mw
;
2023 FOR_EACH_VEC_ELT (collection_rec
.mw_vec
, i
, mw
)
2025 while (*mw_ptr
&& df_mw_compare (*mw_ptr
, mw
) < 0)
2026 mw_ptr
= &DF_MWS_NEXT (*mw_ptr
);
2027 DF_MWS_NEXT (mw
) = *mw_ptr
;
2029 mw_ptr
= &DF_MWS_NEXT (mw
);
2031 df_refs_add_to_chains (&collection_rec
, bb
, insn
, copy_eq_uses
);
2034 df_insn_rescan (insn
);
2039 /*----------------------------------------------------------------------------
2040 Hard core instruction scanning code. No external interfaces here,
2041 just a lot of routines that look inside insns.
2042 ----------------------------------------------------------------------------*/
2045 /* Return true if the contents of two df_ref's are identical.
2046 It ignores DF_REF_MARKER. */
2049 df_ref_equal_p (df_ref ref1
, df_ref ref2
)
2057 if (DF_REF_CLASS (ref1
) != DF_REF_CLASS (ref2
)
2058 || DF_REF_REGNO (ref1
) != DF_REF_REGNO (ref2
)
2059 || DF_REF_REG (ref1
) != DF_REF_REG (ref2
)
2060 || DF_REF_TYPE (ref1
) != DF_REF_TYPE (ref2
)
2061 || ((DF_REF_FLAGS (ref1
) & ~(DF_REF_REG_MARKER
+ DF_REF_MW_HARDREG
))
2062 != (DF_REF_FLAGS (ref2
) & ~(DF_REF_REG_MARKER
+ DF_REF_MW_HARDREG
)))
2063 || DF_REF_BB (ref1
) != DF_REF_BB (ref2
)
2064 || DF_REF_INSN_INFO (ref1
) != DF_REF_INSN_INFO (ref2
))
2067 switch (DF_REF_CLASS (ref1
))
2069 case DF_REF_ARTIFICIAL
:
2073 case DF_REF_REGULAR
:
2074 return DF_REF_LOC (ref1
) == DF_REF_LOC (ref2
);
2083 /* Compare REF1 and REF2 for sorting. This is only called from places
2084 where all of the refs are of the same type, in the same insn, and
2085 have the same bb. So these fields are not checked. */
2088 df_ref_compare (df_ref ref1
, df_ref ref2
)
2090 if (DF_REF_CLASS (ref1
) != DF_REF_CLASS (ref2
))
2091 return (int)DF_REF_CLASS (ref1
) - (int)DF_REF_CLASS (ref2
);
2093 if (DF_REF_REGNO (ref1
) != DF_REF_REGNO (ref2
))
2094 return (int)DF_REF_REGNO (ref1
) - (int)DF_REF_REGNO (ref2
);
2096 if (DF_REF_TYPE (ref1
) != DF_REF_TYPE (ref2
))
2097 return (int)DF_REF_TYPE (ref1
) - (int)DF_REF_TYPE (ref2
);
2099 if (DF_REF_REG (ref1
) != DF_REF_REG (ref2
))
2100 return (int)DF_REF_ORDER (ref1
) - (int)DF_REF_ORDER (ref2
);
2102 /* Cannot look at the LOC field on artificial refs. */
2103 if (DF_REF_CLASS (ref1
) != DF_REF_ARTIFICIAL
2104 && DF_REF_LOC (ref1
) != DF_REF_LOC (ref2
))
2105 return (int)DF_REF_ORDER (ref1
) - (int)DF_REF_ORDER (ref2
);
2107 if (DF_REF_FLAGS (ref1
) != DF_REF_FLAGS (ref2
))
2109 /* If two refs are identical except that one of them has is from
2110 a mw and one is not, we need to have the one with the mw
2112 if (DF_REF_FLAGS_IS_SET (ref1
, DF_REF_MW_HARDREG
) ==
2113 DF_REF_FLAGS_IS_SET (ref2
, DF_REF_MW_HARDREG
))
2114 return DF_REF_FLAGS (ref1
) - DF_REF_FLAGS (ref2
);
2115 else if (DF_REF_FLAGS_IS_SET (ref1
, DF_REF_MW_HARDREG
))
2121 return (int)DF_REF_ORDER (ref1
) - (int)DF_REF_ORDER (ref2
);
2124 /* Like df_ref_compare, but compare two df_ref* pointers R1 and R2. */
2127 df_ref_ptr_compare (const void *r1
, const void *r2
)
2129 return df_ref_compare (*(const df_ref
*) r1
, *(const df_ref
*) r2
);
2132 /* Sort and compress a set of refs. */
2135 df_sort_and_compress_refs (vec
<df_ref
, va_heap
> *ref_vec
)
2139 unsigned int dist
= 0;
2141 count
= ref_vec
->length ();
2143 /* If there are 1 or 0 elements, there is nothing to do. */
2146 else if (count
== 2)
2148 df_ref r0
= (*ref_vec
)[0];
2149 df_ref r1
= (*ref_vec
)[1];
2150 if (df_ref_compare (r0
, r1
) > 0)
2151 std::swap ((*ref_vec
)[0], (*ref_vec
)[1]);
2155 for (i
= 0; i
< count
- 1; i
++)
2157 df_ref r0
= (*ref_vec
)[i
];
2158 df_ref r1
= (*ref_vec
)[i
+ 1];
2159 if (df_ref_compare (r0
, r1
) >= 0)
2162 /* If the array is already strictly ordered,
2163 which is the most common case for large COUNT case
2164 (which happens for CALL INSNs),
2165 no need to sort and filter out duplicate.
2166 Simply return the count.
2167 Make sure DF_GET_ADD_REFS adds refs in the increasing order
2168 of DF_REF_COMPARE. */
2171 ref_vec
->qsort (df_ref_ptr_compare
);
2174 for (i
=0; i
<count
-dist
; i
++)
2176 /* Find the next ref that is not equal to the current ref. */
2177 while (i
+ dist
+ 1 < count
2178 && df_ref_equal_p ((*ref_vec
)[i
],
2179 (*ref_vec
)[i
+ dist
+ 1]))
2181 df_free_ref ((*ref_vec
)[i
+ dist
+ 1]);
2184 /* Copy it down to the next position. */
2185 if (dist
&& i
+ dist
+ 1 < count
)
2186 (*ref_vec
)[i
+ 1] = (*ref_vec
)[i
+ dist
+ 1];
2190 ref_vec
->truncate (count
);
2194 /* Return true if the contents of two df_ref's are identical.
2195 It ignores DF_REF_MARKER. */
2198 df_mw_equal_p (struct df_mw_hardreg
*mw1
, struct df_mw_hardreg
*mw2
)
2202 return (mw1
== mw2
) ||
2203 (mw1
->mw_reg
== mw2
->mw_reg
2204 && mw1
->type
== mw2
->type
2205 && mw1
->flags
== mw2
->flags
2206 && mw1
->start_regno
== mw2
->start_regno
2207 && mw1
->end_regno
== mw2
->end_regno
);
2211 /* Compare MW1 and MW2 for sorting. */
2214 df_mw_compare (const df_mw_hardreg
*mw1
, const df_mw_hardreg
*mw2
)
2216 if (mw1
->type
!= mw2
->type
)
2217 return mw1
->type
- mw2
->type
;
2219 if (mw1
->flags
!= mw2
->flags
)
2220 return mw1
->flags
- mw2
->flags
;
2222 if (mw1
->start_regno
!= mw2
->start_regno
)
2223 return mw1
->start_regno
- mw2
->start_regno
;
2225 if (mw1
->end_regno
!= mw2
->end_regno
)
2226 return mw1
->end_regno
- mw2
->end_regno
;
2228 if (mw1
->mw_reg
!= mw2
->mw_reg
)
2229 return mw1
->mw_order
- mw2
->mw_order
;
2234 /* Like df_mw_compare, but compare two df_mw_hardreg** pointers R1 and R2. */
2237 df_mw_ptr_compare (const void *m1
, const void *m2
)
2239 return df_mw_compare (*(const df_mw_hardreg
*const *) m1
,
2240 *(const df_mw_hardreg
*const *) m2
);
2243 /* Sort and compress a set of refs. */
2246 df_sort_and_compress_mws (vec
<df_mw_hardreg_ptr
, va_heap
> *mw_vec
)
2249 struct df_scan_problem_data
*problem_data
2250 = (struct df_scan_problem_data
*) df_scan
->problem_data
;
2252 unsigned int dist
= 0;
2254 count
= mw_vec
->length ();
2257 else if (count
== 2)
2259 struct df_mw_hardreg
*m0
= (*mw_vec
)[0];
2260 struct df_mw_hardreg
*m1
= (*mw_vec
)[1];
2261 if (df_mw_compare (m0
, m1
) > 0)
2263 struct df_mw_hardreg
*tmp
= (*mw_vec
)[0];
2264 (*mw_vec
)[0] = (*mw_vec
)[1];
2269 mw_vec
->qsort (df_mw_ptr_compare
);
2271 for (i
=0; i
<count
-dist
; i
++)
2273 /* Find the next ref that is not equal to the current ref. */
2274 while (i
+ dist
+ 1 < count
2275 && df_mw_equal_p ((*mw_vec
)[i
], (*mw_vec
)[i
+ dist
+ 1]))
2277 problem_data
->mw_reg_pool
->remove ((*mw_vec
)[i
+ dist
+ 1]);
2280 /* Copy it down to the next position. */
2281 if (dist
&& i
+ dist
+ 1 < count
)
2282 (*mw_vec
)[i
+ 1] = (*mw_vec
)[i
+ dist
+ 1];
2286 mw_vec
->truncate (count
);
2290 /* Sort and remove duplicates from the COLLECTION_REC. */
2293 df_canonize_collection_rec (struct df_collection_rec
*collection_rec
)
2295 df_sort_and_compress_refs (&collection_rec
->def_vec
);
2296 df_sort_and_compress_refs (&collection_rec
->use_vec
);
2297 df_sort_and_compress_refs (&collection_rec
->eq_use_vec
);
2298 df_sort_and_compress_mws (&collection_rec
->mw_vec
);
2302 /* Add the new df_ref to appropriate reg_info/ref_info chains. */
2305 df_install_ref (df_ref this_ref
,
2306 struct df_reg_info
*reg_info
,
2307 struct df_ref_info
*ref_info
,
2310 unsigned int regno
= DF_REF_REGNO (this_ref
);
2311 /* Add the ref to the reg_{def,use,eq_use} chain. */
2312 df_ref head
= reg_info
->reg_chain
;
2314 reg_info
->reg_chain
= this_ref
;
2317 if (DF_REF_FLAGS_IS_SET (this_ref
, DF_HARD_REG_LIVE
))
2319 gcc_assert (regno
< FIRST_PSEUDO_REGISTER
);
2320 df
->hard_regs_live_count
[regno
]++;
2323 gcc_checking_assert (DF_REF_NEXT_REG (this_ref
) == NULL
2324 && DF_REF_PREV_REG (this_ref
) == NULL
);
2326 DF_REF_NEXT_REG (this_ref
) = head
;
2328 /* We cannot actually link to the head of the chain. */
2329 DF_REF_PREV_REG (this_ref
) = NULL
;
2332 DF_REF_PREV_REG (head
) = this_ref
;
2336 gcc_assert (ref_info
->ref_order
!= DF_REF_ORDER_NO_TABLE
);
2337 df_check_and_grow_ref_info (ref_info
, 1);
2338 DF_REF_ID (this_ref
) = ref_info
->table_size
;
2339 /* Add the ref to the big array of defs. */
2340 ref_info
->refs
[ref_info
->table_size
] = this_ref
;
2341 ref_info
->table_size
++;
2344 DF_REF_ID (this_ref
) = -1;
2346 ref_info
->total_size
++;
2350 /* This function takes one of the groups of refs (defs, uses or
2351 eq_uses) and installs the entire group into the insn. It also adds
2352 each of these refs into the appropriate chains. */
2355 df_install_refs (basic_block bb
,
2356 const vec
<df_ref
, va_heap
> *old_vec
,
2357 struct df_reg_info
**reg_info
,
2358 struct df_ref_info
*ref_info
,
2361 unsigned int count
= old_vec
->length ();
2368 switch (ref_info
->ref_order
)
2370 case DF_REF_ORDER_UNORDERED_WITH_NOTES
:
2371 case DF_REF_ORDER_BY_REG_WITH_NOTES
:
2372 case DF_REF_ORDER_BY_INSN_WITH_NOTES
:
2373 ref_info
->ref_order
= DF_REF_ORDER_UNORDERED_WITH_NOTES
;
2374 add_to_table
= true;
2376 case DF_REF_ORDER_UNORDERED
:
2377 case DF_REF_ORDER_BY_REG
:
2378 case DF_REF_ORDER_BY_INSN
:
2379 ref_info
->ref_order
= DF_REF_ORDER_UNORDERED
;
2380 add_to_table
= !is_notes
;
2383 add_to_table
= false;
2387 /* Do not add if ref is not in the right blocks. */
2388 if (add_to_table
&& df
->analyze_subset
)
2389 add_to_table
= bitmap_bit_p (df
->blocks_to_analyze
, bb
->index
);
2391 FOR_EACH_VEC_ELT (*old_vec
, ix
, this_ref
)
2393 DF_REF_NEXT_LOC (this_ref
) = (ix
+ 1 < old_vec
->length ()
2394 ? (*old_vec
)[ix
+ 1]
2396 df_install_ref (this_ref
, reg_info
[DF_REF_REGNO (this_ref
)],
2397 ref_info
, add_to_table
);
2399 return (*old_vec
)[0];
2406 /* This function takes the mws installs the entire group into the
2409 static struct df_mw_hardreg
*
2410 df_install_mws (const vec
<df_mw_hardreg_ptr
, va_heap
> *old_vec
)
2412 unsigned int count
= old_vec
->length ();
2415 for (unsigned int i
= 0; i
< count
- 1; i
++)
2416 DF_MWS_NEXT ((*old_vec
)[i
]) = (*old_vec
)[i
+ 1];
2417 DF_MWS_NEXT ((*old_vec
)[count
- 1]) = 0;
2418 return (*old_vec
)[0];
2425 /* Add a chain of df_refs to appropriate ref chain/reg_info/ref_info
2426 chains and update other necessary information. */
2429 df_refs_add_to_chains (struct df_collection_rec
*collection_rec
,
2430 basic_block bb
, rtx_insn
*insn
, unsigned int flags
)
2434 struct df_insn_info
*insn_rec
= DF_INSN_INFO_GET (insn
);
2435 /* If there is a vector in the collection rec, add it to the
2436 insn. A null rec is a signal that the caller will handle the
2438 if (flags
& copy_defs
)
2440 gcc_checking_assert (!insn_rec
->defs
);
2442 = df_install_refs (bb
, &collection_rec
->def_vec
,
2444 &df
->def_info
, false);
2446 if (flags
& copy_uses
)
2448 gcc_checking_assert (!insn_rec
->uses
);
2450 = df_install_refs (bb
, &collection_rec
->use_vec
,
2452 &df
->use_info
, false);
2454 if (flags
& copy_eq_uses
)
2456 gcc_checking_assert (!insn_rec
->eq_uses
);
2458 = df_install_refs (bb
, &collection_rec
->eq_use_vec
,
2460 &df
->use_info
, true);
2462 if (flags
& copy_mw
)
2464 gcc_checking_assert (!insn_rec
->mw_hardregs
);
2465 insn_rec
->mw_hardregs
2466 = df_install_mws (&collection_rec
->mw_vec
);
2471 struct df_scan_bb_info
*bb_info
= df_scan_get_bb_info (bb
->index
);
2473 gcc_checking_assert (!bb_info
->artificial_defs
);
2474 bb_info
->artificial_defs
2475 = df_install_refs (bb
, &collection_rec
->def_vec
,
2477 &df
->def_info
, false);
2478 gcc_checking_assert (!bb_info
->artificial_uses
);
2479 bb_info
->artificial_uses
2480 = df_install_refs (bb
, &collection_rec
->use_vec
,
2482 &df
->use_info
, false);
2487 /* Allocate a ref and initialize its fields. */
2490 df_ref_create_structure (enum df_ref_class cl
,
2491 struct df_collection_rec
*collection_rec
,
2493 basic_block bb
, struct df_insn_info
*info
,
2494 enum df_ref_type ref_type
,
2497 df_ref this_ref
= NULL
;
2498 int regno
= REGNO (GET_CODE (reg
) == SUBREG
? SUBREG_REG (reg
) : reg
);
2499 struct df_scan_problem_data
*problem_data
2500 = (struct df_scan_problem_data
*) df_scan
->problem_data
;
2505 this_ref
= (df_ref
) (problem_data
->ref_base_pool
->allocate ());
2506 gcc_checking_assert (loc
== NULL
);
2509 case DF_REF_ARTIFICIAL
:
2510 this_ref
= (df_ref
) (problem_data
->ref_artificial_pool
->allocate ());
2511 this_ref
->artificial_ref
.bb
= bb
;
2512 gcc_checking_assert (loc
== NULL
);
2515 case DF_REF_REGULAR
:
2516 this_ref
= (df_ref
) (problem_data
->ref_regular_pool
->allocate ());
2517 this_ref
->regular_ref
.loc
= loc
;
2518 gcc_checking_assert (loc
);
2522 DF_REF_CLASS (this_ref
) = cl
;
2523 DF_REF_ID (this_ref
) = -1;
2524 DF_REF_REG (this_ref
) = reg
;
2525 DF_REF_REGNO (this_ref
) = regno
;
2526 DF_REF_TYPE (this_ref
) = ref_type
;
2527 DF_REF_INSN_INFO (this_ref
) = info
;
2528 DF_REF_CHAIN (this_ref
) = NULL
;
2529 DF_REF_FLAGS (this_ref
) = ref_flags
;
2530 DF_REF_NEXT_REG (this_ref
) = NULL
;
2531 DF_REF_PREV_REG (this_ref
) = NULL
;
2532 DF_REF_ORDER (this_ref
) = df
->ref_order
++;
2534 /* We need to clear this bit because fwprop, and in the future
2535 possibly other optimizations sometimes create new refs using ond
2536 refs as the model. */
2537 DF_REF_FLAGS_CLEAR (this_ref
, DF_HARD_REG_LIVE
);
2539 /* See if this ref needs to have DF_HARD_REG_LIVE bit set. */
2540 if (regno
< FIRST_PSEUDO_REGISTER
2541 && !DF_REF_IS_ARTIFICIAL (this_ref
)
2542 && !DEBUG_INSN_P (DF_REF_INSN (this_ref
)))
2544 if (DF_REF_REG_DEF_P (this_ref
))
2546 if (!DF_REF_FLAGS_IS_SET (this_ref
, DF_REF_MAY_CLOBBER
))
2547 DF_REF_FLAGS_SET (this_ref
, DF_HARD_REG_LIVE
);
2549 else if (!(TEST_HARD_REG_BIT (elim_reg_set
, regno
)
2550 && (regno
== FRAME_POINTER_REGNUM
2551 || regno
== ARG_POINTER_REGNUM
)))
2552 DF_REF_FLAGS_SET (this_ref
, DF_HARD_REG_LIVE
);
2557 if (DF_REF_REG_DEF_P (this_ref
))
2558 collection_rec
->def_vec
.safe_push (this_ref
);
2559 else if (DF_REF_FLAGS (this_ref
) & DF_REF_IN_NOTE
)
2560 collection_rec
->eq_use_vec
.safe_push (this_ref
);
2562 collection_rec
->use_vec
.safe_push (this_ref
);
2565 df_install_ref_incremental (this_ref
);
2571 /* Create new references of type DF_REF_TYPE for each part of register REG
2572 at address LOC within INSN of BB. */
2576 df_ref_record (enum df_ref_class cl
,
2577 struct df_collection_rec
*collection_rec
,
2579 basic_block bb
, struct df_insn_info
*insn_info
,
2580 enum df_ref_type ref_type
,
2585 gcc_checking_assert (REG_P (reg
) || GET_CODE (reg
) == SUBREG
);
2587 regno
= REGNO (GET_CODE (reg
) == SUBREG
? SUBREG_REG (reg
) : reg
);
2588 if (regno
< FIRST_PSEUDO_REGISTER
)
2590 struct df_mw_hardreg
*hardreg
= NULL
;
2591 struct df_scan_problem_data
*problem_data
2592 = (struct df_scan_problem_data
*) df_scan
->problem_data
;
2594 unsigned int endregno
;
2597 if (GET_CODE (reg
) == SUBREG
)
2599 regno
+= subreg_regno_offset (regno
, GET_MODE (SUBREG_REG (reg
)),
2600 SUBREG_BYTE (reg
), GET_MODE (reg
));
2601 endregno
= regno
+ subreg_nregs (reg
);
2604 endregno
= END_REGNO (reg
);
2606 /* If this is a multiword hardreg, we create some extra
2607 datastructures that will enable us to easily build REG_DEAD
2608 and REG_UNUSED notes. */
2610 && (endregno
!= regno
+ 1) && insn_info
)
2612 /* Sets to a subreg of a multiword register are partial.
2613 Sets to a non-subreg of a multiword register are not. */
2614 if (GET_CODE (reg
) == SUBREG
)
2615 ref_flags
|= DF_REF_PARTIAL
;
2616 ref_flags
|= DF_REF_MW_HARDREG
;
2618 hardreg
= problem_data
->mw_reg_pool
->allocate ();
2619 hardreg
->type
= ref_type
;
2620 hardreg
->flags
= ref_flags
;
2621 hardreg
->mw_reg
= reg
;
2622 hardreg
->start_regno
= regno
;
2623 hardreg
->end_regno
= endregno
- 1;
2624 hardreg
->mw_order
= df
->ref_order
++;
2625 collection_rec
->mw_vec
.safe_push (hardreg
);
2628 for (i
= regno
; i
< endregno
; i
++)
2630 ref
= df_ref_create_structure (cl
, collection_rec
, regno_reg_rtx
[i
], loc
,
2631 bb
, insn_info
, ref_type
, ref_flags
);
2633 gcc_assert (ORIGINAL_REGNO (DF_REF_REG (ref
)) == i
);
2638 df_ref_create_structure (cl
, collection_rec
, reg
, loc
, bb
, insn_info
,
2639 ref_type
, ref_flags
);
2644 /* A set to a non-paradoxical SUBREG for which the number of word_mode units
2645 covered by the outer mode is smaller than that covered by the inner mode,
2646 is a read-modify-write operation.
2647 This function returns true iff the SUBREG X is such a SUBREG. */
2650 df_read_modify_subreg_p (rtx x
)
2652 unsigned int isize
, osize
;
2653 if (GET_CODE (x
) != SUBREG
)
2655 isize
= GET_MODE_SIZE (GET_MODE (SUBREG_REG (x
)));
2656 osize
= GET_MODE_SIZE (GET_MODE (x
));
2657 return isize
> osize
2658 && isize
> REGMODE_NATURAL_SIZE (GET_MODE (SUBREG_REG (x
)));
2662 /* Process all the registers defined in the rtx pointed by LOC.
2663 Autoincrement/decrement definitions will be picked up by df_uses_record.
2664 Any change here has to be matched in df_find_hard_reg_defs_1. */
2667 df_def_record_1 (struct df_collection_rec
*collection_rec
,
2668 rtx
*loc
, basic_block bb
, struct df_insn_info
*insn_info
,
2673 /* It is legal to have a set destination be a parallel. */
2674 if (GET_CODE (dst
) == PARALLEL
)
2677 for (i
= XVECLEN (dst
, 0) - 1; i
>= 0; i
--)
2679 rtx temp
= XVECEXP (dst
, 0, i
);
2680 gcc_assert (GET_CODE (temp
) == EXPR_LIST
);
2681 df_def_record_1 (collection_rec
, &XEXP (temp
, 0),
2682 bb
, insn_info
, flags
);
2687 if (GET_CODE (dst
) == STRICT_LOW_PART
)
2689 flags
|= DF_REF_READ_WRITE
| DF_REF_PARTIAL
| DF_REF_STRICT_LOW_PART
;
2691 loc
= &XEXP (dst
, 0);
2695 if (GET_CODE (dst
) == ZERO_EXTRACT
)
2697 flags
|= DF_REF_READ_WRITE
| DF_REF_PARTIAL
| DF_REF_ZERO_EXTRACT
;
2699 loc
= &XEXP (dst
, 0);
2703 /* At this point if we do not have a reg or a subreg, just return. */
2706 df_ref_record (DF_REF_REGULAR
, collection_rec
,
2707 dst
, loc
, bb
, insn_info
, DF_REF_REG_DEF
, flags
);
2709 /* We want to keep sp alive everywhere - by making all
2710 writes to sp also use of sp. */
2711 if (REGNO (dst
) == STACK_POINTER_REGNUM
)
2712 df_ref_record (DF_REF_BASE
, collection_rec
,
2713 dst
, NULL
, bb
, insn_info
, DF_REF_REG_USE
, flags
);
2715 else if (GET_CODE (dst
) == SUBREG
&& REG_P (SUBREG_REG (dst
)))
2717 if (df_read_modify_subreg_p (dst
))
2718 flags
|= DF_REF_READ_WRITE
| DF_REF_PARTIAL
;
2720 flags
|= DF_REF_SUBREG
;
2722 df_ref_record (DF_REF_REGULAR
, collection_rec
,
2723 dst
, loc
, bb
, insn_info
, DF_REF_REG_DEF
, flags
);
2728 /* Process all the registers defined in the pattern rtx, X. Any change
2729 here has to be matched in df_find_hard_reg_defs. */
2732 df_defs_record (struct df_collection_rec
*collection_rec
,
2733 rtx x
, basic_block bb
, struct df_insn_info
*insn_info
,
2736 RTX_CODE code
= GET_CODE (x
);
2742 df_def_record_1 (collection_rec
, &SET_DEST (x
), bb
, insn_info
, flags
);
2746 flags
|= DF_REF_MUST_CLOBBER
;
2747 df_def_record_1 (collection_rec
, &XEXP (x
, 0), bb
, insn_info
, flags
);
2751 df_defs_record (collection_rec
, COND_EXEC_CODE (x
),
2752 bb
, insn_info
, DF_REF_CONDITIONAL
);
2756 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
2757 df_defs_record (collection_rec
, XVECEXP (x
, 0, i
),
2758 bb
, insn_info
, flags
);
2761 /* No DEFs to record in other cases */
2766 /* Set bits in *DEFS for hard registers found in the rtx DST, which is the
2767 destination of a set or clobber. This has to match the logic in
2768 df_defs_record_1. */
2771 df_find_hard_reg_defs_1 (rtx dst
, HARD_REG_SET
*defs
)
2773 /* It is legal to have a set destination be a parallel. */
2774 if (GET_CODE (dst
) == PARALLEL
)
2777 for (i
= XVECLEN (dst
, 0) - 1; i
>= 0; i
--)
2779 rtx temp
= XVECEXP (dst
, 0, i
);
2780 gcc_assert (GET_CODE (temp
) == EXPR_LIST
);
2781 df_find_hard_reg_defs_1 (XEXP (temp
, 0), defs
);
2786 if (GET_CODE (dst
) == STRICT_LOW_PART
)
2787 dst
= XEXP (dst
, 0);
2789 if (GET_CODE (dst
) == ZERO_EXTRACT
)
2790 dst
= XEXP (dst
, 0);
2792 /* At this point if we do not have a reg or a subreg, just return. */
2793 if (REG_P (dst
) && HARD_REGISTER_P (dst
))
2794 SET_HARD_REG_BIT (*defs
, REGNO (dst
));
2795 else if (GET_CODE (dst
) == SUBREG
2796 && REG_P (SUBREG_REG (dst
)) && HARD_REGISTER_P (dst
))
2797 SET_HARD_REG_BIT (*defs
, REGNO (SUBREG_REG (dst
)));
2800 /* Set bits in *DEFS for hard registers defined in the pattern X. This
2801 has to match the logic in df_defs_record. */
2804 df_find_hard_reg_defs (rtx x
, HARD_REG_SET
*defs
)
2806 RTX_CODE code
= GET_CODE (x
);
2812 df_find_hard_reg_defs_1 (SET_DEST (x
), defs
);
2816 df_find_hard_reg_defs_1 (XEXP (x
, 0), defs
);
2820 df_find_hard_reg_defs (COND_EXEC_CODE (x
), defs
);
2824 for (i
= 0; i
< XVECLEN (x
, 0); i
++)
2825 df_find_hard_reg_defs (XVECEXP (x
, 0, i
), defs
);
2828 /* No DEFs to record in other cases */
2834 /* Process all the registers used in the rtx at address LOC. */
2837 df_uses_record (struct df_collection_rec
*collection_rec
,
2838 rtx
*loc
, enum df_ref_type ref_type
,
2839 basic_block bb
, struct df_insn_info
*insn_info
,
2849 code
= GET_CODE (x
);
2863 /* If we are clobbering a MEM, mark any registers inside the address
2865 if (MEM_P (XEXP (x
, 0)))
2866 df_uses_record (collection_rec
,
2867 &XEXP (XEXP (x
, 0), 0),
2868 DF_REF_REG_MEM_STORE
,
2872 /* If we're clobbering a REG then we have a def so ignore. */
2876 df_uses_record (collection_rec
,
2877 &XEXP (x
, 0), DF_REF_REG_MEM_LOAD
,
2878 bb
, insn_info
, flags
& DF_REF_IN_NOTE
);
2882 /* While we're here, optimize this case. */
2883 flags
|= DF_REF_PARTIAL
;
2884 /* In case the SUBREG is not of a REG, do not optimize. */
2885 if (!REG_P (SUBREG_REG (x
)))
2887 loc
= &SUBREG_REG (x
);
2888 df_uses_record (collection_rec
, loc
, ref_type
, bb
, insn_info
, flags
);
2891 /* ... Fall through ... */
2894 df_ref_record (DF_REF_REGULAR
, collection_rec
,
2895 x
, loc
, bb
, insn_info
,
2902 df_uses_record (collection_rec
,
2903 &XEXP (x
, 1), ref_type
, bb
, insn_info
, flags
);
2904 df_uses_record (collection_rec
,
2905 &XEXP (x
, 2), ref_type
, bb
, insn_info
, flags
);
2907 /* If the parameters to the zero or sign extract are
2908 constants, strip them off and recurse, otherwise there is
2909 no information that we can gain from this operation. */
2910 if (code
== ZERO_EXTRACT
)
2911 flags
|= DF_REF_ZERO_EXTRACT
;
2913 flags
|= DF_REF_SIGN_EXTRACT
;
2915 df_uses_record (collection_rec
,
2916 &XEXP (x
, 0), ref_type
, bb
, insn_info
, flags
);
2923 rtx dst
= SET_DEST (x
);
2924 gcc_assert (!(flags
& DF_REF_IN_NOTE
));
2925 df_uses_record (collection_rec
,
2926 &SET_SRC (x
), DF_REF_REG_USE
, bb
, insn_info
, flags
);
2928 switch (GET_CODE (dst
))
2931 if (df_read_modify_subreg_p (dst
))
2933 df_uses_record (collection_rec
, &SUBREG_REG (dst
),
2934 DF_REF_REG_USE
, bb
, insn_info
,
2935 flags
| DF_REF_READ_WRITE
| DF_REF_SUBREG
);
2946 df_uses_record (collection_rec
, &XEXP (dst
, 0),
2947 DF_REF_REG_MEM_STORE
, bb
, insn_info
, flags
);
2949 case STRICT_LOW_PART
:
2951 rtx
*temp
= &XEXP (dst
, 0);
2952 /* A strict_low_part uses the whole REG and not just the
2954 dst
= XEXP (dst
, 0);
2955 df_uses_record (collection_rec
,
2956 (GET_CODE (dst
) == SUBREG
) ? &SUBREG_REG (dst
) : temp
,
2957 DF_REF_REG_USE
, bb
, insn_info
,
2958 DF_REF_READ_WRITE
| DF_REF_STRICT_LOW_PART
);
2963 df_uses_record (collection_rec
, &XEXP (dst
, 1),
2964 DF_REF_REG_USE
, bb
, insn_info
, flags
);
2965 df_uses_record (collection_rec
, &XEXP (dst
, 2),
2966 DF_REF_REG_USE
, bb
, insn_info
, flags
);
2967 if (GET_CODE (XEXP (dst
,0)) == MEM
)
2968 df_uses_record (collection_rec
, &XEXP (dst
, 0),
2969 DF_REF_REG_USE
, bb
, insn_info
,
2972 df_uses_record (collection_rec
, &XEXP (dst
, 0),
2973 DF_REF_REG_USE
, bb
, insn_info
,
2974 DF_REF_READ_WRITE
| DF_REF_ZERO_EXTRACT
);
2989 case UNSPEC_VOLATILE
:
2993 /* Traditional and volatile asm instructions must be
2994 considered to use and clobber all hard registers, all
2995 pseudo-registers and all of memory. So must TRAP_IF and
2996 UNSPEC_VOLATILE operations.
2998 Consider for instance a volatile asm that changes the fpu
2999 rounding mode. An insn should not be moved across this
3000 even if it only uses pseudo-regs because it might give an
3001 incorrectly rounded result.
3003 However, flow.c's liveness computation did *not* do this,
3004 giving the reasoning as " ?!? Unfortunately, marking all
3005 hard registers as live causes massive problems for the
3006 register allocator and marking all pseudos as live creates
3007 mountains of uninitialized variable warnings."
3009 In order to maintain the status quo with regard to liveness
3010 and uses, we do what flow.c did and just mark any regs we
3011 can find in ASM_OPERANDS as used. In global asm insns are
3012 scanned and regs_asm_clobbered is filled out.
3014 For all ASM_OPERANDS, we must traverse the vector of input
3015 operands. We can not just fall through here since then we
3016 would be confused by the ASM_INPUT rtx inside ASM_OPERANDS,
3017 which do not indicate traditional asms unlike their normal
3019 if (code
== ASM_OPERANDS
)
3023 for (j
= 0; j
< ASM_OPERANDS_INPUT_LENGTH (x
); j
++)
3024 df_uses_record (collection_rec
, &ASM_OPERANDS_INPUT (x
, j
),
3025 DF_REF_REG_USE
, bb
, insn_info
, flags
);
3032 df_uses_record (collection_rec
,
3033 &PAT_VAR_LOCATION_LOC (x
),
3034 DF_REF_REG_USE
, bb
, insn_info
, flags
);
3043 gcc_assert (!DEBUG_INSN_P (insn_info
->insn
));
3044 /* Catch the def of the register being modified. */
3045 df_ref_record (DF_REF_REGULAR
, collection_rec
, XEXP (x
, 0), &XEXP (x
, 0),
3048 flags
| DF_REF_READ_WRITE
| DF_REF_PRE_POST_MODIFY
);
3050 /* ... Fall through to handle uses ... */
3056 /* Recursively scan the operands of this expression. */
3058 const char *fmt
= GET_RTX_FORMAT (code
);
3061 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
3065 /* Tail recursive case: save a function call level. */
3071 df_uses_record (collection_rec
, &XEXP (x
, i
), ref_type
,
3072 bb
, insn_info
, flags
);
3074 else if (fmt
[i
] == 'E')
3077 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
3078 df_uses_record (collection_rec
,
3079 &XVECEXP (x
, i
, j
), ref_type
,
3080 bb
, insn_info
, flags
);
3089 /* For all DF_REF_CONDITIONAL defs, add a corresponding uses. */
3092 df_get_conditional_uses (struct df_collection_rec
*collection_rec
)
3097 FOR_EACH_VEC_ELT (collection_rec
->def_vec
, ix
, ref
)
3099 if (DF_REF_FLAGS_IS_SET (ref
, DF_REF_CONDITIONAL
))
3103 use
= df_ref_create_structure (DF_REF_CLASS (ref
), collection_rec
, DF_REF_REG (ref
),
3104 DF_REF_LOC (ref
), DF_REF_BB (ref
),
3105 DF_REF_INSN_INFO (ref
), DF_REF_REG_USE
,
3106 DF_REF_FLAGS (ref
) & ~DF_REF_CONDITIONAL
);
3107 DF_REF_REGNO (use
) = DF_REF_REGNO (ref
);
3113 /* Get call's extra defs and uses (track caller-saved registers). */
3116 df_get_call_refs (struct df_collection_rec
*collection_rec
,
3118 struct df_insn_info
*insn_info
,
3122 bool is_sibling_call
;
3124 HARD_REG_SET defs_generated
;
3125 HARD_REG_SET fn_reg_set_usage
;
3127 CLEAR_HARD_REG_SET (defs_generated
);
3128 df_find_hard_reg_defs (PATTERN (insn_info
->insn
), &defs_generated
);
3129 is_sibling_call
= SIBLING_CALL_P (insn_info
->insn
);
3130 get_call_reg_set_usage (insn_info
->insn
, &fn_reg_set_usage
,
3131 regs_invalidated_by_call
);
3133 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3135 if (i
== STACK_POINTER_REGNUM
)
3136 /* The stack ptr is used (honorarily) by a CALL insn. */
3137 df_ref_record (DF_REF_BASE
, collection_rec
, regno_reg_rtx
[i
],
3138 NULL
, bb
, insn_info
, DF_REF_REG_USE
,
3139 DF_REF_CALL_STACK_USAGE
| flags
);
3140 else if (global_regs
[i
])
3142 /* Calls to const functions cannot access any global registers and
3143 calls to pure functions cannot set them. All other calls may
3144 reference any of the global registers, so they are recorded as
3146 if (!RTL_CONST_CALL_P (insn_info
->insn
))
3148 df_ref_record (DF_REF_BASE
, collection_rec
, regno_reg_rtx
[i
],
3149 NULL
, bb
, insn_info
, DF_REF_REG_USE
, flags
);
3150 if (!RTL_PURE_CALL_P (insn_info
->insn
))
3151 df_ref_record (DF_REF_BASE
, collection_rec
, regno_reg_rtx
[i
],
3152 NULL
, bb
, insn_info
, DF_REF_REG_DEF
, flags
);
3155 else if (TEST_HARD_REG_BIT (fn_reg_set_usage
, i
)
3156 /* no clobbers for regs that are the result of the call */
3157 && !TEST_HARD_REG_BIT (defs_generated
, i
)
3158 && (!is_sibling_call
3159 || !bitmap_bit_p (df
->exit_block_uses
, i
)
3160 || refers_to_regno_p (i
, crtl
->return_rtx
)))
3161 df_ref_record (DF_REF_BASE
, collection_rec
, regno_reg_rtx
[i
],
3162 NULL
, bb
, insn_info
, DF_REF_REG_DEF
,
3163 DF_REF_MAY_CLOBBER
| flags
);
3166 /* Record the registers used to pass arguments, and explicitly
3167 noted as clobbered. */
3168 for (note
= CALL_INSN_FUNCTION_USAGE (insn_info
->insn
); note
;
3169 note
= XEXP (note
, 1))
3171 if (GET_CODE (XEXP (note
, 0)) == USE
)
3172 df_uses_record (collection_rec
, &XEXP (XEXP (note
, 0), 0),
3173 DF_REF_REG_USE
, bb
, insn_info
, flags
);
3174 else if (GET_CODE (XEXP (note
, 0)) == CLOBBER
)
3176 if (REG_P (XEXP (XEXP (note
, 0), 0)))
3178 unsigned int regno
= REGNO (XEXP (XEXP (note
, 0), 0));
3179 if (!TEST_HARD_REG_BIT (defs_generated
, regno
))
3180 df_defs_record (collection_rec
, XEXP (note
, 0), bb
,
3184 df_uses_record (collection_rec
, &XEXP (note
, 0),
3185 DF_REF_REG_USE
, bb
, insn_info
, flags
);
3192 /* Collect all refs in the INSN. This function is free of any
3193 side-effect - it will create and return a lists of df_ref's in the
3194 COLLECTION_REC without putting those refs into existing ref chains
3198 df_insn_refs_collect (struct df_collection_rec
*collection_rec
,
3199 basic_block bb
, struct df_insn_info
*insn_info
)
3202 bool is_cond_exec
= (GET_CODE (PATTERN (insn_info
->insn
)) == COND_EXEC
);
3204 /* Clear out the collection record. */
3205 collection_rec
->def_vec
.truncate (0);
3206 collection_rec
->use_vec
.truncate (0);
3207 collection_rec
->eq_use_vec
.truncate (0);
3208 collection_rec
->mw_vec
.truncate (0);
3210 /* Process REG_EQUIV/REG_EQUAL notes. */
3211 for (note
= REG_NOTES (insn_info
->insn
); note
;
3212 note
= XEXP (note
, 1))
3214 switch (REG_NOTE_KIND (note
))
3218 df_uses_record (collection_rec
,
3219 &XEXP (note
, 0), DF_REF_REG_USE
,
3220 bb
, insn_info
, DF_REF_IN_NOTE
);
3222 case REG_NON_LOCAL_GOTO
:
3223 /* The frame ptr is used by a non-local goto. */
3224 df_ref_record (DF_REF_BASE
, collection_rec
,
3225 regno_reg_rtx
[FRAME_POINTER_REGNUM
],
3226 NULL
, bb
, insn_info
,
3228 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER
)
3229 df_ref_record (DF_REF_BASE
, collection_rec
,
3230 regno_reg_rtx
[HARD_FRAME_POINTER_REGNUM
],
3231 NULL
, bb
, insn_info
,
3239 /* For CALL_INSNs, first record DF_REF_BASE register defs, as well as
3240 uses from CALL_INSN_FUNCTION_USAGE. */
3241 if (CALL_P (insn_info
->insn
))
3242 df_get_call_refs (collection_rec
, bb
, insn_info
,
3243 (is_cond_exec
) ? DF_REF_CONDITIONAL
: 0);
3245 /* Record other defs. These should be mostly for DF_REF_REGULAR, so
3246 that a qsort on the defs is unnecessary in most cases. */
3247 df_defs_record (collection_rec
,
3248 PATTERN (insn_info
->insn
), bb
, insn_info
, 0);
3250 /* Record the register uses. */
3251 df_uses_record (collection_rec
,
3252 &PATTERN (insn_info
->insn
), DF_REF_REG_USE
, bb
, insn_info
, 0);
3254 /* DF_REF_CONDITIONAL needs corresponding USES. */
3256 df_get_conditional_uses (collection_rec
);
3258 df_canonize_collection_rec (collection_rec
);
3261 /* Recompute the luids for the insns in BB. */
3264 df_recompute_luids (basic_block bb
)
3269 df_grow_insn_info ();
3271 /* Scan the block an insn at a time from beginning to end. */
3272 FOR_BB_INSNS (bb
, insn
)
3274 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
3275 /* Inserting labels does not always trigger the incremental
3279 gcc_assert (!INSN_P (insn
));
3280 insn_info
= df_insn_create_insn_record (insn
);
3283 DF_INSN_INFO_LUID (insn_info
) = luid
;
3290 /* Collect all artificial refs at the block level for BB and add them
3291 to COLLECTION_REC. */
3294 df_bb_refs_collect (struct df_collection_rec
*collection_rec
, basic_block bb
)
3296 collection_rec
->def_vec
.truncate (0);
3297 collection_rec
->use_vec
.truncate (0);
3298 collection_rec
->eq_use_vec
.truncate (0);
3299 collection_rec
->mw_vec
.truncate (0);
3301 if (bb
->index
== ENTRY_BLOCK
)
3303 df_entry_block_defs_collect (collection_rec
, df
->entry_block_defs
);
3306 else if (bb
->index
== EXIT_BLOCK
)
3308 df_exit_block_uses_collect (collection_rec
, df
->exit_block_uses
);
3312 if (bb_has_eh_pred (bb
))
3315 /* Mark the registers that will contain data for the handler. */
3318 unsigned regno
= EH_RETURN_DATA_REGNO (i
);
3319 if (regno
== INVALID_REGNUM
)
3321 df_ref_record (DF_REF_ARTIFICIAL
, collection_rec
, regno_reg_rtx
[regno
], NULL
,
3322 bb
, NULL
, DF_REF_REG_DEF
, DF_REF_AT_TOP
);
3326 /* Add the hard_frame_pointer if this block is the target of a
3328 if (bb
->flags
& BB_NON_LOCAL_GOTO_TARGET
)
3329 df_ref_record (DF_REF_ARTIFICIAL
, collection_rec
, hard_frame_pointer_rtx
, NULL
,
3330 bb
, NULL
, DF_REF_REG_DEF
, DF_REF_AT_TOP
);
3332 /* Add the artificial uses. */
3333 if (bb
->index
>= NUM_FIXED_BLOCKS
)
3337 bitmap au
= bb_has_eh_pred (bb
)
3338 ? &df
->eh_block_artificial_uses
3339 : &df
->regular_block_artificial_uses
;
3341 EXECUTE_IF_SET_IN_BITMAP (au
, 0, regno
, bi
)
3343 df_ref_record (DF_REF_ARTIFICIAL
, collection_rec
, regno_reg_rtx
[regno
], NULL
,
3344 bb
, NULL
, DF_REF_REG_USE
, 0);
3348 df_canonize_collection_rec (collection_rec
);
3352 /* Record all the refs within the basic block BB_INDEX and scan the instructions if SCAN_INSNS. */
3355 df_bb_refs_record (int bb_index
, bool scan_insns
)
3357 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, bb_index
);
3364 df_collection_rec collection_rec
;
3365 df_grow_bb_info (df_scan
);
3367 /* Scan the block an insn at a time from beginning to end. */
3368 FOR_BB_INSNS (bb
, insn
)
3370 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
3371 gcc_assert (!insn_info
);
3373 insn_info
= df_insn_create_insn_record (insn
);
3376 /* Record refs within INSN. */
3377 DF_INSN_INFO_LUID (insn_info
) = luid
++;
3378 df_insn_refs_collect (&collection_rec
, bb
, DF_INSN_INFO_GET (insn
));
3379 df_refs_add_to_chains (&collection_rec
, bb
, insn
, copy_all
);
3381 DF_INSN_INFO_LUID (insn_info
) = luid
;
3384 /* Other block level artificial refs */
3385 df_bb_refs_collect (&collection_rec
, bb
);
3386 df_refs_add_to_chains (&collection_rec
, bb
, NULL
, copy_all
);
3388 /* Now that the block has been processed, set the block as dirty so
3389 LR and LIVE will get it processed. */
3390 df_set_bb_dirty (bb
);
3394 /* Get the artificial use set for a regular (i.e. non-exit/non-entry)
3398 df_get_regular_block_artificial_uses (bitmap regular_block_artificial_uses
)
3404 bitmap_clear (regular_block_artificial_uses
);
3406 if (reload_completed
)
3408 if (frame_pointer_needed
)
3409 bitmap_set_bit (regular_block_artificial_uses
, HARD_FRAME_POINTER_REGNUM
);
3412 /* Before reload, there are a few registers that must be forced
3413 live everywhere -- which might not already be the case for
3414 blocks within infinite loops. */
3416 unsigned int picreg
= PIC_OFFSET_TABLE_REGNUM
;
3418 /* Any reference to any pseudo before reload is a potential
3419 reference of the frame pointer. */
3420 bitmap_set_bit (regular_block_artificial_uses
, FRAME_POINTER_REGNUM
);
3422 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER
)
3423 bitmap_set_bit (regular_block_artificial_uses
,
3424 HARD_FRAME_POINTER_REGNUM
);
3426 /* Pseudos with argument area equivalences may require
3427 reloading via the argument pointer. */
3428 if (FRAME_POINTER_REGNUM
!= ARG_POINTER_REGNUM
3429 && fixed_regs
[ARG_POINTER_REGNUM
])
3430 bitmap_set_bit (regular_block_artificial_uses
, ARG_POINTER_REGNUM
);
3432 /* Any constant, or pseudo with constant equivalences, may
3433 require reloading from memory using the pic register. */
3434 if (picreg
!= INVALID_REGNUM
3435 && fixed_regs
[picreg
])
3436 bitmap_set_bit (regular_block_artificial_uses
, picreg
);
3438 /* The all-important stack pointer must always be live. */
3439 bitmap_set_bit (regular_block_artificial_uses
, STACK_POINTER_REGNUM
);
3442 /* EH_USES registers are used:
3443 1) at all insns that might throw (calls or with -fnon-call-exceptions
3446 3) to support backtraces and/or debugging, anywhere between their
3447 initialization and where they the saved registers are restored
3448 from them, including the cases where we don't reach the epilogue
3449 (noreturn call or infinite loop). */
3450 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3452 bitmap_set_bit (regular_block_artificial_uses
, i
);
3457 /* Get the artificial use set for an eh block. */
3460 df_get_eh_block_artificial_uses (bitmap eh_block_artificial_uses
)
3462 bitmap_clear (eh_block_artificial_uses
);
3464 /* The following code (down through the arg_pointer setting APPEARS
3465 to be necessary because there is nothing that actually
3466 describes what the exception handling code may actually need
3468 if (reload_completed
)
3470 if (frame_pointer_needed
)
3472 bitmap_set_bit (eh_block_artificial_uses
, FRAME_POINTER_REGNUM
);
3473 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER
)
3474 bitmap_set_bit (eh_block_artificial_uses
,
3475 HARD_FRAME_POINTER_REGNUM
);
3477 if (FRAME_POINTER_REGNUM
!= ARG_POINTER_REGNUM
3478 && fixed_regs
[ARG_POINTER_REGNUM
])
3479 bitmap_set_bit (eh_block_artificial_uses
, ARG_POINTER_REGNUM
);
3485 /*----------------------------------------------------------------------------
3486 Specialized hard register scanning functions.
3487 ----------------------------------------------------------------------------*/
3490 /* Mark a register in SET. Hard registers in large modes get all
3491 of their component registers set as well. */
3494 df_mark_reg (rtx reg
, void *vset
)
3496 bitmap_set_range ((bitmap
) vset
, REGNO (reg
), REG_NREGS (reg
));
3500 /* Set the bit for regs that are considered being defined at the entry. */
3503 df_get_entry_block_def_set (bitmap entry_block_defs
)
3508 bitmap_clear (entry_block_defs
);
3510 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3513 bitmap_set_bit (entry_block_defs
, i
);
3514 if (FUNCTION_ARG_REGNO_P (i
))
3515 bitmap_set_bit (entry_block_defs
, INCOMING_REGNO (i
));
3518 /* The always important stack pointer. */
3519 bitmap_set_bit (entry_block_defs
, STACK_POINTER_REGNUM
);
3521 /* Once the prologue has been generated, all of these registers
3522 should just show up in the first regular block. */
3523 if (targetm
.have_prologue () && epilogue_completed
)
3525 /* Defs for the callee saved registers are inserted so that the
3526 pushes have some defining location. */
3527 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3528 if ((call_used_regs
[i
] == 0) && (df_regs_ever_live_p (i
)))
3529 bitmap_set_bit (entry_block_defs
, i
);
3532 r
= targetm
.calls
.struct_value_rtx (current_function_decl
, true);
3534 bitmap_set_bit (entry_block_defs
, REGNO (r
));
3536 /* If the function has an incoming STATIC_CHAIN, it has to show up
3537 in the entry def set. */
3538 r
= targetm
.calls
.static_chain (current_function_decl
, true);
3540 bitmap_set_bit (entry_block_defs
, REGNO (r
));
3542 if ((!reload_completed
) || frame_pointer_needed
)
3544 /* Any reference to any pseudo before reload is a potential
3545 reference of the frame pointer. */
3546 bitmap_set_bit (entry_block_defs
, FRAME_POINTER_REGNUM
);
3548 /* If they are different, also mark the hard frame pointer as live. */
3549 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER
3550 && !LOCAL_REGNO (HARD_FRAME_POINTER_REGNUM
))
3551 bitmap_set_bit (entry_block_defs
, HARD_FRAME_POINTER_REGNUM
);
3554 /* These registers are live everywhere. */
3555 if (!reload_completed
)
3557 /* Pseudos with argument area equivalences may require
3558 reloading via the argument pointer. */
3559 if (FRAME_POINTER_REGNUM
!= ARG_POINTER_REGNUM
3560 && fixed_regs
[ARG_POINTER_REGNUM
])
3561 bitmap_set_bit (entry_block_defs
, ARG_POINTER_REGNUM
);
3563 /* Any constant, or pseudo with constant equivalences, may
3564 require reloading from memory using the pic register. */
3565 unsigned int picreg
= PIC_OFFSET_TABLE_REGNUM
;
3566 if (picreg
!= INVALID_REGNUM
3567 && fixed_regs
[picreg
])
3568 bitmap_set_bit (entry_block_defs
, picreg
);
3571 #ifdef INCOMING_RETURN_ADDR_RTX
3572 if (REG_P (INCOMING_RETURN_ADDR_RTX
))
3573 bitmap_set_bit (entry_block_defs
, REGNO (INCOMING_RETURN_ADDR_RTX
));
3576 targetm
.extra_live_on_entry (entry_block_defs
);
3580 /* Return the (conservative) set of hard registers that are defined on
3581 entry to the function.
3582 It uses df->entry_block_defs to determine which register
3583 reference to include. */
3586 df_entry_block_defs_collect (struct df_collection_rec
*collection_rec
,
3587 bitmap entry_block_defs
)
3592 EXECUTE_IF_SET_IN_BITMAP (entry_block_defs
, 0, i
, bi
)
3594 df_ref_record (DF_REF_ARTIFICIAL
, collection_rec
, regno_reg_rtx
[i
], NULL
,
3595 ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, DF_REF_REG_DEF
, 0);
3598 df_canonize_collection_rec (collection_rec
);
3602 /* Record the (conservative) set of hard registers that are defined on
3603 entry to the function. */
3606 df_record_entry_block_defs (bitmap entry_block_defs
)
3608 struct df_collection_rec collection_rec
;
3609 df_entry_block_defs_collect (&collection_rec
, entry_block_defs
);
3611 /* Process bb_refs chain */
3612 df_refs_add_to_chains (&collection_rec
,
3613 BASIC_BLOCK_FOR_FN (cfun
, ENTRY_BLOCK
),
3619 /* Update the defs in the entry block. */
3622 df_update_entry_block_defs (void)
3625 bool changed
= false;
3627 bitmap_initialize (&refs
, &df_bitmap_obstack
);
3628 df_get_entry_block_def_set (&refs
);
3629 if (df
->entry_block_defs
)
3631 if (!bitmap_equal_p (df
->entry_block_defs
, &refs
))
3633 struct df_scan_bb_info
*bb_info
= df_scan_get_bb_info (ENTRY_BLOCK
);
3634 df_ref_chain_delete_du_chain (bb_info
->artificial_defs
);
3635 df_ref_chain_delete (bb_info
->artificial_defs
);
3636 bb_info
->artificial_defs
= NULL
;
3642 struct df_scan_problem_data
*problem_data
3643 = (struct df_scan_problem_data
*) df_scan
->problem_data
;
3645 df
->entry_block_defs
= BITMAP_ALLOC (&problem_data
->reg_bitmaps
);
3651 df_record_entry_block_defs (&refs
);
3652 bitmap_copy (df
->entry_block_defs
, &refs
);
3653 df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun
, ENTRY_BLOCK
));
3655 bitmap_clear (&refs
);
3659 /* Set the bit for regs that are considered being used at the exit. */
3662 df_get_exit_block_use_set (bitmap exit_block_uses
)
3665 unsigned int picreg
= PIC_OFFSET_TABLE_REGNUM
;
3667 bitmap_clear (exit_block_uses
);
3669 /* Stack pointer is always live at the exit. */
3670 bitmap_set_bit (exit_block_uses
, STACK_POINTER_REGNUM
);
3672 /* Mark the frame pointer if needed at the end of the function.
3673 If we end up eliminating it, it will be removed from the live
3674 list of each basic block by reload. */
3676 if ((!reload_completed
) || frame_pointer_needed
)
3678 bitmap_set_bit (exit_block_uses
, FRAME_POINTER_REGNUM
);
3680 /* If they are different, also mark the hard frame pointer as live. */
3681 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER
3682 && !LOCAL_REGNO (HARD_FRAME_POINTER_REGNUM
))
3683 bitmap_set_bit (exit_block_uses
, HARD_FRAME_POINTER_REGNUM
);
3686 /* Many architectures have a GP register even without flag_pic.
3687 Assume the pic register is not in use, or will be handled by
3688 other means, if it is not fixed. */
3689 if (!PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
3690 && picreg
!= INVALID_REGNUM
3691 && fixed_regs
[picreg
])
3692 bitmap_set_bit (exit_block_uses
, picreg
);
3694 /* Mark all global registers, and all registers used by the
3695 epilogue as being live at the end of the function since they
3696 may be referenced by our caller. */
3697 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3698 if (global_regs
[i
] || EPILOGUE_USES (i
))
3699 bitmap_set_bit (exit_block_uses
, i
);
3701 if (targetm
.have_epilogue () && epilogue_completed
)
3703 /* Mark all call-saved registers that we actually used. */
3704 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3705 if (df_regs_ever_live_p (i
) && !LOCAL_REGNO (i
)
3706 && !TEST_HARD_REG_BIT (regs_invalidated_by_call
, i
))
3707 bitmap_set_bit (exit_block_uses
, i
);
3710 /* Mark the registers that will contain data for the handler. */
3711 if (reload_completed
&& crtl
->calls_eh_return
)
3714 unsigned regno
= EH_RETURN_DATA_REGNO (i
);
3715 if (regno
== INVALID_REGNUM
)
3717 bitmap_set_bit (exit_block_uses
, regno
);
3720 #ifdef EH_RETURN_STACKADJ_RTX
3721 if ((!targetm
.have_epilogue () || ! epilogue_completed
)
3722 && crtl
->calls_eh_return
)
3724 rtx tmp
= EH_RETURN_STACKADJ_RTX
;
3725 if (tmp
&& REG_P (tmp
))
3726 df_mark_reg (tmp
, exit_block_uses
);
3730 #ifdef EH_RETURN_HANDLER_RTX
3731 if ((!targetm
.have_epilogue () || ! epilogue_completed
)
3732 && crtl
->calls_eh_return
)
3734 rtx tmp
= EH_RETURN_HANDLER_RTX
;
3735 if (tmp
&& REG_P (tmp
))
3736 df_mark_reg (tmp
, exit_block_uses
);
3740 /* Mark function return value. */
3741 diddle_return_value (df_mark_reg
, (void*) exit_block_uses
);
3745 /* Return the refs of hard registers that are used in the exit block.
3746 It uses df->exit_block_uses to determine register to include. */
3749 df_exit_block_uses_collect (struct df_collection_rec
*collection_rec
, bitmap exit_block_uses
)
3754 EXECUTE_IF_SET_IN_BITMAP (exit_block_uses
, 0, i
, bi
)
3755 df_ref_record (DF_REF_ARTIFICIAL
, collection_rec
, regno_reg_rtx
[i
], NULL
,
3756 EXIT_BLOCK_PTR_FOR_FN (cfun
), NULL
, DF_REF_REG_USE
, 0);
3758 /* It is deliberate that this is not put in the exit block uses but
3759 I do not know why. */
3760 if (FRAME_POINTER_REGNUM
!= ARG_POINTER_REGNUM
3762 && !bitmap_bit_p (exit_block_uses
, ARG_POINTER_REGNUM
)
3763 && bb_has_eh_pred (EXIT_BLOCK_PTR_FOR_FN (cfun
))
3764 && fixed_regs
[ARG_POINTER_REGNUM
])
3765 df_ref_record (DF_REF_ARTIFICIAL
, collection_rec
, regno_reg_rtx
[ARG_POINTER_REGNUM
], NULL
,
3766 EXIT_BLOCK_PTR_FOR_FN (cfun
), NULL
, DF_REF_REG_USE
, 0);
3768 df_canonize_collection_rec (collection_rec
);
3772 /* Record the set of hard registers that are used in the exit block.
3773 It uses df->exit_block_uses to determine which bit to include. */
3776 df_record_exit_block_uses (bitmap exit_block_uses
)
3778 struct df_collection_rec collection_rec
;
3779 df_exit_block_uses_collect (&collection_rec
, exit_block_uses
);
3781 /* Process bb_refs chain */
3782 df_refs_add_to_chains (&collection_rec
,
3783 BASIC_BLOCK_FOR_FN (cfun
, EXIT_BLOCK
),
3789 /* Update the uses in the exit block. */
3792 df_update_exit_block_uses (void)
3795 bool changed
= false;
3797 bitmap_initialize (&refs
, &df_bitmap_obstack
);
3798 df_get_exit_block_use_set (&refs
);
3799 if (df
->exit_block_uses
)
3801 if (!bitmap_equal_p (df
->exit_block_uses
, &refs
))
3803 struct df_scan_bb_info
*bb_info
= df_scan_get_bb_info (EXIT_BLOCK
);
3804 df_ref_chain_delete_du_chain (bb_info
->artificial_uses
);
3805 df_ref_chain_delete (bb_info
->artificial_uses
);
3806 bb_info
->artificial_uses
= NULL
;
3812 struct df_scan_problem_data
*problem_data
3813 = (struct df_scan_problem_data
*) df_scan
->problem_data
;
3815 df
->exit_block_uses
= BITMAP_ALLOC (&problem_data
->reg_bitmaps
);
3821 df_record_exit_block_uses (&refs
);
3822 bitmap_copy (df
->exit_block_uses
,& refs
);
3823 df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun
, EXIT_BLOCK
));
3825 bitmap_clear (&refs
);
3828 static bool initialized
= false;
3831 /* Initialize some platform specific structures. */
3834 df_hard_reg_init (void)
3836 #ifdef ELIMINABLE_REGS
3838 static const struct {const int from
, to
; } eliminables
[] = ELIMINABLE_REGS
;
3843 /* Record which registers will be eliminated. We use this in
3845 CLEAR_HARD_REG_SET (elim_reg_set
);
3847 #ifdef ELIMINABLE_REGS
3848 for (i
= 0; i
< (int) ARRAY_SIZE (eliminables
); i
++)
3849 SET_HARD_REG_BIT (elim_reg_set
, eliminables
[i
].from
);
3851 SET_HARD_REG_BIT (elim_reg_set
, FRAME_POINTER_REGNUM
);
3858 /* Recompute the parts of scanning that are based on regs_ever_live
3859 because something changed in that array. */
3862 df_update_entry_exit_and_calls (void)
3866 df_update_entry_block_defs ();
3867 df_update_exit_block_uses ();
3869 /* The call insns need to be rescanned because there may be changes
3870 in the set of registers clobbered across the call. */
3871 FOR_EACH_BB_FN (bb
, cfun
)
3874 FOR_BB_INSNS (bb
, insn
)
3876 if (INSN_P (insn
) && CALL_P (insn
))
3877 df_insn_rescan (insn
);
3883 /* Return true if hard REG is actually used in the some instruction.
3884 There are a fair number of conditions that affect the setting of
3885 this array. See the comment in df.h for df->hard_regs_live_count
3886 for the conditions that this array is set. */
3889 df_hard_reg_used_p (unsigned int reg
)
3891 return df
->hard_regs_live_count
[reg
] != 0;
3895 /* A count of the number of times REG is actually used in the some
3896 instruction. There are a fair number of conditions that affect the
3897 setting of this array. See the comment in df.h for
3898 df->hard_regs_live_count for the conditions that this array is
3903 df_hard_reg_used_count (unsigned int reg
)
3905 return df
->hard_regs_live_count
[reg
];
3909 /* Get the value of regs_ever_live[REGNO]. */
3912 df_regs_ever_live_p (unsigned int regno
)
3914 return regs_ever_live
[regno
];
3918 /* Set regs_ever_live[REGNO] to VALUE. If this cause regs_ever_live
3919 to change, schedule that change for the next update. */
3922 df_set_regs_ever_live (unsigned int regno
, bool value
)
3924 if (regs_ever_live
[regno
] == value
)
3927 regs_ever_live
[regno
] = value
;
3929 df
->redo_entry_and_exit
= true;
3933 /* Compute "regs_ever_live" information from the underlying df
3934 information. Set the vector to all false if RESET. */
3937 df_compute_regs_ever_live (bool reset
)
3940 bool changed
= df
->redo_entry_and_exit
;
3943 memset (regs_ever_live
, 0, sizeof (regs_ever_live
));
3945 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3946 if ((!regs_ever_live
[i
]) && df_hard_reg_used_p (i
))
3948 regs_ever_live
[i
] = true;
3952 df_update_entry_exit_and_calls ();
3953 df
->redo_entry_and_exit
= false;
3957 /*----------------------------------------------------------------------------
3958 Dataflow ref information verification functions.
3960 df_reg_chain_mark (refs, regno, is_def, is_eq_use)
3961 df_reg_chain_verify_unmarked (refs)
3962 df_refs_verify (vec<stack, va_df_ref>, ref*, bool)
3963 df_mws_verify (mw*, mw*, bool)
3964 df_insn_refs_verify (collection_rec, bb, insn, bool)
3965 df_bb_refs_verify (bb, refs, bool)
3967 df_exit_block_bitmap_verify (bool)
3968 df_entry_block_bitmap_verify (bool)
3970 ----------------------------------------------------------------------------*/
3973 /* Mark all refs in the reg chain. Verify that all of the registers
3974 are in the correct chain. */
3977 df_reg_chain_mark (df_ref refs
, unsigned int regno
,
3978 bool is_def
, bool is_eq_use
)
3980 unsigned int count
= 0;
3982 for (ref
= refs
; ref
; ref
= DF_REF_NEXT_REG (ref
))
3984 gcc_assert (!DF_REF_IS_REG_MARKED (ref
));
3986 /* If there are no def-use or use-def chains, make sure that all
3987 of the chains are clear. */
3989 gcc_assert (!DF_REF_CHAIN (ref
));
3991 /* Check to make sure the ref is in the correct chain. */
3992 gcc_assert (DF_REF_REGNO (ref
) == regno
);
3994 gcc_assert (DF_REF_REG_DEF_P (ref
));
3996 gcc_assert (!DF_REF_REG_DEF_P (ref
));
3999 gcc_assert ((DF_REF_FLAGS (ref
) & DF_REF_IN_NOTE
));
4001 gcc_assert ((DF_REF_FLAGS (ref
) & DF_REF_IN_NOTE
) == 0);
4003 if (DF_REF_NEXT_REG (ref
))
4004 gcc_assert (DF_REF_PREV_REG (DF_REF_NEXT_REG (ref
)) == ref
);
4006 DF_REF_REG_MARK (ref
);
4012 /* Verify that all of the registers in the chain are unmarked. */
4015 df_reg_chain_verify_unmarked (df_ref refs
)
4018 for (ref
= refs
; ref
; ref
= DF_REF_NEXT_REG (ref
))
4019 gcc_assert (!DF_REF_IS_REG_MARKED (ref
));
4023 /* Verify that NEW_REC and OLD_REC have exactly the same members. */
4026 df_refs_verify (const vec
<df_ref
, va_heap
> *new_rec
, df_ref old_rec
,
4032 FOR_EACH_VEC_ELT (*new_rec
, ix
, new_ref
)
4034 if (old_rec
== NULL
|| !df_ref_equal_p (new_ref
, old_rec
))
4042 /* Abort if fail is called from the function level verifier. If
4043 that is the context, mark this reg as being seem. */
4046 gcc_assert (DF_REF_IS_REG_MARKED (old_rec
));
4047 DF_REF_REG_UNMARK (old_rec
);
4050 old_rec
= DF_REF_NEXT_LOC (old_rec
);
4054 gcc_assert (old_rec
== NULL
);
4056 return old_rec
== NULL
;
4061 /* Verify that NEW_REC and OLD_REC have exactly the same members. */
4064 df_mws_verify (const vec
<df_mw_hardreg_ptr
, va_heap
> *new_rec
,
4065 struct df_mw_hardreg
*old_rec
,
4069 struct df_mw_hardreg
*new_reg
;
4071 FOR_EACH_VEC_ELT (*new_rec
, ix
, new_reg
)
4073 if (old_rec
== NULL
|| !df_mw_equal_p (new_reg
, old_rec
))
4080 old_rec
= DF_MWS_NEXT (old_rec
);
4084 gcc_assert (old_rec
== NULL
);
4086 return old_rec
== NULL
;
4091 /* Return true if the existing insn refs information is complete and
4092 correct. Otherwise (i.e. if there's any missing or extra refs),
4093 return the correct df_ref chain in REFS_RETURN.
4095 If ABORT_IF_FAIL, leave the refs that are verified (already in the
4096 ref chain) as DF_REF_MARKED(). If it's false, then it's a per-insn
4097 verification mode instead of the whole function, so unmark
4100 If ABORT_IF_FAIL is set, this function never returns false. */
4103 df_insn_refs_verify (struct df_collection_rec
*collection_rec
,
4108 bool ret1
, ret2
, ret3
, ret4
;
4109 unsigned int uid
= INSN_UID (insn
);
4110 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
4112 df_insn_refs_collect (collection_rec
, bb
, insn_info
);
4114 /* Unfortunately we cannot opt out early if one of these is not
4115 right because the marks will not get cleared. */
4116 ret1
= df_refs_verify (&collection_rec
->def_vec
, DF_INSN_UID_DEFS (uid
),
4118 ret2
= df_refs_verify (&collection_rec
->use_vec
, DF_INSN_UID_USES (uid
),
4120 ret3
= df_refs_verify (&collection_rec
->eq_use_vec
, DF_INSN_UID_EQ_USES (uid
),
4122 ret4
= df_mws_verify (&collection_rec
->mw_vec
, DF_INSN_UID_MWS (uid
),
4124 return (ret1
&& ret2
&& ret3
&& ret4
);
4128 /* Return true if all refs in the basic block are correct and complete.
4129 Due to df_ref_chain_verify, it will cause all refs
4130 that are verified to have DF_REF_MARK bit set. */
4133 df_bb_verify (basic_block bb
)
4136 struct df_scan_bb_info
*bb_info
= df_scan_get_bb_info (bb
->index
);
4137 struct df_collection_rec collection_rec
;
4139 gcc_assert (bb_info
);
4141 /* Scan the block, one insn at a time, from beginning to end. */
4142 FOR_BB_INSNS_REVERSE (bb
, insn
)
4146 df_insn_refs_verify (&collection_rec
, bb
, insn
, true);
4147 df_free_collection_rec (&collection_rec
);
4150 /* Do the artificial defs and uses. */
4151 df_bb_refs_collect (&collection_rec
, bb
);
4152 df_refs_verify (&collection_rec
.def_vec
, df_get_artificial_defs (bb
->index
), true);
4153 df_refs_verify (&collection_rec
.use_vec
, df_get_artificial_uses (bb
->index
), true);
4154 df_free_collection_rec (&collection_rec
);
4160 /* Returns true if the entry block has correct and complete df_ref set.
4161 If not it either aborts if ABORT_IF_FAIL is true or returns false. */
4164 df_entry_block_bitmap_verify (bool abort_if_fail
)
4166 bitmap_head entry_block_defs
;
4169 bitmap_initialize (&entry_block_defs
, &df_bitmap_obstack
);
4170 df_get_entry_block_def_set (&entry_block_defs
);
4172 is_eq
= bitmap_equal_p (&entry_block_defs
, df
->entry_block_defs
);
4174 if (!is_eq
&& abort_if_fail
)
4176 fprintf (stderr
, "entry_block_defs = ");
4177 df_print_regset (stderr
, &entry_block_defs
);
4178 fprintf (stderr
, "df->entry_block_defs = ");
4179 df_print_regset (stderr
, df
->entry_block_defs
);
4183 bitmap_clear (&entry_block_defs
);
4189 /* Returns true if the exit block has correct and complete df_ref set.
4190 If not it either aborts if ABORT_IF_FAIL is true or returns false. */
4193 df_exit_block_bitmap_verify (bool abort_if_fail
)
4195 bitmap_head exit_block_uses
;
4198 bitmap_initialize (&exit_block_uses
, &df_bitmap_obstack
);
4199 df_get_exit_block_use_set (&exit_block_uses
);
4201 is_eq
= bitmap_equal_p (&exit_block_uses
, df
->exit_block_uses
);
4203 if (!is_eq
&& abort_if_fail
)
4205 fprintf (stderr
, "exit_block_uses = ");
4206 df_print_regset (stderr
, &exit_block_uses
);
4207 fprintf (stderr
, "df->exit_block_uses = ");
4208 df_print_regset (stderr
, df
->exit_block_uses
);
4212 bitmap_clear (&exit_block_uses
);
4218 /* Return true if df_ref information for all insns in all blocks are
4219 correct and complete. */
4222 df_scan_verify (void)
4226 bitmap_head regular_block_artificial_uses
;
4227 bitmap_head eh_block_artificial_uses
;
4232 /* Verification is a 4 step process. */
4234 /* (1) All of the refs are marked by going through the reg chains. */
4235 for (i
= 0; i
< DF_REG_SIZE (df
); i
++)
4237 gcc_assert (df_reg_chain_mark (DF_REG_DEF_CHAIN (i
), i
, true, false)
4238 == DF_REG_DEF_COUNT (i
));
4239 gcc_assert (df_reg_chain_mark (DF_REG_USE_CHAIN (i
), i
, false, false)
4240 == DF_REG_USE_COUNT (i
));
4241 gcc_assert (df_reg_chain_mark (DF_REG_EQ_USE_CHAIN (i
), i
, false, true)
4242 == DF_REG_EQ_USE_COUNT (i
));
4245 /* (2) There are various bitmaps whose value may change over the
4246 course of the compilation. This step recomputes them to make
4247 sure that they have not slipped out of date. */
4248 bitmap_initialize (®ular_block_artificial_uses
, &df_bitmap_obstack
);
4249 bitmap_initialize (&eh_block_artificial_uses
, &df_bitmap_obstack
);
4251 df_get_regular_block_artificial_uses (®ular_block_artificial_uses
);
4252 df_get_eh_block_artificial_uses (&eh_block_artificial_uses
);
4254 bitmap_ior_into (&eh_block_artificial_uses
,
4255 ®ular_block_artificial_uses
);
4257 /* Check artificial_uses bitmaps didn't change. */
4258 gcc_assert (bitmap_equal_p (®ular_block_artificial_uses
,
4259 &df
->regular_block_artificial_uses
));
4260 gcc_assert (bitmap_equal_p (&eh_block_artificial_uses
,
4261 &df
->eh_block_artificial_uses
));
4263 bitmap_clear (®ular_block_artificial_uses
);
4264 bitmap_clear (&eh_block_artificial_uses
);
4266 /* Verify entry block and exit block. These only verify the bitmaps,
4267 the refs are verified in df_bb_verify. */
4268 df_entry_block_bitmap_verify (true);
4269 df_exit_block_bitmap_verify (true);
4271 /* (3) All of the insns in all of the blocks are traversed and the
4272 marks are cleared both in the artificial refs attached to the
4273 blocks and the real refs inside the insns. It is a failure to
4274 clear a mark that has not been set as this means that the ref in
4275 the block or insn was not in the reg chain. */
4277 FOR_ALL_BB_FN (bb
, cfun
)
4280 /* (4) See if all reg chains are traversed a second time. This time
4281 a check is made that the marks are clear. A set mark would be a
4282 from a reg that is not in any insn or basic block. */
4284 for (i
= 0; i
< DF_REG_SIZE (df
); i
++)
4286 df_reg_chain_verify_unmarked (DF_REG_DEF_CHAIN (i
));
4287 df_reg_chain_verify_unmarked (DF_REG_USE_CHAIN (i
));
4288 df_reg_chain_verify_unmarked (DF_REG_EQ_USE_CHAIN (i
));