gcc/regstat.c

   1 /* Scanning of rtl for dataflow analysis.
   2    Copyright (C) 2007, 2008, 2009
   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 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_bit_p (live, uregno))
 312             {
 313               /* This register is now live.  */
 314               bitmap_set_bit (live, uregno);
 315
 316               /* If we have seen this regno, then it has already been
 317                  processed correctly with the per insn increment.  If
 318                  we have not seen it we set the bit so that begins to
 319                  get processed locally.  Note that we don't even get
 320                  here if the variable was live at the end of the block
 321                  since just a ref inside the block does not effect the
 322                  calculations.  */
 323               REG_LIVE_LENGTH (uregno) ++;
 324               bitmap_set_bit (local_live, uregno);
 325               bitmap_set_bit (local_processed, uregno);
 326             }
 327         }
 328     }
 329
 330   /* Add the length of the block to all of the registers that were not
 331      referenced, but still live in this block.  */
 332   bitmap_and_compl_into (live, local_processed);
 333   EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi)
 334     REG_LIVE_LENGTH (regno) += luid;
 335
 336   bitmap_clear (local_processed);
 337   bitmap_clear (local_live);
 338 }
 339
 340
 341 /* Compute register info: lifetime, bb, and number of defs and uses.  */
 342 void
 343 regstat_compute_ri (void)
 344 {
 345   basic_block bb;
 346   bitmap live = BITMAP_ALLOC (&df_bitmap_obstack);
 347   bitmap do_not_gen = BITMAP_ALLOC (&df_bitmap_obstack);
 348   bitmap artificial_uses = BITMAP_ALLOC (&df_bitmap_obstack);
 349   bitmap local_live = BITMAP_ALLOC (&df_bitmap_obstack);
 350   bitmap local_processed = BITMAP_ALLOC (&df_bitmap_obstack);
 351   unsigned int regno;
 352   bitmap_iterator bi;
 353
 354   /* Initialize everything.  */
 355
 356   gcc_assert (!reg_info_p);
 357
 358   timevar_push (TV_REG_STATS);
 359   setjmp_crosses = BITMAP_ALLOC (&df_bitmap_obstack);
 360   max_regno = max_reg_num ();
 361   reg_info_p_size = max_regno;
 362   reg_info_p = XCNEWVEC (struct reg_info_t, max_regno);
 363
 364   FOR_EACH_BB (bb)
 365     {
 366       regstat_bb_compute_ri (bb->index, live, do_not_gen, artificial_uses,
 367                              local_live, local_processed);
 368     }
 369
 370   BITMAP_FREE (live);
 371   BITMAP_FREE (do_not_gen);
 372   BITMAP_FREE (artificial_uses);
 373
 374   /* See the setjmp comment in regstat_ri_bb_compute.  */
 375   EXECUTE_IF_SET_IN_BITMAP (setjmp_crosses, FIRST_PSEUDO_REGISTER, regno, bi)
 376     {
 377       REG_BASIC_BLOCK (regno) = REG_BLOCK_UNKNOWN;
 378       REG_LIVE_LENGTH (regno) = -1;
 379     }
 380
 381   BITMAP_FREE (local_live);
 382   BITMAP_FREE (local_processed);
 383   timevar_pop (TV_REG_STATS);
 384 }
 385
 386
 387 /* Free all storage associated with the problem.  */
 388
 389 void
 390 regstat_free_ri (void)
 391 {
 392   gcc_assert (reg_info_p);
 393   reg_info_p_size = 0;
 394   free (reg_info_p);
 395   reg_info_p = NULL;
 396
 397   BITMAP_FREE (setjmp_crosses);
 398 }
 399
 400
 401 /* Return a bitmap containing the set of registers that cross a setjmp.
 402    The client should not change or delete this bitmap.  */
 403
 404 bitmap
 405 regstat_get_setjmp_crosses (void)
 406 {
 407   return setjmp_crosses;
 408 }
 409
 410 /*----------------------------------------------------------------------------
 411    Process REG_N_CALLS_CROSSED.
 412
 413    This is used by sched_deps.  A good implementation of sched-deps
 414    would really process the blocks directly rather than going through
 415    lists of insns.  If it did this, it could use the exact regs that
 416    cross an individual call rather than using this info that merges
 417    the info for all calls.
 418
 419    ----------------------------------------------------------------------------*/
 420
 421
 422
 423 /* Compute calls crossed for BB. Live is a scratch bitvector.  */
 424
 425 static void
 426 regstat_bb_compute_calls_crossed (unsigned int bb_index, bitmap live)
 427 {
 428   basic_block bb = BASIC_BLOCK (bb_index);
 429   rtx insn;
 430   df_ref *def_rec;
 431   df_ref *use_rec;
 432
 433   bitmap_copy (live, df_get_live_out (bb));
 434
 435   /* Process the artificial defs and uses at the bottom of the block
 436      to begin processing.  */
 437   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
 438     {
 439       df_ref def = *def_rec;
 440       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
 441         bitmap_clear_bit (live, DF_REF_REGNO (def));
 442     }
 443
 444   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
 445     {
 446       df_ref use = *use_rec;
 447       if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
 448         bitmap_set_bit (live, DF_REF_REGNO (use));
 449     }
 450
 451   FOR_BB_INSNS_REVERSE (bb, insn)
 452     {
 453       unsigned int uid = INSN_UID (insn);
 454       unsigned int regno;
 455
 456       if (!INSN_P (insn))
 457         continue;
 458
 459       /* Process the defs.  */
 460       if (CALL_P (insn))
 461         {
 462           bitmap_iterator bi;
 463           EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi)
 464             {
 465               REG_N_CALLS_CROSSED (regno)++;
 466               REG_FREQ_CALLS_CROSSED (regno) += REG_FREQ_FROM_BB (bb);
 467             }
 468         }
 469
 470       /* All of the defs except the return value are some sort of
 471          clobber.  This code is for the return.  */
 472       for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
 473         {
 474           df_ref def = *def_rec;
 475           if ((!CALL_P (insn))
 476               || (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))))
 477             {
 478               /* Kill this register if it is not a subreg store or conditional store.  */
 479               if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
 480                 bitmap_clear_bit (live, DF_REF_REGNO (def));
 481             }
 482         }
 483
 484       for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
 485         {
 486           df_ref use = *use_rec;
 487           bitmap_set_bit (live, DF_REF_REGNO (use));
 488         }
 489     }
 490 }
 491
 492
 493 /* Compute register info: lifetime, bb, and number of defs and uses.  */
 494 void
 495 regstat_compute_calls_crossed (void)
 496 {
 497   basic_block bb;
 498   bitmap live = BITMAP_ALLOC (&df_bitmap_obstack);
 499
 500   /* Initialize everything.  */
 501   gcc_assert (!reg_info_p);
 502
 503   timevar_push (TV_REG_STATS);
 504   max_regno = max_reg_num ();
 505   reg_info_p_size = max_regno;
 506   reg_info_p = XCNEWVEC (struct reg_info_t, max_regno);
 507
 508   FOR_EACH_BB (bb)
 509     {
 510       regstat_bb_compute_calls_crossed (bb->index, live);
 511     }
 512
 513   BITMAP_FREE (live);
 514   timevar_pop (TV_REG_STATS);
 515 }
 516
 517
 518 /* Free all storage associated with the problem.  */
 519
 520 void
 521 regstat_free_calls_crossed (void)
 522 {
 523   gcc_assert (reg_info_p);
 524   reg_info_p_size = 0;
 525   free (reg_info_p);
 526   reg_info_p = NULL;
 527 }
 528