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