1/* Scanning of rtl for dataflow analysis.
2   Copyright (C) 2007-2020 Free Software Foundation, Inc.
3   Contributed by Kenneth Zadeck (zadeck@naturalbridge.com).
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3.  If not see
19<http://www.gnu.org/licenses/>.  */
20
21
22#include "config.h"
23#include "system.h"
24#include "coretypes.h"
25#include "backend.h"
26#include "rtl.h"
27#include "predict.h"
28#include "df.h"
29#include "regs.h"
30
31
32struct regstat_n_sets_and_refs_t *regstat_n_sets_and_refs;
33
34/*----------------------------------------------------------------------------
35   REG_N_SETS and REG_N_REFS.
36   ----------------------------------------------------------------------------*/
37
38/* If a pass need to change these values in some magical way or the
39   pass needs to have accurate values for these and is not using
40   incremental df scanning, then it should use REG_N_SETS and
41   REG_N_USES.  If the pass is doing incremental scanning then it
42   should be getting the info from DF_REG_DEF_COUNT and
43   DF_REG_USE_COUNT.  */
44
45void
46regstat_init_n_sets_and_refs (void)
47{
48  unsigned int i;
49  unsigned int max_regno = max_reg_num ();
50
51  timevar_push (TV_REG_STATS);
52  df_grow_reg_info ();
53  gcc_assert (!regstat_n_sets_and_refs);
54
55  regstat_n_sets_and_refs = XNEWVEC (struct regstat_n_sets_and_refs_t, max_regno);
56
57  if (MAY_HAVE_DEBUG_BIND_INSNS)
58    for (i = 0; i < max_regno; i++)
59      {
60	int use_count;
61	df_ref use;
62
63	use_count = DF_REG_USE_COUNT (i);
64	for (use = DF_REG_USE_CHAIN (i); use; use = DF_REF_NEXT_REG (use))
65	  if (DF_REF_INSN_INFO (use) && DEBUG_INSN_P (DF_REF_INSN (use)))
66	    use_count--;
67
68
69	SET_REG_N_SETS (i, DF_REG_DEF_COUNT (i));
70	SET_REG_N_REFS (i, use_count + REG_N_SETS (i));
71      }
72  else
73    for (i = 0; i < max_regno; i++)
74      {
75	SET_REG_N_SETS (i, DF_REG_DEF_COUNT (i));
76	SET_REG_N_REFS (i, DF_REG_USE_COUNT (i) + REG_N_SETS (i));
77      }
78  timevar_pop (TV_REG_STATS);
79
80}
81
82
83/* Free the array that holds the REG_N_SETS and REG_N_REFS.  */
84
85void
86regstat_free_n_sets_and_refs (void)
87{
88  gcc_assert (regstat_n_sets_and_refs);
89  free (regstat_n_sets_and_refs);
90  regstat_n_sets_and_refs = NULL;
91}
92
93
94/*----------------------------------------------------------------------------
95   REGISTER INFORMATION
96
97   Process REG_N_DEATHS, REG_N_CALLS_CROSSED, and REG_BASIC_BLOCK.
98
99   ----------------------------------------------------------------------------*/
100
101static bitmap setjmp_crosses;
102struct reg_info_t *reg_info_p;
103
104/* The number allocated elements of reg_info_p.  */
105size_t reg_info_p_size;
106
107/* Compute register info: lifetime, bb, and number of defs and uses
108   for basic block BB.  LIVE is a scratch bitvector used here.  */
109
110static void
111regstat_bb_compute_ri (basic_block bb, bitmap live)
112{
113  rtx_insn *insn;
114  df_ref def, use;
115  bitmap_iterator bi;
116  unsigned int regno;
117
118  bitmap_copy (live, df_get_live_out (bb));
119
120  /* Process the regs live at the end of the block.  Mark them as
121     not local to any one basic block.  */
122  EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi)
123    REG_BASIC_BLOCK (regno) = REG_BLOCK_GLOBAL;
124
125  /* Process the artificial defs and uses at the bottom of the block
126     to begin processing.  */
127  FOR_EACH_ARTIFICIAL_DEF (def, bb->index)
128    if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
129      bitmap_clear_bit (live, DF_REF_REGNO (def));
130
131  FOR_EACH_ARTIFICIAL_USE (use, bb->index)
132    if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
133      {
134	regno = DF_REF_REGNO (use);
135	bitmap_set_bit (live, regno);
136      }
137
138  FOR_BB_INSNS_REVERSE (bb, insn)
139    {
140      struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
141      bitmap_iterator bi;
142      rtx link;
143
144      if (!NONDEBUG_INSN_P (insn))
145	continue;
146
147      link = REG_NOTES (insn);
148      while (link)
149	{
150	  if (REG_NOTE_KIND (link) == REG_DEAD)
151	    REG_N_DEATHS (REGNO (XEXP (link, 0)))++;
152	  link = XEXP (link, 1);
153	}
154
155      /* Process the defs.  */
156      if (CALL_P (insn))
157	{
158	  bool set_jump = (find_reg_note (insn, REG_SETJMP, NULL) != NULL);
159	  EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi)
160	    {
161	      REG_N_CALLS_CROSSED (regno)++;
162
163	      /* We have a problem with any pseudoreg that lives
164		 across the setjmp.  ANSI says that if a user variable
165		 does not change in value between the setjmp and the
166		 longjmp, then the longjmp preserves it.  This
167		 includes longjmp from a place where the pseudo
168		 appears dead.  (In principle, the value still exists
169		 if it is in scope.)  If the pseudo goes in a hard
170		 reg, some other value may occupy that hard reg where
171		 this pseudo is dead, thus clobbering the pseudo.
172		 Conclusion: such a pseudo must not go in a hard
173		 reg.  */
174	      if (set_jump)
175		bitmap_set_bit (setjmp_crosses, regno);
176	    }
177	}
178
179      /* All of the defs except the return value are some sort of
180	 clobber.  This code is for the return.  */
181      FOR_EACH_INSN_INFO_DEF (def, insn_info)
182	{
183	  if ((!CALL_P (insn))
184	      || (!(DF_REF_FLAGS (def)
185		    & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))))
186	    {
187	      unsigned int dregno = DF_REF_REGNO (def);
188
189	      /* Kill this register if it is not a subreg store or
190		 conditional store.
191		 ??? This means that any partial store is live from
192		 the last use in a basic block to the start of this
193		 basic block.  */
194	      if (!(DF_REF_FLAGS (def)
195		    & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
196		bitmap_clear_bit (live, dregno);
197
198	      if (dregno >= FIRST_PSEUDO_REGISTER)
199		{
200		  REG_FREQ (dregno) += REG_FREQ_FROM_BB (bb);
201		  REG_FREQ (dregno) =
202		    MIN (REG_FREQ (dregno), REG_FREQ_MAX);
203
204		  if (REG_BASIC_BLOCK (dregno) == REG_BLOCK_UNKNOWN)
205		    REG_BASIC_BLOCK (dregno) = bb->index;
206		  else if (REG_BASIC_BLOCK (dregno) != bb->index)
207		    REG_BASIC_BLOCK (dregno) = REG_BLOCK_GLOBAL;
208		}
209	    }
210	}
211
212      FOR_EACH_INSN_INFO_USE (use, insn_info)
213	{
214	  unsigned int uregno = DF_REF_REGNO (use);
215
216	  if (uregno >= FIRST_PSEUDO_REGISTER)
217	    {
218	      REG_FREQ (uregno) += REG_FREQ_FROM_BB (bb);
219	      REG_FREQ (uregno) =
220		MIN (REG_FREQ (uregno), REG_FREQ_MAX);
221
222	      if (REG_BASIC_BLOCK (uregno) == REG_BLOCK_UNKNOWN)
223		REG_BASIC_BLOCK (uregno) = bb->index;
224	      else if (REG_BASIC_BLOCK (uregno) != bb->index)
225		REG_BASIC_BLOCK (uregno) = REG_BLOCK_GLOBAL;
226	    }
227	}
228    }
229}
230
231
232/* Compute register info: lifetime, bb, and number of defs and uses.  */
233void
234regstat_compute_ri (void)
235{
236  basic_block bb;
237  bitmap live = BITMAP_ALLOC (&df_bitmap_obstack);
238  unsigned int regno;
239  bitmap_iterator bi;
240
241  /* Initialize everything.  */
242
243  gcc_assert (!reg_info_p);
244
245  timevar_push (TV_REG_STATS);
246  setjmp_crosses = BITMAP_ALLOC (&df_bitmap_obstack);
247  max_regno = max_reg_num ();
248  reg_info_p_size = max_regno;
249  reg_info_p = XCNEWVEC (struct reg_info_t, max_regno);
250
251  FOR_EACH_BB_FN (bb, cfun)
252    {
253      regstat_bb_compute_ri (bb, live);
254    }
255
256  BITMAP_FREE (live);
257
258  /* See the setjmp comment in regstat_bb_compute_ri.  */
259  EXECUTE_IF_SET_IN_BITMAP (setjmp_crosses, FIRST_PSEUDO_REGISTER, regno, bi)
260    {
261      REG_BASIC_BLOCK (regno) = REG_BLOCK_UNKNOWN;
262    }
263
264  timevar_pop (TV_REG_STATS);
265}
266
267
268/* Free all storage associated with the problem.  */
269
270void
271regstat_free_ri (void)
272{
273  gcc_assert (reg_info_p);
274  reg_info_p_size = 0;
275  free (reg_info_p);
276  reg_info_p = NULL;
277
278  BITMAP_FREE (setjmp_crosses);
279}
280
281
282/* Return a bitmap containing the set of registers that cross a setjmp.
283   The client should not change or delete this bitmap.  */
284
285bitmap
286regstat_get_setjmp_crosses (void)
287{
288  return setjmp_crosses;
289}
290
291/*----------------------------------------------------------------------------
292   Process REG_N_CALLS_CROSSED.
293
294   This is used by sched_deps.  A good implementation of sched-deps
295   would really process the blocks directly rather than going through
296   lists of insns.  If it did this, it could use the exact regs that
297   cross an individual call rather than using this info that merges
298   the info for all calls.
299
300   ----------------------------------------------------------------------------*/
301
302
303
304/* Compute calls crossed for BB. Live is a scratch bitvector.  */
305
306static void
307regstat_bb_compute_calls_crossed (unsigned int bb_index, bitmap live)
308{
309  basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
310  rtx_insn *insn;
311  df_ref def, use;
312
313  bitmap_copy (live, df_get_live_out (bb));
314
315  /* Process the artificial defs and uses at the bottom of the block
316     to begin processing.  */
317  FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
318    if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
319      bitmap_clear_bit (live, DF_REF_REGNO (def));
320
321  FOR_EACH_ARTIFICIAL_USE (use, bb_index)
322    if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
323      bitmap_set_bit (live, DF_REF_REGNO (use));
324
325  FOR_BB_INSNS_REVERSE (bb, insn)
326    {
327      if (!NONDEBUG_INSN_P (insn))
328	continue;
329
330      gcc_assert (INSN_UID (insn) < (int) DF_INSN_SIZE ());
331      struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
332      unsigned int regno;
333
334      /* Process the defs.  */
335      if (CALL_P (insn))
336	{
337	  bitmap_iterator bi;
338	  EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi)
339	    {
340	      REG_N_CALLS_CROSSED (regno)++;
341	    }
342	}
343
344      /* All of the defs except the return value are some sort of
345	 clobber.  This code is for the return.  */
346      FOR_EACH_INSN_INFO_DEF (def, insn_info)
347	{
348	  if ((!CALL_P (insn))
349	      || (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))))
350	    {
351	      /* Kill this register if it is not a subreg store or conditional store.  */
352	      if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
353		bitmap_clear_bit (live, DF_REF_REGNO (def));
354	    }
355	}
356
357      FOR_EACH_INSN_INFO_USE (use, insn_info)
358	bitmap_set_bit (live, DF_REF_REGNO (use));
359    }
360}
361
362
363/* Compute register info: lifetime, bb, and number of defs and uses.  */
364void
365regstat_compute_calls_crossed (void)
366{
367  basic_block bb;
368  bitmap live = BITMAP_ALLOC (&df_bitmap_obstack);
369
370  /* Initialize everything.  */
371  gcc_assert (!reg_info_p);
372
373  timevar_push (TV_REG_STATS);
374  max_regno = max_reg_num ();
375  reg_info_p_size = max_regno;
376  reg_info_p = XCNEWVEC (struct reg_info_t, max_regno);
377
378  FOR_EACH_BB_FN (bb, cfun)
379    {
380      regstat_bb_compute_calls_crossed (bb->index, live);
381    }
382
383  BITMAP_FREE (live);
384  timevar_pop (TV_REG_STATS);
385}
386
387
388/* Free all storage associated with the problem.  */
389
390void
391regstat_free_calls_crossed (void)
392{
393  gcc_assert (reg_info_p);
394  reg_info_p_size = 0;
395  free (reg_info_p);
396  reg_info_p = NULL;
397}
398
399/* Dump the register info to FILE.  */
400
401void
402dump_reg_info (FILE *file)
403{
404  unsigned int i, max = max_reg_num ();
405  if (reload_completed)
406    return;
407
408  if (reg_info_p_size < max)
409    max = reg_info_p_size;
410
411  fprintf (file, "%d registers.\n", max);
412  for (i = FIRST_PSEUDO_REGISTER; i < max; i++)
413    {
414      enum reg_class rclass, altclass;
415
416      if (regstat_n_sets_and_refs)
417	fprintf (file, "\nRegister %d used %d times",
418		 i, REG_N_REFS (i));
419      else if (df)
420	fprintf (file, "\nRegister %d used %d times",
421		 i, DF_REG_USE_COUNT (i) + DF_REG_DEF_COUNT (i));
422
423      if (REG_BASIC_BLOCK (i) >= NUM_FIXED_BLOCKS)
424	fprintf (file, " in block %d", REG_BASIC_BLOCK (i));
425      if (regstat_n_sets_and_refs)
426	fprintf (file, "; set %d time%s", REG_N_SETS (i),
427		 (REG_N_SETS (i) == 1) ? "" : "s");
428      else if (df)
429	fprintf (file, "; set %d time%s", DF_REG_DEF_COUNT (i),
430		 (DF_REG_DEF_COUNT (i) == 1) ? "" : "s");
431      if (regno_reg_rtx[i] != NULL && REG_USERVAR_P (regno_reg_rtx[i]))
432	fputs ("; user var", file);
433      if (REG_N_DEATHS (i) != 1)
434	fprintf (file, "; dies in %d places", REG_N_DEATHS (i));
435      if (REG_N_CALLS_CROSSED (i) == 1)
436	fputs ("; crosses 1 call", file);
437      else if (REG_N_CALLS_CROSSED (i))
438	fprintf (file, "; crosses %d calls", REG_N_CALLS_CROSSED (i));
439      if (regno_reg_rtx[i] != NULL
440	  && maybe_ne (PSEUDO_REGNO_BYTES (i), UNITS_PER_WORD))
441	{
442	  fprintf (file, "; ");
443	  print_dec (PSEUDO_REGNO_BYTES (i), file, SIGNED);
444	  fprintf (file, " bytes");
445	}
446
447      rclass = reg_preferred_class (i);
448      altclass = reg_alternate_class (i);
449      if (rclass != GENERAL_REGS || altclass != ALL_REGS)
450	{
451	  if (altclass == ALL_REGS || rclass == ALL_REGS)
452	    fprintf (file, "; pref %s", reg_class_names[(int) rclass]);
453	  else if (altclass == NO_REGS)
454	    fprintf (file, "; %s or none", reg_class_names[(int) rclass]);
455	  else
456	    fprintf (file, "; pref %s, else %s",
457		     reg_class_names[(int) rclass],
458		     reg_class_names[(int) altclass]);
459	}
460
461      if (regno_reg_rtx[i] != NULL && REG_POINTER (regno_reg_rtx[i]))
462	fputs ("; pointer", file);
463      fputs (".\n", file);
464    }
465}
466
467