1 /* Scanning of rtl for dataflow analysis.
2 Copyright (C) 2007-2013 Free Software Foundation, Inc.
3 Contributed by Kenneth Zadeck (zadeck@naturalbridge.com).
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
31 #include "hard-reg-set.h"
32 #include "basic-block.h"
37 struct regstat_n_sets_and_refs_t
*regstat_n_sets_and_refs
;
39 /*----------------------------------------------------------------------------
40 REG_N_SETS and REG_N_REFS.
41 ----------------------------------------------------------------------------*/
43 /* If a pass need to change these values in some magical way or the
44 pass needs to have accurate values for these and is not using
45 incremental df scanning, then it should use REG_N_SETS and
46 REG_N_USES. If the pass is doing incremental scanning then it
47 should be getting the info from DF_REG_DEF_COUNT and
51 regstat_init_n_sets_and_refs (void)
54 unsigned int max_regno
= max_reg_num ();
56 timevar_push (TV_REG_STATS
);
58 gcc_assert (!regstat_n_sets_and_refs
);
60 regstat_n_sets_and_refs
= XNEWVEC (struct regstat_n_sets_and_refs_t
, max_regno
);
62 if (MAY_HAVE_DEBUG_INSNS
)
63 for (i
= 0; i
< max_regno
; i
++)
68 use_count
= DF_REG_USE_COUNT (i
);
69 for (use
= DF_REG_USE_CHAIN (i
); use
; use
= DF_REF_NEXT_REG (use
))
70 if (DF_REF_INSN_INFO (use
) && DEBUG_INSN_P (DF_REF_INSN (use
)))
74 SET_REG_N_SETS (i
, DF_REG_DEF_COUNT (i
));
75 SET_REG_N_REFS (i
, use_count
+ REG_N_SETS (i
));
78 for (i
= 0; i
< max_regno
; i
++)
80 SET_REG_N_SETS (i
, DF_REG_DEF_COUNT (i
));
81 SET_REG_N_REFS (i
, DF_REG_USE_COUNT (i
) + REG_N_SETS (i
));
83 timevar_pop (TV_REG_STATS
);
88 /* Free the array that holds the REG_N_SETS and REG_N_REFS. */
91 regstat_free_n_sets_and_refs (void)
93 gcc_assert (regstat_n_sets_and_refs
);
94 free (regstat_n_sets_and_refs
);
95 regstat_n_sets_and_refs
= NULL
;
99 /*----------------------------------------------------------------------------
102 Process REG_N_DEATHS, REG_LIVE_LENGTH, REG_N_CALLS_CROSSED,
103 REG_N_THROWING_CALLS_CROSSED and REG_BASIC_BLOCK.
105 ----------------------------------------------------------------------------*/
107 static bitmap setjmp_crosses
;
108 struct reg_info_t
*reg_info_p
;
110 /* The number allocated elements of reg_info_p. */
111 size_t reg_info_p_size
;
113 /* Compute register info: lifetime, bb, and number of defs and uses
114 for basic block BB. The three bitvectors are scratch regs used
118 regstat_bb_compute_ri (unsigned int bb_index
,
119 bitmap live
, bitmap artificial_uses
,
120 bitmap local_live
, bitmap local_processed
,
121 int *local_live_last_luid
)
123 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, bb_index
);
131 bitmap_copy (live
, df_get_live_out (bb
));
132 bitmap_clear (artificial_uses
);
134 /* Process the regs live at the end of the block. Mark them as
135 not local to any one basic block. */
136 EXECUTE_IF_SET_IN_BITMAP (live
, 0, regno
, bi
)
137 REG_BASIC_BLOCK (regno
) = REG_BLOCK_GLOBAL
;
139 /* Process the artificial defs and uses at the bottom of the block
140 to begin processing. */
141 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
143 df_ref def
= *def_rec
;
144 if ((DF_REF_FLAGS (def
) & DF_REF_AT_TOP
) == 0)
145 bitmap_clear_bit (live
, DF_REF_REGNO (def
));
148 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
150 df_ref use
= *use_rec
;
151 if ((DF_REF_FLAGS (use
) & DF_REF_AT_TOP
) == 0)
153 regno
= DF_REF_REGNO (use
);
154 bitmap_set_bit (live
, regno
);
155 bitmap_set_bit (artificial_uses
, regno
);
159 FOR_BB_INSNS_REVERSE (bb
, insn
)
161 unsigned int uid
= INSN_UID (insn
);
163 struct df_mw_hardreg
**mws_rec
;
166 if (!NONDEBUG_INSN_P (insn
))
171 link
= REG_NOTES (insn
);
174 if (REG_NOTE_KIND (link
) == REG_DEAD
)
175 REG_N_DEATHS (REGNO (XEXP (link
, 0)))++;
176 link
= XEXP (link
, 1);
179 /* Process the defs. */
182 bool can_throw
= can_throw_internal (insn
);
183 bool set_jump
= (find_reg_note (insn
, REG_SETJMP
, NULL
) != NULL
);
184 EXECUTE_IF_SET_IN_BITMAP (live
, 0, regno
, bi
)
186 REG_N_CALLS_CROSSED (regno
)++;
187 REG_FREQ_CALLS_CROSSED (regno
) += REG_FREQ_FROM_BB (bb
);
188 REG_FREQ_CALLS_CROSSED (regno
) =
189 MIN (REG_FREQ_CALLS_CROSSED (regno
), REG_FREQ_MAX
);
191 REG_N_THROWING_CALLS_CROSSED (regno
)++;
193 /* We have a problem with any pseudoreg that lives
194 across the setjmp. ANSI says that if a user variable
195 does not change in value between the setjmp and the
196 longjmp, then the longjmp preserves it. This
197 includes longjmp from a place where the pseudo
198 appears dead. (In principle, the value still exists
199 if it is in scope.) If the pseudo goes in a hard
200 reg, some other value may occupy that hard reg where
201 this pseudo is dead, thus clobbering the pseudo.
202 Conclusion: such a pseudo must not go in a hard
205 bitmap_set_bit (setjmp_crosses
, regno
);
209 /* We only care about real sets for calls. Clobbers cannot
211 Only do this if the value is totally dead. */
212 for (mws_rec
= DF_INSN_UID_MWS (uid
); *mws_rec
; mws_rec
++)
214 struct df_mw_hardreg
*mws
= *mws_rec
;
215 if (DF_MWS_REG_DEF_P (mws
))
217 bool all_dead
= true;
220 for (r
= mws
->start_regno
; r
<= mws
->end_regno
; r
++)
221 if (bitmap_bit_p (artificial_uses
, r
)
222 || bitmap_bit_p (live
, r
))
230 regno
= mws
->start_regno
;
231 REG_LIVE_LENGTH (regno
)++;
236 /* All of the defs except the return value are some sort of
237 clobber. This code is for the return. */
238 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
240 df_ref def
= *def_rec
;
242 || (!(DF_REF_FLAGS (def
) & (DF_REF_MUST_CLOBBER
| DF_REF_MAY_CLOBBER
))))
244 unsigned int dregno
= DF_REF_REGNO (def
);
246 if (bitmap_bit_p (live
, dregno
))
248 /* If we have seen a use of DREGNO somewhere before (i.e.
249 later in this basic block), and DEF is not a subreg
250 store or conditional store, then kill the register
251 here and add the proper length to its REG_LIVE_LENGTH.
253 If we have not seen a use of DREGNO later in this basic
254 block, then we need to add the length from here to the
255 end of the block to the live length. */
256 if (bitmap_bit_p (local_live
, dregno
))
258 /* Note that LOCAL_LIVE implies LOCAL_PROCESSED, so
259 we don't have to set LOCAL_PROCESSED in this clause. */
260 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
262 REG_LIVE_LENGTH (dregno
) +=
263 (luid
- local_live_last_luid
[dregno
]);
264 local_live_last_luid
[dregno
] = luid
;
265 bitmap_clear_bit (local_live
, dregno
);
270 bitmap_set_bit (local_processed
, dregno
);
271 REG_LIVE_LENGTH (dregno
) += luid
;
272 local_live_last_luid
[dregno
] = luid
;
275 /* Kill this register if it is not a subreg store or
277 ??? This means that any partial store is live from
278 the last use in a basic block to the start of this
279 basic block. This results in poor calculations of
280 REG_LIVE_LENGTH in large basic blocks. */
281 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
282 bitmap_clear_bit (live
, dregno
);
284 else if ((!(DF_REF_FLAGS (def
) & DF_REF_MW_HARDREG
))
285 && (!bitmap_bit_p (artificial_uses
, dregno
)))
287 REG_LIVE_LENGTH (dregno
)++;
290 if (dregno
>= FIRST_PSEUDO_REGISTER
)
292 REG_FREQ (dregno
) += REG_FREQ_FROM_BB (bb
);
294 MIN (REG_FREQ (dregno
), REG_FREQ_MAX
);
296 if (REG_BASIC_BLOCK (dregno
) == REG_BLOCK_UNKNOWN
)
297 REG_BASIC_BLOCK (dregno
) = bb
->index
;
298 else if (REG_BASIC_BLOCK (dregno
) != bb
->index
)
299 REG_BASIC_BLOCK (dregno
) = REG_BLOCK_GLOBAL
;
304 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
306 df_ref use
= *use_rec
;
307 unsigned int uregno
= DF_REF_REGNO (use
);
309 if (uregno
>= FIRST_PSEUDO_REGISTER
)
311 REG_FREQ (uregno
) += REG_FREQ_FROM_BB (bb
);
313 MIN (REG_FREQ (uregno
), REG_FREQ_MAX
);
315 if (REG_BASIC_BLOCK (uregno
) == REG_BLOCK_UNKNOWN
)
316 REG_BASIC_BLOCK (uregno
) = bb
->index
;
317 else if (REG_BASIC_BLOCK (uregno
) != bb
->index
)
318 REG_BASIC_BLOCK (uregno
) = REG_BLOCK_GLOBAL
;
321 if (bitmap_set_bit (live
, uregno
))
323 /* This register is now live. Begin to process it locally.
325 Note that we don't even get here if the variable was live
326 at the end of the block since just a ref inside the block
327 does not effect the calculations. */
328 REG_LIVE_LENGTH (uregno
) ++;
329 local_live_last_luid
[uregno
] = luid
;
330 bitmap_set_bit (local_live
, uregno
);
331 bitmap_set_bit (local_processed
, uregno
);
336 /* Add the liveness length to all registers that were used somewhere
337 in this bock, but not between that use and the head of this block. */
338 EXECUTE_IF_SET_IN_BITMAP (local_live
, 0, regno
, bi
)
340 REG_LIVE_LENGTH (regno
) += (luid
- local_live_last_luid
[regno
]);
343 /* Add the length of the block to all of the registers that were not
344 referenced, but still live in this block. */
345 bitmap_and_compl_into (live
, local_processed
);
346 EXECUTE_IF_SET_IN_BITMAP (live
, 0, regno
, bi
)
347 REG_LIVE_LENGTH (regno
) += luid
;
349 bitmap_clear (local_processed
);
350 bitmap_clear (local_live
);
354 /* Compute register info: lifetime, bb, and number of defs and uses. */
356 regstat_compute_ri (void)
359 bitmap live
= BITMAP_ALLOC (&df_bitmap_obstack
);
360 bitmap artificial_uses
= BITMAP_ALLOC (&df_bitmap_obstack
);
361 bitmap local_live
= BITMAP_ALLOC (&df_bitmap_obstack
);
362 bitmap local_processed
= BITMAP_ALLOC (&df_bitmap_obstack
);
365 int *local_live_last_luid
;
367 /* Initialize everything. */
369 gcc_assert (!reg_info_p
);
371 timevar_push (TV_REG_STATS
);
372 setjmp_crosses
= BITMAP_ALLOC (&df_bitmap_obstack
);
373 max_regno
= max_reg_num ();
374 reg_info_p_size
= max_regno
;
375 reg_info_p
= XCNEWVEC (struct reg_info_t
, max_regno
);
376 local_live_last_luid
= XNEWVEC (int, max_regno
);
378 FOR_EACH_BB_FN (bb
, cfun
)
380 regstat_bb_compute_ri (bb
->index
, live
, artificial_uses
,
381 local_live
, local_processed
,
382 local_live_last_luid
);
386 BITMAP_FREE (artificial_uses
);
387 BITMAP_FREE (local_live
);
388 BITMAP_FREE (local_processed
);
389 free (local_live_last_luid
);
391 /* See the setjmp comment in regstat_bb_compute_ri. */
392 EXECUTE_IF_SET_IN_BITMAP (setjmp_crosses
, FIRST_PSEUDO_REGISTER
, regno
, bi
)
394 REG_BASIC_BLOCK (regno
) = REG_BLOCK_UNKNOWN
;
395 REG_LIVE_LENGTH (regno
) = -1;
398 timevar_pop (TV_REG_STATS
);
402 /* Free all storage associated with the problem. */
405 regstat_free_ri (void)
407 gcc_assert (reg_info_p
);
412 BITMAP_FREE (setjmp_crosses
);
416 /* Return a bitmap containing the set of registers that cross a setjmp.
417 The client should not change or delete this bitmap. */
420 regstat_get_setjmp_crosses (void)
422 return setjmp_crosses
;
425 /*----------------------------------------------------------------------------
426 Process REG_N_CALLS_CROSSED.
428 This is used by sched_deps. A good implementation of sched-deps
429 would really process the blocks directly rather than going through
430 lists of insns. If it did this, it could use the exact regs that
431 cross an individual call rather than using this info that merges
432 the info for all calls.
434 ----------------------------------------------------------------------------*/
438 /* Compute calls crossed for BB. Live is a scratch bitvector. */
441 regstat_bb_compute_calls_crossed (unsigned int bb_index
, bitmap live
)
443 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, bb_index
);
448 bitmap_copy (live
, df_get_live_out (bb
));
450 /* Process the artificial defs and uses at the bottom of the block
451 to begin processing. */
452 for (def_rec
= df_get_artificial_defs (bb_index
); *def_rec
; def_rec
++)
454 df_ref def
= *def_rec
;
455 if ((DF_REF_FLAGS (def
) & DF_REF_AT_TOP
) == 0)
456 bitmap_clear_bit (live
, DF_REF_REGNO (def
));
459 for (use_rec
= df_get_artificial_uses (bb_index
); *use_rec
; use_rec
++)
461 df_ref use
= *use_rec
;
462 if ((DF_REF_FLAGS (use
) & DF_REF_AT_TOP
) == 0)
463 bitmap_set_bit (live
, DF_REF_REGNO (use
));
466 FOR_BB_INSNS_REVERSE (bb
, insn
)
468 unsigned int uid
= INSN_UID (insn
);
474 /* Process the defs. */
478 EXECUTE_IF_SET_IN_BITMAP (live
, 0, regno
, bi
)
480 REG_N_CALLS_CROSSED (regno
)++;
481 REG_FREQ_CALLS_CROSSED (regno
) += REG_FREQ_FROM_BB (bb
);
482 REG_FREQ_CALLS_CROSSED (regno
) =
483 MIN (REG_FREQ_CALLS_CROSSED (regno
), REG_FREQ_MAX
);
487 /* All of the defs except the return value are some sort of
488 clobber. This code is for the return. */
489 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
491 df_ref def
= *def_rec
;
493 || (!(DF_REF_FLAGS (def
) & (DF_REF_MUST_CLOBBER
| DF_REF_MAY_CLOBBER
))))
495 /* Kill this register if it is not a subreg store or conditional store. */
496 if (!(DF_REF_FLAGS (def
) & (DF_REF_PARTIAL
| DF_REF_CONDITIONAL
)))
497 bitmap_clear_bit (live
, DF_REF_REGNO (def
));
501 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
503 df_ref use
= *use_rec
;
504 bitmap_set_bit (live
, DF_REF_REGNO (use
));
510 /* Compute register info: lifetime, bb, and number of defs and uses. */
512 regstat_compute_calls_crossed (void)
515 bitmap live
= BITMAP_ALLOC (&df_bitmap_obstack
);
517 /* Initialize everything. */
518 gcc_assert (!reg_info_p
);
520 timevar_push (TV_REG_STATS
);
521 max_regno
= max_reg_num ();
522 reg_info_p_size
= max_regno
;
523 reg_info_p
= XCNEWVEC (struct reg_info_t
, max_regno
);
525 FOR_EACH_BB_FN (bb
, cfun
)
527 regstat_bb_compute_calls_crossed (bb
->index
, live
);
531 timevar_pop (TV_REG_STATS
);
535 /* Free all storage associated with the problem. */
538 regstat_free_calls_crossed (void)
540 gcc_assert (reg_info_p
);
546 /* Dump the register info to FILE. */
549 dump_reg_info (FILE *file
)
551 unsigned int i
, max
= max_reg_num ();
552 if (reload_completed
)
555 if (reg_info_p_size
< max
)
556 max
= reg_info_p_size
;
558 fprintf (file
, "%d registers.\n", max
);
559 for (i
= FIRST_PSEUDO_REGISTER
; i
< max
; i
++)
561 enum reg_class rclass
, altclass
;
563 if (regstat_n_sets_and_refs
)
564 fprintf (file
, "\nRegister %d used %d times across %d insns",
565 i
, REG_N_REFS (i
), REG_LIVE_LENGTH (i
));
567 fprintf (file
, "\nRegister %d used %d times across %d insns",
568 i
, DF_REG_USE_COUNT (i
) + DF_REG_DEF_COUNT (i
), REG_LIVE_LENGTH (i
));
570 if (REG_BASIC_BLOCK (i
) >= NUM_FIXED_BLOCKS
)
571 fprintf (file
, " in block %d", REG_BASIC_BLOCK (i
));
572 if (regstat_n_sets_and_refs
)
573 fprintf (file
, "; set %d time%s", REG_N_SETS (i
),
574 (REG_N_SETS (i
) == 1) ? "" : "s");
576 fprintf (file
, "; set %d time%s", DF_REG_DEF_COUNT (i
),
577 (DF_REG_DEF_COUNT (i
) == 1) ? "" : "s");
578 if (regno_reg_rtx
[i
] != NULL
&& REG_USERVAR_P (regno_reg_rtx
[i
]))
579 fputs ("; user var", file
);
580 if (REG_N_DEATHS (i
) != 1)
581 fprintf (file
, "; dies in %d places", REG_N_DEATHS (i
));
582 if (REG_N_CALLS_CROSSED (i
) == 1)
583 fputs ("; crosses 1 call", file
);
584 else if (REG_N_CALLS_CROSSED (i
))
585 fprintf (file
, "; crosses %d calls", REG_N_CALLS_CROSSED (i
));
586 if (REG_FREQ_CALLS_CROSSED (i
))
587 fprintf (file
, "; crosses call with %d frequency", REG_FREQ_CALLS_CROSSED (i
));
588 if (regno_reg_rtx
[i
] != NULL
589 && PSEUDO_REGNO_BYTES (i
) != UNITS_PER_WORD
)
590 fprintf (file
, "; %d bytes", PSEUDO_REGNO_BYTES (i
));
592 rclass
= reg_preferred_class (i
);
593 altclass
= reg_alternate_class (i
);
594 if (rclass
!= GENERAL_REGS
|| altclass
!= ALL_REGS
)
596 if (altclass
== ALL_REGS
|| rclass
== ALL_REGS
)
597 fprintf (file
, "; pref %s", reg_class_names
[(int) rclass
]);
598 else if (altclass
== NO_REGS
)
599 fprintf (file
, "; %s or none", reg_class_names
[(int) rclass
]);
601 fprintf (file
, "; pref %s, else %s",
602 reg_class_names
[(int) rclass
],
603 reg_class_names
[(int) altclass
]);
606 if (regno_reg_rtx
[i
] != NULL
&& REG_POINTER (regno_reg_rtx
[i
]))
607 fputs ("; pointer", file
);