gcc/regstat.c

   1 /* Scanning of rtl for dataflow analysis.
   2    Copyright (C) 2007, 2008
   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 = XNEWVEC (struct regstat_n_sets_and_refs_t, max_regno);
  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   df_ref *def_rec;
 112   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       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       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               REG_FREQ_CALLS_CROSSED (regno) += REG_FREQ_FROM_BB (bb);
 184               if (can_throw)
 185                 REG_N_THROWING_CALLS_CROSSED (regno)++;
 186
 187               /* We have a problem with any pseudoreg that lives
 188                  across the setjmp.  ANSI says that if a user variable
 189                  does not change in value between the setjmp and the
 190                  longjmp, then the longjmp preserves it.  This
 191                  includes longjmp from a place where the pseudo
 192                  appears dead.  (In principle, the value still exists
 193                  if it is in scope.)  If the pseudo goes in a hard
 194                  reg, some other value may occupy that hard reg where
 195                  this pseudo is dead, thus clobbering the pseudo.
 196                  Conclusion: such a pseudo must not go in a hard
 197                  reg.  */
 198               if (set_jump)
 199                 bitmap_set_bit (setjmp_crosses, regno);
 200             }
 201         }
 202
 203       /* We only care about real sets for calls.  Clobbers only
 204          may clobbers cannot be depended on.  */
 205       for (mws_rec = DF_INSN_UID_MWS (uid); *mws_rec; mws_rec++)
 206         {
 207           struct df_mw_hardreg *mws = *mws_rec;
 208           if (DF_MWS_REG_DEF_P (mws))
 209             {
 210               bool all_dead = true;
 211               unsigned int r;
 212
 213               for (r=mws->start_regno; r <= mws->end_regno; r++)
 214                 if ((bitmap_bit_p (live, r))
 215                     || bitmap_bit_p (artificial_uses, r))
 216                   {
 217                     all_dead = false;
 218                     break;
 219                   }
 220
 221               if (all_dead)
 222                 {
 223                   unsigned int regno = mws->start_regno;
 224                   bitmap_set_bit (do_not_gen, regno);
 225                   /* Only do this if the value is totally dead.  */
 226                   REG_LIVE_LENGTH (regno)++;
 227                 }
 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 (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
 234         {
 235           df_ref def = *def_rec;
 236           if ((!CALL_P (insn))
 237               || (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))))
 238             {
 239               unsigned int dregno = DF_REF_REGNO (def);
 240
 241               if (bitmap_bit_p (live, dregno))
 242                 {
 243                   /* If we have seen this regno, then it has already been
 244                      processed correctly with the per insn increment.  If we
 245                      have not seen it we need to add the length from here to
 246                      the end of the block to the live length.  */
 247                   if (bitmap_bit_p (local_processed, dregno))
 248                     {
 249                       if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
 250                         bitmap_clear_bit (local_live, dregno);
 251                     }
 252                   else
 253                     {
 254                       bitmap_set_bit (local_processed, dregno);
 255                       REG_LIVE_LENGTH (dregno) += luid;
 256                     }
 257                 }
 258               else if ((!(DF_REF_FLAGS (def) & DF_REF_MW_HARDREG))
 259                        && (!bitmap_bit_p (artificial_uses, dregno)))
 260                 {
 261                   REG_LIVE_LENGTH (dregno)++;
 262                 }
 263
 264               if (dregno >= FIRST_PSEUDO_REGISTER)
 265                 {
 266                   REG_FREQ (dregno) += REG_FREQ_FROM_BB (bb);
 267                   if (REG_BASIC_BLOCK (dregno) == REG_BLOCK_UNKNOWN)
 268                     REG_BASIC_BLOCK (dregno) = bb->index;
 269                   else if (REG_BASIC_BLOCK (dregno) != bb->index)
 270                     REG_BASIC_BLOCK (dregno) = REG_BLOCK_GLOBAL;
 271                 }
 272
 273               if (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER + DF_REF_MAY_CLOBBER)))
 274                 bitmap_set_bit (do_not_gen, dregno);
 275
 276               /* Kill this register if it is not a subreg store or conditional store.  */
 277               if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
 278                 bitmap_clear_bit (live, dregno);
 279             }
 280         }
 281
 282       for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
 283         {
 284           df_ref use = *use_rec;
 285           unsigned int uregno = DF_REF_REGNO (use);
 286
 287           if (uregno >= FIRST_PSEUDO_REGISTER)
 288             {
 289               REG_FREQ (uregno) += REG_FREQ_FROM_BB (bb);
 290               if (REG_BASIC_BLOCK (uregno) == REG_BLOCK_UNKNOWN)
 291                 REG_BASIC_BLOCK (uregno) = bb->index;
 292               else if (REG_BASIC_BLOCK (uregno) != bb->index)
 293                 REG_BASIC_BLOCK (uregno) = REG_BLOCK_GLOBAL;
 294             }
 295
 296           if (!bitmap_bit_p (live, uregno))
 297             {
 298               /* This register is now live.  */
 299               bitmap_set_bit (live, uregno);
 300
 301               /* If we have seen this regno, then it has already been
 302                  processed correctly with the per insn increment.  If
 303                  we have not seen it we set the bit so that begins to
 304                  get processed locally.  Note that we don't even get
 305                  here if the variable was live at the end of the block
 306                  since just a ref inside the block does not effect the
 307                  calculations.  */
 308               REG_LIVE_LENGTH (uregno) ++;
 309               bitmap_set_bit (local_live, uregno);
 310               bitmap_set_bit (local_processed, uregno);
 311             }
 312         }
 313     }
 314
 315   /* Add the length of the block to all of the registers that were not
 316      referenced, but still live in this block.  */
 317   bitmap_and_compl_into (live, local_processed);
 318   EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi)
 319     REG_LIVE_LENGTH (regno) += luid;
 320
 321   bitmap_clear (local_processed);
 322   bitmap_clear (local_live);
 323 }
 324
 325
 326 /* Compute register info: lifetime, bb, and number of defs and uses.  */
 327 void
 328 regstat_compute_ri (void)
 329 {
 330   basic_block bb;
 331   bitmap live = BITMAP_ALLOC (&df_bitmap_obstack);
 332   bitmap do_not_gen = BITMAP_ALLOC (&df_bitmap_obstack);
 333   bitmap artificial_uses = BITMAP_ALLOC (&df_bitmap_obstack);
 334   bitmap local_live = BITMAP_ALLOC (&df_bitmap_obstack);
 335   bitmap local_processed = BITMAP_ALLOC (&df_bitmap_obstack);
 336   unsigned int regno;
 337   bitmap_iterator bi;
 338
 339   /* Initialize everything.  */
 340
 341   gcc_assert (!reg_info_p);
 342
 343   timevar_push (TV_REG_STATS);
 344   setjmp_crosses = BITMAP_ALLOC (&df_bitmap_obstack);
 345   max_regno = max_reg_num ();
 346   reg_info_p_size = max_regno;
 347   reg_info_p = XCNEWVEC (struct reg_info_t, max_regno);
 348
 349   FOR_EACH_BB (bb)
 350     {
 351       regstat_bb_compute_ri (bb->index, live, do_not_gen, artificial_uses,
 352                              local_live, local_processed);
 353     }
 354
 355   BITMAP_FREE (live);
 356   BITMAP_FREE (do_not_gen);
 357   BITMAP_FREE (artificial_uses);
 358
 359   /* See the setjmp comment in regstat_ri_bb_compute.  */
 360   EXECUTE_IF_SET_IN_BITMAP (setjmp_crosses, FIRST_PSEUDO_REGISTER, regno, bi)
 361     {
 362       REG_BASIC_BLOCK (regno) = REG_BLOCK_UNKNOWN;
 363       REG_LIVE_LENGTH (regno) = -1;
 364     }
 365
 366   BITMAP_FREE (local_live);
 367   BITMAP_FREE (local_processed);
 368   timevar_pop (TV_REG_STATS);
 369 }
 370
 371
 372 /* Free all storage associated with the problem.  */
 373
 374 void
 375 regstat_free_ri (void)
 376 {
 377   gcc_assert (reg_info_p);
 378   reg_info_p_size = 0;
 379   free (reg_info_p);
 380   reg_info_p = NULL;
 381
 382   BITMAP_FREE (setjmp_crosses);
 383 }
 384
 385
 386 /* Return a bitmap containing the set of registers that cross a setjmp.
 387    The client should not change or delete this bitmap.  */
 388
 389 bitmap
 390 regstat_get_setjmp_crosses (void)
 391 {
 392   return setjmp_crosses;
 393 }
 394
 395 /*----------------------------------------------------------------------------
 396    Process REG_N_CALLS_CROSSED.
 397
 398    This is used by sched_deps.  A good implementation of sched-deps
 399    would really process the blocks directly rather than going through
 400    lists of insns.  If it did this, it could use the exact regs that
 401    cross an individual call rather than using this info that merges
 402    the info for all calls.
 403
 404    ----------------------------------------------------------------------------*/
 405
 406
 407
 408 /* Compute calls crossed for BB. Live is a scratch bitvector.  */
 409
 410 static void
 411 regstat_bb_compute_calls_crossed (unsigned int bb_index, bitmap live)
 412 {
 413   basic_block bb = BASIC_BLOCK (bb_index);
 414   rtx insn;
 415   df_ref *def_rec;
 416   df_ref *use_rec;
 417
 418   bitmap_copy (live, df_get_live_out (bb));
 419
 420   /* Process the artificial defs and uses at the bottom of the block
 421      to begin processing.  */
 422   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
 423     {
 424       df_ref def = *def_rec;
 425       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
 426         bitmap_clear_bit (live, DF_REF_REGNO (def));
 427     }
 428
 429   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
 430     {
 431       df_ref use = *use_rec;
 432       if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
 433         bitmap_set_bit (live, DF_REF_REGNO (use));
 434     }
 435
 436   FOR_BB_INSNS_REVERSE (bb, insn)
 437     {
 438       unsigned int uid = INSN_UID (insn);
 439       unsigned int regno;
 440
 441       if (!INSN_P (insn))
 442         continue;
 443
 444       /* Process the defs.  */
 445       if (CALL_P (insn))
 446         {
 447           bitmap_iterator bi;
 448           EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi)
 449             {
 450               REG_N_CALLS_CROSSED (regno)++;
 451               REG_FREQ_CALLS_CROSSED (regno) += REG_FREQ_FROM_BB (bb);
 452             }
 453         }
 454
 455       /* All of the defs except the return value are some sort of
 456          clobber.  This code is for the return.  */
 457       for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
 458         {
 459           df_ref def = *def_rec;
 460           if ((!CALL_P (insn))
 461               || (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))))
 462             {
 463               /* Kill this register if it is not a subreg store or conditional store.  */
 464               if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
 465                 bitmap_clear_bit (live, DF_REF_REGNO (def));
 466             }
 467         }
 468
 469       for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
 470         {
 471           df_ref use = *use_rec;
 472           bitmap_set_bit (live, DF_REF_REGNO (use));
 473         }
 474     }
 475 }
 476
 477
 478 /* Compute register info: lifetime, bb, and number of defs and uses.  */
 479 void
 480 regstat_compute_calls_crossed (void)
 481 {
 482   basic_block bb;
 483   bitmap live = BITMAP_ALLOC (&df_bitmap_obstack);
 484
 485   /* Initialize everything.  */
 486   gcc_assert (!reg_info_p);
 487
 488   timevar_push (TV_REG_STATS);
 489   max_regno = max_reg_num ();
 490   reg_info_p_size = max_regno;
 491   reg_info_p = XCNEWVEC (struct reg_info_t, max_regno);
 492
 493   FOR_EACH_BB (bb)
 494     {
 495       regstat_bb_compute_calls_crossed (bb->index, live);
 496     }
 497
 498   BITMAP_FREE (live);
 499   timevar_pop (TV_REG_STATS);
 500 }
 501
 502
 503 /* Free all storage associated with the problem.  */
 504
 505 void
 506 regstat_free_calls_crossed (void)
 507 {
 508   gcc_assert (reg_info_p);
 509   reg_info_p_size = 0;
 510   free (reg_info_p);
 511   reg_info_p = NULL;
 512 }
 513