1/* Scanning of rtl for dataflow analysis.
2   Copyright (C) 2007, 2008, 2009
3   Free Software Foundation, Inc.
4   Contributed by Kenneth Zadeck (zadeck@naturalbridge.com).
5
6This file is part of GCC.
7
8GCC is free software; you can redistribute it and/or modify it under
9the terms of the GNU General Public License as published by the Free
10Software Foundation; either version 3, or (at your option) any later
11version.
12
13GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14WARRANTY; without even the implied warranty of MERCHANTABILITY or
15FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16for more details.
17
18You should have received a copy of the GNU General Public License
19along with GCC; see the file COPYING3.  If not see
20<http://www.gnu.org/licenses/>.  */
21
22
23#include "config.h"
24#include "system.h"
25#include "coretypes.h"
26#include "tm.h"
27#include "rtl.h"
28#include "tm_p.h"
29#include "flags.h"
30#include "regs.h"
31#include "output.h"
32#include "except.h"
33#include "hard-reg-set.h"
34#include "basic-block.h"
35#include "timevar.h"
36#include "df.h"
37
38
39struct regstat_n_sets_and_refs_t *regstat_n_sets_and_refs;
40
41/*----------------------------------------------------------------------------
42   REG_N_SETS and REG_N_REFS.
43   ----------------------------------------------------------------------------*/
44
45/* If a pass need to change these values in some magical way or or the
46   pass needs to have accurate values for these and is not using
47   incremental df scanning, then it should use REG_N_SETS and
48   REG_N_USES.  If the pass is doing incremental scanning then it
49   should be getting the info from DF_REG_DEF_COUNT and
50   DF_REG_USE_COUNT.  */
51
52void
53regstat_init_n_sets_and_refs (void)
54{
55  unsigned int i;
56  unsigned int max_regno = max_reg_num ();
57
58  timevar_push (TV_REG_STATS);
59  df_grow_reg_info ();
60  gcc_assert (!regstat_n_sets_and_refs);
61
62  regstat_n_sets_and_refs = XNEWVEC (struct regstat_n_sets_and_refs_t, max_regno);
63
64  if (MAY_HAVE_DEBUG_INSNS)
65    for (i = 0; i < max_regno; i++)
66      {
67	int use_count;
68	df_ref use;
69
70	use_count = DF_REG_USE_COUNT (i);
71	for (use = DF_REG_USE_CHAIN (i); use; use = DF_REF_NEXT_REG (use))
72	  if (DF_REF_INSN_INFO (use) && DEBUG_INSN_P (DF_REF_INSN (use)))
73	    use_count--;
74
75
76	SET_REG_N_SETS (i, DF_REG_DEF_COUNT (i));
77	SET_REG_N_REFS (i, use_count + REG_N_SETS (i));
78      }
79  else
80    for (i = 0; i < max_regno; i++)
81      {
82	SET_REG_N_SETS (i, DF_REG_DEF_COUNT (i));
83	SET_REG_N_REFS (i, DF_REG_USE_COUNT (i) + REG_N_SETS (i));
84      }
85  timevar_pop (TV_REG_STATS);
86
87}
88
89
90/* Free the array that holds the REG_N_SETS and REG_N_REFS.  */
91
92void
93regstat_free_n_sets_and_refs (void)
94{
95  gcc_assert (regstat_n_sets_and_refs);
96  free (regstat_n_sets_and_refs);
97  regstat_n_sets_and_refs = NULL;
98}
99
100
101/*----------------------------------------------------------------------------
102   REGISTER INFORMATION
103
104   Process REG_N_DEATHS, REG_LIVE_LENGTH, REG_N_CALLS_CROSSED,
105   REG_N_THROWING_CALLS_CROSSED and REG_BASIC_BLOCK.
106
107   ----------------------------------------------------------------------------*/
108
109static bitmap setjmp_crosses;
110struct reg_info_t *reg_info_p;
111
112/* The number allocated elements of reg_info_p.  */
113size_t reg_info_p_size;
114
115/* Compute register info: lifetime, bb, and number of defs and uses
116   for basic block BB.  The three bitvectors are scratch regs used
117   here.  */
118
119static void
120regstat_bb_compute_ri (unsigned int bb_index,
121		       bitmap live, bitmap do_not_gen, bitmap artificial_uses,
122		       bitmap local_live, bitmap local_processed)
123{
124  basic_block bb = BASIC_BLOCK (bb_index);
125  rtx insn;
126  df_ref *def_rec;
127  df_ref *use_rec;
128  int luid = 0;
129  bitmap_iterator bi;
130  unsigned int regno;
131
132  bitmap_copy (live, df_get_live_out (bb));
133  bitmap_clear (artificial_uses);
134
135  /* Process the regs live at the end of the block.  Mark them as
136     not local to any one basic block.  */
137  EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi)
138    REG_BASIC_BLOCK (regno) = REG_BLOCK_GLOBAL;
139
140  /* Process the artificial defs and uses at the bottom of the block
141     to begin processing.  */
142  for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
143    {
144      df_ref def = *def_rec;
145      if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
146	bitmap_clear_bit (live, DF_REF_REGNO (def));
147    }
148
149  for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
150    {
151      df_ref use = *use_rec;
152      if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
153	{
154	  regno = DF_REF_REGNO (use);
155	  bitmap_set_bit (live, regno);
156	  bitmap_set_bit (artificial_uses, regno);
157	}
158    }
159
160  FOR_BB_INSNS_REVERSE (bb, insn)
161    {
162      unsigned int uid = INSN_UID (insn);
163      unsigned int regno;
164      bitmap_iterator bi;
165      struct df_mw_hardreg **mws_rec;
166      rtx link;
167
168      if (!NONDEBUG_INSN_P (insn))
169	continue;
170
171      /* Increment the live_length for all of the registers that
172	 are are referenced in this block and live at this
173	 particular point.  */
174      EXECUTE_IF_SET_IN_BITMAP (local_live, 0, regno, bi)
175	{
176	  REG_LIVE_LENGTH (regno)++;
177	}
178      luid++;
179
180      bitmap_clear (do_not_gen);
181
182      link = REG_NOTES (insn);
183      while (link)
184	{
185	  if (REG_NOTE_KIND (link) == REG_DEAD)
186	    REG_N_DEATHS(REGNO (XEXP (link, 0)))++;
187	  link = XEXP (link, 1);
188	}
189
190      /* Process the defs.  */
191      if (CALL_P (insn))
192	{
193	  bool can_throw = can_throw_internal (insn);
194	  bool set_jump = (find_reg_note (insn, REG_SETJMP, NULL) != NULL);
195	  EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi)
196	    {
197	      REG_N_CALLS_CROSSED (regno)++;
198	      REG_FREQ_CALLS_CROSSED (regno) += REG_FREQ_FROM_BB (bb);
199	      if (can_throw)
200		REG_N_THROWING_CALLS_CROSSED (regno)++;
201
202	      /* We have a problem with any pseudoreg that lives
203		 across the setjmp.  ANSI says that if a user variable
204		 does not change in value between the setjmp and the
205		 longjmp, then the longjmp preserves it.  This
206		 includes longjmp from a place where the pseudo
207		 appears dead.  (In principle, the value still exists
208		 if it is in scope.)  If the pseudo goes in a hard
209		 reg, some other value may occupy that hard reg where
210		 this pseudo is dead, thus clobbering the pseudo.
211		 Conclusion: such a pseudo must not go in a hard
212		 reg.  */
213	      if (set_jump)
214		bitmap_set_bit (setjmp_crosses, regno);
215	    }
216	}
217
218      /* We only care about real sets for calls.  Clobbers only
219	 may clobbers cannot be depended on.  */
220      for (mws_rec = DF_INSN_UID_MWS (uid); *mws_rec; mws_rec++)
221	{
222	  struct df_mw_hardreg *mws = *mws_rec;
223	  if (DF_MWS_REG_DEF_P (mws))
224	    {
225	      bool all_dead = true;
226	      unsigned int r;
227
228	      for (r=mws->start_regno; r <= mws->end_regno; r++)
229		if ((bitmap_bit_p (live, r))
230		    || bitmap_bit_p (artificial_uses, r))
231		  {
232		    all_dead = false;
233		    break;
234		  }
235
236	      if (all_dead)
237		{
238		  unsigned int regno = mws->start_regno;
239		  bitmap_set_bit (do_not_gen, regno);
240		  /* Only do this if the value is totally dead.  */
241		  REG_LIVE_LENGTH (regno)++;
242		}
243	    }
244	}
245
246      /* All of the defs except the return value are some sort of
247	 clobber.  This code is for the return.  */
248      for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
249	{
250	  df_ref def = *def_rec;
251	  if ((!CALL_P (insn))
252	      || (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))))
253	    {
254	      unsigned int dregno = DF_REF_REGNO (def);
255
256	      if (bitmap_bit_p (live, dregno))
257		{
258		  /* If we have seen this regno, then it has already been
259		     processed correctly with the per insn increment.  If we
260		     have not seen it we need to add the length from here to
261		     the end of the block to the live length.  */
262		  if (bitmap_bit_p (local_processed, dregno))
263		    {
264		      if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
265			bitmap_clear_bit (local_live, dregno);
266		    }
267		  else
268		    {
269		      bitmap_set_bit (local_processed, dregno);
270		      REG_LIVE_LENGTH (dregno) += luid;
271		    }
272		}
273	      else if ((!(DF_REF_FLAGS (def) & DF_REF_MW_HARDREG))
274		       && (!bitmap_bit_p (artificial_uses, dregno)))
275		{
276		  REG_LIVE_LENGTH (dregno)++;
277		}
278
279	      if (dregno >= FIRST_PSEUDO_REGISTER)
280		{
281		  REG_FREQ (dregno) += REG_FREQ_FROM_BB (bb);
282		  if (REG_BASIC_BLOCK (dregno) == REG_BLOCK_UNKNOWN)
283		    REG_BASIC_BLOCK (dregno) = bb->index;
284		  else if (REG_BASIC_BLOCK (dregno) != bb->index)
285		    REG_BASIC_BLOCK (dregno) = REG_BLOCK_GLOBAL;
286		}
287
288	      if (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER + DF_REF_MAY_CLOBBER)))
289		bitmap_set_bit (do_not_gen, dregno);
290
291	      /* Kill this register if it is not a subreg store or conditional store.  */
292	      if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
293		bitmap_clear_bit (live, dregno);
294	    }
295	}
296
297      for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
298	{
299	  df_ref use = *use_rec;
300	  unsigned int uregno = DF_REF_REGNO (use);
301
302	  if (uregno >= FIRST_PSEUDO_REGISTER)
303	    {
304	      REG_FREQ (uregno) += REG_FREQ_FROM_BB (bb);
305	      if (REG_BASIC_BLOCK (uregno) == REG_BLOCK_UNKNOWN)
306		REG_BASIC_BLOCK (uregno) = bb->index;
307	      else if (REG_BASIC_BLOCK (uregno) != bb->index)
308		REG_BASIC_BLOCK (uregno) = REG_BLOCK_GLOBAL;
309	    }
310
311	  if (!bitmap_bit_p (live, uregno))
312	    {
313	      /* This register is now live.  */
314	      bitmap_set_bit (live, uregno);
315
316	      /* If we have seen this regno, then it has already been
317		 processed correctly with the per insn increment.  If
318		 we have not seen it we set the bit so that begins to
319		 get processed locally.  Note that we don't even get
320		 here if the variable was live at the end of the block
321		 since just a ref inside the block does not effect the
322		 calculations.  */
323	      REG_LIVE_LENGTH (uregno) ++;
324	      bitmap_set_bit (local_live, uregno);
325	      bitmap_set_bit (local_processed, uregno);
326	    }
327	}
328    }
329
330  /* Add the length of the block to all of the registers that were not
331     referenced, but still live in this block.  */
332  bitmap_and_compl_into (live, local_processed);
333  EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi)
334    REG_LIVE_LENGTH (regno) += luid;
335
336  bitmap_clear (local_processed);
337  bitmap_clear (local_live);
338}
339
340
341/* Compute register info: lifetime, bb, and number of defs and uses.  */
342void
343regstat_compute_ri (void)
344{
345  basic_block bb;
346  bitmap live = BITMAP_ALLOC (&df_bitmap_obstack);
347  bitmap do_not_gen = BITMAP_ALLOC (&df_bitmap_obstack);
348  bitmap artificial_uses = BITMAP_ALLOC (&df_bitmap_obstack);
349  bitmap local_live = BITMAP_ALLOC (&df_bitmap_obstack);
350  bitmap local_processed = BITMAP_ALLOC (&df_bitmap_obstack);
351  unsigned int regno;
352  bitmap_iterator bi;
353
354  /* Initialize everything.  */
355
356  gcc_assert (!reg_info_p);
357
358  timevar_push (TV_REG_STATS);
359  setjmp_crosses = BITMAP_ALLOC (&df_bitmap_obstack);
360  max_regno = max_reg_num ();
361  reg_info_p_size = max_regno;
362  reg_info_p = XCNEWVEC (struct reg_info_t, max_regno);
363
364  FOR_EACH_BB (bb)
365    {
366      regstat_bb_compute_ri (bb->index, live, do_not_gen, artificial_uses,
367			     local_live, local_processed);
368    }
369
370  BITMAP_FREE (live);
371  BITMAP_FREE (do_not_gen);
372  BITMAP_FREE (artificial_uses);
373
374  /* See the setjmp comment in regstat_ri_bb_compute.  */
375  EXECUTE_IF_SET_IN_BITMAP (setjmp_crosses, FIRST_PSEUDO_REGISTER, regno, bi)
376    {
377      REG_BASIC_BLOCK (regno) = REG_BLOCK_UNKNOWN;
378      REG_LIVE_LENGTH (regno) = -1;
379    }
380
381  BITMAP_FREE (local_live);
382  BITMAP_FREE (local_processed);
383  timevar_pop (TV_REG_STATS);
384}
385
386
387/* Free all storage associated with the problem.  */
388
389void
390regstat_free_ri (void)
391{
392  gcc_assert (reg_info_p);
393  reg_info_p_size = 0;
394  free (reg_info_p);
395  reg_info_p = NULL;
396
397  BITMAP_FREE (setjmp_crosses);
398}
399
400
401/* Return a bitmap containing the set of registers that cross a setjmp.
402   The client should not change or delete this bitmap.  */
403
404bitmap
405regstat_get_setjmp_crosses (void)
406{
407  return setjmp_crosses;
408}
409
410/*----------------------------------------------------------------------------
411   Process REG_N_CALLS_CROSSED.
412
413   This is used by sched_deps.  A good implementation of sched-deps
414   would really process the blocks directly rather than going through
415   lists of insns.  If it did this, it could use the exact regs that
416   cross an individual call rather than using this info that merges
417   the info for all calls.
418
419   ----------------------------------------------------------------------------*/
420
421
422
423/* Compute calls crossed for BB. Live is a scratch bitvector.  */
424
425static void
426regstat_bb_compute_calls_crossed (unsigned int bb_index, bitmap live)
427{
428  basic_block bb = BASIC_BLOCK (bb_index);
429  rtx insn;
430  df_ref *def_rec;
431  df_ref *use_rec;
432
433  bitmap_copy (live, df_get_live_out (bb));
434
435  /* Process the artificial defs and uses at the bottom of the block
436     to begin processing.  */
437  for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
438    {
439      df_ref def = *def_rec;
440      if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
441	bitmap_clear_bit (live, DF_REF_REGNO (def));
442    }
443
444  for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
445    {
446      df_ref use = *use_rec;
447      if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
448	bitmap_set_bit (live, DF_REF_REGNO (use));
449    }
450
451  FOR_BB_INSNS_REVERSE (bb, insn)
452    {
453      unsigned int uid = INSN_UID (insn);
454      unsigned int regno;
455
456      if (!INSN_P (insn))
457	continue;
458
459      /* Process the defs.  */
460      if (CALL_P (insn))
461	{
462	  bitmap_iterator bi;
463	  EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi)
464	    {
465	      REG_N_CALLS_CROSSED (regno)++;
466	      REG_FREQ_CALLS_CROSSED (regno) += REG_FREQ_FROM_BB (bb);
467	    }
468	}
469
470      /* All of the defs except the return value are some sort of
471	 clobber.  This code is for the return.  */
472      for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
473	{
474	  df_ref def = *def_rec;
475	  if ((!CALL_P (insn))
476	      || (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))))
477	    {
478	      /* Kill this register if it is not a subreg store or conditional store.  */
479	      if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
480		bitmap_clear_bit (live, DF_REF_REGNO (def));
481	    }
482	}
483
484      for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
485	{
486	  df_ref use = *use_rec;
487	  bitmap_set_bit (live, DF_REF_REGNO (use));
488	}
489    }
490}
491
492
493/* Compute register info: lifetime, bb, and number of defs and uses.  */
494void
495regstat_compute_calls_crossed (void)
496{
497  basic_block bb;
498  bitmap live = BITMAP_ALLOC (&df_bitmap_obstack);
499
500  /* Initialize everything.  */
501  gcc_assert (!reg_info_p);
502
503  timevar_push (TV_REG_STATS);
504  max_regno = max_reg_num ();
505  reg_info_p_size = max_regno;
506  reg_info_p = XCNEWVEC (struct reg_info_t, max_regno);
507
508  FOR_EACH_BB (bb)
509    {
510      regstat_bb_compute_calls_crossed (bb->index, live);
511    }
512
513  BITMAP_FREE (live);
514  timevar_pop (TV_REG_STATS);
515}
516
517
518/* Free all storage associated with the problem.  */
519
520void
521regstat_free_calls_crossed (void)
522{
523  gcc_assert (reg_info_p);
524  reg_info_p_size = 0;
525  free (reg_info_p);
526  reg_info_p = NULL;
527}
528
529