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