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   for (i = 0; i < max_regno; i++)
  65     {
  66       SET_REG_N_SETS (i, DF_REG_DEF_COUNT (i));
  67       SET_REG_N_REFS (i, DF_REG_USE_COUNT (i) + REG_N_SETS (i));
  68     }
  69   timevar_pop (TV_REG_STATS);
  70
  71 }
  72
  73
  74 /* Free the array that holds the REG_N_SETS and REG_N_REFS.  */
  75
  76 void
  77 regstat_free_n_sets_and_refs (void)
  78 {
  79   gcc_assert (regstat_n_sets_and_refs);
  80   free (regstat_n_sets_and_refs);
  81   regstat_n_sets_and_refs = NULL;
  82 }
  83
  84
  85 /*----------------------------------------------------------------------------
  86    REGISTER INFORMATION
  87
  88    Process REG_N_DEATHS, REG_LIVE_LENGTH, REG_N_CALLS_CROSSED,
  89    REG_N_THROWING_CALLS_CROSSED and REG_BASIC_BLOCK.
  90
  91    ----------------------------------------------------------------------------*/
  92
  93 static bitmap setjmp_crosses;
  94 struct reg_info_t *reg_info_p;
  95
  96 /* The number allocated elements of reg_info_p.  */
  97 size_t reg_info_p_size;
  98
  99 /* Compute register info: lifetime, bb, and number of defs and uses
 100    for basic block BB.  The three bitvectors are scratch regs used
 101    here.  */
 102
 103 static void
 104 regstat_bb_compute_ri (unsigned int bb_index,
 105                        bitmap live, bitmap do_not_gen, bitmap artificial_uses,
 106                        bitmap local_live, bitmap local_processed)
 107 {
 108   basic_block bb = BASIC_BLOCK (bb_index);
 109   rtx insn;
 110   df_ref *def_rec;
 111   df_ref *use_rec;
 112   int luid = 0;
 113   bitmap_iterator bi;
 114   unsigned int regno;
 115
 116   bitmap_copy (live, df_get_live_out (bb));
 117   bitmap_clear (artificial_uses);
 118
 119   /* Process the regs live at the end of the block.  Mark them as
 120      not local to any one basic block.  */
 121   EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi)
 122     REG_BASIC_BLOCK (regno) = REG_BLOCK_GLOBAL;
 123
 124   /* Process the artificial defs and uses at the bottom of the block
 125      to begin processing.  */
 126   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
 127     {
 128       df_ref def = *def_rec;
 129       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
 130         bitmap_clear_bit (live, DF_REF_REGNO (def));
 131     }
 132
 133   for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
 134     {
 135       df_ref use = *use_rec;
 136       if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
 137         {
 138           regno = DF_REF_REGNO (use);
 139           bitmap_set_bit (live, regno);
 140           bitmap_set_bit (artificial_uses, regno);
 141         }
 142     }
 143
 144   FOR_BB_INSNS_REVERSE (bb, insn)
 145     {
 146       unsigned int uid = INSN_UID (insn);
 147       unsigned int regno;
 148       bitmap_iterator bi;
 149       struct df_mw_hardreg **mws_rec;
 150       rtx link;
 151
 152       if (!INSN_P (insn))
 153         continue;
 154
 155       /* Increment the live_length for all of the registers that
 156          are are referenced in this block and live at this
 157          particular point.  */
 158       EXECUTE_IF_SET_IN_BITMAP (local_live, 0, regno, bi)
 159         {
 160           REG_LIVE_LENGTH (regno)++;
 161         }
 162       luid++;
 163
 164       bitmap_clear (do_not_gen);
 165
 166       link = REG_NOTES (insn);
 167       while (link)
 168         {
 169           if (REG_NOTE_KIND (link) == REG_DEAD)
 170             REG_N_DEATHS(REGNO (XEXP (link, 0)))++;
 171           link = XEXP (link, 1);
 172         }
 173
 174       /* Process the defs.  */
 175       if (CALL_P (insn))
 176         {
 177           bool can_throw = can_throw_internal (insn);
 178           bool set_jump = (find_reg_note (insn, REG_SETJMP, NULL) != NULL);
 179           EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi)
 180             {
 181               REG_N_CALLS_CROSSED (regno)++;
 182               REG_FREQ_CALLS_CROSSED (regno) += REG_FREQ_FROM_BB (bb);
 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 (DF_MWS_REG_DEF_P (mws))
 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           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           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 = XCNEWVEC (struct reg_info_t, max_regno);
 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   df_ref *def_rec;
 415   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       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       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             {
 449               REG_N_CALLS_CROSSED (regno)++;
 450               REG_FREQ_CALLS_CROSSED (regno) += REG_FREQ_FROM_BB (bb);
 451             }
 452         }
 453
 454       /* All of the defs except the return value are some sort of
 455          clobber.  This code is for the return.  */
 456       for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
 457         {
 458           df_ref def = *def_rec;
 459           if ((!CALL_P (insn))
 460               || (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))))
 461             {
 462               /* Kill this register if it is not a subreg store or conditional store.  */
 463               if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
 464                 bitmap_clear_bit (live, DF_REF_REGNO (def));
 465             }
 466         }
 467
 468       for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
 469         {
 470           df_ref use = *use_rec;
 471           bitmap_set_bit (live, DF_REF_REGNO (use));
 472         }
 473     }
 474 }
 475
 476
 477 /* Compute register info: lifetime, bb, and number of defs and uses.  */
 478 void
 479 regstat_compute_calls_crossed (void)
 480 {
 481   basic_block bb;
 482   bitmap live = BITMAP_ALLOC (&df_bitmap_obstack);
 483
 484   /* Initialize everything.  */
 485   gcc_assert (!reg_info_p);
 486
 487   timevar_push (TV_REG_STATS);
 488   max_regno = max_reg_num ();
 489   reg_info_p_size = max_regno;
 490   reg_info_p = XCNEWVEC (struct reg_info_t, max_regno);
 491
 492   FOR_EACH_BB (bb)
 493     {
 494       regstat_bb_compute_calls_crossed (bb->index, live);
 495     }
 496
 497   BITMAP_FREE (live);
 498   timevar_pop (TV_REG_STATS);
 499 }
 500
 501
 502 /* Free all storage associated with the problem.  */
 503
 504 void
 505 regstat_free_calls_crossed (void)
 506 {
 507   gcc_assert (reg_info_p);
 508   reg_info_p_size = 0;
 509   free (reg_info_p);
 510   reg_info_p = NULL;
 511 }
 512