1/* Scanning of rtl for dataflow analysis. 2 Copyright (C) 1999-2015 Free Software Foundation, Inc. 3 Originally contributed by Michael P. Hayes 4 (m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com) 5 Major rewrite contributed by Danny Berlin (dberlin@dberlin.org) 6 and Kenneth Zadeck (zadeck@naturalbridge.com). 7 8This file is part of GCC. 9 10GCC is free software; you can redistribute it and/or modify it under 11the terms of the GNU General Public License as published by the Free 12Software Foundation; either version 3, or (at your option) any later 13version. 14 15GCC is distributed in the hope that it will be useful, but WITHOUT ANY 16WARRANTY; without even the implied warranty of MERCHANTABILITY or 17FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 18for more details. 19 20You should have received a copy of the GNU General Public License 21along with GCC; see the file COPYING3. If not see 22<http://www.gnu.org/licenses/>. */ 23 24#include "config.h" 25#include "system.h" 26#include "coretypes.h" 27#include "tm.h" 28#include "rtl.h" 29#include "tm_p.h" 30#include "insn-config.h" 31#include "recog.h" 32#include "hashtab.h" 33#include "hash-set.h" 34#include "machmode.h" 35#include "vec.h" 36#include "double-int.h" 37#include "input.h" 38#include "alias.h" 39#include "symtab.h" 40#include "wide-int.h" 41#include "inchash.h" 42#include "hard-reg-set.h" 43#include "input.h" 44#include "function.h" 45#include "regs.h" 46#include "alloc-pool.h" 47#include "flags.h" 48#include "predict.h" 49#include "dominance.h" 50#include "cfg.h" 51#include "basic-block.h" 52#include "sbitmap.h" 53#include "bitmap.h" 54#include "dumpfile.h" 55#include "tree.h" 56#include "target.h" 57#include "target-def.h" 58#include "df.h" 59#include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */ 60 61 62typedef struct df_mw_hardreg *df_mw_hardreg_ptr; 63 64 65#ifndef HAVE_epilogue 66#define HAVE_epilogue 0 67#endif 68#ifndef HAVE_prologue 69#define HAVE_prologue 0 70#endif 71#ifndef HAVE_sibcall_epilogue 72#define HAVE_sibcall_epilogue 0 73#endif 74 75#ifndef EPILOGUE_USES 76#define EPILOGUE_USES(REGNO) 0 77#endif 78 79/* The set of hard registers in eliminables[i].from. */ 80 81static HARD_REG_SET elim_reg_set; 82 83/* Initialize ur_in and ur_out as if all hard registers were partially 84 available. */ 85 86struct df_collection_rec 87{ 88 auto_vec<df_ref, 128> def_vec; 89 auto_vec<df_ref, 32> use_vec; 90 auto_vec<df_ref, 32> eq_use_vec; 91 auto_vec<df_mw_hardreg_ptr, 32> mw_vec; 92}; 93 94static void df_ref_record (enum df_ref_class, struct df_collection_rec *, 95 rtx, rtx *, 96 basic_block, struct df_insn_info *, 97 enum df_ref_type, int ref_flags); 98static void df_def_record_1 (struct df_collection_rec *, rtx *, 99 basic_block, struct df_insn_info *, 100 int ref_flags); 101static void df_defs_record (struct df_collection_rec *, rtx, 102 basic_block, struct df_insn_info *, 103 int ref_flags); 104static void df_uses_record (struct df_collection_rec *, 105 rtx *, enum df_ref_type, 106 basic_block, struct df_insn_info *, 107 int ref_flags); 108 109static void df_install_ref_incremental (df_ref); 110static void df_insn_refs_collect (struct df_collection_rec*, 111 basic_block, struct df_insn_info *); 112static void df_canonize_collection_rec (struct df_collection_rec *); 113 114static void df_get_regular_block_artificial_uses (bitmap); 115static void df_get_eh_block_artificial_uses (bitmap); 116 117static void df_record_entry_block_defs (bitmap); 118static void df_record_exit_block_uses (bitmap); 119static void df_get_exit_block_use_set (bitmap); 120static void df_get_entry_block_def_set (bitmap); 121static void df_grow_ref_info (struct df_ref_info *, unsigned int); 122static void df_ref_chain_delete_du_chain (df_ref); 123static void df_ref_chain_delete (df_ref); 124 125static void df_refs_add_to_chains (struct df_collection_rec *, 126 basic_block, rtx_insn *, unsigned int); 127 128static bool df_insn_refs_verify (struct df_collection_rec *, basic_block, 129 rtx_insn *, bool); 130static void df_entry_block_defs_collect (struct df_collection_rec *, bitmap); 131static void df_exit_block_uses_collect (struct df_collection_rec *, bitmap); 132static void df_install_ref (df_ref, struct df_reg_info *, 133 struct df_ref_info *, bool); 134 135static int df_ref_compare (df_ref, df_ref); 136static int df_ref_ptr_compare (const void *, const void *); 137static int df_mw_compare (const df_mw_hardreg *, const df_mw_hardreg *); 138static int df_mw_ptr_compare (const void *, const void *); 139 140static void df_insn_info_delete (unsigned int); 141 142/* Indexed by hardware reg number, is true if that register is ever 143 used in the current function. 144 145 In df-scan.c, this is set up to record the hard regs used 146 explicitly. Reload adds in the hard regs used for holding pseudo 147 regs. Final uses it to generate the code in the function prologue 148 and epilogue to save and restore registers as needed. */ 149 150static bool regs_ever_live[FIRST_PSEUDO_REGISTER]; 151 152/* Flags used to tell df_refs_add_to_chains() which vectors it should copy. */ 153static const unsigned int copy_defs = 0x1; 154static const unsigned int copy_uses = 0x2; 155static const unsigned int copy_eq_uses = 0x4; 156static const unsigned int copy_mw = 0x8; 157static const unsigned int copy_all = copy_defs | copy_uses | copy_eq_uses 158| copy_mw; 159 160/*---------------------------------------------------------------------------- 161 SCANNING DATAFLOW PROBLEM 162 163 There are several ways in which scanning looks just like the other 164 dataflow problems. It shares the all the mechanisms for local info 165 as well as basic block info. Where it differs is when and how often 166 it gets run. It also has no need for the iterative solver. 167----------------------------------------------------------------------------*/ 168 169/* Problem data for the scanning dataflow function. */ 170struct df_scan_problem_data 171{ 172 alloc_pool ref_base_pool; 173 alloc_pool ref_artificial_pool; 174 alloc_pool ref_regular_pool; 175 alloc_pool insn_pool; 176 alloc_pool reg_pool; 177 alloc_pool mw_reg_pool; 178 bitmap_obstack reg_bitmaps; 179 bitmap_obstack insn_bitmaps; 180}; 181 182typedef struct df_scan_bb_info *df_scan_bb_info_t; 183 184 185/* Internal function to shut down the scanning problem. */ 186static void 187df_scan_free_internal (void) 188{ 189 struct df_scan_problem_data *problem_data 190 = (struct df_scan_problem_data *) df_scan->problem_data; 191 192 free (df->def_info.refs); 193 free (df->def_info.begin); 194 free (df->def_info.count); 195 memset (&df->def_info, 0, (sizeof (struct df_ref_info))); 196 197 free (df->use_info.refs); 198 free (df->use_info.begin); 199 free (df->use_info.count); 200 memset (&df->use_info, 0, (sizeof (struct df_ref_info))); 201 202 free (df->def_regs); 203 df->def_regs = NULL; 204 free (df->use_regs); 205 df->use_regs = NULL; 206 free (df->eq_use_regs); 207 df->eq_use_regs = NULL; 208 df->regs_size = 0; 209 DF_REG_SIZE (df) = 0; 210 211 free (df->insns); 212 df->insns = NULL; 213 DF_INSN_SIZE () = 0; 214 215 free (df_scan->block_info); 216 df_scan->block_info = NULL; 217 df_scan->block_info_size = 0; 218 219 bitmap_clear (&df->hardware_regs_used); 220 bitmap_clear (&df->regular_block_artificial_uses); 221 bitmap_clear (&df->eh_block_artificial_uses); 222 BITMAP_FREE (df->entry_block_defs); 223 BITMAP_FREE (df->exit_block_uses); 224 bitmap_clear (&df->insns_to_delete); 225 bitmap_clear (&df->insns_to_rescan); 226 bitmap_clear (&df->insns_to_notes_rescan); 227 228 free_alloc_pool (problem_data->ref_base_pool); 229 free_alloc_pool (problem_data->ref_artificial_pool); 230 free_alloc_pool (problem_data->ref_regular_pool); 231 free_alloc_pool (problem_data->insn_pool); 232 free_alloc_pool (problem_data->reg_pool); 233 free_alloc_pool (problem_data->mw_reg_pool); 234 bitmap_obstack_release (&problem_data->reg_bitmaps); 235 bitmap_obstack_release (&problem_data->insn_bitmaps); 236 free (df_scan->problem_data); 237} 238 239 240/* Free basic block info. */ 241 242static void 243df_scan_free_bb_info (basic_block bb, void *vbb_info) 244{ 245 struct df_scan_bb_info *bb_info = (struct df_scan_bb_info *) vbb_info; 246 unsigned int bb_index = bb->index; 247 rtx_insn *insn; 248 249 FOR_BB_INSNS (bb, insn) 250 if (INSN_P (insn)) 251 df_insn_info_delete (INSN_UID (insn)); 252 253 if (bb_index < df_scan->block_info_size) 254 bb_info = df_scan_get_bb_info (bb_index); 255 256 /* Get rid of any artificial uses or defs. */ 257 df_ref_chain_delete_du_chain (bb_info->artificial_defs); 258 df_ref_chain_delete_du_chain (bb_info->artificial_uses); 259 df_ref_chain_delete (bb_info->artificial_defs); 260 df_ref_chain_delete (bb_info->artificial_uses); 261 bb_info->artificial_defs = NULL; 262 bb_info->artificial_uses = NULL; 263} 264 265 266/* Allocate the problem data for the scanning problem. This should be 267 called when the problem is created or when the entire function is to 268 be rescanned. */ 269void 270df_scan_alloc (bitmap all_blocks ATTRIBUTE_UNUSED) 271{ 272 struct df_scan_problem_data *problem_data; 273 unsigned int insn_num = get_max_uid () + 1; 274 unsigned int block_size = 512; 275 basic_block bb; 276 277 /* Given the number of pools, this is really faster than tearing 278 everything apart. */ 279 if (df_scan->problem_data) 280 df_scan_free_internal (); 281 282 problem_data = XNEW (struct df_scan_problem_data); 283 df_scan->problem_data = problem_data; 284 df_scan->computed = true; 285 286 problem_data->ref_base_pool 287 = create_alloc_pool ("df_scan ref base", 288 sizeof (struct df_base_ref), block_size); 289 problem_data->ref_artificial_pool 290 = create_alloc_pool ("df_scan ref artificial", 291 sizeof (struct df_artificial_ref), block_size); 292 problem_data->ref_regular_pool 293 = create_alloc_pool ("df_scan ref regular", 294 sizeof (struct df_regular_ref), block_size); 295 problem_data->insn_pool 296 = create_alloc_pool ("df_scan insn", 297 sizeof (struct df_insn_info), block_size); 298 problem_data->reg_pool 299 = create_alloc_pool ("df_scan reg", 300 sizeof (struct df_reg_info), block_size); 301 problem_data->mw_reg_pool 302 = create_alloc_pool ("df_scan mw_reg", 303 sizeof (struct df_mw_hardreg), block_size / 16); 304 305 bitmap_obstack_initialize (&problem_data->reg_bitmaps); 306 bitmap_obstack_initialize (&problem_data->insn_bitmaps); 307 308 insn_num += insn_num / 4; 309 df_grow_reg_info (); 310 311 df_grow_insn_info (); 312 df_grow_bb_info (df_scan); 313 314 FOR_ALL_BB_FN (bb, cfun) 315 { 316 unsigned int bb_index = bb->index; 317 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb_index); 318 bb_info->artificial_defs = NULL; 319 bb_info->artificial_uses = NULL; 320 } 321 322 bitmap_initialize (&df->hardware_regs_used, &problem_data->reg_bitmaps); 323 bitmap_initialize (&df->regular_block_artificial_uses, &problem_data->reg_bitmaps); 324 bitmap_initialize (&df->eh_block_artificial_uses, &problem_data->reg_bitmaps); 325 df->entry_block_defs = BITMAP_ALLOC (&problem_data->reg_bitmaps); 326 df->exit_block_uses = BITMAP_ALLOC (&problem_data->reg_bitmaps); 327 bitmap_initialize (&df->insns_to_delete, &problem_data->insn_bitmaps); 328 bitmap_initialize (&df->insns_to_rescan, &problem_data->insn_bitmaps); 329 bitmap_initialize (&df->insns_to_notes_rescan, &problem_data->insn_bitmaps); 330 df_scan->optional_p = false; 331} 332 333 334/* Free all of the data associated with the scan problem. */ 335 336static void 337df_scan_free (void) 338{ 339 if (df_scan->problem_data) 340 df_scan_free_internal (); 341 342 if (df->blocks_to_analyze) 343 { 344 BITMAP_FREE (df->blocks_to_analyze); 345 df->blocks_to_analyze = NULL; 346 } 347 348 free (df_scan); 349} 350 351/* Dump the preamble for DF_SCAN dump. */ 352static void 353df_scan_start_dump (FILE *file ATTRIBUTE_UNUSED) 354{ 355 int i; 356 int dcount = 0; 357 int ucount = 0; 358 int ecount = 0; 359 int icount = 0; 360 int ccount = 0; 361 basic_block bb; 362 rtx_insn *insn; 363 364 fprintf (file, ";; invalidated by call \t"); 365 df_print_regset (file, regs_invalidated_by_call_regset); 366 fprintf (file, ";; hardware regs used \t"); 367 df_print_regset (file, &df->hardware_regs_used); 368 fprintf (file, ";; regular block artificial uses \t"); 369 df_print_regset (file, &df->regular_block_artificial_uses); 370 fprintf (file, ";; eh block artificial uses \t"); 371 df_print_regset (file, &df->eh_block_artificial_uses); 372 fprintf (file, ";; entry block defs \t"); 373 df_print_regset (file, df->entry_block_defs); 374 fprintf (file, ";; exit block uses \t"); 375 df_print_regset (file, df->exit_block_uses); 376 fprintf (file, ";; regs ever live \t"); 377 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 378 if (df_regs_ever_live_p (i)) 379 fprintf (file, " %d[%s]", i, reg_names[i]); 380 fprintf (file, "\n;; ref usage \t"); 381 382 for (i = 0; i < (int)df->regs_inited; i++) 383 if (DF_REG_DEF_COUNT (i) || DF_REG_USE_COUNT (i) || DF_REG_EQ_USE_COUNT (i)) 384 { 385 const char * sep = ""; 386 387 fprintf (file, "r%d={", i); 388 if (DF_REG_DEF_COUNT (i)) 389 { 390 fprintf (file, "%dd", DF_REG_DEF_COUNT (i)); 391 sep = ","; 392 dcount += DF_REG_DEF_COUNT (i); 393 } 394 if (DF_REG_USE_COUNT (i)) 395 { 396 fprintf (file, "%s%du", sep, DF_REG_USE_COUNT (i)); 397 sep = ","; 398 ucount += DF_REG_USE_COUNT (i); 399 } 400 if (DF_REG_EQ_USE_COUNT (i)) 401 { 402 fprintf (file, "%s%de", sep, DF_REG_EQ_USE_COUNT (i)); 403 ecount += DF_REG_EQ_USE_COUNT (i); 404 } 405 fprintf (file, "} "); 406 } 407 408 FOR_EACH_BB_FN (bb, cfun) 409 FOR_BB_INSNS (bb, insn) 410 if (INSN_P (insn)) 411 { 412 if (CALL_P (insn)) 413 ccount++; 414 else 415 icount++; 416 } 417 418 fprintf (file, "\n;; total ref usage %d{%dd,%du,%de}" 419 " in %d{%d regular + %d call} insns.\n", 420 dcount + ucount + ecount, dcount, ucount, ecount, 421 icount + ccount, icount, ccount); 422} 423 424/* Dump the bb_info for a given basic block. */ 425static void 426df_scan_start_block (basic_block bb, FILE *file) 427{ 428 struct df_scan_bb_info *bb_info 429 = df_scan_get_bb_info (bb->index); 430 431 if (bb_info) 432 { 433 fprintf (file, ";; bb %d artificial_defs: ", bb->index); 434 df_refs_chain_dump (bb_info->artificial_defs, true, file); 435 fprintf (file, "\n;; bb %d artificial_uses: ", bb->index); 436 df_refs_chain_dump (bb_info->artificial_uses, true, file); 437 fprintf (file, "\n"); 438 } 439#if 0 440 { 441 rtx_insn *insn; 442 FOR_BB_INSNS (bb, insn) 443 if (INSN_P (insn)) 444 df_insn_debug (insn, false, file); 445 } 446#endif 447} 448 449static struct df_problem problem_SCAN = 450{ 451 DF_SCAN, /* Problem id. */ 452 DF_NONE, /* Direction. */ 453 df_scan_alloc, /* Allocate the problem specific data. */ 454 NULL, /* Reset global information. */ 455 df_scan_free_bb_info, /* Free basic block info. */ 456 NULL, /* Local compute function. */ 457 NULL, /* Init the solution specific data. */ 458 NULL, /* Iterative solver. */ 459 NULL, /* Confluence operator 0. */ 460 NULL, /* Confluence operator n. */ 461 NULL, /* Transfer function. */ 462 NULL, /* Finalize function. */ 463 df_scan_free, /* Free all of the problem information. */ 464 NULL, /* Remove this problem from the stack of dataflow problems. */ 465 df_scan_start_dump, /* Debugging. */ 466 df_scan_start_block, /* Debugging start block. */ 467 NULL, /* Debugging end block. */ 468 NULL, /* Debugging start insn. */ 469 NULL, /* Debugging end insn. */ 470 NULL, /* Incremental solution verify start. */ 471 NULL, /* Incremental solution verify end. */ 472 NULL, /* Dependent problem. */ 473 sizeof (struct df_scan_bb_info),/* Size of entry of block_info array. */ 474 TV_DF_SCAN, /* Timing variable. */ 475 false /* Reset blocks on dropping out of blocks_to_analyze. */ 476}; 477 478 479/* Create a new DATAFLOW instance and add it to an existing instance 480 of DF. The returned structure is what is used to get at the 481 solution. */ 482 483void 484df_scan_add_problem (void) 485{ 486 df_add_problem (&problem_SCAN); 487} 488 489 490/*---------------------------------------------------------------------------- 491 Storage Allocation Utilities 492----------------------------------------------------------------------------*/ 493 494 495/* First, grow the reg_info information. If the current size is less than 496 the number of pseudos, grow to 25% more than the number of 497 pseudos. 498 499 Second, assure that all of the slots up to max_reg_num have been 500 filled with reg_info structures. */ 501 502void 503df_grow_reg_info (void) 504{ 505 unsigned int max_reg = max_reg_num (); 506 unsigned int new_size = max_reg; 507 struct df_scan_problem_data *problem_data 508 = (struct df_scan_problem_data *) df_scan->problem_data; 509 unsigned int i; 510 511 if (df->regs_size < new_size) 512 { 513 new_size += new_size / 4; 514 df->def_regs = XRESIZEVEC (struct df_reg_info *, df->def_regs, new_size); 515 df->use_regs = XRESIZEVEC (struct df_reg_info *, df->use_regs, new_size); 516 df->eq_use_regs = XRESIZEVEC (struct df_reg_info *, df->eq_use_regs, 517 new_size); 518 df->def_info.begin = XRESIZEVEC (unsigned, df->def_info.begin, new_size); 519 df->def_info.count = XRESIZEVEC (unsigned, df->def_info.count, new_size); 520 df->use_info.begin = XRESIZEVEC (unsigned, df->use_info.begin, new_size); 521 df->use_info.count = XRESIZEVEC (unsigned, df->use_info.count, new_size); 522 df->regs_size = new_size; 523 } 524 525 for (i = df->regs_inited; i < max_reg; i++) 526 { 527 struct df_reg_info *reg_info; 528 529 reg_info = (struct df_reg_info *) pool_alloc (problem_data->reg_pool); 530 memset (reg_info, 0, sizeof (struct df_reg_info)); 531 df->def_regs[i] = reg_info; 532 reg_info = (struct df_reg_info *) pool_alloc (problem_data->reg_pool); 533 memset (reg_info, 0, sizeof (struct df_reg_info)); 534 df->use_regs[i] = reg_info; 535 reg_info = (struct df_reg_info *) pool_alloc (problem_data->reg_pool); 536 memset (reg_info, 0, sizeof (struct df_reg_info)); 537 df->eq_use_regs[i] = reg_info; 538 df->def_info.begin[i] = 0; 539 df->def_info.count[i] = 0; 540 df->use_info.begin[i] = 0; 541 df->use_info.count[i] = 0; 542 } 543 544 df->regs_inited = max_reg; 545} 546 547 548/* Grow the ref information. */ 549 550static void 551df_grow_ref_info (struct df_ref_info *ref_info, unsigned int new_size) 552{ 553 if (ref_info->refs_size < new_size) 554 { 555 ref_info->refs = XRESIZEVEC (df_ref, ref_info->refs, new_size); 556 memset (ref_info->refs + ref_info->refs_size, 0, 557 (new_size - ref_info->refs_size) *sizeof (df_ref)); 558 ref_info->refs_size = new_size; 559 } 560} 561 562 563/* Check and grow the ref information if necessary. This routine 564 guarantees total_size + BITMAP_ADDEND amount of entries in refs 565 array. It updates ref_info->refs_size only and does not change 566 ref_info->total_size. */ 567 568static void 569df_check_and_grow_ref_info (struct df_ref_info *ref_info, 570 unsigned bitmap_addend) 571{ 572 if (ref_info->refs_size < ref_info->total_size + bitmap_addend) 573 { 574 int new_size = ref_info->total_size + bitmap_addend; 575 new_size += ref_info->total_size / 4; 576 df_grow_ref_info (ref_info, new_size); 577 } 578} 579 580 581/* Grow the ref information. If the current size is less than the 582 number of instructions, grow to 25% more than the number of 583 instructions. */ 584 585void 586df_grow_insn_info (void) 587{ 588 unsigned int new_size = get_max_uid () + 1; 589 if (DF_INSN_SIZE () < new_size) 590 { 591 new_size += new_size / 4; 592 df->insns = XRESIZEVEC (struct df_insn_info *, df->insns, new_size); 593 memset (df->insns + df->insns_size, 0, 594 (new_size - DF_INSN_SIZE ()) *sizeof (struct df_insn_info *)); 595 DF_INSN_SIZE () = new_size; 596 } 597} 598 599 600 601 602/*---------------------------------------------------------------------------- 603 PUBLIC INTERFACES FOR SMALL GRAIN CHANGES TO SCANNING. 604----------------------------------------------------------------------------*/ 605 606/* Rescan all of the block_to_analyze or all of the blocks in the 607 function if df_set_blocks if blocks_to_analyze is NULL; */ 608 609void 610df_scan_blocks (void) 611{ 612 basic_block bb; 613 614 df->def_info.ref_order = DF_REF_ORDER_NO_TABLE; 615 df->use_info.ref_order = DF_REF_ORDER_NO_TABLE; 616 617 df_get_regular_block_artificial_uses (&df->regular_block_artificial_uses); 618 df_get_eh_block_artificial_uses (&df->eh_block_artificial_uses); 619 620 bitmap_ior_into (&df->eh_block_artificial_uses, 621 &df->regular_block_artificial_uses); 622 623 /* ENTRY and EXIT blocks have special defs/uses. */ 624 df_get_entry_block_def_set (df->entry_block_defs); 625 df_record_entry_block_defs (df->entry_block_defs); 626 df_get_exit_block_use_set (df->exit_block_uses); 627 df_record_exit_block_uses (df->exit_block_uses); 628 df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun, ENTRY_BLOCK)); 629 df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun, EXIT_BLOCK)); 630 631 /* Regular blocks */ 632 FOR_EACH_BB_FN (bb, cfun) 633 { 634 unsigned int bb_index = bb->index; 635 df_bb_refs_record (bb_index, true); 636 } 637} 638 639/* Create new refs under address LOC within INSN. This function is 640 only used externally. REF_FLAGS must be either 0 or DF_REF_IN_NOTE, 641 depending on whether LOC is inside PATTERN (INSN) or a note. */ 642 643void 644df_uses_create (rtx *loc, rtx_insn *insn, int ref_flags) 645{ 646 gcc_assert (!(ref_flags & ~DF_REF_IN_NOTE)); 647 df_uses_record (NULL, loc, DF_REF_REG_USE, 648 BLOCK_FOR_INSN (insn), 649 DF_INSN_INFO_GET (insn), 650 ref_flags); 651} 652 653static void 654df_install_ref_incremental (df_ref ref) 655{ 656 struct df_reg_info **reg_info; 657 struct df_ref_info *ref_info; 658 df_ref *ref_ptr; 659 bool add_to_table; 660 661 rtx_insn *insn = DF_REF_INSN (ref); 662 basic_block bb = BLOCK_FOR_INSN (insn); 663 664 if (DF_REF_REG_DEF_P (ref)) 665 { 666 reg_info = df->def_regs; 667 ref_info = &df->def_info; 668 ref_ptr = &DF_INSN_DEFS (insn); 669 add_to_table = ref_info->ref_order != DF_REF_ORDER_NO_TABLE; 670 } 671 else if (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE) 672 { 673 reg_info = df->eq_use_regs; 674 ref_info = &df->use_info; 675 ref_ptr = &DF_INSN_EQ_USES (insn); 676 switch (ref_info->ref_order) 677 { 678 case DF_REF_ORDER_UNORDERED_WITH_NOTES: 679 case DF_REF_ORDER_BY_REG_WITH_NOTES: 680 case DF_REF_ORDER_BY_INSN_WITH_NOTES: 681 add_to_table = true; 682 break; 683 default: 684 add_to_table = false; 685 break; 686 } 687 } 688 else 689 { 690 reg_info = df->use_regs; 691 ref_info = &df->use_info; 692 ref_ptr = &DF_INSN_USES (insn); 693 add_to_table = ref_info->ref_order != DF_REF_ORDER_NO_TABLE; 694 } 695 696 /* Do not add if ref is not in the right blocks. */ 697 if (add_to_table && df->analyze_subset) 698 add_to_table = bitmap_bit_p (df->blocks_to_analyze, bb->index); 699 700 df_install_ref (ref, reg_info[DF_REF_REGNO (ref)], ref_info, add_to_table); 701 702 if (add_to_table) 703 switch (ref_info->ref_order) 704 { 705 case DF_REF_ORDER_UNORDERED_WITH_NOTES: 706 case DF_REF_ORDER_BY_REG_WITH_NOTES: 707 case DF_REF_ORDER_BY_INSN_WITH_NOTES: 708 ref_info->ref_order = DF_REF_ORDER_UNORDERED_WITH_NOTES; 709 break; 710 default: 711 ref_info->ref_order = DF_REF_ORDER_UNORDERED; 712 break; 713 } 714 715 while (*ref_ptr && df_ref_compare (*ref_ptr, ref) < 0) 716 ref_ptr = &DF_REF_NEXT_LOC (*ref_ptr); 717 718 DF_REF_NEXT_LOC (ref) = *ref_ptr; 719 *ref_ptr = ref; 720 721#if 0 722 if (dump_file) 723 { 724 fprintf (dump_file, "adding ref "); 725 df_ref_debug (ref, dump_file); 726 } 727#endif 728 /* By adding the ref directly, df_insn_rescan my not find any 729 differences even though the block will have changed. So we need 730 to mark the block dirty ourselves. */ 731 if (!DEBUG_INSN_P (DF_REF_INSN (ref))) 732 df_set_bb_dirty (bb); 733} 734 735 736 737/*---------------------------------------------------------------------------- 738 UTILITIES TO CREATE AND DESTROY REFS AND CHAINS. 739----------------------------------------------------------------------------*/ 740 741static void 742df_free_ref (df_ref ref) 743{ 744 struct df_scan_problem_data *problem_data 745 = (struct df_scan_problem_data *) df_scan->problem_data; 746 747 switch (DF_REF_CLASS (ref)) 748 { 749 case DF_REF_BASE: 750 pool_free (problem_data->ref_base_pool, ref); 751 break; 752 753 case DF_REF_ARTIFICIAL: 754 pool_free (problem_data->ref_artificial_pool, ref); 755 break; 756 757 case DF_REF_REGULAR: 758 pool_free (problem_data->ref_regular_pool, ref); 759 break; 760 } 761} 762 763 764/* Unlink and delete REF at the reg_use, reg_eq_use or reg_def chain. 765 Also delete the def-use or use-def chain if it exists. */ 766 767static void 768df_reg_chain_unlink (df_ref ref) 769{ 770 df_ref next = DF_REF_NEXT_REG (ref); 771 df_ref prev = DF_REF_PREV_REG (ref); 772 int id = DF_REF_ID (ref); 773 struct df_reg_info *reg_info; 774 df_ref *refs = NULL; 775 776 if (DF_REF_REG_DEF_P (ref)) 777 { 778 int regno = DF_REF_REGNO (ref); 779 reg_info = DF_REG_DEF_GET (regno); 780 refs = df->def_info.refs; 781 } 782 else 783 { 784 if (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE) 785 { 786 reg_info = DF_REG_EQ_USE_GET (DF_REF_REGNO (ref)); 787 switch (df->use_info.ref_order) 788 { 789 case DF_REF_ORDER_UNORDERED_WITH_NOTES: 790 case DF_REF_ORDER_BY_REG_WITH_NOTES: 791 case DF_REF_ORDER_BY_INSN_WITH_NOTES: 792 refs = df->use_info.refs; 793 break; 794 default: 795 break; 796 } 797 } 798 else 799 { 800 reg_info = DF_REG_USE_GET (DF_REF_REGNO (ref)); 801 refs = df->use_info.refs; 802 } 803 } 804 805 if (refs) 806 { 807 if (df->analyze_subset) 808 { 809 if (bitmap_bit_p (df->blocks_to_analyze, DF_REF_BBNO (ref))) 810 refs[id] = NULL; 811 } 812 else 813 refs[id] = NULL; 814 } 815 816 /* Delete any def-use or use-def chains that start here. It is 817 possible that there is trash in this field. This happens for 818 insns that have been deleted when rescanning has been deferred 819 and the chain problem has also been deleted. The chain tear down 820 code skips deleted insns. */ 821 if (df_chain && DF_REF_CHAIN (ref)) 822 df_chain_unlink (ref); 823 824 reg_info->n_refs--; 825 if (DF_REF_FLAGS_IS_SET (ref, DF_HARD_REG_LIVE)) 826 { 827 gcc_assert (DF_REF_REGNO (ref) < FIRST_PSEUDO_REGISTER); 828 df->hard_regs_live_count[DF_REF_REGNO (ref)]--; 829 } 830 831 /* Unlink from the reg chain. If there is no prev, this is the 832 first of the list. If not, just join the next and prev. */ 833 if (prev) 834 DF_REF_NEXT_REG (prev) = next; 835 else 836 { 837 gcc_assert (reg_info->reg_chain == ref); 838 reg_info->reg_chain = next; 839 } 840 if (next) 841 DF_REF_PREV_REG (next) = prev; 842 843 df_free_ref (ref); 844} 845 846 847/* Create the insn record for INSN. If there was one there, zero it 848 out. */ 849 850struct df_insn_info * 851df_insn_create_insn_record (rtx_insn *insn) 852{ 853 struct df_scan_problem_data *problem_data 854 = (struct df_scan_problem_data *) df_scan->problem_data; 855 struct df_insn_info *insn_rec; 856 857 df_grow_insn_info (); 858 insn_rec = DF_INSN_INFO_GET (insn); 859 if (!insn_rec) 860 { 861 insn_rec = (struct df_insn_info *) pool_alloc (problem_data->insn_pool); 862 DF_INSN_INFO_SET (insn, insn_rec); 863 } 864 memset (insn_rec, 0, sizeof (struct df_insn_info)); 865 insn_rec->insn = insn; 866 return insn_rec; 867} 868 869 870/* Delete all du chain (DF_REF_CHAIN()) of all refs in the ref chain. */ 871 872static void 873df_ref_chain_delete_du_chain (df_ref ref) 874{ 875 for (; ref; ref = DF_REF_NEXT_LOC (ref)) 876 /* CHAIN is allocated by DF_CHAIN. So make sure to 877 pass df_scan instance for the problem. */ 878 if (DF_REF_CHAIN (ref)) 879 df_chain_unlink (ref); 880} 881 882 883/* Delete all refs in the ref chain. */ 884 885static void 886df_ref_chain_delete (df_ref ref) 887{ 888 df_ref next; 889 for (; ref; ref = next) 890 { 891 next = DF_REF_NEXT_LOC (ref); 892 df_reg_chain_unlink (ref); 893 } 894} 895 896 897/* Delete the hardreg chain. */ 898 899static void 900df_mw_hardreg_chain_delete (struct df_mw_hardreg *hardregs) 901{ 902 struct df_scan_problem_data *problem_data 903 = (struct df_scan_problem_data *) df_scan->problem_data; 904 df_mw_hardreg *next; 905 906 for (; hardregs; hardregs = next) 907 { 908 next = DF_MWS_NEXT (hardregs); 909 pool_free (problem_data->mw_reg_pool, hardregs); 910 } 911} 912 913 914/* Delete all of the refs information from the insn with UID. 915 Internal helper for df_insn_delete, df_insn_rescan, and other 916 df-scan routines that don't have to work in deferred mode 917 and do not have to mark basic blocks for re-processing. */ 918 919static void 920df_insn_info_delete (unsigned int uid) 921{ 922 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid); 923 924 bitmap_clear_bit (&df->insns_to_delete, uid); 925 bitmap_clear_bit (&df->insns_to_rescan, uid); 926 bitmap_clear_bit (&df->insns_to_notes_rescan, uid); 927 if (insn_info) 928 { 929 struct df_scan_problem_data *problem_data 930 = (struct df_scan_problem_data *) df_scan->problem_data; 931 932 /* In general, notes do not have the insn_info fields 933 initialized. However, combine deletes insns by changing them 934 to notes. How clever. So we cannot just check if it is a 935 valid insn before short circuiting this code, we need to see 936 if we actually initialized it. */ 937 df_mw_hardreg_chain_delete (insn_info->mw_hardregs); 938 939 if (df_chain) 940 { 941 df_ref_chain_delete_du_chain (insn_info->defs); 942 df_ref_chain_delete_du_chain (insn_info->uses); 943 df_ref_chain_delete_du_chain (insn_info->eq_uses); 944 } 945 946 df_ref_chain_delete (insn_info->defs); 947 df_ref_chain_delete (insn_info->uses); 948 df_ref_chain_delete (insn_info->eq_uses); 949 950 pool_free (problem_data->insn_pool, insn_info); 951 DF_INSN_UID_SET (uid, NULL); 952 } 953} 954 955/* Delete all of the refs information from INSN, either right now 956 or marked for later in deferred mode. */ 957 958void 959df_insn_delete (rtx_insn *insn) 960{ 961 unsigned int uid; 962 basic_block bb; 963 964 gcc_checking_assert (INSN_P (insn)); 965 966 if (!df) 967 return; 968 969 uid = INSN_UID (insn); 970 bb = BLOCK_FOR_INSN (insn); 971 972 /* ??? bb can be NULL after pass_free_cfg. At that point, DF should 973 not exist anymore (as mentioned in df-core.c: "The only requirement 974 [for DF] is that there be a correct control flow graph." Clearly 975 that isn't the case after pass_free_cfg. But DF is freed much later 976 because some back-ends want to use DF info even though the CFG is 977 already gone. It's not clear to me whether that is safe, actually. 978 In any case, we expect BB to be non-NULL at least up to register 979 allocation, so disallow a non-NULL BB up to there. Not perfect 980 but better than nothing... */ 981 gcc_checking_assert (bb != NULL || reload_completed); 982 983 df_grow_bb_info (df_scan); 984 df_grow_reg_info (); 985 986 /* The block must be marked as dirty now, rather than later as in 987 df_insn_rescan and df_notes_rescan because it may not be there at 988 rescanning time and the mark would blow up. 989 DEBUG_INSNs do not make a block's data flow solution dirty (at 990 worst the LUIDs are no longer contiguous). */ 991 if (bb != NULL && NONDEBUG_INSN_P (insn)) 992 df_set_bb_dirty (bb); 993 994 /* The client has deferred rescanning. */ 995 if (df->changeable_flags & DF_DEFER_INSN_RESCAN) 996 { 997 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid); 998 if (insn_info) 999 { 1000 bitmap_clear_bit (&df->insns_to_rescan, uid); 1001 bitmap_clear_bit (&df->insns_to_notes_rescan, uid); 1002 bitmap_set_bit (&df->insns_to_delete, uid); 1003 } 1004 if (dump_file) 1005 fprintf (dump_file, "deferring deletion of insn with uid = %d.\n", uid); 1006 return; 1007 } 1008 1009 if (dump_file) 1010 fprintf (dump_file, "deleting insn with uid = %d.\n", uid); 1011 1012 df_insn_info_delete (uid); 1013} 1014 1015 1016/* Free all of the refs and the mw_hardregs in COLLECTION_REC. */ 1017 1018static void 1019df_free_collection_rec (struct df_collection_rec *collection_rec) 1020{ 1021 unsigned int ix; 1022 struct df_scan_problem_data *problem_data 1023 = (struct df_scan_problem_data *) df_scan->problem_data; 1024 df_ref ref; 1025 struct df_mw_hardreg *mw; 1026 1027 FOR_EACH_VEC_ELT (collection_rec->def_vec, ix, ref) 1028 df_free_ref (ref); 1029 FOR_EACH_VEC_ELT (collection_rec->use_vec, ix, ref) 1030 df_free_ref (ref); 1031 FOR_EACH_VEC_ELT (collection_rec->eq_use_vec, ix, ref) 1032 df_free_ref (ref); 1033 FOR_EACH_VEC_ELT (collection_rec->mw_vec, ix, mw) 1034 pool_free (problem_data->mw_reg_pool, mw); 1035 1036 collection_rec->def_vec.release (); 1037 collection_rec->use_vec.release (); 1038 collection_rec->eq_use_vec.release (); 1039 collection_rec->mw_vec.release (); 1040} 1041 1042/* Rescan INSN. Return TRUE if the rescanning produced any changes. */ 1043 1044bool 1045df_insn_rescan (rtx_insn *insn) 1046{ 1047 unsigned int uid = INSN_UID (insn); 1048 struct df_insn_info *insn_info = NULL; 1049 basic_block bb = BLOCK_FOR_INSN (insn); 1050 struct df_collection_rec collection_rec; 1051 1052 if ((!df) || (!INSN_P (insn))) 1053 return false; 1054 1055 if (!bb) 1056 { 1057 if (dump_file) 1058 fprintf (dump_file, "no bb for insn with uid = %d.\n", uid); 1059 return false; 1060 } 1061 1062 /* The client has disabled rescanning and plans to do it itself. */ 1063 if (df->changeable_flags & DF_NO_INSN_RESCAN) 1064 return false; 1065 1066 df_grow_bb_info (df_scan); 1067 df_grow_reg_info (); 1068 1069 insn_info = DF_INSN_UID_SAFE_GET (uid); 1070 1071 /* The client has deferred rescanning. */ 1072 if (df->changeable_flags & DF_DEFER_INSN_RESCAN) 1073 { 1074 if (!insn_info) 1075 { 1076 insn_info = df_insn_create_insn_record (insn); 1077 insn_info->defs = 0; 1078 insn_info->uses = 0; 1079 insn_info->eq_uses = 0; 1080 insn_info->mw_hardregs = 0; 1081 } 1082 if (dump_file) 1083 fprintf (dump_file, "deferring rescan insn with uid = %d.\n", uid); 1084 1085 bitmap_clear_bit (&df->insns_to_delete, uid); 1086 bitmap_clear_bit (&df->insns_to_notes_rescan, uid); 1087 bitmap_set_bit (&df->insns_to_rescan, INSN_UID (insn)); 1088 return false; 1089 } 1090 1091 bitmap_clear_bit (&df->insns_to_delete, uid); 1092 bitmap_clear_bit (&df->insns_to_rescan, uid); 1093 bitmap_clear_bit (&df->insns_to_notes_rescan, uid); 1094 if (insn_info) 1095 { 1096 int luid; 1097 bool the_same = df_insn_refs_verify (&collection_rec, bb, insn, false); 1098 /* If there's no change, return false. */ 1099 if (the_same) 1100 { 1101 df_free_collection_rec (&collection_rec); 1102 if (dump_file) 1103 fprintf (dump_file, "verify found no changes in insn with uid = %d.\n", uid); 1104 return false; 1105 } 1106 if (dump_file) 1107 fprintf (dump_file, "rescanning insn with uid = %d.\n", uid); 1108 1109 /* There's change - we need to delete the existing info. 1110 Since the insn isn't moved, we can salvage its LUID. */ 1111 luid = DF_INSN_LUID (insn); 1112 df_insn_info_delete (uid); 1113 df_insn_create_insn_record (insn); 1114 DF_INSN_LUID (insn) = luid; 1115 } 1116 else 1117 { 1118 struct df_insn_info *insn_info = df_insn_create_insn_record (insn); 1119 df_insn_refs_collect (&collection_rec, bb, insn_info); 1120 if (dump_file) 1121 fprintf (dump_file, "scanning new insn with uid = %d.\n", uid); 1122 } 1123 1124 df_refs_add_to_chains (&collection_rec, bb, insn, copy_all); 1125 if (!DEBUG_INSN_P (insn)) 1126 df_set_bb_dirty (bb); 1127 1128 return true; 1129} 1130 1131/* Same as df_insn_rescan, but don't mark the basic block as 1132 dirty. */ 1133 1134bool 1135df_insn_rescan_debug_internal (rtx_insn *insn) 1136{ 1137 unsigned int uid = INSN_UID (insn); 1138 struct df_insn_info *insn_info; 1139 1140 gcc_assert (DEBUG_INSN_P (insn) 1141 && VAR_LOC_UNKNOWN_P (INSN_VAR_LOCATION_LOC (insn))); 1142 1143 if (!df) 1144 return false; 1145 1146 insn_info = DF_INSN_UID_SAFE_GET (INSN_UID (insn)); 1147 if (!insn_info) 1148 return false; 1149 1150 if (dump_file) 1151 fprintf (dump_file, "deleting debug_insn with uid = %d.\n", uid); 1152 1153 bitmap_clear_bit (&df->insns_to_delete, uid); 1154 bitmap_clear_bit (&df->insns_to_rescan, uid); 1155 bitmap_clear_bit (&df->insns_to_notes_rescan, uid); 1156 1157 if (insn_info->defs == 0 1158 && insn_info->uses == 0 1159 && insn_info->eq_uses == 0 1160 && insn_info->mw_hardregs == 0) 1161 return false; 1162 1163 df_mw_hardreg_chain_delete (insn_info->mw_hardregs); 1164 1165 if (df_chain) 1166 { 1167 df_ref_chain_delete_du_chain (insn_info->defs); 1168 df_ref_chain_delete_du_chain (insn_info->uses); 1169 df_ref_chain_delete_du_chain (insn_info->eq_uses); 1170 } 1171 1172 df_ref_chain_delete (insn_info->defs); 1173 df_ref_chain_delete (insn_info->uses); 1174 df_ref_chain_delete (insn_info->eq_uses); 1175 1176 insn_info->defs = 0; 1177 insn_info->uses = 0; 1178 insn_info->eq_uses = 0; 1179 insn_info->mw_hardregs = 0; 1180 1181 return true; 1182} 1183 1184 1185/* Rescan all of the insns in the function. Note that the artificial 1186 uses and defs are not touched. This function will destroy def-use 1187 or use-def chains. */ 1188 1189void 1190df_insn_rescan_all (void) 1191{ 1192 bool no_insn_rescan = false; 1193 bool defer_insn_rescan = false; 1194 basic_block bb; 1195 bitmap_iterator bi; 1196 unsigned int uid; 1197 bitmap_head tmp; 1198 1199 bitmap_initialize (&tmp, &df_bitmap_obstack); 1200 1201 if (df->changeable_flags & DF_NO_INSN_RESCAN) 1202 { 1203 df_clear_flags (DF_NO_INSN_RESCAN); 1204 no_insn_rescan = true; 1205 } 1206 1207 if (df->changeable_flags & DF_DEFER_INSN_RESCAN) 1208 { 1209 df_clear_flags (DF_DEFER_INSN_RESCAN); 1210 defer_insn_rescan = true; 1211 } 1212 1213 bitmap_copy (&tmp, &df->insns_to_delete); 1214 EXECUTE_IF_SET_IN_BITMAP (&tmp, 0, uid, bi) 1215 { 1216 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid); 1217 if (insn_info) 1218 df_insn_info_delete (uid); 1219 } 1220 1221 bitmap_clear (&tmp); 1222 bitmap_clear (&df->insns_to_delete); 1223 bitmap_clear (&df->insns_to_rescan); 1224 bitmap_clear (&df->insns_to_notes_rescan); 1225 1226 FOR_EACH_BB_FN (bb, cfun) 1227 { 1228 rtx_insn *insn; 1229 FOR_BB_INSNS (bb, insn) 1230 { 1231 df_insn_rescan (insn); 1232 } 1233 } 1234 1235 if (no_insn_rescan) 1236 df_set_flags (DF_NO_INSN_RESCAN); 1237 if (defer_insn_rescan) 1238 df_set_flags (DF_DEFER_INSN_RESCAN); 1239} 1240 1241 1242/* Process all of the deferred rescans or deletions. */ 1243 1244void 1245df_process_deferred_rescans (void) 1246{ 1247 bool no_insn_rescan = false; 1248 bool defer_insn_rescan = false; 1249 bitmap_iterator bi; 1250 unsigned int uid; 1251 bitmap_head tmp; 1252 1253 bitmap_initialize (&tmp, &df_bitmap_obstack); 1254 1255 if (df->changeable_flags & DF_NO_INSN_RESCAN) 1256 { 1257 df_clear_flags (DF_NO_INSN_RESCAN); 1258 no_insn_rescan = true; 1259 } 1260 1261 if (df->changeable_flags & DF_DEFER_INSN_RESCAN) 1262 { 1263 df_clear_flags (DF_DEFER_INSN_RESCAN); 1264 defer_insn_rescan = true; 1265 } 1266 1267 if (dump_file) 1268 fprintf (dump_file, "starting the processing of deferred insns\n"); 1269 1270 bitmap_copy (&tmp, &df->insns_to_delete); 1271 EXECUTE_IF_SET_IN_BITMAP (&tmp, 0, uid, bi) 1272 { 1273 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid); 1274 if (insn_info) 1275 df_insn_info_delete (uid); 1276 } 1277 1278 bitmap_copy (&tmp, &df->insns_to_rescan); 1279 EXECUTE_IF_SET_IN_BITMAP (&tmp, 0, uid, bi) 1280 { 1281 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid); 1282 if (insn_info) 1283 df_insn_rescan (insn_info->insn); 1284 } 1285 1286 bitmap_copy (&tmp, &df->insns_to_notes_rescan); 1287 EXECUTE_IF_SET_IN_BITMAP (&tmp, 0, uid, bi) 1288 { 1289 struct df_insn_info *insn_info = DF_INSN_UID_SAFE_GET (uid); 1290 if (insn_info) 1291 df_notes_rescan (insn_info->insn); 1292 } 1293 1294 if (dump_file) 1295 fprintf (dump_file, "ending the processing of deferred insns\n"); 1296 1297 bitmap_clear (&tmp); 1298 bitmap_clear (&df->insns_to_delete); 1299 bitmap_clear (&df->insns_to_rescan); 1300 bitmap_clear (&df->insns_to_notes_rescan); 1301 1302 if (no_insn_rescan) 1303 df_set_flags (DF_NO_INSN_RESCAN); 1304 if (defer_insn_rescan) 1305 df_set_flags (DF_DEFER_INSN_RESCAN); 1306 1307 /* If someone changed regs_ever_live during this pass, fix up the 1308 entry and exit blocks. */ 1309 if (df->redo_entry_and_exit) 1310 { 1311 df_update_entry_exit_and_calls (); 1312 df->redo_entry_and_exit = false; 1313 } 1314} 1315 1316 1317/* Count the number of refs. Include the defs if INCLUDE_DEFS. Include 1318 the uses if INCLUDE_USES. Include the eq_uses if 1319 INCLUDE_EQ_USES. */ 1320 1321static unsigned int 1322df_count_refs (bool include_defs, bool include_uses, 1323 bool include_eq_uses) 1324{ 1325 unsigned int regno; 1326 int size = 0; 1327 unsigned int m = df->regs_inited; 1328 1329 for (regno = 0; regno < m; regno++) 1330 { 1331 if (include_defs) 1332 size += DF_REG_DEF_COUNT (regno); 1333 if (include_uses) 1334 size += DF_REG_USE_COUNT (regno); 1335 if (include_eq_uses) 1336 size += DF_REG_EQ_USE_COUNT (regno); 1337 } 1338 return size; 1339} 1340 1341 1342/* Take build ref table for either the uses or defs from the reg-use 1343 or reg-def chains. This version processes the refs in reg order 1344 which is likely to be best if processing the whole function. */ 1345 1346static void 1347df_reorganize_refs_by_reg_by_reg (struct df_ref_info *ref_info, 1348 bool include_defs, 1349 bool include_uses, 1350 bool include_eq_uses) 1351{ 1352 unsigned int m = df->regs_inited; 1353 unsigned int regno; 1354 unsigned int offset = 0; 1355 unsigned int start; 1356 1357 if (df->changeable_flags & DF_NO_HARD_REGS) 1358 { 1359 start = FIRST_PSEUDO_REGISTER; 1360 memset (ref_info->begin, 0, sizeof (int) * FIRST_PSEUDO_REGISTER); 1361 memset (ref_info->count, 0, sizeof (int) * FIRST_PSEUDO_REGISTER); 1362 } 1363 else 1364 start = 0; 1365 1366 ref_info->total_size 1367 = df_count_refs (include_defs, include_uses, include_eq_uses); 1368 1369 df_check_and_grow_ref_info (ref_info, 1); 1370 1371 for (regno = start; regno < m; regno++) 1372 { 1373 int count = 0; 1374 ref_info->begin[regno] = offset; 1375 if (include_defs) 1376 { 1377 df_ref ref = DF_REG_DEF_CHAIN (regno); 1378 while (ref) 1379 { 1380 ref_info->refs[offset] = ref; 1381 DF_REF_ID (ref) = offset++; 1382 count++; 1383 ref = DF_REF_NEXT_REG (ref); 1384 gcc_checking_assert (offset < ref_info->refs_size); 1385 } 1386 } 1387 if (include_uses) 1388 { 1389 df_ref ref = DF_REG_USE_CHAIN (regno); 1390 while (ref) 1391 { 1392 ref_info->refs[offset] = ref; 1393 DF_REF_ID (ref) = offset++; 1394 count++; 1395 ref = DF_REF_NEXT_REG (ref); 1396 gcc_checking_assert (offset < ref_info->refs_size); 1397 } 1398 } 1399 if (include_eq_uses) 1400 { 1401 df_ref ref = DF_REG_EQ_USE_CHAIN (regno); 1402 while (ref) 1403 { 1404 ref_info->refs[offset] = ref; 1405 DF_REF_ID (ref) = offset++; 1406 count++; 1407 ref = DF_REF_NEXT_REG (ref); 1408 gcc_checking_assert (offset < ref_info->refs_size); 1409 } 1410 } 1411 ref_info->count[regno] = count; 1412 } 1413 1414 /* The bitmap size is not decremented when refs are deleted. So 1415 reset it now that we have squished out all of the empty 1416 slots. */ 1417 ref_info->table_size = offset; 1418} 1419 1420 1421/* Take build ref table for either the uses or defs from the reg-use 1422 or reg-def chains. This version processes the refs in insn order 1423 which is likely to be best if processing some segment of the 1424 function. */ 1425 1426static void 1427df_reorganize_refs_by_reg_by_insn (struct df_ref_info *ref_info, 1428 bool include_defs, 1429 bool include_uses, 1430 bool include_eq_uses) 1431{ 1432 bitmap_iterator bi; 1433 unsigned int bb_index; 1434 unsigned int m = df->regs_inited; 1435 unsigned int offset = 0; 1436 unsigned int r; 1437 unsigned int start 1438 = (df->changeable_flags & DF_NO_HARD_REGS) ? FIRST_PSEUDO_REGISTER : 0; 1439 1440 memset (ref_info->begin, 0, sizeof (int) * df->regs_inited); 1441 memset (ref_info->count, 0, sizeof (int) * df->regs_inited); 1442 1443 ref_info->total_size = df_count_refs (include_defs, include_uses, include_eq_uses); 1444 df_check_and_grow_ref_info (ref_info, 1); 1445 1446 EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi) 1447 { 1448 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index); 1449 rtx_insn *insn; 1450 df_ref def, use; 1451 1452 if (include_defs) 1453 FOR_EACH_ARTIFICIAL_DEF (def, bb_index) 1454 { 1455 unsigned int regno = DF_REF_REGNO (def); 1456 ref_info->count[regno]++; 1457 } 1458 if (include_uses) 1459 FOR_EACH_ARTIFICIAL_USE (use, bb_index) 1460 { 1461 unsigned int regno = DF_REF_REGNO (use); 1462 ref_info->count[regno]++; 1463 } 1464 1465 FOR_BB_INSNS (bb, insn) 1466 { 1467 if (INSN_P (insn)) 1468 { 1469 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn); 1470 1471 if (include_defs) 1472 FOR_EACH_INSN_INFO_DEF (def, insn_info) 1473 { 1474 unsigned int regno = DF_REF_REGNO (def); 1475 ref_info->count[regno]++; 1476 } 1477 if (include_uses) 1478 FOR_EACH_INSN_INFO_USE (use, insn_info) 1479 { 1480 unsigned int regno = DF_REF_REGNO (use); 1481 ref_info->count[regno]++; 1482 } 1483 if (include_eq_uses) 1484 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info) 1485 { 1486 unsigned int regno = DF_REF_REGNO (use); 1487 ref_info->count[regno]++; 1488 } 1489 } 1490 } 1491 } 1492 1493 for (r = start; r < m; r++) 1494 { 1495 ref_info->begin[r] = offset; 1496 offset += ref_info->count[r]; 1497 ref_info->count[r] = 0; 1498 } 1499 1500 EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi) 1501 { 1502 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index); 1503 rtx_insn *insn; 1504 df_ref def, use; 1505 1506 if (include_defs) 1507 FOR_EACH_ARTIFICIAL_DEF (def, bb_index) 1508 { 1509 unsigned int regno = DF_REF_REGNO (def); 1510 if (regno >= start) 1511 { 1512 unsigned int id 1513 = ref_info->begin[regno] + ref_info->count[regno]++; 1514 DF_REF_ID (def) = id; 1515 ref_info->refs[id] = def; 1516 } 1517 } 1518 if (include_uses) 1519 FOR_EACH_ARTIFICIAL_USE (use, bb_index) 1520 { 1521 unsigned int regno = DF_REF_REGNO (def); 1522 if (regno >= start) 1523 { 1524 unsigned int id 1525 = ref_info->begin[regno] + ref_info->count[regno]++; 1526 DF_REF_ID (use) = id; 1527 ref_info->refs[id] = use; 1528 } 1529 } 1530 1531 FOR_BB_INSNS (bb, insn) 1532 { 1533 if (INSN_P (insn)) 1534 { 1535 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn); 1536 1537 if (include_defs) 1538 FOR_EACH_INSN_INFO_DEF (def, insn_info) 1539 { 1540 unsigned int regno = DF_REF_REGNO (def); 1541 if (regno >= start) 1542 { 1543 unsigned int id 1544 = ref_info->begin[regno] + ref_info->count[regno]++; 1545 DF_REF_ID (def) = id; 1546 ref_info->refs[id] = def; 1547 } 1548 } 1549 if (include_uses) 1550 FOR_EACH_INSN_INFO_USE (use, insn_info) 1551 { 1552 unsigned int regno = DF_REF_REGNO (use); 1553 if (regno >= start) 1554 { 1555 unsigned int id 1556 = ref_info->begin[regno] + ref_info->count[regno]++; 1557 DF_REF_ID (use) = id; 1558 ref_info->refs[id] = use; 1559 } 1560 } 1561 if (include_eq_uses) 1562 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info) 1563 { 1564 unsigned int regno = DF_REF_REGNO (use); 1565 if (regno >= start) 1566 { 1567 unsigned int id 1568 = ref_info->begin[regno] + ref_info->count[regno]++; 1569 DF_REF_ID (use) = id; 1570 ref_info->refs[id] = use; 1571 } 1572 } 1573 } 1574 } 1575 } 1576 1577 /* The bitmap size is not decremented when refs are deleted. So 1578 reset it now that we have squished out all of the empty 1579 slots. */ 1580 1581 ref_info->table_size = offset; 1582} 1583 1584/* Take build ref table for either the uses or defs from the reg-use 1585 or reg-def chains. */ 1586 1587static void 1588df_reorganize_refs_by_reg (struct df_ref_info *ref_info, 1589 bool include_defs, 1590 bool include_uses, 1591 bool include_eq_uses) 1592{ 1593 if (df->analyze_subset) 1594 df_reorganize_refs_by_reg_by_insn (ref_info, include_defs, 1595 include_uses, include_eq_uses); 1596 else 1597 df_reorganize_refs_by_reg_by_reg (ref_info, include_defs, 1598 include_uses, include_eq_uses); 1599} 1600 1601 1602/* Add the refs in REF_VEC to the table in REF_INFO starting at OFFSET. */ 1603static unsigned int 1604df_add_refs_to_table (unsigned int offset, 1605 struct df_ref_info *ref_info, 1606 df_ref ref) 1607{ 1608 for (; ref; ref = DF_REF_NEXT_LOC (ref)) 1609 if (!(df->changeable_flags & DF_NO_HARD_REGS) 1610 || (DF_REF_REGNO (ref) >= FIRST_PSEUDO_REGISTER)) 1611 { 1612 ref_info->refs[offset] = ref; 1613 DF_REF_ID (ref) = offset++; 1614 } 1615 return offset; 1616} 1617 1618 1619/* Count the number of refs in all of the insns of BB. Include the 1620 defs if INCLUDE_DEFS. Include the uses if INCLUDE_USES. Include the 1621 eq_uses if INCLUDE_EQ_USES. */ 1622 1623static unsigned int 1624df_reorganize_refs_by_insn_bb (basic_block bb, unsigned int offset, 1625 struct df_ref_info *ref_info, 1626 bool include_defs, bool include_uses, 1627 bool include_eq_uses) 1628{ 1629 rtx_insn *insn; 1630 1631 if (include_defs) 1632 offset = df_add_refs_to_table (offset, ref_info, 1633 df_get_artificial_defs (bb->index)); 1634 if (include_uses) 1635 offset = df_add_refs_to_table (offset, ref_info, 1636 df_get_artificial_uses (bb->index)); 1637 1638 FOR_BB_INSNS (bb, insn) 1639 if (INSN_P (insn)) 1640 { 1641 unsigned int uid = INSN_UID (insn); 1642 if (include_defs) 1643 offset = df_add_refs_to_table (offset, ref_info, 1644 DF_INSN_UID_DEFS (uid)); 1645 if (include_uses) 1646 offset = df_add_refs_to_table (offset, ref_info, 1647 DF_INSN_UID_USES (uid)); 1648 if (include_eq_uses) 1649 offset = df_add_refs_to_table (offset, ref_info, 1650 DF_INSN_UID_EQ_USES (uid)); 1651 } 1652 return offset; 1653} 1654 1655 1656/* Organize the refs by insn into the table in REF_INFO. If 1657 blocks_to_analyze is defined, use that set, otherwise the entire 1658 program. Include the defs if INCLUDE_DEFS. Include the uses if 1659 INCLUDE_USES. Include the eq_uses if INCLUDE_EQ_USES. */ 1660 1661static void 1662df_reorganize_refs_by_insn (struct df_ref_info *ref_info, 1663 bool include_defs, bool include_uses, 1664 bool include_eq_uses) 1665{ 1666 basic_block bb; 1667 unsigned int offset = 0; 1668 1669 ref_info->total_size = df_count_refs (include_defs, include_uses, include_eq_uses); 1670 df_check_and_grow_ref_info (ref_info, 1); 1671 if (df->blocks_to_analyze) 1672 { 1673 bitmap_iterator bi; 1674 unsigned int index; 1675 1676 EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, index, bi) 1677 { 1678 offset = df_reorganize_refs_by_insn_bb (BASIC_BLOCK_FOR_FN (cfun, 1679 index), 1680 offset, ref_info, 1681 include_defs, include_uses, 1682 include_eq_uses); 1683 } 1684 1685 ref_info->table_size = offset; 1686 } 1687 else 1688 { 1689 FOR_ALL_BB_FN (bb, cfun) 1690 offset = df_reorganize_refs_by_insn_bb (bb, offset, ref_info, 1691 include_defs, include_uses, 1692 include_eq_uses); 1693 ref_info->table_size = offset; 1694 } 1695} 1696 1697 1698/* If the use refs in DF are not organized, reorganize them. */ 1699 1700void 1701df_maybe_reorganize_use_refs (enum df_ref_order order) 1702{ 1703 if (order == df->use_info.ref_order) 1704 return; 1705 1706 switch (order) 1707 { 1708 case DF_REF_ORDER_BY_REG: 1709 df_reorganize_refs_by_reg (&df->use_info, false, true, false); 1710 break; 1711 1712 case DF_REF_ORDER_BY_REG_WITH_NOTES: 1713 df_reorganize_refs_by_reg (&df->use_info, false, true, true); 1714 break; 1715 1716 case DF_REF_ORDER_BY_INSN: 1717 df_reorganize_refs_by_insn (&df->use_info, false, true, false); 1718 break; 1719 1720 case DF_REF_ORDER_BY_INSN_WITH_NOTES: 1721 df_reorganize_refs_by_insn (&df->use_info, false, true, true); 1722 break; 1723 1724 case DF_REF_ORDER_NO_TABLE: 1725 free (df->use_info.refs); 1726 df->use_info.refs = NULL; 1727 df->use_info.refs_size = 0; 1728 break; 1729 1730 case DF_REF_ORDER_UNORDERED: 1731 case DF_REF_ORDER_UNORDERED_WITH_NOTES: 1732 gcc_unreachable (); 1733 break; 1734 } 1735 1736 df->use_info.ref_order = order; 1737} 1738 1739 1740/* If the def refs in DF are not organized, reorganize them. */ 1741 1742void 1743df_maybe_reorganize_def_refs (enum df_ref_order order) 1744{ 1745 if (order == df->def_info.ref_order) 1746 return; 1747 1748 switch (order) 1749 { 1750 case DF_REF_ORDER_BY_REG: 1751 df_reorganize_refs_by_reg (&df->def_info, true, false, false); 1752 break; 1753 1754 case DF_REF_ORDER_BY_INSN: 1755 df_reorganize_refs_by_insn (&df->def_info, true, false, false); 1756 break; 1757 1758 case DF_REF_ORDER_NO_TABLE: 1759 free (df->def_info.refs); 1760 df->def_info.refs = NULL; 1761 df->def_info.refs_size = 0; 1762 break; 1763 1764 case DF_REF_ORDER_BY_INSN_WITH_NOTES: 1765 case DF_REF_ORDER_BY_REG_WITH_NOTES: 1766 case DF_REF_ORDER_UNORDERED: 1767 case DF_REF_ORDER_UNORDERED_WITH_NOTES: 1768 gcc_unreachable (); 1769 break; 1770 } 1771 1772 df->def_info.ref_order = order; 1773} 1774 1775 1776/* Change all of the basic block references in INSN to use the insn's 1777 current basic block. This function is called from routines that move 1778 instructions from one block to another. */ 1779 1780void 1781df_insn_change_bb (rtx_insn *insn, basic_block new_bb) 1782{ 1783 basic_block old_bb = BLOCK_FOR_INSN (insn); 1784 struct df_insn_info *insn_info; 1785 unsigned int uid = INSN_UID (insn); 1786 1787 if (old_bb == new_bb) 1788 return; 1789 1790 set_block_for_insn (insn, new_bb); 1791 1792 if (!df) 1793 return; 1794 1795 if (dump_file) 1796 fprintf (dump_file, "changing bb of uid %d\n", uid); 1797 1798 insn_info = DF_INSN_UID_SAFE_GET (uid); 1799 if (insn_info == NULL) 1800 { 1801 if (dump_file) 1802 fprintf (dump_file, " unscanned insn\n"); 1803 df_insn_rescan (insn); 1804 return; 1805 } 1806 1807 if (!INSN_P (insn)) 1808 return; 1809 1810 df_set_bb_dirty (new_bb); 1811 if (old_bb) 1812 { 1813 if (dump_file) 1814 fprintf (dump_file, " from %d to %d\n", 1815 old_bb->index, new_bb->index); 1816 df_set_bb_dirty (old_bb); 1817 } 1818 else 1819 if (dump_file) 1820 fprintf (dump_file, " to %d\n", new_bb->index); 1821} 1822 1823 1824/* Helper function for df_ref_change_reg_with_loc. */ 1825 1826static void 1827df_ref_change_reg_with_loc_1 (struct df_reg_info *old_df, 1828 struct df_reg_info *new_df, 1829 int new_regno, rtx loc) 1830{ 1831 df_ref the_ref = old_df->reg_chain; 1832 1833 while (the_ref) 1834 { 1835 if ((!DF_REF_IS_ARTIFICIAL (the_ref)) 1836 && DF_REF_LOC (the_ref) 1837 && (*DF_REF_LOC (the_ref) == loc)) 1838 { 1839 df_ref next_ref = DF_REF_NEXT_REG (the_ref); 1840 df_ref prev_ref = DF_REF_PREV_REG (the_ref); 1841 df_ref *ref_ptr; 1842 struct df_insn_info *insn_info = DF_REF_INSN_INFO (the_ref); 1843 1844 DF_REF_REGNO (the_ref) = new_regno; 1845 DF_REF_REG (the_ref) = regno_reg_rtx[new_regno]; 1846 1847 /* Pull the_ref out of the old regno chain. */ 1848 if (prev_ref) 1849 DF_REF_NEXT_REG (prev_ref) = next_ref; 1850 else 1851 old_df->reg_chain = next_ref; 1852 if (next_ref) 1853 DF_REF_PREV_REG (next_ref) = prev_ref; 1854 old_df->n_refs--; 1855 1856 /* Put the ref into the new regno chain. */ 1857 DF_REF_PREV_REG (the_ref) = NULL; 1858 DF_REF_NEXT_REG (the_ref) = new_df->reg_chain; 1859 if (new_df->reg_chain) 1860 DF_REF_PREV_REG (new_df->reg_chain) = the_ref; 1861 new_df->reg_chain = the_ref; 1862 new_df->n_refs++; 1863 if (DF_REF_BB (the_ref)) 1864 df_set_bb_dirty (DF_REF_BB (the_ref)); 1865 1866 /* Need to sort the record again that the ref was in because 1867 the regno is a sorting key. First, find the right 1868 record. */ 1869 if (DF_REF_REG_DEF_P (the_ref)) 1870 ref_ptr = &insn_info->defs; 1871 else if (DF_REF_FLAGS (the_ref) & DF_REF_IN_NOTE) 1872 ref_ptr = &insn_info->eq_uses; 1873 else 1874 ref_ptr = &insn_info->uses; 1875 if (dump_file) 1876 fprintf (dump_file, "changing reg in insn %d\n", 1877 DF_REF_INSN_UID (the_ref)); 1878 1879 /* Stop if we find the current reference or where the reference 1880 needs to be. */ 1881 while (*ref_ptr != the_ref && df_ref_compare (*ref_ptr, the_ref) < 0) 1882 ref_ptr = &DF_REF_NEXT_LOC (*ref_ptr); 1883 if (*ref_ptr != the_ref) 1884 { 1885 /* The reference needs to be promoted up the list. */ 1886 df_ref next = DF_REF_NEXT_LOC (the_ref); 1887 DF_REF_NEXT_LOC (the_ref) = *ref_ptr; 1888 *ref_ptr = the_ref; 1889 do 1890 ref_ptr = &DF_REF_NEXT_LOC (*ref_ptr); 1891 while (*ref_ptr != the_ref); 1892 *ref_ptr = next; 1893 } 1894 else if (DF_REF_NEXT_LOC (the_ref) 1895 && df_ref_compare (the_ref, DF_REF_NEXT_LOC (the_ref)) > 0) 1896 { 1897 /* The reference needs to be demoted down the list. */ 1898 *ref_ptr = DF_REF_NEXT_LOC (the_ref); 1899 do 1900 ref_ptr = &DF_REF_NEXT_LOC (*ref_ptr); 1901 while (*ref_ptr && df_ref_compare (the_ref, *ref_ptr) > 0); 1902 DF_REF_NEXT_LOC (the_ref) = *ref_ptr; 1903 *ref_ptr = the_ref; 1904 } 1905 1906 the_ref = next_ref; 1907 } 1908 else 1909 the_ref = DF_REF_NEXT_REG (the_ref); 1910 } 1911} 1912 1913 1914/* Change the regno of all refs that contained LOC from OLD_REGNO to 1915 NEW_REGNO. Refs that do not match LOC are not changed which means 1916 that artificial refs are not changed since they have no loc. This 1917 call is to support the SET_REGNO macro. */ 1918 1919void 1920df_ref_change_reg_with_loc (int old_regno, int new_regno, rtx loc) 1921{ 1922 if ((!df) || (old_regno == -1) || (old_regno == new_regno)) 1923 return; 1924 1925 df_grow_reg_info (); 1926 1927 df_ref_change_reg_with_loc_1 (DF_REG_DEF_GET (old_regno), 1928 DF_REG_DEF_GET (new_regno), new_regno, loc); 1929 df_ref_change_reg_with_loc_1 (DF_REG_USE_GET (old_regno), 1930 DF_REG_USE_GET (new_regno), new_regno, loc); 1931 df_ref_change_reg_with_loc_1 (DF_REG_EQ_USE_GET (old_regno), 1932 DF_REG_EQ_USE_GET (new_regno), new_regno, loc); 1933} 1934 1935 1936/* Delete the mw_hardregs that point into the eq_notes. */ 1937 1938static void 1939df_mw_hardreg_chain_delete_eq_uses (struct df_insn_info *insn_info) 1940{ 1941 struct df_mw_hardreg **mw_ptr = &insn_info->mw_hardregs; 1942 struct df_scan_problem_data *problem_data 1943 = (struct df_scan_problem_data *) df_scan->problem_data; 1944 1945 while (*mw_ptr) 1946 { 1947 df_mw_hardreg *mw = *mw_ptr; 1948 if (mw->flags & DF_REF_IN_NOTE) 1949 { 1950 *mw_ptr = DF_MWS_NEXT (mw); 1951 pool_free (problem_data->mw_reg_pool, mw); 1952 } 1953 else 1954 mw_ptr = &DF_MWS_NEXT (mw); 1955 } 1956} 1957 1958 1959/* Rescan only the REG_EQUIV/REG_EQUAL notes part of INSN. */ 1960 1961void 1962df_notes_rescan (rtx_insn *insn) 1963{ 1964 struct df_insn_info *insn_info; 1965 unsigned int uid = INSN_UID (insn); 1966 1967 if (!df) 1968 return; 1969 1970 /* The client has disabled rescanning and plans to do it itself. */ 1971 if (df->changeable_flags & DF_NO_INSN_RESCAN) 1972 return; 1973 1974 /* Do nothing if the insn hasn't been emitted yet. */ 1975 if (!BLOCK_FOR_INSN (insn)) 1976 return; 1977 1978 df_grow_bb_info (df_scan); 1979 df_grow_reg_info (); 1980 1981 insn_info = DF_INSN_UID_SAFE_GET (INSN_UID (insn)); 1982 1983 /* The client has deferred rescanning. */ 1984 if (df->changeable_flags & DF_DEFER_INSN_RESCAN) 1985 { 1986 if (!insn_info) 1987 { 1988 insn_info = df_insn_create_insn_record (insn); 1989 insn_info->defs = 0; 1990 insn_info->uses = 0; 1991 insn_info->eq_uses = 0; 1992 insn_info->mw_hardregs = 0; 1993 } 1994 1995 bitmap_clear_bit (&df->insns_to_delete, uid); 1996 /* If the insn is set to be rescanned, it does not need to also 1997 be notes rescanned. */ 1998 if (!bitmap_bit_p (&df->insns_to_rescan, uid)) 1999 bitmap_set_bit (&df->insns_to_notes_rescan, INSN_UID (insn)); 2000 return; 2001 } 2002 2003 bitmap_clear_bit (&df->insns_to_delete, uid); 2004 bitmap_clear_bit (&df->insns_to_notes_rescan, uid); 2005 2006 if (insn_info) 2007 { 2008 basic_block bb = BLOCK_FOR_INSN (insn); 2009 rtx note; 2010 struct df_collection_rec collection_rec; 2011 unsigned int i; 2012 2013 df_mw_hardreg_chain_delete_eq_uses (insn_info); 2014 df_ref_chain_delete (insn_info->eq_uses); 2015 insn_info->eq_uses = NULL; 2016 2017 /* Process REG_EQUIV/REG_EQUAL notes */ 2018 for (note = REG_NOTES (insn); note; 2019 note = XEXP (note, 1)) 2020 { 2021 switch (REG_NOTE_KIND (note)) 2022 { 2023 case REG_EQUIV: 2024 case REG_EQUAL: 2025 df_uses_record (&collection_rec, 2026 &XEXP (note, 0), DF_REF_REG_USE, 2027 bb, insn_info, DF_REF_IN_NOTE); 2028 default: 2029 break; 2030 } 2031 } 2032 2033 /* Find some place to put any new mw_hardregs. */ 2034 df_canonize_collection_rec (&collection_rec); 2035 struct df_mw_hardreg **mw_ptr = &insn_info->mw_hardregs, *mw; 2036 FOR_EACH_VEC_ELT (collection_rec.mw_vec, i, mw) 2037 { 2038 while (*mw_ptr && df_mw_compare (*mw_ptr, mw) < 0) 2039 mw_ptr = &DF_MWS_NEXT (*mw_ptr); 2040 DF_MWS_NEXT (mw) = *mw_ptr; 2041 *mw_ptr = mw; 2042 mw_ptr = &DF_MWS_NEXT (mw); 2043 } 2044 df_refs_add_to_chains (&collection_rec, bb, insn, copy_eq_uses); 2045 } 2046 else 2047 df_insn_rescan (insn); 2048 2049} 2050 2051 2052/*---------------------------------------------------------------------------- 2053 Hard core instruction scanning code. No external interfaces here, 2054 just a lot of routines that look inside insns. 2055----------------------------------------------------------------------------*/ 2056 2057 2058/* Return true if the contents of two df_ref's are identical. 2059 It ignores DF_REF_MARKER. */ 2060 2061static bool 2062df_ref_equal_p (df_ref ref1, df_ref ref2) 2063{ 2064 if (!ref2) 2065 return false; 2066 2067 if (ref1 == ref2) 2068 return true; 2069 2070 if (DF_REF_CLASS (ref1) != DF_REF_CLASS (ref2) 2071 || DF_REF_REGNO (ref1) != DF_REF_REGNO (ref2) 2072 || DF_REF_REG (ref1) != DF_REF_REG (ref2) 2073 || DF_REF_TYPE (ref1) != DF_REF_TYPE (ref2) 2074 || ((DF_REF_FLAGS (ref1) & ~(DF_REF_REG_MARKER + DF_REF_MW_HARDREG)) 2075 != (DF_REF_FLAGS (ref2) & ~(DF_REF_REG_MARKER + DF_REF_MW_HARDREG))) 2076 || DF_REF_BB (ref1) != DF_REF_BB (ref2) 2077 || DF_REF_INSN_INFO (ref1) != DF_REF_INSN_INFO (ref2)) 2078 return false; 2079 2080 switch (DF_REF_CLASS (ref1)) 2081 { 2082 case DF_REF_ARTIFICIAL: 2083 case DF_REF_BASE: 2084 return true; 2085 2086 case DF_REF_REGULAR: 2087 return DF_REF_LOC (ref1) == DF_REF_LOC (ref2); 2088 2089 default: 2090 gcc_unreachable (); 2091 } 2092 return false; 2093} 2094 2095 2096/* Compare REF1 and REF2 for sorting. This is only called from places 2097 where all of the refs are of the same type, in the same insn, and 2098 have the same bb. So these fields are not checked. */ 2099 2100static int 2101df_ref_compare (df_ref ref1, df_ref ref2) 2102{ 2103 if (DF_REF_CLASS (ref1) != DF_REF_CLASS (ref2)) 2104 return (int)DF_REF_CLASS (ref1) - (int)DF_REF_CLASS (ref2); 2105 2106 if (DF_REF_REGNO (ref1) != DF_REF_REGNO (ref2)) 2107 return (int)DF_REF_REGNO (ref1) - (int)DF_REF_REGNO (ref2); 2108 2109 if (DF_REF_TYPE (ref1) != DF_REF_TYPE (ref2)) 2110 return (int)DF_REF_TYPE (ref1) - (int)DF_REF_TYPE (ref2); 2111 2112 if (DF_REF_REG (ref1) != DF_REF_REG (ref2)) 2113 return (int)DF_REF_ORDER (ref1) - (int)DF_REF_ORDER (ref2); 2114 2115 /* Cannot look at the LOC field on artificial refs. */ 2116 if (DF_REF_CLASS (ref1) != DF_REF_ARTIFICIAL 2117 && DF_REF_LOC (ref1) != DF_REF_LOC (ref2)) 2118 return (int)DF_REF_ORDER (ref1) - (int)DF_REF_ORDER (ref2); 2119 2120 if (DF_REF_FLAGS (ref1) != DF_REF_FLAGS (ref2)) 2121 { 2122 /* If two refs are identical except that one of them has is from 2123 a mw and one is not, we need to have the one with the mw 2124 first. */ 2125 if (DF_REF_FLAGS_IS_SET (ref1, DF_REF_MW_HARDREG) == 2126 DF_REF_FLAGS_IS_SET (ref2, DF_REF_MW_HARDREG)) 2127 return DF_REF_FLAGS (ref1) - DF_REF_FLAGS (ref2); 2128 else if (DF_REF_FLAGS_IS_SET (ref1, DF_REF_MW_HARDREG)) 2129 return -1; 2130 else 2131 return 1; 2132 } 2133 2134 return (int)DF_REF_ORDER (ref1) - (int)DF_REF_ORDER (ref2); 2135} 2136 2137/* Like df_ref_compare, but compare two df_ref* pointers R1 and R2. */ 2138 2139static int 2140df_ref_ptr_compare (const void *r1, const void *r2) 2141{ 2142 return df_ref_compare (*(const df_ref *) r1, *(const df_ref *) r2); 2143} 2144 2145static void 2146df_swap_refs (vec<df_ref, va_heap> *ref_vec, int i, int j) 2147{ 2148 df_ref tmp = (*ref_vec)[i]; 2149 (*ref_vec)[i] = (*ref_vec)[j]; 2150 (*ref_vec)[j] = tmp; 2151} 2152 2153/* Sort and compress a set of refs. */ 2154 2155static void 2156df_sort_and_compress_refs (vec<df_ref, va_heap> *ref_vec) 2157{ 2158 unsigned int count; 2159 unsigned int i; 2160 unsigned int dist = 0; 2161 2162 count = ref_vec->length (); 2163 2164 /* If there are 1 or 0 elements, there is nothing to do. */ 2165 if (count < 2) 2166 return; 2167 else if (count == 2) 2168 { 2169 df_ref r0 = (*ref_vec)[0]; 2170 df_ref r1 = (*ref_vec)[1]; 2171 if (df_ref_compare (r0, r1) > 0) 2172 df_swap_refs (ref_vec, 0, 1); 2173 } 2174 else 2175 { 2176 for (i = 0; i < count - 1; i++) 2177 { 2178 df_ref r0 = (*ref_vec)[i]; 2179 df_ref r1 = (*ref_vec)[i + 1]; 2180 if (df_ref_compare (r0, r1) >= 0) 2181 break; 2182 } 2183 /* If the array is already strictly ordered, 2184 which is the most common case for large COUNT case 2185 (which happens for CALL INSNs), 2186 no need to sort and filter out duplicate. 2187 Simply return the count. 2188 Make sure DF_GET_ADD_REFS adds refs in the increasing order 2189 of DF_REF_COMPARE. */ 2190 if (i == count - 1) 2191 return; 2192 ref_vec->qsort (df_ref_ptr_compare); 2193 } 2194 2195 for (i=0; i<count-dist; i++) 2196 { 2197 /* Find the next ref that is not equal to the current ref. */ 2198 while (i + dist + 1 < count 2199 && df_ref_equal_p ((*ref_vec)[i], 2200 (*ref_vec)[i + dist + 1])) 2201 { 2202 df_free_ref ((*ref_vec)[i + dist + 1]); 2203 dist++; 2204 } 2205 /* Copy it down to the next position. */ 2206 if (dist && i + dist + 1 < count) 2207 (*ref_vec)[i + 1] = (*ref_vec)[i + dist + 1]; 2208 } 2209 2210 count -= dist; 2211 ref_vec->truncate (count); 2212} 2213 2214 2215/* Return true if the contents of two df_ref's are identical. 2216 It ignores DF_REF_MARKER. */ 2217 2218static bool 2219df_mw_equal_p (struct df_mw_hardreg *mw1, struct df_mw_hardreg *mw2) 2220{ 2221 if (!mw2) 2222 return false; 2223 return (mw1 == mw2) || 2224 (mw1->mw_reg == mw2->mw_reg 2225 && mw1->type == mw2->type 2226 && mw1->flags == mw2->flags 2227 && mw1->start_regno == mw2->start_regno 2228 && mw1->end_regno == mw2->end_regno); 2229} 2230 2231 2232/* Compare MW1 and MW2 for sorting. */ 2233 2234static int 2235df_mw_compare (const df_mw_hardreg *mw1, const df_mw_hardreg *mw2) 2236{ 2237 if (mw1->type != mw2->type) 2238 return mw1->type - mw2->type; 2239 2240 if (mw1->flags != mw2->flags) 2241 return mw1->flags - mw2->flags; 2242 2243 if (mw1->start_regno != mw2->start_regno) 2244 return mw1->start_regno - mw2->start_regno; 2245 2246 if (mw1->end_regno != mw2->end_regno) 2247 return mw1->end_regno - mw2->end_regno; 2248 2249 if (mw1->mw_reg != mw2->mw_reg) 2250 return mw1->mw_order - mw2->mw_order; 2251 2252 return 0; 2253} 2254 2255/* Like df_mw_compare, but compare two df_mw_hardreg** pointers R1 and R2. */ 2256 2257static int 2258df_mw_ptr_compare (const void *m1, const void *m2) 2259{ 2260 return df_mw_compare (*(const df_mw_hardreg *const *) m1, 2261 *(const df_mw_hardreg *const *) m2); 2262} 2263 2264/* Sort and compress a set of refs. */ 2265 2266static void 2267df_sort_and_compress_mws (vec<df_mw_hardreg_ptr, va_heap> *mw_vec) 2268{ 2269 unsigned int count; 2270 struct df_scan_problem_data *problem_data 2271 = (struct df_scan_problem_data *) df_scan->problem_data; 2272 unsigned int i; 2273 unsigned int dist = 0; 2274 2275 count = mw_vec->length (); 2276 if (count < 2) 2277 return; 2278 else if (count == 2) 2279 { 2280 struct df_mw_hardreg *m0 = (*mw_vec)[0]; 2281 struct df_mw_hardreg *m1 = (*mw_vec)[1]; 2282 if (df_mw_compare (m0, m1) > 0) 2283 { 2284 struct df_mw_hardreg *tmp = (*mw_vec)[0]; 2285 (*mw_vec)[0] = (*mw_vec)[1]; 2286 (*mw_vec)[1] = tmp; 2287 } 2288 } 2289 else 2290 mw_vec->qsort (df_mw_ptr_compare); 2291 2292 for (i=0; i<count-dist; i++) 2293 { 2294 /* Find the next ref that is not equal to the current ref. */ 2295 while (i + dist + 1 < count 2296 && df_mw_equal_p ((*mw_vec)[i], (*mw_vec)[i + dist + 1])) 2297 { 2298 pool_free (problem_data->mw_reg_pool, 2299 (*mw_vec)[i + dist + 1]); 2300 dist++; 2301 } 2302 /* Copy it down to the next position. */ 2303 if (dist && i + dist + 1 < count) 2304 (*mw_vec)[i + 1] = (*mw_vec)[i + dist + 1]; 2305 } 2306 2307 count -= dist; 2308 mw_vec->truncate (count); 2309} 2310 2311 2312/* Sort and remove duplicates from the COLLECTION_REC. */ 2313 2314static void 2315df_canonize_collection_rec (struct df_collection_rec *collection_rec) 2316{ 2317 df_sort_and_compress_refs (&collection_rec->def_vec); 2318 df_sort_and_compress_refs (&collection_rec->use_vec); 2319 df_sort_and_compress_refs (&collection_rec->eq_use_vec); 2320 df_sort_and_compress_mws (&collection_rec->mw_vec); 2321} 2322 2323 2324/* Add the new df_ref to appropriate reg_info/ref_info chains. */ 2325 2326static void 2327df_install_ref (df_ref this_ref, 2328 struct df_reg_info *reg_info, 2329 struct df_ref_info *ref_info, 2330 bool add_to_table) 2331{ 2332 unsigned int regno = DF_REF_REGNO (this_ref); 2333 /* Add the ref to the reg_{def,use,eq_use} chain. */ 2334 df_ref head = reg_info->reg_chain; 2335 2336 reg_info->reg_chain = this_ref; 2337 reg_info->n_refs++; 2338 2339 if (DF_REF_FLAGS_IS_SET (this_ref, DF_HARD_REG_LIVE)) 2340 { 2341 gcc_assert (regno < FIRST_PSEUDO_REGISTER); 2342 df->hard_regs_live_count[regno]++; 2343 } 2344 2345 gcc_checking_assert (DF_REF_NEXT_REG (this_ref) == NULL 2346 && DF_REF_PREV_REG (this_ref) == NULL); 2347 2348 DF_REF_NEXT_REG (this_ref) = head; 2349 2350 /* We cannot actually link to the head of the chain. */ 2351 DF_REF_PREV_REG (this_ref) = NULL; 2352 2353 if (head) 2354 DF_REF_PREV_REG (head) = this_ref; 2355 2356 if (add_to_table) 2357 { 2358 gcc_assert (ref_info->ref_order != DF_REF_ORDER_NO_TABLE); 2359 df_check_and_grow_ref_info (ref_info, 1); 2360 DF_REF_ID (this_ref) = ref_info->table_size; 2361 /* Add the ref to the big array of defs. */ 2362 ref_info->refs[ref_info->table_size] = this_ref; 2363 ref_info->table_size++; 2364 } 2365 else 2366 DF_REF_ID (this_ref) = -1; 2367 2368 ref_info->total_size++; 2369} 2370 2371 2372/* This function takes one of the groups of refs (defs, uses or 2373 eq_uses) and installs the entire group into the insn. It also adds 2374 each of these refs into the appropriate chains. */ 2375 2376static df_ref 2377df_install_refs (basic_block bb, 2378 const vec<df_ref, va_heap> *old_vec, 2379 struct df_reg_info **reg_info, 2380 struct df_ref_info *ref_info, 2381 bool is_notes) 2382{ 2383 unsigned int count = old_vec->length (); 2384 if (count) 2385 { 2386 bool add_to_table; 2387 df_ref this_ref; 2388 unsigned int ix; 2389 2390 switch (ref_info->ref_order) 2391 { 2392 case DF_REF_ORDER_UNORDERED_WITH_NOTES: 2393 case DF_REF_ORDER_BY_REG_WITH_NOTES: 2394 case DF_REF_ORDER_BY_INSN_WITH_NOTES: 2395 ref_info->ref_order = DF_REF_ORDER_UNORDERED_WITH_NOTES; 2396 add_to_table = true; 2397 break; 2398 case DF_REF_ORDER_UNORDERED: 2399 case DF_REF_ORDER_BY_REG: 2400 case DF_REF_ORDER_BY_INSN: 2401 ref_info->ref_order = DF_REF_ORDER_UNORDERED; 2402 add_to_table = !is_notes; 2403 break; 2404 default: 2405 add_to_table = false; 2406 break; 2407 } 2408 2409 /* Do not add if ref is not in the right blocks. */ 2410 if (add_to_table && df->analyze_subset) 2411 add_to_table = bitmap_bit_p (df->blocks_to_analyze, bb->index); 2412 2413 FOR_EACH_VEC_ELT (*old_vec, ix, this_ref) 2414 { 2415 DF_REF_NEXT_LOC (this_ref) = (ix + 1 < old_vec->length () 2416 ? (*old_vec)[ix + 1] 2417 : NULL); 2418 df_install_ref (this_ref, reg_info[DF_REF_REGNO (this_ref)], 2419 ref_info, add_to_table); 2420 } 2421 return (*old_vec)[0]; 2422 } 2423 else 2424 return 0; 2425} 2426 2427 2428/* This function takes the mws installs the entire group into the 2429 insn. */ 2430 2431static struct df_mw_hardreg * 2432df_install_mws (const vec<df_mw_hardreg_ptr, va_heap> *old_vec) 2433{ 2434 unsigned int count = old_vec->length (); 2435 if (count) 2436 { 2437 for (unsigned int i = 0; i < count - 1; i++) 2438 DF_MWS_NEXT ((*old_vec)[i]) = (*old_vec)[i + 1]; 2439 DF_MWS_NEXT ((*old_vec)[count - 1]) = 0; 2440 return (*old_vec)[0]; 2441 } 2442 else 2443 return 0; 2444} 2445 2446 2447/* Add a chain of df_refs to appropriate ref chain/reg_info/ref_info 2448 chains and update other necessary information. */ 2449 2450static void 2451df_refs_add_to_chains (struct df_collection_rec *collection_rec, 2452 basic_block bb, rtx_insn *insn, unsigned int flags) 2453{ 2454 if (insn) 2455 { 2456 struct df_insn_info *insn_rec = DF_INSN_INFO_GET (insn); 2457 /* If there is a vector in the collection rec, add it to the 2458 insn. A null rec is a signal that the caller will handle the 2459 chain specially. */ 2460 if (flags & copy_defs) 2461 { 2462 gcc_checking_assert (!insn_rec->defs); 2463 insn_rec->defs 2464 = df_install_refs (bb, &collection_rec->def_vec, 2465 df->def_regs, 2466 &df->def_info, false); 2467 } 2468 if (flags & copy_uses) 2469 { 2470 gcc_checking_assert (!insn_rec->uses); 2471 insn_rec->uses 2472 = df_install_refs (bb, &collection_rec->use_vec, 2473 df->use_regs, 2474 &df->use_info, false); 2475 } 2476 if (flags & copy_eq_uses) 2477 { 2478 gcc_checking_assert (!insn_rec->eq_uses); 2479 insn_rec->eq_uses 2480 = df_install_refs (bb, &collection_rec->eq_use_vec, 2481 df->eq_use_regs, 2482 &df->use_info, true); 2483 } 2484 if (flags & copy_mw) 2485 { 2486 gcc_checking_assert (!insn_rec->mw_hardregs); 2487 insn_rec->mw_hardregs 2488 = df_install_mws (&collection_rec->mw_vec); 2489 } 2490 } 2491 else 2492 { 2493 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb->index); 2494 2495 gcc_checking_assert (!bb_info->artificial_defs); 2496 bb_info->artificial_defs 2497 = df_install_refs (bb, &collection_rec->def_vec, 2498 df->def_regs, 2499 &df->def_info, false); 2500 gcc_checking_assert (!bb_info->artificial_uses); 2501 bb_info->artificial_uses 2502 = df_install_refs (bb, &collection_rec->use_vec, 2503 df->use_regs, 2504 &df->use_info, false); 2505 } 2506} 2507 2508 2509/* Allocate a ref and initialize its fields. */ 2510 2511static df_ref 2512df_ref_create_structure (enum df_ref_class cl, 2513 struct df_collection_rec *collection_rec, 2514 rtx reg, rtx *loc, 2515 basic_block bb, struct df_insn_info *info, 2516 enum df_ref_type ref_type, 2517 int ref_flags) 2518{ 2519 df_ref this_ref = NULL; 2520 int regno = REGNO (GET_CODE (reg) == SUBREG ? SUBREG_REG (reg) : reg); 2521 struct df_scan_problem_data *problem_data 2522 = (struct df_scan_problem_data *) df_scan->problem_data; 2523 2524 switch (cl) 2525 { 2526 case DF_REF_BASE: 2527 this_ref = (df_ref) pool_alloc (problem_data->ref_base_pool); 2528 gcc_checking_assert (loc == NULL); 2529 break; 2530 2531 case DF_REF_ARTIFICIAL: 2532 this_ref = (df_ref) pool_alloc (problem_data->ref_artificial_pool); 2533 this_ref->artificial_ref.bb = bb; 2534 gcc_checking_assert (loc == NULL); 2535 break; 2536 2537 case DF_REF_REGULAR: 2538 this_ref = (df_ref) pool_alloc (problem_data->ref_regular_pool); 2539 this_ref->regular_ref.loc = loc; 2540 gcc_checking_assert (loc); 2541 break; 2542 } 2543 2544 DF_REF_CLASS (this_ref) = cl; 2545 DF_REF_ID (this_ref) = -1; 2546 DF_REF_REG (this_ref) = reg; 2547 DF_REF_REGNO (this_ref) = regno; 2548 DF_REF_TYPE (this_ref) = ref_type; 2549 DF_REF_INSN_INFO (this_ref) = info; 2550 DF_REF_CHAIN (this_ref) = NULL; 2551 DF_REF_FLAGS (this_ref) = ref_flags; 2552 DF_REF_NEXT_REG (this_ref) = NULL; 2553 DF_REF_PREV_REG (this_ref) = NULL; 2554 DF_REF_ORDER (this_ref) = df->ref_order++; 2555 2556 /* We need to clear this bit because fwprop, and in the future 2557 possibly other optimizations sometimes create new refs using ond 2558 refs as the model. */ 2559 DF_REF_FLAGS_CLEAR (this_ref, DF_HARD_REG_LIVE); 2560 2561 /* See if this ref needs to have DF_HARD_REG_LIVE bit set. */ 2562 if (regno < FIRST_PSEUDO_REGISTER 2563 && !DF_REF_IS_ARTIFICIAL (this_ref) 2564 && !DEBUG_INSN_P (DF_REF_INSN (this_ref))) 2565 { 2566 if (DF_REF_REG_DEF_P (this_ref)) 2567 { 2568 if (!DF_REF_FLAGS_IS_SET (this_ref, DF_REF_MAY_CLOBBER)) 2569 DF_REF_FLAGS_SET (this_ref, DF_HARD_REG_LIVE); 2570 } 2571 else if (!(TEST_HARD_REG_BIT (elim_reg_set, regno) 2572 && (regno == FRAME_POINTER_REGNUM 2573 || regno == ARG_POINTER_REGNUM))) 2574 DF_REF_FLAGS_SET (this_ref, DF_HARD_REG_LIVE); 2575 } 2576 2577 if (collection_rec) 2578 { 2579 if (DF_REF_REG_DEF_P (this_ref)) 2580 collection_rec->def_vec.safe_push (this_ref); 2581 else if (DF_REF_FLAGS (this_ref) & DF_REF_IN_NOTE) 2582 collection_rec->eq_use_vec.safe_push (this_ref); 2583 else 2584 collection_rec->use_vec.safe_push (this_ref); 2585 } 2586 else 2587 df_install_ref_incremental (this_ref); 2588 2589 return this_ref; 2590} 2591 2592 2593/* Create new references of type DF_REF_TYPE for each part of register REG 2594 at address LOC within INSN of BB. */ 2595 2596 2597static void 2598df_ref_record (enum df_ref_class cl, 2599 struct df_collection_rec *collection_rec, 2600 rtx reg, rtx *loc, 2601 basic_block bb, struct df_insn_info *insn_info, 2602 enum df_ref_type ref_type, 2603 int ref_flags) 2604{ 2605 unsigned int regno; 2606 2607 gcc_checking_assert (REG_P (reg) || GET_CODE (reg) == SUBREG); 2608 2609 regno = REGNO (GET_CODE (reg) == SUBREG ? SUBREG_REG (reg) : reg); 2610 if (regno < FIRST_PSEUDO_REGISTER) 2611 { 2612 struct df_mw_hardreg *hardreg = NULL; 2613 struct df_scan_problem_data *problem_data 2614 = (struct df_scan_problem_data *) df_scan->problem_data; 2615 unsigned int i; 2616 unsigned int endregno; 2617 df_ref ref; 2618 2619 if (GET_CODE (reg) == SUBREG) 2620 { 2621 regno += subreg_regno_offset (regno, GET_MODE (SUBREG_REG (reg)), 2622 SUBREG_BYTE (reg), GET_MODE (reg)); 2623 endregno = regno + subreg_nregs (reg); 2624 } 2625 else 2626 endregno = END_HARD_REGNO (reg); 2627 2628 /* If this is a multiword hardreg, we create some extra 2629 datastructures that will enable us to easily build REG_DEAD 2630 and REG_UNUSED notes. */ 2631 if (collection_rec 2632 && (endregno != regno + 1) && insn_info) 2633 { 2634 /* Sets to a subreg of a multiword register are partial. 2635 Sets to a non-subreg of a multiword register are not. */ 2636 if (GET_CODE (reg) == SUBREG) 2637 ref_flags |= DF_REF_PARTIAL; 2638 ref_flags |= DF_REF_MW_HARDREG; 2639 2640 hardreg = (struct df_mw_hardreg *) pool_alloc (problem_data->mw_reg_pool); 2641 hardreg->type = ref_type; 2642 hardreg->flags = ref_flags; 2643 hardreg->mw_reg = reg; 2644 hardreg->start_regno = regno; 2645 hardreg->end_regno = endregno - 1; 2646 hardreg->mw_order = df->ref_order++; 2647 collection_rec->mw_vec.safe_push (hardreg); 2648 } 2649 2650 for (i = regno; i < endregno; i++) 2651 { 2652 ref = df_ref_create_structure (cl, collection_rec, regno_reg_rtx[i], loc, 2653 bb, insn_info, ref_type, ref_flags); 2654 2655 gcc_assert (ORIGINAL_REGNO (DF_REF_REG (ref)) == i); 2656 } 2657 } 2658 else 2659 { 2660 df_ref_create_structure (cl, collection_rec, reg, loc, bb, insn_info, 2661 ref_type, ref_flags); 2662 } 2663} 2664 2665 2666/* A set to a non-paradoxical SUBREG for which the number of word_mode units 2667 covered by the outer mode is smaller than that covered by the inner mode, 2668 is a read-modify-write operation. 2669 This function returns true iff the SUBREG X is such a SUBREG. */ 2670 2671bool 2672df_read_modify_subreg_p (rtx x) 2673{ 2674 unsigned int isize, osize; 2675 if (GET_CODE (x) != SUBREG) 2676 return false; 2677 isize = GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))); 2678 osize = GET_MODE_SIZE (GET_MODE (x)); 2679 return isize > osize 2680 && isize > REGMODE_NATURAL_SIZE (GET_MODE (SUBREG_REG (x))); 2681} 2682 2683 2684/* Process all the registers defined in the rtx pointed by LOC. 2685 Autoincrement/decrement definitions will be picked up by df_uses_record. 2686 Any change here has to be matched in df_find_hard_reg_defs_1. */ 2687 2688static void 2689df_def_record_1 (struct df_collection_rec *collection_rec, 2690 rtx *loc, basic_block bb, struct df_insn_info *insn_info, 2691 int flags) 2692{ 2693 rtx dst = *loc; 2694 2695 /* It is legal to have a set destination be a parallel. */ 2696 if (GET_CODE (dst) == PARALLEL) 2697 { 2698 int i; 2699 for (i = XVECLEN (dst, 0) - 1; i >= 0; i--) 2700 { 2701 rtx temp = XVECEXP (dst, 0, i); 2702 gcc_assert (GET_CODE (temp) == EXPR_LIST); 2703 df_def_record_1 (collection_rec, &XEXP (temp, 0), 2704 bb, insn_info, flags); 2705 } 2706 return; 2707 } 2708 2709 if (GET_CODE (dst) == STRICT_LOW_PART) 2710 { 2711 flags |= DF_REF_READ_WRITE | DF_REF_PARTIAL | DF_REF_STRICT_LOW_PART; 2712 2713 loc = &XEXP (dst, 0); 2714 dst = *loc; 2715 } 2716 2717 if (GET_CODE (dst) == ZERO_EXTRACT) 2718 { 2719 flags |= DF_REF_READ_WRITE | DF_REF_PARTIAL | DF_REF_ZERO_EXTRACT; 2720 2721 loc = &XEXP (dst, 0); 2722 dst = *loc; 2723 } 2724 2725 /* At this point if we do not have a reg or a subreg, just return. */ 2726 if (REG_P (dst)) 2727 { 2728 df_ref_record (DF_REF_REGULAR, collection_rec, 2729 dst, loc, bb, insn_info, DF_REF_REG_DEF, flags); 2730 2731 /* We want to keep sp alive everywhere - by making all 2732 writes to sp also use of sp. */ 2733 if (REGNO (dst) == STACK_POINTER_REGNUM) 2734 df_ref_record (DF_REF_BASE, collection_rec, 2735 dst, NULL, bb, insn_info, DF_REF_REG_USE, flags); 2736 } 2737 else if (GET_CODE (dst) == SUBREG && REG_P (SUBREG_REG (dst))) 2738 { 2739 if (df_read_modify_subreg_p (dst)) 2740 flags |= DF_REF_READ_WRITE | DF_REF_PARTIAL; 2741 2742 flags |= DF_REF_SUBREG; 2743 2744 df_ref_record (DF_REF_REGULAR, collection_rec, 2745 dst, loc, bb, insn_info, DF_REF_REG_DEF, flags); 2746 } 2747} 2748 2749 2750/* Process all the registers defined in the pattern rtx, X. Any change 2751 here has to be matched in df_find_hard_reg_defs. */ 2752 2753static void 2754df_defs_record (struct df_collection_rec *collection_rec, 2755 rtx x, basic_block bb, struct df_insn_info *insn_info, 2756 int flags) 2757{ 2758 RTX_CODE code = GET_CODE (x); 2759 int i; 2760 2761 switch (code) 2762 { 2763 case SET: 2764 df_def_record_1 (collection_rec, &SET_DEST (x), bb, insn_info, flags); 2765 break; 2766 2767 case CLOBBER: 2768 flags |= DF_REF_MUST_CLOBBER; 2769 df_def_record_1 (collection_rec, &XEXP (x, 0), bb, insn_info, flags); 2770 break; 2771 2772 case COND_EXEC: 2773 df_defs_record (collection_rec, COND_EXEC_CODE (x), 2774 bb, insn_info, DF_REF_CONDITIONAL); 2775 break; 2776 2777 case PARALLEL: 2778 for (i = 0; i < XVECLEN (x, 0); i++) 2779 df_defs_record (collection_rec, XVECEXP (x, 0, i), 2780 bb, insn_info, flags); 2781 break; 2782 default: 2783 /* No DEFs to record in other cases */ 2784 break; 2785 } 2786} 2787 2788/* Set bits in *DEFS for hard registers found in the rtx DST, which is the 2789 destination of a set or clobber. This has to match the logic in 2790 df_defs_record_1. */ 2791 2792static void 2793df_find_hard_reg_defs_1 (rtx dst, HARD_REG_SET *defs) 2794{ 2795 /* It is legal to have a set destination be a parallel. */ 2796 if (GET_CODE (dst) == PARALLEL) 2797 { 2798 int i; 2799 for (i = XVECLEN (dst, 0) - 1; i >= 0; i--) 2800 { 2801 rtx temp = XVECEXP (dst, 0, i); 2802 gcc_assert (GET_CODE (temp) == EXPR_LIST); 2803 df_find_hard_reg_defs_1 (XEXP (temp, 0), defs); 2804 } 2805 return; 2806 } 2807 2808 if (GET_CODE (dst) == STRICT_LOW_PART) 2809 dst = XEXP (dst, 0); 2810 2811 if (GET_CODE (dst) == ZERO_EXTRACT) 2812 dst = XEXP (dst, 0); 2813 2814 /* At this point if we do not have a reg or a subreg, just return. */ 2815 if (REG_P (dst) && HARD_REGISTER_P (dst)) 2816 SET_HARD_REG_BIT (*defs, REGNO (dst)); 2817 else if (GET_CODE (dst) == SUBREG 2818 && REG_P (SUBREG_REG (dst)) && HARD_REGISTER_P (dst)) 2819 SET_HARD_REG_BIT (*defs, REGNO (SUBREG_REG (dst))); 2820} 2821 2822/* Set bits in *DEFS for hard registers defined in the pattern X. This 2823 has to match the logic in df_defs_record. */ 2824 2825static void 2826df_find_hard_reg_defs (rtx x, HARD_REG_SET *defs) 2827{ 2828 RTX_CODE code = GET_CODE (x); 2829 int i; 2830 2831 switch (code) 2832 { 2833 case SET: 2834 df_find_hard_reg_defs_1 (SET_DEST (x), defs); 2835 break; 2836 2837 case CLOBBER: 2838 df_find_hard_reg_defs_1 (XEXP (x, 0), defs); 2839 break; 2840 2841 case COND_EXEC: 2842 df_find_hard_reg_defs (COND_EXEC_CODE (x), defs); 2843 break; 2844 2845 case PARALLEL: 2846 for (i = 0; i < XVECLEN (x, 0); i++) 2847 df_find_hard_reg_defs (XVECEXP (x, 0, i), defs); 2848 break; 2849 default: 2850 /* No DEFs to record in other cases */ 2851 break; 2852 } 2853} 2854 2855 2856/* Process all the registers used in the rtx at address LOC. */ 2857 2858static void 2859df_uses_record (struct df_collection_rec *collection_rec, 2860 rtx *loc, enum df_ref_type ref_type, 2861 basic_block bb, struct df_insn_info *insn_info, 2862 int flags) 2863{ 2864 RTX_CODE code; 2865 rtx x; 2866 2867 retry: 2868 x = *loc; 2869 if (!x) 2870 return; 2871 code = GET_CODE (x); 2872 switch (code) 2873 { 2874 case LABEL_REF: 2875 case SYMBOL_REF: 2876 case CONST: 2877 CASE_CONST_ANY: 2878 case PC: 2879 case CC0: 2880 case ADDR_VEC: 2881 case ADDR_DIFF_VEC: 2882 return; 2883 2884 case CLOBBER: 2885 /* If we are clobbering a MEM, mark any registers inside the address 2886 as being used. */ 2887 if (MEM_P (XEXP (x, 0))) 2888 df_uses_record (collection_rec, 2889 &XEXP (XEXP (x, 0), 0), 2890 DF_REF_REG_MEM_STORE, 2891 bb, insn_info, 2892 flags); 2893 2894 /* If we're clobbering a REG then we have a def so ignore. */ 2895 return; 2896 2897 case MEM: 2898 df_uses_record (collection_rec, 2899 &XEXP (x, 0), DF_REF_REG_MEM_LOAD, 2900 bb, insn_info, flags & DF_REF_IN_NOTE); 2901 return; 2902 2903 case SUBREG: 2904 /* While we're here, optimize this case. */ 2905 flags |= DF_REF_PARTIAL; 2906 /* In case the SUBREG is not of a REG, do not optimize. */ 2907 if (!REG_P (SUBREG_REG (x))) 2908 { 2909 loc = &SUBREG_REG (x); 2910 df_uses_record (collection_rec, loc, ref_type, bb, insn_info, flags); 2911 return; 2912 } 2913 /* ... Fall through ... */ 2914 2915 case REG: 2916 df_ref_record (DF_REF_REGULAR, collection_rec, 2917 x, loc, bb, insn_info, 2918 ref_type, flags); 2919 return; 2920 2921 case SIGN_EXTRACT: 2922 case ZERO_EXTRACT: 2923 { 2924 df_uses_record (collection_rec, 2925 &XEXP (x, 1), ref_type, bb, insn_info, flags); 2926 df_uses_record (collection_rec, 2927 &XEXP (x, 2), ref_type, bb, insn_info, flags); 2928 2929 /* If the parameters to the zero or sign extract are 2930 constants, strip them off and recurse, otherwise there is 2931 no information that we can gain from this operation. */ 2932 if (code == ZERO_EXTRACT) 2933 flags |= DF_REF_ZERO_EXTRACT; 2934 else 2935 flags |= DF_REF_SIGN_EXTRACT; 2936 2937 df_uses_record (collection_rec, 2938 &XEXP (x, 0), ref_type, bb, insn_info, flags); 2939 return; 2940 } 2941 break; 2942 2943 case SET: 2944 { 2945 rtx dst = SET_DEST (x); 2946 gcc_assert (!(flags & DF_REF_IN_NOTE)); 2947 df_uses_record (collection_rec, 2948 &SET_SRC (x), DF_REF_REG_USE, bb, insn_info, flags); 2949 2950 switch (GET_CODE (dst)) 2951 { 2952 case SUBREG: 2953 if (df_read_modify_subreg_p (dst)) 2954 { 2955 df_uses_record (collection_rec, &SUBREG_REG (dst), 2956 DF_REF_REG_USE, bb, insn_info, 2957 flags | DF_REF_READ_WRITE | DF_REF_SUBREG); 2958 break; 2959 } 2960 /* Fall through. */ 2961 case REG: 2962 case PARALLEL: 2963 case SCRATCH: 2964 case PC: 2965 case CC0: 2966 break; 2967 case MEM: 2968 df_uses_record (collection_rec, &XEXP (dst, 0), 2969 DF_REF_REG_MEM_STORE, bb, insn_info, flags); 2970 break; 2971 case STRICT_LOW_PART: 2972 { 2973 rtx *temp = &XEXP (dst, 0); 2974 /* A strict_low_part uses the whole REG and not just the 2975 SUBREG. */ 2976 dst = XEXP (dst, 0); 2977 df_uses_record (collection_rec, 2978 (GET_CODE (dst) == SUBREG) ? &SUBREG_REG (dst) : temp, 2979 DF_REF_REG_USE, bb, insn_info, 2980 DF_REF_READ_WRITE | DF_REF_STRICT_LOW_PART); 2981 } 2982 break; 2983 case ZERO_EXTRACT: 2984 { 2985 df_uses_record (collection_rec, &XEXP (dst, 1), 2986 DF_REF_REG_USE, bb, insn_info, flags); 2987 df_uses_record (collection_rec, &XEXP (dst, 2), 2988 DF_REF_REG_USE, bb, insn_info, flags); 2989 if (GET_CODE (XEXP (dst,0)) == MEM) 2990 df_uses_record (collection_rec, &XEXP (dst, 0), 2991 DF_REF_REG_USE, bb, insn_info, 2992 flags); 2993 else 2994 df_uses_record (collection_rec, &XEXP (dst, 0), 2995 DF_REF_REG_USE, bb, insn_info, 2996 DF_REF_READ_WRITE | DF_REF_ZERO_EXTRACT); 2997 } 2998 break; 2999 3000 default: 3001 gcc_unreachable (); 3002 } 3003 return; 3004 } 3005 3006 case RETURN: 3007 case SIMPLE_RETURN: 3008 break; 3009 3010 case ASM_OPERANDS: 3011 case UNSPEC_VOLATILE: 3012 case TRAP_IF: 3013 case ASM_INPUT: 3014 { 3015 /* Traditional and volatile asm instructions must be 3016 considered to use and clobber all hard registers, all 3017 pseudo-registers and all of memory. So must TRAP_IF and 3018 UNSPEC_VOLATILE operations. 3019 3020 Consider for instance a volatile asm that changes the fpu 3021 rounding mode. An insn should not be moved across this 3022 even if it only uses pseudo-regs because it might give an 3023 incorrectly rounded result. 3024 3025 However, flow.c's liveness computation did *not* do this, 3026 giving the reasoning as " ?!? Unfortunately, marking all 3027 hard registers as live causes massive problems for the 3028 register allocator and marking all pseudos as live creates 3029 mountains of uninitialized variable warnings." 3030 3031 In order to maintain the status quo with regard to liveness 3032 and uses, we do what flow.c did and just mark any regs we 3033 can find in ASM_OPERANDS as used. In global asm insns are 3034 scanned and regs_asm_clobbered is filled out. 3035 3036 For all ASM_OPERANDS, we must traverse the vector of input 3037 operands. We can not just fall through here since then we 3038 would be confused by the ASM_INPUT rtx inside ASM_OPERANDS, 3039 which do not indicate traditional asms unlike their normal 3040 usage. */ 3041 if (code == ASM_OPERANDS) 3042 { 3043 int j; 3044 3045 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++) 3046 df_uses_record (collection_rec, &ASM_OPERANDS_INPUT (x, j), 3047 DF_REF_REG_USE, bb, insn_info, flags); 3048 return; 3049 } 3050 break; 3051 } 3052 3053 case VAR_LOCATION: 3054 df_uses_record (collection_rec, 3055 &PAT_VAR_LOCATION_LOC (x), 3056 DF_REF_REG_USE, bb, insn_info, flags); 3057 return; 3058 3059 case PRE_DEC: 3060 case POST_DEC: 3061 case PRE_INC: 3062 case POST_INC: 3063 case PRE_MODIFY: 3064 case POST_MODIFY: 3065 gcc_assert (!DEBUG_INSN_P (insn_info->insn)); 3066 /* Catch the def of the register being modified. */ 3067 df_ref_record (DF_REF_REGULAR, collection_rec, XEXP (x, 0), &XEXP (x, 0), 3068 bb, insn_info, 3069 DF_REF_REG_DEF, 3070 flags | DF_REF_READ_WRITE | DF_REF_PRE_POST_MODIFY); 3071 3072 /* ... Fall through to handle uses ... */ 3073 3074 default: 3075 break; 3076 } 3077 3078 /* Recursively scan the operands of this expression. */ 3079 { 3080 const char *fmt = GET_RTX_FORMAT (code); 3081 int i; 3082 3083 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 3084 { 3085 if (fmt[i] == 'e') 3086 { 3087 /* Tail recursive case: save a function call level. */ 3088 if (i == 0) 3089 { 3090 loc = &XEXP (x, 0); 3091 goto retry; 3092 } 3093 df_uses_record (collection_rec, &XEXP (x, i), ref_type, 3094 bb, insn_info, flags); 3095 } 3096 else if (fmt[i] == 'E') 3097 { 3098 int j; 3099 for (j = 0; j < XVECLEN (x, i); j++) 3100 df_uses_record (collection_rec, 3101 &XVECEXP (x, i, j), ref_type, 3102 bb, insn_info, flags); 3103 } 3104 } 3105 } 3106 3107 return; 3108} 3109 3110 3111/* For all DF_REF_CONDITIONAL defs, add a corresponding uses. */ 3112 3113static void 3114df_get_conditional_uses (struct df_collection_rec *collection_rec) 3115{ 3116 unsigned int ix; 3117 df_ref ref; 3118 3119 FOR_EACH_VEC_ELT (collection_rec->def_vec, ix, ref) 3120 { 3121 if (DF_REF_FLAGS_IS_SET (ref, DF_REF_CONDITIONAL)) 3122 { 3123 df_ref use; 3124 3125 use = df_ref_create_structure (DF_REF_CLASS (ref), collection_rec, DF_REF_REG (ref), 3126 DF_REF_LOC (ref), DF_REF_BB (ref), 3127 DF_REF_INSN_INFO (ref), DF_REF_REG_USE, 3128 DF_REF_FLAGS (ref) & ~DF_REF_CONDITIONAL); 3129 DF_REF_REGNO (use) = DF_REF_REGNO (ref); 3130 } 3131 } 3132} 3133 3134 3135/* Get call's extra defs and uses (track caller-saved registers). */ 3136 3137static void 3138df_get_call_refs (struct df_collection_rec *collection_rec, 3139 basic_block bb, 3140 struct df_insn_info *insn_info, 3141 int flags) 3142{ 3143 rtx note; 3144 bool is_sibling_call; 3145 unsigned int i; 3146 HARD_REG_SET defs_generated; 3147 HARD_REG_SET fn_reg_set_usage; 3148 3149 CLEAR_HARD_REG_SET (defs_generated); 3150 df_find_hard_reg_defs (PATTERN (insn_info->insn), &defs_generated); 3151 is_sibling_call = SIBLING_CALL_P (insn_info->insn); 3152 get_call_reg_set_usage (insn_info->insn, &fn_reg_set_usage, 3153 regs_invalidated_by_call); 3154 3155 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 3156 { 3157 if (i == STACK_POINTER_REGNUM) 3158 /* The stack ptr is used (honorarily) by a CALL insn. */ 3159 df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i], 3160 NULL, bb, insn_info, DF_REF_REG_USE, 3161 DF_REF_CALL_STACK_USAGE | flags); 3162 else if (global_regs[i]) 3163 { 3164 /* Calls to const functions cannot access any global registers and 3165 calls to pure functions cannot set them. All other calls may 3166 reference any of the global registers, so they are recorded as 3167 used. */ 3168 if (!RTL_CONST_CALL_P (insn_info->insn)) 3169 { 3170 df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i], 3171 NULL, bb, insn_info, DF_REF_REG_USE, flags); 3172 if (!RTL_PURE_CALL_P (insn_info->insn)) 3173 df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i], 3174 NULL, bb, insn_info, DF_REF_REG_DEF, flags); 3175 } 3176 } 3177 else if (TEST_HARD_REG_BIT (fn_reg_set_usage, i) 3178 /* no clobbers for regs that are the result of the call */ 3179 && !TEST_HARD_REG_BIT (defs_generated, i) 3180 && (!is_sibling_call 3181 || !bitmap_bit_p (df->exit_block_uses, i) 3182 || refers_to_regno_p (i, crtl->return_rtx))) 3183 df_ref_record (DF_REF_BASE, collection_rec, regno_reg_rtx[i], 3184 NULL, bb, insn_info, DF_REF_REG_DEF, 3185 DF_REF_MAY_CLOBBER | flags); 3186 } 3187 3188 /* Record the registers used to pass arguments, and explicitly 3189 noted as clobbered. */ 3190 for (note = CALL_INSN_FUNCTION_USAGE (insn_info->insn); note; 3191 note = XEXP (note, 1)) 3192 { 3193 if (GET_CODE (XEXP (note, 0)) == USE) 3194 df_uses_record (collection_rec, &XEXP (XEXP (note, 0), 0), 3195 DF_REF_REG_USE, bb, insn_info, flags); 3196 else if (GET_CODE (XEXP (note, 0)) == CLOBBER) 3197 { 3198 if (REG_P (XEXP (XEXP (note, 0), 0))) 3199 { 3200 unsigned int regno = REGNO (XEXP (XEXP (note, 0), 0)); 3201 if (!TEST_HARD_REG_BIT (defs_generated, regno)) 3202 df_defs_record (collection_rec, XEXP (note, 0), bb, 3203 insn_info, flags); 3204 } 3205 else 3206 df_uses_record (collection_rec, &XEXP (note, 0), 3207 DF_REF_REG_USE, bb, insn_info, flags); 3208 } 3209 } 3210 3211 return; 3212} 3213 3214/* Collect all refs in the INSN. This function is free of any 3215 side-effect - it will create and return a lists of df_ref's in the 3216 COLLECTION_REC without putting those refs into existing ref chains 3217 and reg chains. */ 3218 3219static void 3220df_insn_refs_collect (struct df_collection_rec *collection_rec, 3221 basic_block bb, struct df_insn_info *insn_info) 3222{ 3223 rtx note; 3224 bool is_cond_exec = (GET_CODE (PATTERN (insn_info->insn)) == COND_EXEC); 3225 3226 /* Clear out the collection record. */ 3227 collection_rec->def_vec.truncate (0); 3228 collection_rec->use_vec.truncate (0); 3229 collection_rec->eq_use_vec.truncate (0); 3230 collection_rec->mw_vec.truncate (0); 3231 3232 /* Process REG_EQUIV/REG_EQUAL notes. */ 3233 for (note = REG_NOTES (insn_info->insn); note; 3234 note = XEXP (note, 1)) 3235 { 3236 switch (REG_NOTE_KIND (note)) 3237 { 3238 case REG_EQUIV: 3239 case REG_EQUAL: 3240 df_uses_record (collection_rec, 3241 &XEXP (note, 0), DF_REF_REG_USE, 3242 bb, insn_info, DF_REF_IN_NOTE); 3243 break; 3244 case REG_NON_LOCAL_GOTO: 3245 /* The frame ptr is used by a non-local goto. */ 3246 df_ref_record (DF_REF_BASE, collection_rec, 3247 regno_reg_rtx[FRAME_POINTER_REGNUM], 3248 NULL, bb, insn_info, 3249 DF_REF_REG_USE, 0); 3250#if !HARD_FRAME_POINTER_IS_FRAME_POINTER 3251 df_ref_record (DF_REF_BASE, collection_rec, 3252 regno_reg_rtx[HARD_FRAME_POINTER_REGNUM], 3253 NULL, bb, insn_info, 3254 DF_REF_REG_USE, 0); 3255#endif 3256 break; 3257 default: 3258 break; 3259 } 3260 } 3261 3262 /* For CALL_INSNs, first record DF_REF_BASE register defs, as well as 3263 uses from CALL_INSN_FUNCTION_USAGE. */ 3264 if (CALL_P (insn_info->insn)) 3265 df_get_call_refs (collection_rec, bb, insn_info, 3266 (is_cond_exec) ? DF_REF_CONDITIONAL : 0); 3267 3268 /* Record other defs. These should be mostly for DF_REF_REGULAR, so 3269 that a qsort on the defs is unnecessary in most cases. */ 3270 df_defs_record (collection_rec, 3271 PATTERN (insn_info->insn), bb, insn_info, 0); 3272 3273 /* Record the register uses. */ 3274 df_uses_record (collection_rec, 3275 &PATTERN (insn_info->insn), DF_REF_REG_USE, bb, insn_info, 0); 3276 3277 /* DF_REF_CONDITIONAL needs corresponding USES. */ 3278 if (is_cond_exec) 3279 df_get_conditional_uses (collection_rec); 3280 3281 df_canonize_collection_rec (collection_rec); 3282} 3283 3284/* Recompute the luids for the insns in BB. */ 3285 3286void 3287df_recompute_luids (basic_block bb) 3288{ 3289 rtx_insn *insn; 3290 int luid = 0; 3291 3292 df_grow_insn_info (); 3293 3294 /* Scan the block an insn at a time from beginning to end. */ 3295 FOR_BB_INSNS (bb, insn) 3296 { 3297 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn); 3298 /* Inserting labels does not always trigger the incremental 3299 rescanning. */ 3300 if (!insn_info) 3301 { 3302 gcc_assert (!INSN_P (insn)); 3303 insn_info = df_insn_create_insn_record (insn); 3304 } 3305 3306 DF_INSN_INFO_LUID (insn_info) = luid; 3307 if (INSN_P (insn)) 3308 luid++; 3309 } 3310} 3311 3312 3313/* Collect all artificial refs at the block level for BB and add them 3314 to COLLECTION_REC. */ 3315 3316static void 3317df_bb_refs_collect (struct df_collection_rec *collection_rec, basic_block bb) 3318{ 3319 collection_rec->def_vec.truncate (0); 3320 collection_rec->use_vec.truncate (0); 3321 collection_rec->eq_use_vec.truncate (0); 3322 collection_rec->mw_vec.truncate (0); 3323 3324 if (bb->index == ENTRY_BLOCK) 3325 { 3326 df_entry_block_defs_collect (collection_rec, df->entry_block_defs); 3327 return; 3328 } 3329 else if (bb->index == EXIT_BLOCK) 3330 { 3331 df_exit_block_uses_collect (collection_rec, df->exit_block_uses); 3332 return; 3333 } 3334 3335#ifdef EH_RETURN_DATA_REGNO 3336 if (bb_has_eh_pred (bb)) 3337 { 3338 unsigned int i; 3339 /* Mark the registers that will contain data for the handler. */ 3340 for (i = 0; ; ++i) 3341 { 3342 unsigned regno = EH_RETURN_DATA_REGNO (i); 3343 if (regno == INVALID_REGNUM) 3344 break; 3345 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[regno], NULL, 3346 bb, NULL, DF_REF_REG_DEF, DF_REF_AT_TOP); 3347 } 3348 } 3349#endif 3350 3351 /* Add the hard_frame_pointer if this block is the target of a 3352 non-local goto. */ 3353 if (bb->flags & BB_NON_LOCAL_GOTO_TARGET) 3354 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, hard_frame_pointer_rtx, NULL, 3355 bb, NULL, DF_REF_REG_DEF, DF_REF_AT_TOP); 3356 3357 /* Add the artificial uses. */ 3358 if (bb->index >= NUM_FIXED_BLOCKS) 3359 { 3360 bitmap_iterator bi; 3361 unsigned int regno; 3362 bitmap au = bb_has_eh_pred (bb) 3363 ? &df->eh_block_artificial_uses 3364 : &df->regular_block_artificial_uses; 3365 3366 EXECUTE_IF_SET_IN_BITMAP (au, 0, regno, bi) 3367 { 3368 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[regno], NULL, 3369 bb, NULL, DF_REF_REG_USE, 0); 3370 } 3371 } 3372 3373 df_canonize_collection_rec (collection_rec); 3374} 3375 3376 3377/* Record all the refs within the basic block BB_INDEX and scan the instructions if SCAN_INSNS. */ 3378 3379void 3380df_bb_refs_record (int bb_index, bool scan_insns) 3381{ 3382 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index); 3383 rtx_insn *insn; 3384 int luid = 0; 3385 3386 if (!df) 3387 return; 3388 3389 df_collection_rec collection_rec; 3390 df_grow_bb_info (df_scan); 3391 if (scan_insns) 3392 /* Scan the block an insn at a time from beginning to end. */ 3393 FOR_BB_INSNS (bb, insn) 3394 { 3395 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn); 3396 gcc_assert (!insn_info); 3397 3398 insn_info = df_insn_create_insn_record (insn); 3399 if (INSN_P (insn)) 3400 { 3401 /* Record refs within INSN. */ 3402 DF_INSN_INFO_LUID (insn_info) = luid++; 3403 df_insn_refs_collect (&collection_rec, bb, DF_INSN_INFO_GET (insn)); 3404 df_refs_add_to_chains (&collection_rec, bb, insn, copy_all); 3405 } 3406 DF_INSN_INFO_LUID (insn_info) = luid; 3407 } 3408 3409 /* Other block level artificial refs */ 3410 df_bb_refs_collect (&collection_rec, bb); 3411 df_refs_add_to_chains (&collection_rec, bb, NULL, copy_all); 3412 3413 /* Now that the block has been processed, set the block as dirty so 3414 LR and LIVE will get it processed. */ 3415 df_set_bb_dirty (bb); 3416} 3417 3418 3419/* Get the artificial use set for a regular (i.e. non-exit/non-entry) 3420 block. */ 3421 3422static void 3423df_get_regular_block_artificial_uses (bitmap regular_block_artificial_uses) 3424{ 3425#ifdef EH_USES 3426 unsigned int i; 3427#endif 3428 3429 bitmap_clear (regular_block_artificial_uses); 3430 3431 if (reload_completed) 3432 { 3433 if (frame_pointer_needed) 3434 bitmap_set_bit (regular_block_artificial_uses, HARD_FRAME_POINTER_REGNUM); 3435 } 3436 else 3437 /* Before reload, there are a few registers that must be forced 3438 live everywhere -- which might not already be the case for 3439 blocks within infinite loops. */ 3440 { 3441 unsigned int picreg = PIC_OFFSET_TABLE_REGNUM; 3442 3443 /* Any reference to any pseudo before reload is a potential 3444 reference of the frame pointer. */ 3445 bitmap_set_bit (regular_block_artificial_uses, FRAME_POINTER_REGNUM); 3446 3447#if !HARD_FRAME_POINTER_IS_FRAME_POINTER 3448 bitmap_set_bit (regular_block_artificial_uses, HARD_FRAME_POINTER_REGNUM); 3449#endif 3450 3451#if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM 3452 /* Pseudos with argument area equivalences may require 3453 reloading via the argument pointer. */ 3454 if (fixed_regs[ARG_POINTER_REGNUM]) 3455 bitmap_set_bit (regular_block_artificial_uses, ARG_POINTER_REGNUM); 3456#endif 3457 3458 /* Any constant, or pseudo with constant equivalences, may 3459 require reloading from memory using the pic register. */ 3460 if (picreg != INVALID_REGNUM 3461 && fixed_regs[picreg]) 3462 bitmap_set_bit (regular_block_artificial_uses, picreg); 3463 } 3464 /* The all-important stack pointer must always be live. */ 3465 bitmap_set_bit (regular_block_artificial_uses, STACK_POINTER_REGNUM); 3466 3467#ifdef EH_USES 3468 /* EH_USES registers are used: 3469 1) at all insns that might throw (calls or with -fnon-call-exceptions 3470 trapping insns) 3471 2) in all EH edges 3472 3) to support backtraces and/or debugging, anywhere between their 3473 initialization and where they the saved registers are restored 3474 from them, including the cases where we don't reach the epilogue 3475 (noreturn call or infinite loop). */ 3476 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 3477 if (EH_USES (i)) 3478 bitmap_set_bit (regular_block_artificial_uses, i); 3479#endif 3480} 3481 3482 3483/* Get the artificial use set for an eh block. */ 3484 3485static void 3486df_get_eh_block_artificial_uses (bitmap eh_block_artificial_uses) 3487{ 3488 bitmap_clear (eh_block_artificial_uses); 3489 3490 /* The following code (down through the arg_pointer setting APPEARS 3491 to be necessary because there is nothing that actually 3492 describes what the exception handling code may actually need 3493 to keep alive. */ 3494 if (reload_completed) 3495 { 3496 if (frame_pointer_needed) 3497 { 3498 bitmap_set_bit (eh_block_artificial_uses, FRAME_POINTER_REGNUM); 3499#if !HARD_FRAME_POINTER_IS_FRAME_POINTER 3500 bitmap_set_bit (eh_block_artificial_uses, HARD_FRAME_POINTER_REGNUM); 3501#endif 3502 } 3503#if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM 3504 if (fixed_regs[ARG_POINTER_REGNUM]) 3505 bitmap_set_bit (eh_block_artificial_uses, ARG_POINTER_REGNUM); 3506#endif 3507 } 3508} 3509 3510 3511 3512/*---------------------------------------------------------------------------- 3513 Specialized hard register scanning functions. 3514----------------------------------------------------------------------------*/ 3515 3516 3517/* Mark a register in SET. Hard registers in large modes get all 3518 of their component registers set as well. */ 3519 3520static void 3521df_mark_reg (rtx reg, void *vset) 3522{ 3523 bitmap set = (bitmap) vset; 3524 int regno = REGNO (reg); 3525 3526 gcc_assert (GET_MODE (reg) != BLKmode); 3527 3528 if (regno < FIRST_PSEUDO_REGISTER) 3529 { 3530 int n = hard_regno_nregs[regno][GET_MODE (reg)]; 3531 bitmap_set_range (set, regno, n); 3532 } 3533 else 3534 bitmap_set_bit (set, regno); 3535} 3536 3537 3538/* Set the bit for regs that are considered being defined at the entry. */ 3539 3540static void 3541df_get_entry_block_def_set (bitmap entry_block_defs) 3542{ 3543 rtx r; 3544 int i; 3545 3546 bitmap_clear (entry_block_defs); 3547 3548 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 3549 { 3550 if (global_regs[i]) 3551 bitmap_set_bit (entry_block_defs, i); 3552 if (FUNCTION_ARG_REGNO_P (i)) 3553 bitmap_set_bit (entry_block_defs, INCOMING_REGNO (i)); 3554 } 3555 3556 /* The always important stack pointer. */ 3557 bitmap_set_bit (entry_block_defs, STACK_POINTER_REGNUM); 3558 3559 /* Once the prologue has been generated, all of these registers 3560 should just show up in the first regular block. */ 3561 if (HAVE_prologue && epilogue_completed) 3562 { 3563 /* Defs for the callee saved registers are inserted so that the 3564 pushes have some defining location. */ 3565 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 3566 if ((call_used_regs[i] == 0) && (df_regs_ever_live_p (i))) 3567 bitmap_set_bit (entry_block_defs, i); 3568 } 3569 3570 r = targetm.calls.struct_value_rtx (current_function_decl, true); 3571 if (r && REG_P (r)) 3572 bitmap_set_bit (entry_block_defs, REGNO (r)); 3573 3574 /* If the function has an incoming STATIC_CHAIN, it has to show up 3575 in the entry def set. */ 3576 r = targetm.calls.static_chain (current_function_decl, true); 3577 if (r && REG_P (r)) 3578 bitmap_set_bit (entry_block_defs, REGNO (r)); 3579 3580 if ((!reload_completed) || frame_pointer_needed) 3581 { 3582 /* Any reference to any pseudo before reload is a potential 3583 reference of the frame pointer. */ 3584 bitmap_set_bit (entry_block_defs, FRAME_POINTER_REGNUM); 3585#if !HARD_FRAME_POINTER_IS_FRAME_POINTER 3586 /* If they are different, also mark the hard frame pointer as live. */ 3587 if (!LOCAL_REGNO (HARD_FRAME_POINTER_REGNUM)) 3588 bitmap_set_bit (entry_block_defs, HARD_FRAME_POINTER_REGNUM); 3589#endif 3590 } 3591 3592 /* These registers are live everywhere. */ 3593 if (!reload_completed) 3594 { 3595#ifdef PIC_OFFSET_TABLE_REGNUM 3596 unsigned int picreg = PIC_OFFSET_TABLE_REGNUM; 3597#endif 3598 3599#if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM 3600 /* Pseudos with argument area equivalences may require 3601 reloading via the argument pointer. */ 3602 if (fixed_regs[ARG_POINTER_REGNUM]) 3603 bitmap_set_bit (entry_block_defs, ARG_POINTER_REGNUM); 3604#endif 3605 3606#ifdef PIC_OFFSET_TABLE_REGNUM 3607 /* Any constant, or pseudo with constant equivalences, may 3608 require reloading from memory using the pic register. */ 3609 if (picreg != INVALID_REGNUM 3610 && fixed_regs[picreg]) 3611 bitmap_set_bit (entry_block_defs, picreg); 3612#endif 3613 } 3614 3615#ifdef INCOMING_RETURN_ADDR_RTX 3616 if (REG_P (INCOMING_RETURN_ADDR_RTX)) 3617 bitmap_set_bit (entry_block_defs, REGNO (INCOMING_RETURN_ADDR_RTX)); 3618#endif 3619 3620 targetm.extra_live_on_entry (entry_block_defs); 3621} 3622 3623 3624/* Return the (conservative) set of hard registers that are defined on 3625 entry to the function. 3626 It uses df->entry_block_defs to determine which register 3627 reference to include. */ 3628 3629static void 3630df_entry_block_defs_collect (struct df_collection_rec *collection_rec, 3631 bitmap entry_block_defs) 3632{ 3633 unsigned int i; 3634 bitmap_iterator bi; 3635 3636 EXECUTE_IF_SET_IN_BITMAP (entry_block_defs, 0, i, bi) 3637 { 3638 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[i], NULL, 3639 ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, DF_REF_REG_DEF, 0); 3640 } 3641 3642 df_canonize_collection_rec (collection_rec); 3643} 3644 3645 3646/* Record the (conservative) set of hard registers that are defined on 3647 entry to the function. */ 3648 3649static void 3650df_record_entry_block_defs (bitmap entry_block_defs) 3651{ 3652 struct df_collection_rec collection_rec; 3653 df_entry_block_defs_collect (&collection_rec, entry_block_defs); 3654 3655 /* Process bb_refs chain */ 3656 df_refs_add_to_chains (&collection_rec, 3657 BASIC_BLOCK_FOR_FN (cfun, ENTRY_BLOCK), 3658 NULL, 3659 copy_defs); 3660} 3661 3662 3663/* Update the defs in the entry block. */ 3664 3665void 3666df_update_entry_block_defs (void) 3667{ 3668 bitmap_head refs; 3669 bool changed = false; 3670 3671 bitmap_initialize (&refs, &df_bitmap_obstack); 3672 df_get_entry_block_def_set (&refs); 3673 if (df->entry_block_defs) 3674 { 3675 if (!bitmap_equal_p (df->entry_block_defs, &refs)) 3676 { 3677 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (ENTRY_BLOCK); 3678 df_ref_chain_delete_du_chain (bb_info->artificial_defs); 3679 df_ref_chain_delete (bb_info->artificial_defs); 3680 bb_info->artificial_defs = NULL; 3681 changed = true; 3682 } 3683 } 3684 else 3685 { 3686 struct df_scan_problem_data *problem_data 3687 = (struct df_scan_problem_data *) df_scan->problem_data; 3688 gcc_unreachable (); 3689 df->entry_block_defs = BITMAP_ALLOC (&problem_data->reg_bitmaps); 3690 changed = true; 3691 } 3692 3693 if (changed) 3694 { 3695 df_record_entry_block_defs (&refs); 3696 bitmap_copy (df->entry_block_defs, &refs); 3697 df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun, ENTRY_BLOCK)); 3698 } 3699 bitmap_clear (&refs); 3700} 3701 3702 3703/* Set the bit for regs that are considered being used at the exit. */ 3704 3705static void 3706df_get_exit_block_use_set (bitmap exit_block_uses) 3707{ 3708 unsigned int i; 3709 unsigned int picreg = PIC_OFFSET_TABLE_REGNUM; 3710 3711 bitmap_clear (exit_block_uses); 3712 3713 /* Stack pointer is always live at the exit. */ 3714 bitmap_set_bit (exit_block_uses, STACK_POINTER_REGNUM); 3715 3716 /* Mark the frame pointer if needed at the end of the function. 3717 If we end up eliminating it, it will be removed from the live 3718 list of each basic block by reload. */ 3719 3720 if ((!reload_completed) || frame_pointer_needed) 3721 { 3722 bitmap_set_bit (exit_block_uses, FRAME_POINTER_REGNUM); 3723#if !HARD_FRAME_POINTER_IS_FRAME_POINTER 3724 /* If they are different, also mark the hard frame pointer as live. */ 3725 if (!LOCAL_REGNO (HARD_FRAME_POINTER_REGNUM)) 3726 bitmap_set_bit (exit_block_uses, HARD_FRAME_POINTER_REGNUM); 3727#endif 3728 } 3729 3730 /* Many architectures have a GP register even without flag_pic. 3731 Assume the pic register is not in use, or will be handled by 3732 other means, if it is not fixed. */ 3733 if (!PIC_OFFSET_TABLE_REG_CALL_CLOBBERED 3734 && picreg != INVALID_REGNUM 3735 && fixed_regs[picreg]) 3736 bitmap_set_bit (exit_block_uses, picreg); 3737 3738 /* Mark all global registers, and all registers used by the 3739 epilogue as being live at the end of the function since they 3740 may be referenced by our caller. */ 3741 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 3742 if (global_regs[i] || EPILOGUE_USES (i)) 3743 bitmap_set_bit (exit_block_uses, i); 3744 3745 if (HAVE_epilogue && epilogue_completed) 3746 { 3747 /* Mark all call-saved registers that we actually used. */ 3748 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 3749 if (df_regs_ever_live_p (i) && !LOCAL_REGNO (i) 3750 && !TEST_HARD_REG_BIT (regs_invalidated_by_call, i)) 3751 bitmap_set_bit (exit_block_uses, i); 3752 } 3753 3754#ifdef EH_RETURN_DATA_REGNO 3755 /* Mark the registers that will contain data for the handler. */ 3756 if (reload_completed && crtl->calls_eh_return) 3757 for (i = 0; ; ++i) 3758 { 3759 unsigned regno = EH_RETURN_DATA_REGNO (i); 3760 if (regno == INVALID_REGNUM) 3761 break; 3762 bitmap_set_bit (exit_block_uses, regno); 3763 } 3764#endif 3765 3766#ifdef EH_RETURN_STACKADJ_RTX 3767 if ((!HAVE_epilogue || ! epilogue_completed) 3768 && crtl->calls_eh_return) 3769 { 3770 rtx tmp = EH_RETURN_STACKADJ_RTX; 3771 if (tmp && REG_P (tmp)) 3772 df_mark_reg (tmp, exit_block_uses); 3773 } 3774#endif 3775 3776#ifdef EH_RETURN_HANDLER_RTX 3777 if ((!HAVE_epilogue || ! epilogue_completed) 3778 && crtl->calls_eh_return) 3779 { 3780 rtx tmp = EH_RETURN_HANDLER_RTX; 3781 if (tmp && REG_P (tmp)) 3782 df_mark_reg (tmp, exit_block_uses); 3783 } 3784#endif 3785 3786 /* Mark function return value. */ 3787 diddle_return_value (df_mark_reg, (void*) exit_block_uses); 3788} 3789 3790 3791/* Return the refs of hard registers that are used in the exit block. 3792 It uses df->exit_block_uses to determine register to include. */ 3793 3794static void 3795df_exit_block_uses_collect (struct df_collection_rec *collection_rec, bitmap exit_block_uses) 3796{ 3797 unsigned int i; 3798 bitmap_iterator bi; 3799 3800 EXECUTE_IF_SET_IN_BITMAP (exit_block_uses, 0, i, bi) 3801 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[i], NULL, 3802 EXIT_BLOCK_PTR_FOR_FN (cfun), NULL, DF_REF_REG_USE, 0); 3803 3804#if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM 3805 /* It is deliberate that this is not put in the exit block uses but 3806 I do not know why. */ 3807 if (reload_completed 3808 && !bitmap_bit_p (exit_block_uses, ARG_POINTER_REGNUM) 3809 && bb_has_eh_pred (EXIT_BLOCK_PTR_FOR_FN (cfun)) 3810 && fixed_regs[ARG_POINTER_REGNUM]) 3811 df_ref_record (DF_REF_ARTIFICIAL, collection_rec, regno_reg_rtx[ARG_POINTER_REGNUM], NULL, 3812 EXIT_BLOCK_PTR_FOR_FN (cfun), NULL, DF_REF_REG_USE, 0); 3813#endif 3814 3815 df_canonize_collection_rec (collection_rec); 3816} 3817 3818 3819/* Record the set of hard registers that are used in the exit block. 3820 It uses df->exit_block_uses to determine which bit to include. */ 3821 3822static void 3823df_record_exit_block_uses (bitmap exit_block_uses) 3824{ 3825 struct df_collection_rec collection_rec; 3826 df_exit_block_uses_collect (&collection_rec, exit_block_uses); 3827 3828 /* Process bb_refs chain */ 3829 df_refs_add_to_chains (&collection_rec, 3830 BASIC_BLOCK_FOR_FN (cfun, EXIT_BLOCK), 3831 NULL, 3832 copy_uses); 3833} 3834 3835 3836/* Update the uses in the exit block. */ 3837 3838void 3839df_update_exit_block_uses (void) 3840{ 3841 bitmap_head refs; 3842 bool changed = false; 3843 3844 bitmap_initialize (&refs, &df_bitmap_obstack); 3845 df_get_exit_block_use_set (&refs); 3846 if (df->exit_block_uses) 3847 { 3848 if (!bitmap_equal_p (df->exit_block_uses, &refs)) 3849 { 3850 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (EXIT_BLOCK); 3851 df_ref_chain_delete_du_chain (bb_info->artificial_uses); 3852 df_ref_chain_delete (bb_info->artificial_uses); 3853 bb_info->artificial_uses = NULL; 3854 changed = true; 3855 } 3856 } 3857 else 3858 { 3859 struct df_scan_problem_data *problem_data 3860 = (struct df_scan_problem_data *) df_scan->problem_data; 3861 gcc_unreachable (); 3862 df->exit_block_uses = BITMAP_ALLOC (&problem_data->reg_bitmaps); 3863 changed = true; 3864 } 3865 3866 if (changed) 3867 { 3868 df_record_exit_block_uses (&refs); 3869 bitmap_copy (df->exit_block_uses,& refs); 3870 df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun, EXIT_BLOCK)); 3871 } 3872 bitmap_clear (&refs); 3873} 3874 3875static bool initialized = false; 3876 3877 3878/* Initialize some platform specific structures. */ 3879 3880void 3881df_hard_reg_init (void) 3882{ 3883#ifdef ELIMINABLE_REGS 3884 int i; 3885 static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS; 3886#endif 3887 if (initialized) 3888 return; 3889 3890 /* Record which registers will be eliminated. We use this in 3891 mark_used_regs. */ 3892 CLEAR_HARD_REG_SET (elim_reg_set); 3893 3894#ifdef ELIMINABLE_REGS 3895 for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++) 3896 SET_HARD_REG_BIT (elim_reg_set, eliminables[i].from); 3897#else 3898 SET_HARD_REG_BIT (elim_reg_set, FRAME_POINTER_REGNUM); 3899#endif 3900 3901 initialized = true; 3902} 3903 3904 3905/* Recompute the parts of scanning that are based on regs_ever_live 3906 because something changed in that array. */ 3907 3908void 3909df_update_entry_exit_and_calls (void) 3910{ 3911 basic_block bb; 3912 3913 df_update_entry_block_defs (); 3914 df_update_exit_block_uses (); 3915 3916 /* The call insns need to be rescanned because there may be changes 3917 in the set of registers clobbered across the call. */ 3918 FOR_EACH_BB_FN (bb, cfun) 3919 { 3920 rtx_insn *insn; 3921 FOR_BB_INSNS (bb, insn) 3922 { 3923 if (INSN_P (insn) && CALL_P (insn)) 3924 df_insn_rescan (insn); 3925 } 3926 } 3927} 3928 3929 3930/* Return true if hard REG is actually used in the some instruction. 3931 There are a fair number of conditions that affect the setting of 3932 this array. See the comment in df.h for df->hard_regs_live_count 3933 for the conditions that this array is set. */ 3934 3935bool 3936df_hard_reg_used_p (unsigned int reg) 3937{ 3938 return df->hard_regs_live_count[reg] != 0; 3939} 3940 3941 3942/* A count of the number of times REG is actually used in the some 3943 instruction. There are a fair number of conditions that affect the 3944 setting of this array. See the comment in df.h for 3945 df->hard_regs_live_count for the conditions that this array is 3946 set. */ 3947 3948 3949unsigned int 3950df_hard_reg_used_count (unsigned int reg) 3951{ 3952 return df->hard_regs_live_count[reg]; 3953} 3954 3955 3956/* Get the value of regs_ever_live[REGNO]. */ 3957 3958bool 3959df_regs_ever_live_p (unsigned int regno) 3960{ 3961 return regs_ever_live[regno]; 3962} 3963 3964 3965/* Set regs_ever_live[REGNO] to VALUE. If this cause regs_ever_live 3966 to change, schedule that change for the next update. */ 3967 3968void 3969df_set_regs_ever_live (unsigned int regno, bool value) 3970{ 3971 if (regs_ever_live[regno] == value) 3972 return; 3973 3974 regs_ever_live[regno] = value; 3975 if (df) 3976 df->redo_entry_and_exit = true; 3977} 3978 3979 3980/* Compute "regs_ever_live" information from the underlying df 3981 information. Set the vector to all false if RESET. */ 3982 3983void 3984df_compute_regs_ever_live (bool reset) 3985{ 3986 unsigned int i; 3987 bool changed = df->redo_entry_and_exit; 3988 3989 if (reset) 3990 memset (regs_ever_live, 0, sizeof (regs_ever_live)); 3991 3992 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 3993 if ((!regs_ever_live[i]) && df_hard_reg_used_p (i)) 3994 { 3995 regs_ever_live[i] = true; 3996 changed = true; 3997 } 3998 if (changed) 3999 df_update_entry_exit_and_calls (); 4000 df->redo_entry_and_exit = false; 4001} 4002 4003 4004/*---------------------------------------------------------------------------- 4005 Dataflow ref information verification functions. 4006 4007 df_reg_chain_mark (refs, regno, is_def, is_eq_use) 4008 df_reg_chain_verify_unmarked (refs) 4009 df_refs_verify (vec<stack, va_df_ref>, ref*, bool) 4010 df_mws_verify (mw*, mw*, bool) 4011 df_insn_refs_verify (collection_rec, bb, insn, bool) 4012 df_bb_refs_verify (bb, refs, bool) 4013 df_bb_verify (bb) 4014 df_exit_block_bitmap_verify (bool) 4015 df_entry_block_bitmap_verify (bool) 4016 df_scan_verify () 4017----------------------------------------------------------------------------*/ 4018 4019 4020/* Mark all refs in the reg chain. Verify that all of the registers 4021are in the correct chain. */ 4022 4023static unsigned int 4024df_reg_chain_mark (df_ref refs, unsigned int regno, 4025 bool is_def, bool is_eq_use) 4026{ 4027 unsigned int count = 0; 4028 df_ref ref; 4029 for (ref = refs; ref; ref = DF_REF_NEXT_REG (ref)) 4030 { 4031 gcc_assert (!DF_REF_IS_REG_MARKED (ref)); 4032 4033 /* If there are no def-use or use-def chains, make sure that all 4034 of the chains are clear. */ 4035 if (!df_chain) 4036 gcc_assert (!DF_REF_CHAIN (ref)); 4037 4038 /* Check to make sure the ref is in the correct chain. */ 4039 gcc_assert (DF_REF_REGNO (ref) == regno); 4040 if (is_def) 4041 gcc_assert (DF_REF_REG_DEF_P (ref)); 4042 else 4043 gcc_assert (!DF_REF_REG_DEF_P (ref)); 4044 4045 if (is_eq_use) 4046 gcc_assert ((DF_REF_FLAGS (ref) & DF_REF_IN_NOTE)); 4047 else 4048 gcc_assert ((DF_REF_FLAGS (ref) & DF_REF_IN_NOTE) == 0); 4049 4050 if (DF_REF_NEXT_REG (ref)) 4051 gcc_assert (DF_REF_PREV_REG (DF_REF_NEXT_REG (ref)) == ref); 4052 count++; 4053 DF_REF_REG_MARK (ref); 4054 } 4055 return count; 4056} 4057 4058 4059/* Verify that all of the registers in the chain are unmarked. */ 4060 4061static void 4062df_reg_chain_verify_unmarked (df_ref refs) 4063{ 4064 df_ref ref; 4065 for (ref = refs; ref; ref = DF_REF_NEXT_REG (ref)) 4066 gcc_assert (!DF_REF_IS_REG_MARKED (ref)); 4067} 4068 4069 4070/* Verify that NEW_REC and OLD_REC have exactly the same members. */ 4071 4072static bool 4073df_refs_verify (const vec<df_ref, va_heap> *new_rec, df_ref old_rec, 4074 bool abort_if_fail) 4075{ 4076 unsigned int ix; 4077 df_ref new_ref; 4078 4079 FOR_EACH_VEC_ELT (*new_rec, ix, new_ref) 4080 { 4081 if (old_rec == NULL || !df_ref_equal_p (new_ref, old_rec)) 4082 { 4083 if (abort_if_fail) 4084 gcc_assert (0); 4085 else 4086 return false; 4087 } 4088 4089 /* Abort if fail is called from the function level verifier. If 4090 that is the context, mark this reg as being seem. */ 4091 if (abort_if_fail) 4092 { 4093 gcc_assert (DF_REF_IS_REG_MARKED (old_rec)); 4094 DF_REF_REG_UNMARK (old_rec); 4095 } 4096 4097 old_rec = DF_REF_NEXT_LOC (old_rec); 4098 } 4099 4100 if (abort_if_fail) 4101 gcc_assert (old_rec == NULL); 4102 else 4103 return old_rec == NULL; 4104 return false; 4105} 4106 4107 4108/* Verify that NEW_REC and OLD_REC have exactly the same members. */ 4109 4110static bool 4111df_mws_verify (const vec<df_mw_hardreg_ptr, va_heap> *new_rec, 4112 struct df_mw_hardreg *old_rec, 4113 bool abort_if_fail) 4114{ 4115 unsigned int ix; 4116 struct df_mw_hardreg *new_reg; 4117 4118 FOR_EACH_VEC_ELT (*new_rec, ix, new_reg) 4119 { 4120 if (old_rec == NULL || !df_mw_equal_p (new_reg, old_rec)) 4121 { 4122 if (abort_if_fail) 4123 gcc_assert (0); 4124 else 4125 return false; 4126 } 4127 old_rec = DF_MWS_NEXT (old_rec); 4128 } 4129 4130 if (abort_if_fail) 4131 gcc_assert (old_rec == NULL); 4132 else 4133 return old_rec == NULL; 4134 return false; 4135} 4136 4137 4138/* Return true if the existing insn refs information is complete and 4139 correct. Otherwise (i.e. if there's any missing or extra refs), 4140 return the correct df_ref chain in REFS_RETURN. 4141 4142 If ABORT_IF_FAIL, leave the refs that are verified (already in the 4143 ref chain) as DF_REF_MARKED(). If it's false, then it's a per-insn 4144 verification mode instead of the whole function, so unmark 4145 everything. 4146 4147 If ABORT_IF_FAIL is set, this function never returns false. */ 4148 4149static bool 4150df_insn_refs_verify (struct df_collection_rec *collection_rec, 4151 basic_block bb, 4152 rtx_insn *insn, 4153 bool abort_if_fail) 4154{ 4155 bool ret1, ret2, ret3, ret4; 4156 unsigned int uid = INSN_UID (insn); 4157 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn); 4158 4159 df_insn_refs_collect (collection_rec, bb, insn_info); 4160 4161 /* Unfortunately we cannot opt out early if one of these is not 4162 right because the marks will not get cleared. */ 4163 ret1 = df_refs_verify (&collection_rec->def_vec, DF_INSN_UID_DEFS (uid), 4164 abort_if_fail); 4165 ret2 = df_refs_verify (&collection_rec->use_vec, DF_INSN_UID_USES (uid), 4166 abort_if_fail); 4167 ret3 = df_refs_verify (&collection_rec->eq_use_vec, DF_INSN_UID_EQ_USES (uid), 4168 abort_if_fail); 4169 ret4 = df_mws_verify (&collection_rec->mw_vec, DF_INSN_UID_MWS (uid), 4170 abort_if_fail); 4171 return (ret1 && ret2 && ret3 && ret4); 4172} 4173 4174 4175/* Return true if all refs in the basic block are correct and complete. 4176 Due to df_ref_chain_verify, it will cause all refs 4177 that are verified to have DF_REF_MARK bit set. */ 4178 4179static bool 4180df_bb_verify (basic_block bb) 4181{ 4182 rtx_insn *insn; 4183 struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb->index); 4184 struct df_collection_rec collection_rec; 4185 4186 gcc_assert (bb_info); 4187 4188 /* Scan the block, one insn at a time, from beginning to end. */ 4189 FOR_BB_INSNS_REVERSE (bb, insn) 4190 { 4191 if (!INSN_P (insn)) 4192 continue; 4193 df_insn_refs_verify (&collection_rec, bb, insn, true); 4194 df_free_collection_rec (&collection_rec); 4195 } 4196 4197 /* Do the artificial defs and uses. */ 4198 df_bb_refs_collect (&collection_rec, bb); 4199 df_refs_verify (&collection_rec.def_vec, df_get_artificial_defs (bb->index), true); 4200 df_refs_verify (&collection_rec.use_vec, df_get_artificial_uses (bb->index), true); 4201 df_free_collection_rec (&collection_rec); 4202 4203 return true; 4204} 4205 4206 4207/* Returns true if the entry block has correct and complete df_ref set. 4208 If not it either aborts if ABORT_IF_FAIL is true or returns false. */ 4209 4210static bool 4211df_entry_block_bitmap_verify (bool abort_if_fail) 4212{ 4213 bitmap_head entry_block_defs; 4214 bool is_eq; 4215 4216 bitmap_initialize (&entry_block_defs, &df_bitmap_obstack); 4217 df_get_entry_block_def_set (&entry_block_defs); 4218 4219 is_eq = bitmap_equal_p (&entry_block_defs, df->entry_block_defs); 4220 4221 if (!is_eq && abort_if_fail) 4222 { 4223 fprintf (stderr, "entry_block_defs = "); 4224 df_print_regset (stderr, &entry_block_defs); 4225 fprintf (stderr, "df->entry_block_defs = "); 4226 df_print_regset (stderr, df->entry_block_defs); 4227 gcc_assert (0); 4228 } 4229 4230 bitmap_clear (&entry_block_defs); 4231 4232 return is_eq; 4233} 4234 4235 4236/* Returns true if the exit block has correct and complete df_ref set. 4237 If not it either aborts if ABORT_IF_FAIL is true or returns false. */ 4238 4239static bool 4240df_exit_block_bitmap_verify (bool abort_if_fail) 4241{ 4242 bitmap_head exit_block_uses; 4243 bool is_eq; 4244 4245 bitmap_initialize (&exit_block_uses, &df_bitmap_obstack); 4246 df_get_exit_block_use_set (&exit_block_uses); 4247 4248 is_eq = bitmap_equal_p (&exit_block_uses, df->exit_block_uses); 4249 4250 if (!is_eq && abort_if_fail) 4251 { 4252 fprintf (stderr, "exit_block_uses = "); 4253 df_print_regset (stderr, &exit_block_uses); 4254 fprintf (stderr, "df->exit_block_uses = "); 4255 df_print_regset (stderr, df->exit_block_uses); 4256 gcc_assert (0); 4257 } 4258 4259 bitmap_clear (&exit_block_uses); 4260 4261 return is_eq; 4262} 4263 4264 4265/* Return true if df_ref information for all insns in all blocks are 4266 correct and complete. */ 4267 4268void 4269df_scan_verify (void) 4270{ 4271 unsigned int i; 4272 basic_block bb; 4273 bitmap_head regular_block_artificial_uses; 4274 bitmap_head eh_block_artificial_uses; 4275 4276 if (!df) 4277 return; 4278 4279 /* Verification is a 4 step process. */ 4280 4281 /* (1) All of the refs are marked by going through the reg chains. */ 4282 for (i = 0; i < DF_REG_SIZE (df); i++) 4283 { 4284 gcc_assert (df_reg_chain_mark (DF_REG_DEF_CHAIN (i), i, true, false) 4285 == DF_REG_DEF_COUNT (i)); 4286 gcc_assert (df_reg_chain_mark (DF_REG_USE_CHAIN (i), i, false, false) 4287 == DF_REG_USE_COUNT (i)); 4288 gcc_assert (df_reg_chain_mark (DF_REG_EQ_USE_CHAIN (i), i, false, true) 4289 == DF_REG_EQ_USE_COUNT (i)); 4290 } 4291 4292 /* (2) There are various bitmaps whose value may change over the 4293 course of the compilation. This step recomputes them to make 4294 sure that they have not slipped out of date. */ 4295 bitmap_initialize (®ular_block_artificial_uses, &df_bitmap_obstack); 4296 bitmap_initialize (&eh_block_artificial_uses, &df_bitmap_obstack); 4297 4298 df_get_regular_block_artificial_uses (®ular_block_artificial_uses); 4299 df_get_eh_block_artificial_uses (&eh_block_artificial_uses); 4300 4301 bitmap_ior_into (&eh_block_artificial_uses, 4302 ®ular_block_artificial_uses); 4303 4304 /* Check artificial_uses bitmaps didn't change. */ 4305 gcc_assert (bitmap_equal_p (®ular_block_artificial_uses, 4306 &df->regular_block_artificial_uses)); 4307 gcc_assert (bitmap_equal_p (&eh_block_artificial_uses, 4308 &df->eh_block_artificial_uses)); 4309 4310 bitmap_clear (®ular_block_artificial_uses); 4311 bitmap_clear (&eh_block_artificial_uses); 4312 4313 /* Verify entry block and exit block. These only verify the bitmaps, 4314 the refs are verified in df_bb_verify. */ 4315 df_entry_block_bitmap_verify (true); 4316 df_exit_block_bitmap_verify (true); 4317 4318 /* (3) All of the insns in all of the blocks are traversed and the 4319 marks are cleared both in the artificial refs attached to the 4320 blocks and the real refs inside the insns. It is a failure to 4321 clear a mark that has not been set as this means that the ref in 4322 the block or insn was not in the reg chain. */ 4323 4324 FOR_ALL_BB_FN (bb, cfun) 4325 df_bb_verify (bb); 4326 4327 /* (4) See if all reg chains are traversed a second time. This time 4328 a check is made that the marks are clear. A set mark would be a 4329 from a reg that is not in any insn or basic block. */ 4330 4331 for (i = 0; i < DF_REG_SIZE (df); i++) 4332 { 4333 df_reg_chain_verify_unmarked (DF_REG_DEF_CHAIN (i)); 4334 df_reg_chain_verify_unmarked (DF_REG_USE_CHAIN (i)); 4335 df_reg_chain_verify_unmarked (DF_REG_EQ_USE_CHAIN (i)); 4336 } 4337} 4338