gcc/regstat.c

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