gcc/regstat.c

   1 /* Scanning of rtl for dataflow analysis.
   2    Copyright (C) 2007
   3    Free Software Foundation, Inc.
   4    Contributed by Kenneth Zadeck (zadeck@naturalbridge.com).
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 2, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING.  If not, write to the Free
  20 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  21 02110-1301, USA.
  22 */
  23
  24
  25 #include "config.h"
  26 #include "system.h"
  27 #include "coretypes.h"
  28 #include "tm.h"
  29 #include "rtl.h"
  30 #include "tm_p.h"
  31 #include "flags.h"
  32 #include "regs.h"
  33 #include "output.h"
  34 #include "except.h"
  35 #include "hard-reg-set.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 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 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 = xmalloc (max_regno * sizeof (struct regstat_n_sets_and_refs_t));
  66
  67   for (i = 0; i < max_regno; i++)
  68     {
  69       SET_REG_N_SETS (i, DF_REG_DEF_COUNT (i));
  70       SET_REG_N_REFS (i, DF_REG_USE_COUNT (i) + REG_N_SETS (i));
  71     }
  72   timevar_pop (TV_REG_STATS);
  73
  74 }
  75
  76
  77 /* Free the array that holds the REG_N_SETS and REG_N_REFS.  */
  78
  79 void
  80 regstat_free_n_sets_and_refs (void)
  81 {
  82   gcc_assert (regstat_n_sets_and_refs);
  83   free (regstat_n_sets_and_refs);
  84   regstat_n_sets_and_refs = NULL;
  85 }
  86
  87
  88 /*----------------------------------------------------------------------------
  89    REGISTER INFORMATION
  90
  91    Process REG_N_DEATHS, REG_LIVE_LENGTH, REG_N_CALLS_CROSSED,
  92    REG_N_THROWING_CALLS_CROSSED and REG_BASIC_BLOCK.
  93
  94    ----------------------------------------------------------------------------*/
  95
  96 static bitmap setjmp_crosses;
  97 struct reg_info_t *reg_info_p;
  98
  99 /* The number allocated elements of reg_info_p.  */
 100 size_t reg_info_p_size;
 101
 102 /* Compute register info: lifetime, bb, and number of defs and uses
 103    for basic block BB.  The three bitvectors are scratch regs used
 104    here.  */
 105
 106 static void
 107 regstat_bb_compute_ri (unsigned int bb_index,
 108                        bitmap live, bitmap do_not_gen, bitmap artificial_uses,
 109                        bitmap local_live, bitmap local_processed)
 110 {
 111   basic_block bb = BASIC_BLOCK (bb_index);
 112   rtx insn;
 113   struct df_ref **def_rec;
 114   struct df_ref **use_rec;
 115   int luid = 0;
 116   bitmap_iterator bi;
 117   unsigned int regno;
 118
 119   bitmap_copy (live, df_get_live_out (bb));
 120   bitmap_clear (artificial_uses);
 121
 122   /* Process the regs live at the end of the block.  Mark them as
 123      not local to any one basic block.  */
 124   EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi)
 125     REG_BASIC_BLOCK (regno) = REG_BLOCK_GLOBAL;
 126
 127   /* Process the artificial defs and uses at the bottom of the block
 128      to begin processing.  */
 129   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
 130     {
 131       struct df_ref *def = *def_rec;
 132       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
 133         bitmap_clear_bit (live, DF_REF_REGNO (def));
 134     }
 135
 136   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
 137     {
 138       struct df_ref *use = *use_rec;
 139       if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
 140         {
 141           regno = DF_REF_REGNO (use);
 142           bitmap_set_bit (live, regno);
 143           bitmap_set_bit (artificial_uses, regno);
 144         }
 145     }
 146
 147   FOR_BB_INSNS_REVERSE (bb, insn)
 148     {
 149       unsigned int uid = INSN_UID (insn);
 150       unsigned int regno;
 151       bitmap_iterator bi;
 152       struct df_mw_hardreg **mws_rec;
 153       rtx link;
 154
 155       if (!INSN_P (insn))
 156         continue;
 157
 158       /* Increment the live_length for all of the registers that
 159          are are referenced in this block and live at this
 160          particular point.  */
 161       EXECUTE_IF_SET_IN_BITMAP (local_live, 0, regno, bi)
 162         {
 163           REG_LIVE_LENGTH (regno)++;
 164         }
 165       luid++;
 166
 167       bitmap_clear (do_not_gen);
 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               if (can_throw)
 186                 REG_N_THROWING_CALLS_CROSSED (regno)++;
 187
 188               /* We have a problem with any pseudoreg that lives
 189                  across the setjmp.  ANSI says that if a user variable
 190                  does not change in value between the setjmp and the
 191                  longjmp, then the longjmp preserves it.  This
 192                  includes longjmp from a place where the pseudo
 193                  appears dead.  (In principle, the value still exists
 194                  if it is in scope.)  If the pseudo goes in a hard
 195                  reg, some other value may occupy that hard reg where
 196                  this pseudo is dead, thus clobbering the pseudo.
 197                  Conclusion: such a pseudo must not go in a hard
 198                  reg.  */
 199               if (set_jump)
 200                 bitmap_set_bit (setjmp_crosses, regno);
 201             }
 202         }
 203
 204       /* We only care about real sets for calls.  Clobbers only
 205          may clobbers cannot be depended on.  */
 206       for (mws_rec = DF_INSN_UID_MWS (uid); *mws_rec; mws_rec++)
 207         {
 208           struct df_mw_hardreg *mws = *mws_rec;
 209           if (mws->type == DF_REF_REG_DEF)
 210             {
 211               bool all_dead = true;
 212               unsigned int r;
 213
 214               for (r=mws->start_regno; r <= mws->end_regno; r++)
 215                 if ((bitmap_bit_p (live, r))
 216                     || bitmap_bit_p (artificial_uses, r))
 217                   {
 218                     all_dead = false;
 219                     break;
 220                   }
 221
 222               if (all_dead)
 223                 {
 224                   unsigned int regno = mws->start_regno;
 225                   bitmap_set_bit (do_not_gen, regno);
 226                   /* Only do this if the value is totally dead.  */
 227                   REG_LIVE_LENGTH (regno)++;
 228                 }
 229             }
 230         }
 231
 232       /* All of the defs except the return value are some sort of
 233          clobber.  This code is for the return.  */
 234       for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
 235         {
 236           struct df_ref *def = *def_rec;
 237           if ((!CALL_P (insn))
 238               || (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))))
 239             {
 240               unsigned int dregno = DF_REF_REGNO (def);
 241
 242               if (bitmap_bit_p (live, dregno))
 243                 {
 244                   /* If we have seen this regno, then it has already been
 245                      processed correctly with the per insn increment.  If we
 246                      have not seen it we need to add the length from here to
 247                      the end of the block to the live length.  */
 248                   if (bitmap_bit_p (local_processed, dregno))
 249                     {
 250                       if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
 251                         bitmap_clear_bit (local_live, dregno);
 252                     }
 253                   else
 254                     {
 255                       bitmap_set_bit (local_processed, dregno);
 256                       REG_LIVE_LENGTH (dregno) += luid;
 257                     }
 258                 }
 259               else if ((!(DF_REF_FLAGS (def) & DF_REF_MW_HARDREG))
 260                        && (!bitmap_bit_p (artificial_uses, dregno)))
 261                 {
 262                   REG_LIVE_LENGTH (dregno)++;
 263                 }
 264
 265               if (dregno >= FIRST_PSEUDO_REGISTER)
 266                 {
 267                   REG_FREQ (dregno) += REG_FREQ_FROM_BB (bb);
 268                   if (REG_BASIC_BLOCK (dregno) == REG_BLOCK_UNKNOWN)
 269                     REG_BASIC_BLOCK (dregno) = bb->index;
 270                   else if (REG_BASIC_BLOCK (dregno) != bb->index)
 271                     REG_BASIC_BLOCK (dregno) = REG_BLOCK_GLOBAL;
 272                 }
 273
 274               if (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER + DF_REF_MAY_CLOBBER)))
 275                 bitmap_set_bit (do_not_gen, dregno);
 276
 277               /* Kill this register if it is not a subreg store or conditional store.  */
 278               if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
 279                 bitmap_clear_bit (live, dregno);
 280             }
 281         }
 282
 283       for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
 284         {
 285           struct df_ref *use = *use_rec;
 286           unsigned int uregno = DF_REF_REGNO (use);
 287
 288           if (uregno >= FIRST_PSEUDO_REGISTER)
 289             {
 290               REG_FREQ (uregno) += REG_FREQ_FROM_BB (bb);
 291               if (REG_BASIC_BLOCK (uregno) == REG_BLOCK_UNKNOWN)
 292                 REG_BASIC_BLOCK (uregno) = bb->index;
 293               else if (REG_BASIC_BLOCK (uregno) != bb->index)
 294                 REG_BASIC_BLOCK (uregno) = REG_BLOCK_GLOBAL;
 295             }
 296
 297           if (!bitmap_bit_p (live, uregno))
 298             {
 299               /* This register is now live.  */
 300               bitmap_set_bit (live, uregno);
 301
 302               /* If we have seen this regno, then it has already been
 303                  processed correctly with the per insn increment.  If
 304                  we have not seen it we set the bit so that begins to
 305                  get processed locally.  Note that we don't even get
 306                  here if the variable was live at the end of the block
 307                  since just a ref inside the block does not effect the
 308                  calculations.  */
 309               REG_LIVE_LENGTH (uregno) ++;
 310               bitmap_set_bit (local_live, uregno);
 311               bitmap_set_bit (local_processed, uregno);
 312             }
 313         }
 314     }
 315
 316   /* Add the length of the block to all of the registers that were not
 317      referenced, but still live in this block.  */
 318   bitmap_and_compl_into (live, local_processed);
 319   EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi)
 320     REG_LIVE_LENGTH (regno) += luid;
 321
 322   bitmap_clear (local_processed);
 323   bitmap_clear (local_live);
 324 }
 325
 326
 327 /* Compute register info: lifetime, bb, and number of defs and uses.  */
 328 void
 329 regstat_compute_ri (void)
 330 {
 331   basic_block bb;
 332   bitmap live = BITMAP_ALLOC (&df_bitmap_obstack);
 333   bitmap do_not_gen = BITMAP_ALLOC (&df_bitmap_obstack);
 334   bitmap artificial_uses = BITMAP_ALLOC (&df_bitmap_obstack);
 335   bitmap local_live = BITMAP_ALLOC (&df_bitmap_obstack);
 336   bitmap local_processed = BITMAP_ALLOC (&df_bitmap_obstack);
 337   unsigned int regno;
 338   bitmap_iterator bi;
 339
 340   /* Initialize everything.  */
 341
 342   gcc_assert (!reg_info_p);
 343
 344   timevar_push (TV_REG_STATS);
 345   setjmp_crosses = BITMAP_ALLOC (&df_bitmap_obstack);
 346   max_regno = max_reg_num ();
 347   reg_info_p_size = max_regno;
 348   reg_info_p = xcalloc (max_regno, sizeof (struct reg_info_t));
 349
 350   FOR_EACH_BB (bb)
 351     {
 352       regstat_bb_compute_ri (bb->index, live, do_not_gen, artificial_uses,
 353                              local_live, local_processed);
 354     }
 355
 356   BITMAP_FREE (live);
 357   BITMAP_FREE (do_not_gen);
 358   BITMAP_FREE (artificial_uses);
 359
 360   /* See the setjmp comment in regstat_ri_bb_compute.  */
 361   EXECUTE_IF_SET_IN_BITMAP (setjmp_crosses, FIRST_PSEUDO_REGISTER, regno, bi)
 362     {
 363       REG_BASIC_BLOCK (regno) = REG_BLOCK_UNKNOWN;
 364       REG_LIVE_LENGTH (regno) = -1;
 365     }
 366
 367   BITMAP_FREE (local_live);
 368   BITMAP_FREE (local_processed);
 369   timevar_pop (TV_REG_STATS);
 370 }
 371
 372
 373 /* Free all storage associated with the problem.  */
 374
 375 void
 376 regstat_free_ri (void)
 377 {
 378   gcc_assert (reg_info_p);
 379   reg_info_p_size = 0;
 380   free (reg_info_p);
 381   reg_info_p = NULL;
 382
 383   BITMAP_FREE (setjmp_crosses);
 384 }
 385
 386
 387 /* Return a bitmap containing the set of registers that cross a setjmp.
 388    The client should not change or delete this bitmap.  */
 389
 390 bitmap
 391 regstat_get_setjmp_crosses (void)
 392 {
 393   return setjmp_crosses;
 394 }
 395
 396 /*----------------------------------------------------------------------------
 397    Process REG_N_CALLS_CROSSED.
 398
 399    This is used by sched_deps.  A good implementation of sched-deps
 400    would really process the blocks directly rather than going thur
 401    lists of insns.  If it did this, it could use the exact regs that
 402    cross an individual call rather than using this info that merges
 403    the info for all calls.
 404
 405    ----------------------------------------------------------------------------*/
 406
 407
 408
 409 /* Compute calls crossed for BB. Live is a scratch bitvector.  */
 410
 411 static void
 412 regstat_bb_compute_calls_crossed (unsigned int bb_index, bitmap live)
 413 {
 414   basic_block bb = BASIC_BLOCK (bb_index);
 415   rtx insn;
 416   struct df_ref **def_rec;
 417   struct df_ref **use_rec;
 418
 419   bitmap_copy (live, df_get_live_out (bb));
 420
 421   /* Process the artificial defs and uses at the bottom of the block
 422      to begin processing.  */
 423   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
 424     {
 425       struct df_ref *def = *def_rec;
 426       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
 427         bitmap_clear_bit (live, DF_REF_REGNO (def));
 428     }
 429
 430   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
 431     {
 432       struct df_ref *use = *use_rec;
 433       if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
 434         bitmap_set_bit (live, DF_REF_REGNO (use));
 435     }
 436
 437   FOR_BB_INSNS_REVERSE (bb, insn)
 438     {
 439       unsigned int uid = INSN_UID (insn);
 440       unsigned int regno;
 441
 442       if (!INSN_P (insn))
 443         continue;
 444
 445       /* Process the defs.  */
 446       if (CALL_P (insn))
 447         {
 448           bitmap_iterator bi;
 449           EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi)
 450             REG_N_CALLS_CROSSED (regno)++;
 451         }
 452
 453       /* All of the defs except the return value are some sort of
 454          clobber.  This code is for the return.  */
 455       for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
 456         {
 457           struct df_ref *def = *def_rec;
 458           if ((!CALL_P (insn))
 459               || (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))))
 460             {
 461               /* Kill this register if it is not a subreg store or conditional store.  */
 462               if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
 463                 bitmap_clear_bit (live, DF_REF_REGNO (def));
 464             }
 465         }
 466
 467       for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
 468         {
 469           struct df_ref *use = *use_rec;
 470           bitmap_set_bit (live, DF_REF_REGNO (use));
 471         }
 472     }
 473 }
 474
 475
 476 /* Compute register info: lifetime, bb, and number of defs and uses.  */
 477 void
 478 regstat_compute_calls_crossed (void)
 479 {
 480   basic_block bb;
 481   bitmap live = BITMAP_ALLOC (&df_bitmap_obstack);
 482
 483   /* Initialize everything.  */
 484   gcc_assert (!reg_info_p);
 485
 486   timevar_push (TV_REG_STATS);
 487   max_regno = max_reg_num ();
 488   reg_info_p_size = max_regno;
 489   reg_info_p = xcalloc (max_regno, sizeof (struct reg_info_t));
 490
 491   FOR_EACH_BB (bb)
 492     {
 493       regstat_bb_compute_calls_crossed (bb->index, live);
 494     }
 495
 496   BITMAP_FREE (live);
 497   timevar_pop (TV_REG_STATS);
 498 }
 499
 500
 501 /* Free all storage associated with the problem.  */
 502
 503 void
 504 regstat_free_calls_crossed (void)
 505 {
 506   gcc_assert (reg_info_p);
 507   reg_info_p_size = 0;
 508   free (reg_info_p);
 509   reg_info_p = NULL;
 510 }
 511