OSDN Git Service

2012-09-27 Vladimir Makarov <vmakarov@redhat.com>
[pf3gnuchains/gcc-fork.git] / gcc / regstat.c
1 /* Scanning of rtl for dataflow analysis.
2    Copyright (C) 2007, 2008, 2009, 2010
3    Free Software Foundation, Inc.
4    Contributed by Kenneth Zadeck (zadeck@naturalbridge.com).
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
12
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16 for more details.
17
18 You should have received a copy of the GNU General Public License
19 along 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 "except.h"
32 #include "hard-reg-set.h"
33 #include "basic-block.h"
34 #include "timevar.h"
35 #include "df.h"
36
37
38 struct regstat_n_sets_and_refs_t *regstat_n_sets_and_refs;
39
40 /*----------------------------------------------------------------------------
41    REG_N_SETS and REG_N_REFS.
42    ----------------------------------------------------------------------------*/
43
44 /* If a pass need to change these values in some magical way or the
45    pass needs to have accurate values for these and is not using
46    incremental df scanning, then it should use REG_N_SETS and
47    REG_N_USES.  If the pass is doing incremental scanning then it
48    should be getting the info from DF_REG_DEF_COUNT and
49    DF_REG_USE_COUNT.  */
50
51 void
52 regstat_init_n_sets_and_refs (void)
53 {
54   unsigned int i;
55   unsigned int max_regno = max_reg_num ();
56
57   timevar_push (TV_REG_STATS);
58   df_grow_reg_info ();
59   gcc_assert (!regstat_n_sets_and_refs);
60
61   regstat_n_sets_and_refs = XNEWVEC (struct regstat_n_sets_and_refs_t, max_regno);
62
63   if (MAY_HAVE_DEBUG_INSNS)
64     for (i = 0; i < max_regno; i++)
65       {
66         int use_count;
67         df_ref use;
68
69         use_count = DF_REG_USE_COUNT (i);
70         for (use = DF_REG_USE_CHAIN (i); use; use = DF_REF_NEXT_REG (use))
71           if (DF_REF_INSN_INFO (use) && DEBUG_INSN_P (DF_REF_INSN (use)))
72             use_count--;
73
74
75         SET_REG_N_SETS (i, DF_REG_DEF_COUNT (i));
76         SET_REG_N_REFS (i, use_count + REG_N_SETS (i));
77       }
78   else
79     for (i = 0; i < max_regno; i++)
80       {
81         SET_REG_N_SETS (i, DF_REG_DEF_COUNT (i));
82         SET_REG_N_REFS (i, DF_REG_USE_COUNT (i) + REG_N_SETS (i));
83       }
84   timevar_pop (TV_REG_STATS);
85
86 }
87
88
89 /* Free the array that holds the REG_N_SETS and REG_N_REFS.  */
90
91 void
92 regstat_free_n_sets_and_refs (void)
93 {
94   gcc_assert (regstat_n_sets_and_refs);
95   free (regstat_n_sets_and_refs);
96   regstat_n_sets_and_refs = NULL;
97 }
98
99
100 /*----------------------------------------------------------------------------
101    REGISTER INFORMATION
102
103    Process REG_N_DEATHS, REG_LIVE_LENGTH, REG_N_CALLS_CROSSED,
104    REG_N_THROWING_CALLS_CROSSED and REG_BASIC_BLOCK.
105
106    ----------------------------------------------------------------------------*/
107
108 static bitmap setjmp_crosses;
109 struct reg_info_t *reg_info_p;
110
111 /* The number allocated elements of reg_info_p.  */
112 size_t reg_info_p_size;
113
114 /* Compute register info: lifetime, bb, and number of defs and uses
115    for basic block BB.  The three bitvectors are scratch regs used
116    here.  */
117
118 static void
119 regstat_bb_compute_ri (unsigned int bb_index,
120                        bitmap live, bitmap artificial_uses,
121                        bitmap local_live, bitmap local_processed,
122                        int *local_live_last_luid)
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       bitmap_iterator bi;
164       struct df_mw_hardreg **mws_rec;
165       rtx link;
166
167       if (!NONDEBUG_INSN_P (insn))
168         continue;
169
170       luid++;
171
172       link = REG_NOTES (insn);
173       while (link)
174         {
175           if (REG_NOTE_KIND (link) == REG_DEAD)
176             REG_N_DEATHS(REGNO (XEXP (link, 0)))++;
177           link = XEXP (link, 1);
178         }
179
180       /* Process the defs.  */
181       if (CALL_P (insn))
182         {
183           bool can_throw = can_throw_internal (insn);
184           bool set_jump = (find_reg_note (insn, REG_SETJMP, NULL) != NULL);
185           EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi)
186             {
187               REG_N_CALLS_CROSSED (regno)++;
188               REG_FREQ_CALLS_CROSSED (regno) += REG_FREQ_FROM_BB (bb);
189               REG_FREQ_CALLS_CROSSED (regno) =
190                 MIN (REG_FREQ_CALLS_CROSSED (regno), REG_FREQ_MAX);
191               if (can_throw)
192                 REG_N_THROWING_CALLS_CROSSED (regno)++;
193
194               /* We have a problem with any pseudoreg that lives
195                  across the setjmp.  ANSI says that if a user variable
196                  does not change in value between the setjmp and the
197                  longjmp, then the longjmp preserves it.  This
198                  includes longjmp from a place where the pseudo
199                  appears dead.  (In principle, the value still exists
200                  if it is in scope.)  If the pseudo goes in a hard
201                  reg, some other value may occupy that hard reg where
202                  this pseudo is dead, thus clobbering the pseudo.
203                  Conclusion: such a pseudo must not go in a hard
204                  reg.  */
205               if (set_jump)
206                 bitmap_set_bit (setjmp_crosses, regno);
207             }
208         }
209
210       /* We only care about real sets for calls.  Clobbers cannot
211          be depended on.
212          Only do this if the value is totally dead.  */
213       for (mws_rec = DF_INSN_UID_MWS (uid); *mws_rec; mws_rec++)
214         {
215           struct df_mw_hardreg *mws = *mws_rec;
216           if (DF_MWS_REG_DEF_P (mws))
217             {
218               bool all_dead = true;
219               unsigned int r;
220
221               for (r = mws->start_regno; r <= mws->end_regno; r++)
222                 if (bitmap_bit_p (artificial_uses, r)
223                     || bitmap_bit_p (live, r))
224                   {
225                     all_dead = false;
226                     break;
227                   }
228
229               if (all_dead)
230                 {
231                   regno = mws->start_regno;
232                   REG_LIVE_LENGTH (regno)++;
233                 }
234             }
235         }
236
237       /* All of the defs except the return value are some sort of
238          clobber.  This code is for the return.  */
239       for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
240         {
241           df_ref def = *def_rec;
242           if ((!CALL_P (insn))
243               || (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))))
244             {
245               unsigned int dregno = DF_REF_REGNO (def);
246
247               if (bitmap_bit_p (live, dregno))
248                 {
249                   /* If we have seen a use of DREGNO somewhere before (i.e.
250                      later in this basic block), and DEF is not a subreg
251                      store or conditional store, then kill the register
252                      here and add the proper length to its REG_LIVE_LENGTH.
253
254                      If we have not seen a use of DREGNO later in this basic
255                      block, then we need to add the length from here to the
256                      end of the block to the live length.  */
257                   if (bitmap_bit_p (local_live, dregno))
258                     {
259                       /* Note that LOCAL_LIVE implies LOCAL_PROCESSED, so
260                          we don't have to set LOCAL_PROCESSED in this clause.  */
261                       if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
262                         {
263                           REG_LIVE_LENGTH (dregno) +=
264                             (luid - local_live_last_luid[dregno]);
265                           local_live_last_luid[dregno] = luid;
266                           bitmap_clear_bit (local_live, dregno);
267                         }
268                     }
269                   else
270                     {
271                       bitmap_set_bit (local_processed, dregno);
272                       REG_LIVE_LENGTH (dregno) += luid;
273                       local_live_last_luid[dregno] = luid;
274                     }
275
276                   /* Kill this register if it is not a subreg store or
277                      conditional store.
278                      ??? This means that any partial store is live from
279                      the last use in a basic block to the start of this
280                      basic block.  This results in poor calculations of
281                      REG_LIVE_LENGTH in large basic blocks.  */
282                   if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
283                     bitmap_clear_bit (live, dregno);
284                 }
285               else if ((!(DF_REF_FLAGS (def) & DF_REF_MW_HARDREG))
286                        && (!bitmap_bit_p (artificial_uses, dregno)))
287                 {
288                   REG_LIVE_LENGTH (dregno)++;
289                 }
290
291               if (dregno >= FIRST_PSEUDO_REGISTER)
292                 {
293                   REG_FREQ (dregno) += REG_FREQ_FROM_BB (bb);
294                   REG_FREQ (dregno) =
295                     MIN (REG_FREQ (dregno), REG_FREQ_MAX);
296
297                   if (REG_BASIC_BLOCK (dregno) == REG_BLOCK_UNKNOWN)
298                     REG_BASIC_BLOCK (dregno) = bb->index;
299                   else if (REG_BASIC_BLOCK (dregno) != bb->index)
300                     REG_BASIC_BLOCK (dregno) = REG_BLOCK_GLOBAL;
301                 }
302             }
303         }
304
305       for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
306         {
307           df_ref use = *use_rec;
308           unsigned int uregno = DF_REF_REGNO (use);
309
310           if (uregno >= FIRST_PSEUDO_REGISTER)
311             {
312               REG_FREQ (uregno) += REG_FREQ_FROM_BB (bb);
313               REG_FREQ (uregno) =
314                 MIN (REG_FREQ (uregno), REG_FREQ_MAX);
315
316               if (REG_BASIC_BLOCK (uregno) == REG_BLOCK_UNKNOWN)
317                 REG_BASIC_BLOCK (uregno) = bb->index;
318               else if (REG_BASIC_BLOCK (uregno) != bb->index)
319                 REG_BASIC_BLOCK (uregno) = REG_BLOCK_GLOBAL;
320             }
321
322           if (bitmap_set_bit (live, uregno))
323             {
324               /* This register is now live.  Begin to process it locally.
325
326                  Note that we don't even get here if the variable was live
327                  at the end of the block since just a ref inside the block
328                  does not effect the calculations.  */
329               REG_LIVE_LENGTH (uregno) ++;
330               local_live_last_luid[uregno] = luid;
331               bitmap_set_bit (local_live, uregno);
332               bitmap_set_bit (local_processed, uregno);
333             }
334         }
335     }
336
337   /* Add the liveness length to all registers that were used somewhere
338      in this bock, but not between that use and the head of this block.  */
339   EXECUTE_IF_SET_IN_BITMAP (local_live, 0, regno, bi)
340     {
341       REG_LIVE_LENGTH (regno) += (luid - local_live_last_luid[regno]);
342     }
343
344   /* Add the length of the block to all of the registers that were not
345      referenced, but still live in this block.  */
346   bitmap_and_compl_into (live, local_processed);
347   EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi)
348     REG_LIVE_LENGTH (regno) += luid;
349
350   bitmap_clear (local_processed);
351   bitmap_clear (local_live);
352 }
353
354
355 /* Compute register info: lifetime, bb, and number of defs and uses.  */
356 void
357 regstat_compute_ri (void)
358 {
359   basic_block bb;
360   bitmap live = BITMAP_ALLOC (&df_bitmap_obstack);
361   bitmap artificial_uses = BITMAP_ALLOC (&df_bitmap_obstack);
362   bitmap local_live = BITMAP_ALLOC (&df_bitmap_obstack);
363   bitmap local_processed = BITMAP_ALLOC (&df_bitmap_obstack);
364   unsigned int regno;
365   bitmap_iterator bi;
366   int *local_live_last_luid;
367
368   /* Initialize everything.  */
369
370   gcc_assert (!reg_info_p);
371
372   timevar_push (TV_REG_STATS);
373   setjmp_crosses = BITMAP_ALLOC (&df_bitmap_obstack);
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   local_live_last_luid = XNEWVEC (int, max_regno);
378
379   FOR_EACH_BB (bb)
380     {
381       regstat_bb_compute_ri (bb->index, live, artificial_uses,
382                              local_live, local_processed,
383                              local_live_last_luid);
384     }
385
386   BITMAP_FREE (live);
387   BITMAP_FREE (artificial_uses);
388   BITMAP_FREE (local_live);
389   BITMAP_FREE (local_processed);
390   free (local_live_last_luid);
391
392   /* See the setjmp comment in regstat_ri_bb_compute.  */
393   EXECUTE_IF_SET_IN_BITMAP (setjmp_crosses, FIRST_PSEUDO_REGISTER, regno, bi)
394     {
395       REG_BASIC_BLOCK (regno) = REG_BLOCK_UNKNOWN;
396       REG_LIVE_LENGTH (regno) = -1;
397     }
398
399   timevar_pop (TV_REG_STATS);
400 }
401
402
403 /* Free all storage associated with the problem.  */
404
405 void
406 regstat_free_ri (void)
407 {
408   gcc_assert (reg_info_p);
409   reg_info_p_size = 0;
410   free (reg_info_p);
411   reg_info_p = NULL;
412
413   BITMAP_FREE (setjmp_crosses);
414 }
415
416
417 /* Return a bitmap containing the set of registers that cross a setjmp.
418    The client should not change or delete this bitmap.  */
419
420 bitmap
421 regstat_get_setjmp_crosses (void)
422 {
423   return setjmp_crosses;
424 }
425
426 /*----------------------------------------------------------------------------
427    Process REG_N_CALLS_CROSSED.
428
429    This is used by sched_deps.  A good implementation of sched-deps
430    would really process the blocks directly rather than going through
431    lists of insns.  If it did this, it could use the exact regs that
432    cross an individual call rather than using this info that merges
433    the info for all calls.
434
435    ----------------------------------------------------------------------------*/
436
437
438
439 /* Compute calls crossed for BB. Live is a scratch bitvector.  */
440
441 static void
442 regstat_bb_compute_calls_crossed (unsigned int bb_index, bitmap live)
443 {
444   basic_block bb = BASIC_BLOCK (bb_index);
445   rtx insn;
446   df_ref *def_rec;
447   df_ref *use_rec;
448
449   bitmap_copy (live, df_get_live_out (bb));
450
451   /* Process the artificial defs and uses at the bottom of the block
452      to begin processing.  */
453   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
454     {
455       df_ref def = *def_rec;
456       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
457         bitmap_clear_bit (live, DF_REF_REGNO (def));
458     }
459
460   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
461     {
462       df_ref use = *use_rec;
463       if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
464         bitmap_set_bit (live, DF_REF_REGNO (use));
465     }
466
467   FOR_BB_INSNS_REVERSE (bb, insn)
468     {
469       unsigned int uid = INSN_UID (insn);
470       unsigned int regno;
471
472       if (!INSN_P (insn))
473         continue;
474
475       /* Process the defs.  */
476       if (CALL_P (insn))
477         {
478           bitmap_iterator bi;
479           EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi)
480             {
481               REG_N_CALLS_CROSSED (regno)++;
482               REG_FREQ_CALLS_CROSSED (regno) += REG_FREQ_FROM_BB (bb);
483               REG_FREQ_CALLS_CROSSED (regno) =
484                 MIN (REG_FREQ_CALLS_CROSSED (regno), REG_FREQ_MAX);
485             }
486         }
487
488       /* All of the defs except the return value are some sort of
489          clobber.  This code is for the return.  */
490       for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
491         {
492           df_ref def = *def_rec;
493           if ((!CALL_P (insn))
494               || (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))))
495             {
496               /* Kill this register if it is not a subreg store or conditional store.  */
497               if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
498                 bitmap_clear_bit (live, DF_REF_REGNO (def));
499             }
500         }
501
502       for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
503         {
504           df_ref use = *use_rec;
505           bitmap_set_bit (live, DF_REF_REGNO (use));
506         }
507     }
508 }
509
510
511 /* Compute register info: lifetime, bb, and number of defs and uses.  */
512 void
513 regstat_compute_calls_crossed (void)
514 {
515   basic_block bb;
516   bitmap live = BITMAP_ALLOC (&df_bitmap_obstack);
517
518   /* Initialize everything.  */
519   gcc_assert (!reg_info_p);
520
521   timevar_push (TV_REG_STATS);
522   max_regno = max_reg_num ();
523   reg_info_p_size = max_regno;
524   reg_info_p = XCNEWVEC (struct reg_info_t, max_regno);
525
526   FOR_EACH_BB (bb)
527     {
528       regstat_bb_compute_calls_crossed (bb->index, live);
529     }
530
531   BITMAP_FREE (live);
532   timevar_pop (TV_REG_STATS);
533 }
534
535
536 /* Free all storage associated with the problem.  */
537
538 void
539 regstat_free_calls_crossed (void)
540 {
541   gcc_assert (reg_info_p);
542   reg_info_p_size = 0;
543   free (reg_info_p);
544   reg_info_p = NULL;
545 }
546
547 /* Dump the register info to FILE.  */
548
549 void
550 dump_reg_info (FILE *file)
551 {
552   unsigned int i, max = max_reg_num ();
553   if (reload_completed)
554     return;
555
556   if (reg_info_p_size < max)
557     max = reg_info_p_size;
558
559   fprintf (file, "%d registers.\n", max);
560   for (i = FIRST_PSEUDO_REGISTER; i < max; i++)
561     {
562       enum reg_class rclass, altclass;
563
564       if (regstat_n_sets_and_refs)
565         fprintf (file, "\nRegister %d used %d times across %d insns",
566                  i, REG_N_REFS (i), REG_LIVE_LENGTH (i));
567       else if (df)
568         fprintf (file, "\nRegister %d used %d times across %d insns",
569                  i, DF_REG_USE_COUNT (i) + DF_REG_DEF_COUNT (i), REG_LIVE_LENGTH (i));
570
571       if (REG_BASIC_BLOCK (i) >= NUM_FIXED_BLOCKS)
572         fprintf (file, " in block %d", REG_BASIC_BLOCK (i));
573       if (regstat_n_sets_and_refs)
574         fprintf (file, "; set %d time%s", REG_N_SETS (i),
575                  (REG_N_SETS (i) == 1) ? "" : "s");
576       else if (df)
577         fprintf (file, "; set %d time%s", DF_REG_DEF_COUNT (i),
578                  (DF_REG_DEF_COUNT (i) == 1) ? "" : "s");
579       if (regno_reg_rtx[i] != NULL && REG_USERVAR_P (regno_reg_rtx[i]))
580         fputs ("; user var", file);
581       if (REG_N_DEATHS (i) != 1)
582         fprintf (file, "; dies in %d places", REG_N_DEATHS (i));
583       if (REG_N_CALLS_CROSSED (i) == 1)
584         fputs ("; crosses 1 call", file);
585       else if (REG_N_CALLS_CROSSED (i))
586         fprintf (file, "; crosses %d calls", REG_N_CALLS_CROSSED (i));
587       if (REG_FREQ_CALLS_CROSSED (i))
588         fprintf (file, "; crosses call with %d frequency", REG_FREQ_CALLS_CROSSED (i));
589       if (regno_reg_rtx[i] != NULL
590           && PSEUDO_REGNO_BYTES (i) != UNITS_PER_WORD)
591         fprintf (file, "; %d bytes", PSEUDO_REGNO_BYTES (i));
592
593       rclass = reg_preferred_class (i);
594       altclass = reg_alternate_class (i);
595       if (rclass != GENERAL_REGS || altclass != ALL_REGS)
596         {
597           if (altclass == ALL_REGS || rclass == ALL_REGS)
598             fprintf (file, "; pref %s", reg_class_names[(int) rclass]);
599           else if (altclass == NO_REGS)
600             fprintf (file, "; %s or none", reg_class_names[(int) rclass]);
601           else
602             fprintf (file, "; pref %s, else %s",
603                      reg_class_names[(int) rclass],
604                      reg_class_names[(int) altclass]);
605         }
606
607       if (regno_reg_rtx[i] != NULL && REG_POINTER (regno_reg_rtx[i]))
608         fputs ("; pointer", file);
609       fputs (".\n", file);
610     }
611 }
612