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