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 6This file is part of GCC. 7 8GCC is free software; you can redistribute it and/or modify it under 9the terms of the GNU General Public License as published by the Free 10Software Foundation; either version 3, or (at your option) any later 11version. 12 13GCC is distributed in the hope that it will be useful, but WITHOUT ANY 14WARRANTY; without even the implied warranty of MERCHANTABILITY or 15FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 16for more details. 17 18You should have received a copy of the GNU General Public License 19along 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 39struct 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 52void 53regstat_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 92void 93regstat_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 109static bitmap setjmp_crosses; 110struct reg_info_t *reg_info_p; 111 112/* The number allocated elements of reg_info_p. */ 113size_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 119static void 120regstat_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. */ 342void 343regstat_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 389void 390regstat_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 404bitmap 405regstat_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 425static void 426regstat_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. */ 494void 495regstat_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 520void 521regstat_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 529