gcc/regstat.c

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