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 3, 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 COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22
  23 #include "config.h"
  24 #include "system.h"
  25 #include "coretypes.h"
  26 #include "tm.h"
  27 #include "rtl.h"
  28 #include "tm_p.h"
  29 #include "flags.h"
  30 #include "regs.h"
  31 #include "output.h"
  32 #include "except.h"
  33 #include "hard-reg-set.h"
  34 #include "basic-block.h"
  35 #include "timevar.h"
  36 #include "df.h"
  37
  38
  39 struct regstat_n_sets_and_refs_t *regstat_n_sets_and_refs;
  40 struct regstat_n_sets_and_refs_t *regstat_n_sets_and_refs;
  41
  42 /*----------------------------------------------------------------------------
  43    REG_N_SETS and REG_N_REFS.
  44    ----------------------------------------------------------------------------*/
  45
  46 /* If a pass need to change these values in some magical way or or the
  47    pass needs to have accurate values for these and is not using
  48    incremental df scanning, then it should use REG_N_SETS and
  49    REG_N_USES.  If the pass is doing incremental scanning then it
  50    should be getting the info from DF_REG_DEF_COUNT and
  51    DF_REG_USE_COUNT.  */
  52
  53 void
  54 regstat_init_n_sets_and_refs (void)
  55 {
  56   unsigned int i;
  57   unsigned int max_regno = max_reg_num ();
  58
  59   timevar_push (TV_REG_STATS);
  60   df_grow_reg_info ();
  61   gcc_assert (!regstat_n_sets_and_refs);
  62
  63   regstat_n_sets_and_refs = xmalloc (max_regno * sizeof (struct regstat_n_sets_and_refs_t));
  64
  65   for (i = 0; i < max_regno; i++)
  66     {
  67       SET_REG_N_SETS (i, DF_REG_DEF_COUNT (i));
  68       SET_REG_N_REFS (i, DF_REG_USE_COUNT (i) + REG_N_SETS (i));
  69     }
  70   timevar_pop (TV_REG_STATS);
  71
  72 }
  73
  74
  75 /* Free the array that holds the REG_N_SETS and REG_N_REFS.  */
  76
  77 void
  78 regstat_free_n_sets_and_refs (void)
  79 {
  80   gcc_assert (regstat_n_sets_and_refs);
  81   free (regstat_n_sets_and_refs);
  82   regstat_n_sets_and_refs = NULL;
  83 }
  84
  85
  86 /*----------------------------------------------------------------------------
  87    REGISTER INFORMATION
  88
  89    Process REG_N_DEATHS, REG_LIVE_LENGTH, REG_N_CALLS_CROSSED,
  90    REG_N_THROWING_CALLS_CROSSED and REG_BASIC_BLOCK.
  91
  92    ----------------------------------------------------------------------------*/
  93
  94 static bitmap setjmp_crosses;
  95 struct reg_info_t *reg_info_p;
  96
  97 /* The number allocated elements of reg_info_p.  */
  98 size_t reg_info_p_size;
  99
 100 /* Compute register info: lifetime, bb, and number of defs and uses
 101    for basic block BB.  The three bitvectors are scratch regs used
 102    here.  */
 103
 104 static void
 105 regstat_bb_compute_ri (unsigned int bb_index,
 106                        bitmap live, bitmap do_not_gen, bitmap artificial_uses,
 107                        bitmap local_live, bitmap local_processed)
 108 {
 109   basic_block bb = BASIC_BLOCK (bb_index);
 110   rtx insn;
 111   struct df_ref **def_rec;
 112   struct df_ref **use_rec;
 113   int luid = 0;
 114   bitmap_iterator bi;
 115   unsigned int regno;
 116
 117   bitmap_copy (live, df_get_live_out (bb));
 118   bitmap_clear (artificial_uses);
 119
 120   /* Process the regs live at the end of the block.  Mark them as
 121      not local to any one basic block.  */
 122   EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi)
 123     REG_BASIC_BLOCK (regno) = REG_BLOCK_GLOBAL;
 124
 125   /* Process the artificial defs and uses at the bottom of the block
 126      to begin processing.  */
 127   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
 128     {
 129       struct df_ref *def = *def_rec;
 130       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
 131         bitmap_clear_bit (live, DF_REF_REGNO (def));
 132     }
 133
 134   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
 135     {
 136       struct df_ref *use = *use_rec;
 137       if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
 138         {
 139           regno = DF_REF_REGNO (use);
 140           bitmap_set_bit (live, regno);
 141           bitmap_set_bit (artificial_uses, regno);
 142         }
 143     }
 144
 145   FOR_BB_INSNS_REVERSE (bb, insn)
 146     {
 147       unsigned int uid = INSN_UID (insn);
 148       unsigned int regno;
 149       bitmap_iterator bi;
 150       struct df_mw_hardreg **mws_rec;
 151       rtx link;
 152
 153       if (!INSN_P (insn))
 154         continue;
 155
 156       /* Increment the live_length for all of the registers that
 157          are are referenced in this block and live at this
 158          particular point.  */
 159       EXECUTE_IF_SET_IN_BITMAP (local_live, 0, regno, bi)
 160         {
 161           REG_LIVE_LENGTH (regno)++;
 162         }
 163       luid++;
 164
 165       bitmap_clear (do_not_gen);
 166
 167       link = REG_NOTES (insn);
 168       while (link)
 169         {
 170           if (REG_NOTE_KIND (link) == REG_DEAD)
 171             REG_N_DEATHS(REGNO (XEXP (link, 0)))++;
 172           link = XEXP (link, 1);
 173         }
 174
 175       /* Process the defs.  */
 176       if (CALL_P (insn))
 177         {
 178           bool can_throw = can_throw_internal (insn);
 179           bool set_jump = (find_reg_note (insn, REG_SETJMP, NULL) != NULL);
 180           EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi)
 181             {
 182               REG_N_CALLS_CROSSED (regno)++;
 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 only
 203          may clobbers cannot be depended on.  */
 204       for (mws_rec = DF_INSN_UID_MWS (uid); *mws_rec; mws_rec++)
 205         {
 206           struct df_mw_hardreg *mws = *mws_rec;
 207           if (mws->type == DF_REF_REG_DEF)
 208             {
 209               bool all_dead = true;
 210               unsigned int r;
 211
 212               for (r=mws->start_regno; r <= mws->end_regno; r++)
 213                 if ((bitmap_bit_p (live, r))
 214                     || bitmap_bit_p (artificial_uses, r))
 215                   {
 216                     all_dead = false;
 217                     break;
 218                   }
 219
 220               if (all_dead)
 221                 {
 222                   unsigned int regno = mws->start_regno;
 223                   bitmap_set_bit (do_not_gen, regno);
 224                   /* Only do this if the value is totally dead.  */
 225                   REG_LIVE_LENGTH (regno)++;
 226                 }
 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 (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
 233         {
 234           struct df_ref *def = *def_rec;
 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 this regno, then it has already been
 243                      processed correctly with the per insn increment.  If we
 244                      have not seen it we need to add the length from here to
 245                      the end of the block to the live length.  */
 246                   if (bitmap_bit_p (local_processed, dregno))
 247                     {
 248                       if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
 249                         bitmap_clear_bit (local_live, dregno);
 250                     }
 251                   else
 252                     {
 253                       bitmap_set_bit (local_processed, dregno);
 254                       REG_LIVE_LENGTH (dregno) += luid;
 255                     }
 256                 }
 257               else if ((!(DF_REF_FLAGS (def) & DF_REF_MW_HARDREG))
 258                        && (!bitmap_bit_p (artificial_uses, dregno)))
 259                 {
 260                   REG_LIVE_LENGTH (dregno)++;
 261                 }
 262
 263               if (dregno >= FIRST_PSEUDO_REGISTER)
 264                 {
 265                   REG_FREQ (dregno) += REG_FREQ_FROM_BB (bb);
 266                   if (REG_BASIC_BLOCK (dregno) == REG_BLOCK_UNKNOWN)
 267                     REG_BASIC_BLOCK (dregno) = bb->index;
 268                   else if (REG_BASIC_BLOCK (dregno) != bb->index)
 269                     REG_BASIC_BLOCK (dregno) = REG_BLOCK_GLOBAL;
 270                 }
 271
 272               if (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER + DF_REF_MAY_CLOBBER)))
 273                 bitmap_set_bit (do_not_gen, dregno);
 274
 275               /* Kill this register if it is not a subreg store or conditional store.  */
 276               if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
 277                 bitmap_clear_bit (live, dregno);
 278             }
 279         }
 280
 281       for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
 282         {
 283           struct df_ref *use = *use_rec;
 284           unsigned int uregno = DF_REF_REGNO (use);
 285
 286           if (uregno >= FIRST_PSEUDO_REGISTER)
 287             {
 288               REG_FREQ (uregno) += REG_FREQ_FROM_BB (bb);
 289               if (REG_BASIC_BLOCK (uregno) == REG_BLOCK_UNKNOWN)
 290                 REG_BASIC_BLOCK (uregno) = bb->index;
 291               else if (REG_BASIC_BLOCK (uregno) != bb->index)
 292                 REG_BASIC_BLOCK (uregno) = REG_BLOCK_GLOBAL;
 293             }
 294
 295           if (!bitmap_bit_p (live, uregno))
 296             {
 297               /* This register is now live.  */
 298               bitmap_set_bit (live, uregno);
 299
 300               /* If we have seen this regno, then it has already been
 301                  processed correctly with the per insn increment.  If
 302                  we have not seen it we set the bit so that begins to
 303                  get processed locally.  Note that we don't even get
 304                  here if the variable was live at the end of the block
 305                  since just a ref inside the block does not effect the
 306                  calculations.  */
 307               REG_LIVE_LENGTH (uregno) ++;
 308               bitmap_set_bit (local_live, uregno);
 309               bitmap_set_bit (local_processed, uregno);
 310             }
 311         }
 312     }
 313
 314   /* Add the length of the block to all of the registers that were not
 315      referenced, but still live in this block.  */
 316   bitmap_and_compl_into (live, local_processed);
 317   EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi)
 318     REG_LIVE_LENGTH (regno) += luid;
 319
 320   bitmap_clear (local_processed);
 321   bitmap_clear (local_live);
 322 }
 323
 324
 325 /* Compute register info: lifetime, bb, and number of defs and uses.  */
 326 void
 327 regstat_compute_ri (void)
 328 {
 329   basic_block bb;
 330   bitmap live = BITMAP_ALLOC (&df_bitmap_obstack);
 331   bitmap do_not_gen = BITMAP_ALLOC (&df_bitmap_obstack);
 332   bitmap artificial_uses = BITMAP_ALLOC (&df_bitmap_obstack);
 333   bitmap local_live = BITMAP_ALLOC (&df_bitmap_obstack);
 334   bitmap local_processed = BITMAP_ALLOC (&df_bitmap_obstack);
 335   unsigned int regno;
 336   bitmap_iterator bi;
 337
 338   /* Initialize everything.  */
 339
 340   gcc_assert (!reg_info_p);
 341
 342   timevar_push (TV_REG_STATS);
 343   setjmp_crosses = BITMAP_ALLOC (&df_bitmap_obstack);
 344   max_regno = max_reg_num ();
 345   reg_info_p_size = max_regno;
 346   reg_info_p = xcalloc (max_regno, sizeof (struct reg_info_t));
 347
 348   FOR_EACH_BB (bb)
 349     {
 350       regstat_bb_compute_ri (bb->index, live, do_not_gen, artificial_uses,
 351                              local_live, local_processed);
 352     }
 353
 354   BITMAP_FREE (live);
 355   BITMAP_FREE (do_not_gen);
 356   BITMAP_FREE (artificial_uses);
 357
 358   /* See the setjmp comment in regstat_ri_bb_compute.  */
 359   EXECUTE_IF_SET_IN_BITMAP (setjmp_crosses, FIRST_PSEUDO_REGISTER, regno, bi)
 360     {
 361       REG_BASIC_BLOCK (regno) = REG_BLOCK_UNKNOWN;
 362       REG_LIVE_LENGTH (regno) = -1;
 363     }
 364
 365   BITMAP_FREE (local_live);
 366   BITMAP_FREE (local_processed);
 367   timevar_pop (TV_REG_STATS);
 368 }
 369
 370
 371 /* Free all storage associated with the problem.  */
 372
 373 void
 374 regstat_free_ri (void)
 375 {
 376   gcc_assert (reg_info_p);
 377   reg_info_p_size = 0;
 378   free (reg_info_p);
 379   reg_info_p = NULL;
 380
 381   BITMAP_FREE (setjmp_crosses);
 382 }
 383
 384
 385 /* Return a bitmap containing the set of registers that cross a setjmp.
 386    The client should not change or delete this bitmap.  */
 387
 388 bitmap
 389 regstat_get_setjmp_crosses (void)
 390 {
 391   return setjmp_crosses;
 392 }
 393
 394 /*----------------------------------------------------------------------------
 395    Process REG_N_CALLS_CROSSED.
 396
 397    This is used by sched_deps.  A good implementation of sched-deps
 398    would really process the blocks directly rather than going through
 399    lists of insns.  If it did this, it could use the exact regs that
 400    cross an individual call rather than using this info that merges
 401    the info for all calls.
 402
 403    ----------------------------------------------------------------------------*/
 404
 405
 406
 407 /* Compute calls crossed for BB. Live is a scratch bitvector.  */
 408
 409 static void
 410 regstat_bb_compute_calls_crossed (unsigned int bb_index, bitmap live)
 411 {
 412   basic_block bb = BASIC_BLOCK (bb_index);
 413   rtx insn;
 414   struct df_ref **def_rec;
 415   struct df_ref **use_rec;
 416
 417   bitmap_copy (live, df_get_live_out (bb));
 418
 419   /* Process the artificial defs and uses at the bottom of the block
 420      to begin processing.  */
 421   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
 422     {
 423       struct df_ref *def = *def_rec;
 424       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
 425         bitmap_clear_bit (live, DF_REF_REGNO (def));
 426     }
 427
 428   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
 429     {
 430       struct df_ref *use = *use_rec;
 431       if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
 432         bitmap_set_bit (live, DF_REF_REGNO (use));
 433     }
 434
 435   FOR_BB_INSNS_REVERSE (bb, insn)
 436     {
 437       unsigned int uid = INSN_UID (insn);
 438       unsigned int regno;
 439
 440       if (!INSN_P (insn))
 441         continue;
 442
 443       /* Process the defs.  */
 444       if (CALL_P (insn))
 445         {
 446           bitmap_iterator bi;
 447           EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi)
 448             REG_N_CALLS_CROSSED (regno)++;
 449         }
 450
 451       /* All of the defs except the return value are some sort of
 452          clobber.  This code is for the return.  */
 453       for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
 454         {
 455           struct df_ref *def = *def_rec;
 456           if ((!CALL_P (insn))
 457               || (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))))
 458             {
 459               /* Kill this register if it is not a subreg store or conditional store.  */
 460               if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
 461                 bitmap_clear_bit (live, DF_REF_REGNO (def));
 462             }
 463         }
 464
 465       for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
 466         {
 467           struct df_ref *use = *use_rec;
 468           bitmap_set_bit (live, DF_REF_REGNO (use));
 469         }
 470     }
 471 }
 472
 473
 474 /* Compute register info: lifetime, bb, and number of defs and uses.  */
 475 void
 476 regstat_compute_calls_crossed (void)
 477 {
 478   basic_block bb;
 479   bitmap live = BITMAP_ALLOC (&df_bitmap_obstack);
 480
 481   /* Initialize everything.  */
 482   gcc_assert (!reg_info_p);
 483
 484   timevar_push (TV_REG_STATS);
 485   max_regno = max_reg_num ();
 486   reg_info_p_size = max_regno;
 487   reg_info_p = xcalloc (max_regno, sizeof (struct reg_info_t));
 488
 489   FOR_EACH_BB (bb)
 490     {
 491       regstat_bb_compute_calls_crossed (bb->index, live);
 492     }
 493
 494   BITMAP_FREE (live);
 495   timevar_pop (TV_REG_STATS);
 496 }
 497
 498
 499 /* Free all storage associated with the problem.  */
 500
 501 void
 502 regstat_free_calls_crossed (void)
 503 {
 504   gcc_assert (reg_info_p);
 505   reg_info_p_size = 0;
 506   free (reg_info_p);
 507   reg_info_p = NULL;
 508 }
 509