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 528