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