gcc/regstat.c

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