df-core.c revision 1.3
1/* Allocation for dataflow support routines. 2 Copyright (C) 1999-2013 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/* 25OVERVIEW: 26 27The files in this collection (df*.c,df.h) provide a general framework 28for solving dataflow problems. The global dataflow is performed using 29a good implementation of iterative dataflow analysis. 30 31The file df-problems.c provides problem instance for the most common 32dataflow problems: reaching defs, upward exposed uses, live variables, 33uninitialized variables, def-use chains, and use-def chains. However, 34the interface allows other dataflow problems to be defined as well. 35 36Dataflow analysis is available in most of the rtl backend (the parts 37between pass_df_initialize and pass_df_finish). It is quite likely 38that these boundaries will be expanded in the future. The only 39requirement is that there be a correct control flow graph. 40 41There are three variations of the live variable problem that are 42available whenever dataflow is available. The LR problem finds the 43areas that can reach a use of a variable, the UR problems finds the 44areas that can be reached from a definition of a variable. The LIVE 45problem finds the intersection of these two areas. 46 47There are several optional problems. These can be enabled when they 48are needed and disabled when they are not needed. 49 50Dataflow problems are generally solved in three layers. The bottom 51layer is called scanning where a data structure is built for each rtl 52insn that describes the set of defs and uses of that insn. Scanning 53is generally kept up to date, i.e. as the insns changes, the scanned 54version of that insn changes also. There are various mechanisms for 55making this happen and are described in the INCREMENTAL SCANNING 56section. 57 58In the middle layer, basic blocks are scanned to produce transfer 59functions which describe the effects of that block on the global 60dataflow solution. The transfer functions are only rebuilt if the 61some instruction within the block has changed. 62 63The top layer is the dataflow solution itself. The dataflow solution 64is computed by using an efficient iterative solver and the transfer 65functions. The dataflow solution must be recomputed whenever the 66control changes or if one of the transfer function changes. 67 68 69USAGE: 70 71Here is an example of using the dataflow routines. 72 73 df_[chain,live,note,rd]_add_problem (flags); 74 75 df_set_blocks (blocks); 76 77 df_analyze (); 78 79 df_dump (stderr); 80 81 df_finish_pass (false); 82 83DF_[chain,live,note,rd]_ADD_PROBLEM adds a problem, defined by an 84instance to struct df_problem, to the set of problems solved in this 85instance of df. All calls to add a problem for a given instance of df 86must occur before the first call to DF_ANALYZE. 87 88Problems can be dependent on other problems. For instance, solving 89def-use or use-def chains is dependent on solving reaching 90definitions. As long as these dependencies are listed in the problem 91definition, the order of adding the problems is not material. 92Otherwise, the problems will be solved in the order of calls to 93df_add_problem. Note that it is not necessary to have a problem. In 94that case, df will just be used to do the scanning. 95 96 97 98DF_SET_BLOCKS is an optional call used to define a region of the 99function on which the analysis will be performed. The normal case is 100to analyze the entire function and no call to df_set_blocks is made. 101DF_SET_BLOCKS only effects the blocks that are effected when computing 102the transfer functions and final solution. The insn level information 103is always kept up to date. 104 105When a subset is given, the analysis behaves as if the function only 106contains those blocks and any edges that occur directly between the 107blocks in the set. Care should be taken to call df_set_blocks right 108before the call to analyze in order to eliminate the possibility that 109optimizations that reorder blocks invalidate the bitvector. 110 111DF_ANALYZE causes all of the defined problems to be (re)solved. When 112DF_ANALYZE is completes, the IN and OUT sets for each basic block 113contain the computer information. The DF_*_BB_INFO macros can be used 114to access these bitvectors. All deferred rescannings are down before 115the transfer functions are recomputed. 116 117DF_DUMP can then be called to dump the information produce to some 118file. This calls DF_DUMP_START, to print the information that is not 119basic block specific, and then calls DF_DUMP_TOP and DF_DUMP_BOTTOM 120for each block to print the basic specific information. These parts 121can all be called separately as part of a larger dump function. 122 123 124DF_FINISH_PASS causes df_remove_problem to be called on all of the 125optional problems. It also causes any insns whose scanning has been 126deferred to be rescanned as well as clears all of the changeable flags. 127Setting the pass manager TODO_df_finish flag causes this function to 128be run. However, the pass manager will call df_finish_pass AFTER the 129pass dumping has been done, so if you want to see the results of the 130optional problems in the pass dumps, use the TODO flag rather than 131calling the function yourself. 132 133INCREMENTAL SCANNING 134 135There are four ways of doing the incremental scanning: 136 1371) Immediate rescanning - Calls to df_insn_rescan, df_notes_rescan, 138 df_bb_delete, df_insn_change_bb have been added to most of 139 the low level service functions that maintain the cfg and change 140 rtl. Calling and of these routines many cause some number of insns 141 to be rescanned. 142 143 For most modern rtl passes, this is certainly the easiest way to 144 manage rescanning the insns. This technique also has the advantage 145 that the scanning information is always correct and can be relied 146 upon even after changes have been made to the instructions. This 147 technique is contra indicated in several cases: 148 149 a) If def-use chains OR use-def chains (but not both) are built, 150 using this is SIMPLY WRONG. The problem is that when a ref is 151 deleted that is the target of an edge, there is not enough 152 information to efficiently find the source of the edge and 153 delete the edge. This leaves a dangling reference that may 154 cause problems. 155 156 b) If def-use chains AND use-def chains are built, this may 157 produce unexpected results. The problem is that the incremental 158 scanning of an insn does not know how to repair the chains that 159 point into an insn when the insn changes. So the incremental 160 scanning just deletes the chains that enter and exit the insn 161 being changed. The dangling reference issue in (a) is not a 162 problem here, but if the pass is depending on the chains being 163 maintained after insns have been modified, this technique will 164 not do the correct thing. 165 166 c) If the pass modifies insns several times, this incremental 167 updating may be expensive. 168 169 d) If the pass modifies all of the insns, as does register 170 allocation, it is simply better to rescan the entire function. 171 1722) Deferred rescanning - Calls to df_insn_rescan, df_notes_rescan, and 173 df_insn_delete do not immediately change the insn but instead make 174 a note that the insn needs to be rescanned. The next call to 175 df_analyze, df_finish_pass, or df_process_deferred_rescans will 176 cause all of the pending rescans to be processed. 177 178 This is the technique of choice if either 1a, 1b, or 1c are issues 179 in the pass. In the case of 1a or 1b, a call to df_finish_pass 180 (either manually or via TODO_df_finish) should be made before the 181 next call to df_analyze or df_process_deferred_rescans. 182 183 This mode is also used by a few passes that still rely on note_uses, 184 note_stores and for_each_rtx instead of using the DF data. This 185 can be said to fall under case 1c. 186 187 To enable this mode, call df_set_flags (DF_DEFER_INSN_RESCAN). 188 (This mode can be cleared by calling df_clear_flags 189 (DF_DEFER_INSN_RESCAN) but this does not cause the deferred insns to 190 be rescanned. 191 1923) Total rescanning - In this mode the rescanning is disabled. 193 Only when insns are deleted is the df information associated with 194 it also deleted. At the end of the pass, a call must be made to 195 df_insn_rescan_all. This method is used by the register allocator 196 since it generally changes each insn multiple times (once for each ref) 197 and does not need to make use of the updated scanning information. 198 1994) Do it yourself - In this mechanism, the pass updates the insns 200 itself using the low level df primitives. Currently no pass does 201 this, but it has the advantage that it is quite efficient given 202 that the pass generally has exact knowledge of what it is changing. 203 204DATA STRUCTURES 205 206Scanning produces a `struct df_ref' data structure (ref) is allocated 207for every register reference (def or use) and this records the insn 208and bb the ref is found within. The refs are linked together in 209chains of uses and defs for each insn and for each register. Each ref 210also has a chain field that links all the use refs for a def or all 211the def refs for a use. This is used to create use-def or def-use 212chains. 213 214Different optimizations have different needs. Ultimately, only 215register allocation and schedulers should be using the bitmaps 216produced for the live register and uninitialized register problems. 217The rest of the backend should be upgraded to using and maintaining 218the linked information such as def use or use def chains. 219 220 221PHILOSOPHY: 222 223While incremental bitmaps are not worthwhile to maintain, incremental 224chains may be perfectly reasonable. The fastest way to build chains 225from scratch or after significant modifications is to build reaching 226definitions (RD) and build the chains from this. 227 228However, general algorithms for maintaining use-def or def-use chains 229are not practical. The amount of work to recompute the chain any 230chain after an arbitrary change is large. However, with a modest 231amount of work it is generally possible to have the application that 232uses the chains keep them up to date. The high level knowledge of 233what is really happening is essential to crafting efficient 234incremental algorithms. 235 236As for the bit vector problems, there is no interface to give a set of 237blocks over with to resolve the iteration. In general, restarting a 238dataflow iteration is difficult and expensive. Again, the best way to 239keep the dataflow information up to data (if this is really what is 240needed) it to formulate a problem specific solution. 241 242There are fine grained calls for creating and deleting references from 243instructions in df-scan.c. However, these are not currently connected 244to the engine that resolves the dataflow equations. 245 246 247DATA STRUCTURES: 248 249The basic object is a DF_REF (reference) and this may either be a 250DEF (definition) or a USE of a register. 251 252These are linked into a variety of lists; namely reg-def, reg-use, 253insn-def, insn-use, def-use, and use-def lists. For example, the 254reg-def lists contain all the locations that define a given register 255while the insn-use lists contain all the locations that use a 256register. 257 258Note that the reg-def and reg-use chains are generally short for 259pseudos and long for the hard registers. 260 261ACCESSING INSNS: 262 2631) The df insn information is kept in an array of DF_INSN_INFO objects. 264 The array is indexed by insn uid, and every DF_REF points to the 265 DF_INSN_INFO object of the insn that contains the reference. 266 2672) Each insn has three sets of refs, which are linked into one of three 268 lists: The insn's defs list (accessed by the DF_INSN_INFO_DEFS, 269 DF_INSN_DEFS, or DF_INSN_UID_DEFS macros), the insn's uses list 270 (accessed by the DF_INSN_INFO_USES, DF_INSN_USES, or 271 DF_INSN_UID_USES macros) or the insn's eq_uses list (accessed by the 272 DF_INSN_INFO_EQ_USES, DF_INSN_EQ_USES or DF_INSN_UID_EQ_USES macros). 273 The latter list are the list of references in REG_EQUAL or REG_EQUIV 274 notes. These macros produce a ref (or NULL), the rest of the list 275 can be obtained by traversal of the NEXT_REF field (accessed by the 276 DF_REF_NEXT_REF macro.) There is no significance to the ordering of 277 the uses or refs in an instruction. 278 2793) Each insn has a logical uid field (LUID) which is stored in the 280 DF_INSN_INFO object for the insn. The LUID field is accessed by 281 the DF_INSN_INFO_LUID, DF_INSN_LUID, and DF_INSN_UID_LUID macros. 282 When properly set, the LUID is an integer that numbers each insn in 283 the basic block, in order from the start of the block. 284 The numbers are only correct after a call to df_analyze. They will 285 rot after insns are added deleted or moved round. 286 287ACCESSING REFS: 288 289There are 4 ways to obtain access to refs: 290 2911) References are divided into two categories, REAL and ARTIFICIAL. 292 293 REAL refs are associated with instructions. 294 295 ARTIFICIAL refs are associated with basic blocks. The heads of 296 these lists can be accessed by calling df_get_artificial_defs or 297 df_get_artificial_uses for the particular basic block. 298 299 Artificial defs and uses occur both at the beginning and ends of blocks. 300 301 For blocks that area at the destination of eh edges, the 302 artificial uses and defs occur at the beginning. The defs relate 303 to the registers specified in EH_RETURN_DATA_REGNO and the uses 304 relate to the registers specified in ED_USES. Logically these 305 defs and uses should really occur along the eh edge, but there is 306 no convenient way to do this. Artificial edges that occur at the 307 beginning of the block have the DF_REF_AT_TOP flag set. 308 309 Artificial uses occur at the end of all blocks. These arise from 310 the hard registers that are always live, such as the stack 311 register and are put there to keep the code from forgetting about 312 them. 313 314 Artificial defs occur at the end of the entry block. These arise 315 from registers that are live at entry to the function. 316 3172) There are three types of refs: defs, uses and eq_uses. (Eq_uses are 318 uses that appear inside a REG_EQUAL or REG_EQUIV note.) 319 320 All of the eq_uses, uses and defs associated with each pseudo or 321 hard register may be linked in a bidirectional chain. These are 322 called reg-use or reg_def chains. If the changeable flag 323 DF_EQ_NOTES is set when the chains are built, the eq_uses will be 324 treated like uses. If it is not set they are ignored. 325 326 The first use, eq_use or def for a register can be obtained using 327 the DF_REG_USE_CHAIN, DF_REG_EQ_USE_CHAIN or DF_REG_DEF_CHAIN 328 macros. Subsequent uses for the same regno can be obtained by 329 following the next_reg field of the ref. The number of elements in 330 each of the chains can be found by using the DF_REG_USE_COUNT, 331 DF_REG_EQ_USE_COUNT or DF_REG_DEF_COUNT macros. 332 333 In previous versions of this code, these chains were ordered. It 334 has not been practical to continue this practice. 335 3363) If def-use or use-def chains are built, these can be traversed to 337 get to other refs. If the flag DF_EQ_NOTES has been set, the chains 338 include the eq_uses. Otherwise these are ignored when building the 339 chains. 340 3414) An array of all of the uses (and an array of all of the defs) can 342 be built. These arrays are indexed by the value in the id 343 structure. These arrays are only lazily kept up to date, and that 344 process can be expensive. To have these arrays built, call 345 df_reorganize_defs or df_reorganize_uses. If the flag DF_EQ_NOTES 346 has been set the array will contain the eq_uses. Otherwise these 347 are ignored when building the array and assigning the ids. Note 348 that the values in the id field of a ref may change across calls to 349 df_analyze or df_reorganize_defs or df_reorganize_uses. 350 351 If the only use of this array is to find all of the refs, it is 352 better to traverse all of the registers and then traverse all of 353 reg-use or reg-def chains. 354 355NOTES: 356 357Embedded addressing side-effects, such as POST_INC or PRE_INC, generate 358both a use and a def. These are both marked read/write to show that they 359are dependent. For example, (set (reg 40) (mem (post_inc (reg 42)))) 360will generate a use of reg 42 followed by a def of reg 42 (both marked 361read/write). Similarly, (set (reg 40) (mem (pre_dec (reg 41)))) 362generates a use of reg 41 then a def of reg 41 (both marked read/write), 363even though reg 41 is decremented before it is used for the memory 364address in this second example. 365 366A set to a REG inside a ZERO_EXTRACT, or a set to a non-paradoxical SUBREG 367for which the number of word_mode units covered by the outer mode is 368smaller than that covered by the inner mode, invokes a read-modify-write 369operation. We generate both a use and a def and again mark them 370read/write. 371 372Paradoxical subreg writes do not leave a trace of the old content, so they 373are write-only operations. 374*/ 375 376 377#include "config.h" 378#include "system.h" 379#include "coretypes.h" 380#include "tm.h" 381#include "rtl.h" 382#include "tm_p.h" 383#include "insn-config.h" 384#include "recog.h" 385#include "function.h" 386#include "regs.h" 387#include "alloc-pool.h" 388#include "flags.h" 389#include "hard-reg-set.h" 390#include "basic-block.h" 391#include "sbitmap.h" 392#include "bitmap.h" 393#include "df.h" 394#include "tree-pass.h" 395#include "params.h" 396 397static void *df_get_bb_info (struct dataflow *, unsigned int); 398static void df_set_bb_info (struct dataflow *, unsigned int, void *); 399static void df_clear_bb_info (struct dataflow *, unsigned int); 400#ifdef DF_DEBUG_CFG 401static void df_set_clean_cfg (void); 402#endif 403 404/* The obstack on which regsets are allocated. */ 405struct bitmap_obstack reg_obstack; 406 407/* An obstack for bitmap not related to specific dataflow problems. 408 This obstack should e.g. be used for bitmaps with a short life time 409 such as temporary bitmaps. */ 410 411bitmap_obstack df_bitmap_obstack; 412 413 414/*---------------------------------------------------------------------------- 415 Functions to create, destroy and manipulate an instance of df. 416----------------------------------------------------------------------------*/ 417 418struct df_d *df; 419 420/* Add PROBLEM (and any dependent problems) to the DF instance. */ 421 422void 423df_add_problem (struct df_problem *problem) 424{ 425 struct dataflow *dflow; 426 int i; 427 428 /* First try to add the dependent problem. */ 429 if (problem->dependent_problem) 430 df_add_problem (problem->dependent_problem); 431 432 /* Check to see if this problem has already been defined. If it 433 has, just return that instance, if not, add it to the end of the 434 vector. */ 435 dflow = df->problems_by_index[problem->id]; 436 if (dflow) 437 return; 438 439 /* Make a new one and add it to the end. */ 440 dflow = XCNEW (struct dataflow); 441 dflow->problem = problem; 442 dflow->computed = false; 443 dflow->solutions_dirty = true; 444 df->problems_by_index[dflow->problem->id] = dflow; 445 446 /* Keep the defined problems ordered by index. This solves the 447 problem that RI will use the information from UREC if UREC has 448 been defined, or from LIVE if LIVE is defined and otherwise LR. 449 However for this to work, the computation of RI must be pushed 450 after which ever of those problems is defined, but we do not 451 require any of those except for LR to have actually been 452 defined. */ 453 df->num_problems_defined++; 454 for (i = df->num_problems_defined - 2; i >= 0; i--) 455 { 456 if (problem->id < df->problems_in_order[i]->problem->id) 457 df->problems_in_order[i+1] = df->problems_in_order[i]; 458 else 459 { 460 df->problems_in_order[i+1] = dflow; 461 return; 462 } 463 } 464 df->problems_in_order[0] = dflow; 465} 466 467 468/* Set the MASK flags in the DFLOW problem. The old flags are 469 returned. If a flag is not allowed to be changed this will fail if 470 checking is enabled. */ 471int 472df_set_flags (int changeable_flags) 473{ 474 int old_flags = df->changeable_flags; 475 df->changeable_flags |= changeable_flags; 476 return old_flags; 477} 478 479 480/* Clear the MASK flags in the DFLOW problem. The old flags are 481 returned. If a flag is not allowed to be changed this will fail if 482 checking is enabled. */ 483int 484df_clear_flags (int changeable_flags) 485{ 486 int old_flags = df->changeable_flags; 487 df->changeable_flags &= ~changeable_flags; 488 return old_flags; 489} 490 491 492/* Set the blocks that are to be considered for analysis. If this is 493 not called or is called with null, the entire function in 494 analyzed. */ 495 496void 497df_set_blocks (bitmap blocks) 498{ 499 if (blocks) 500 { 501 if (dump_file) 502 bitmap_print (dump_file, blocks, "setting blocks to analyze ", "\n"); 503 if (df->blocks_to_analyze) 504 { 505 /* This block is called to change the focus from one subset 506 to another. */ 507 int p; 508 bitmap_head diff; 509 bitmap_initialize (&diff, &df_bitmap_obstack); 510 bitmap_and_compl (&diff, df->blocks_to_analyze, blocks); 511 for (p = 0; p < df->num_problems_defined; p++) 512 { 513 struct dataflow *dflow = df->problems_in_order[p]; 514 if (dflow->optional_p && dflow->problem->reset_fun) 515 dflow->problem->reset_fun (df->blocks_to_analyze); 516 else if (dflow->problem->free_blocks_on_set_blocks) 517 { 518 bitmap_iterator bi; 519 unsigned int bb_index; 520 521 EXECUTE_IF_SET_IN_BITMAP (&diff, 0, bb_index, bi) 522 { 523 basic_block bb = BASIC_BLOCK (bb_index); 524 if (bb) 525 { 526 void *bb_info = df_get_bb_info (dflow, bb_index); 527 dflow->problem->free_bb_fun (bb, bb_info); 528 df_clear_bb_info (dflow, bb_index); 529 } 530 } 531 } 532 } 533 534 bitmap_clear (&diff); 535 } 536 else 537 { 538 /* This block of code is executed to change the focus from 539 the entire function to a subset. */ 540 bitmap_head blocks_to_reset; 541 bool initialized = false; 542 int p; 543 for (p = 0; p < df->num_problems_defined; p++) 544 { 545 struct dataflow *dflow = df->problems_in_order[p]; 546 if (dflow->optional_p && dflow->problem->reset_fun) 547 { 548 if (!initialized) 549 { 550 basic_block bb; 551 bitmap_initialize (&blocks_to_reset, &df_bitmap_obstack); 552 FOR_ALL_BB(bb) 553 { 554 bitmap_set_bit (&blocks_to_reset, bb->index); 555 } 556 } 557 dflow->problem->reset_fun (&blocks_to_reset); 558 } 559 } 560 if (initialized) 561 bitmap_clear (&blocks_to_reset); 562 563 df->blocks_to_analyze = BITMAP_ALLOC (&df_bitmap_obstack); 564 } 565 bitmap_copy (df->blocks_to_analyze, blocks); 566 df->analyze_subset = true; 567 } 568 else 569 { 570 /* This block is executed to reset the focus to the entire 571 function. */ 572 if (dump_file) 573 fprintf (dump_file, "clearing blocks_to_analyze\n"); 574 if (df->blocks_to_analyze) 575 { 576 BITMAP_FREE (df->blocks_to_analyze); 577 df->blocks_to_analyze = NULL; 578 } 579 df->analyze_subset = false; 580 } 581 582 /* Setting the blocks causes the refs to be unorganized since only 583 the refs in the blocks are seen. */ 584 df_maybe_reorganize_def_refs (DF_REF_ORDER_NO_TABLE); 585 df_maybe_reorganize_use_refs (DF_REF_ORDER_NO_TABLE); 586 df_mark_solutions_dirty (); 587} 588 589 590/* Delete a DFLOW problem (and any problems that depend on this 591 problem). */ 592 593void 594df_remove_problem (struct dataflow *dflow) 595{ 596 struct df_problem *problem; 597 int i; 598 599 if (!dflow) 600 return; 601 602 problem = dflow->problem; 603 gcc_assert (problem->remove_problem_fun); 604 605 /* Delete any problems that depended on this problem first. */ 606 for (i = 0; i < df->num_problems_defined; i++) 607 if (df->problems_in_order[i]->problem->dependent_problem == problem) 608 df_remove_problem (df->problems_in_order[i]); 609 610 /* Now remove this problem. */ 611 for (i = 0; i < df->num_problems_defined; i++) 612 if (df->problems_in_order[i] == dflow) 613 { 614 int j; 615 for (j = i + 1; j < df->num_problems_defined; j++) 616 df->problems_in_order[j-1] = df->problems_in_order[j]; 617 df->problems_in_order[j-1] = NULL; 618 df->num_problems_defined--; 619 break; 620 } 621 622 (problem->remove_problem_fun) (); 623 df->problems_by_index[problem->id] = NULL; 624} 625 626 627/* Remove all of the problems that are not permanent. Scanning, LR 628 and (at -O2 or higher) LIVE are permanent, the rest are removable. 629 Also clear all of the changeable_flags. */ 630 631void 632df_finish_pass (bool verify ATTRIBUTE_UNUSED) 633{ 634 int i; 635 int removed = 0; 636 637#ifdef ENABLE_DF_CHECKING 638 int saved_flags; 639#endif 640 641 if (!df) 642 return; 643 644 df_maybe_reorganize_def_refs (DF_REF_ORDER_NO_TABLE); 645 df_maybe_reorganize_use_refs (DF_REF_ORDER_NO_TABLE); 646 647#ifdef ENABLE_DF_CHECKING 648 saved_flags = df->changeable_flags; 649#endif 650 651 for (i = 0; i < df->num_problems_defined; i++) 652 { 653 struct dataflow *dflow = df->problems_in_order[i]; 654 struct df_problem *problem = dflow->problem; 655 656 if (dflow->optional_p) 657 { 658 gcc_assert (problem->remove_problem_fun); 659 (problem->remove_problem_fun) (); 660 df->problems_in_order[i] = NULL; 661 df->problems_by_index[problem->id] = NULL; 662 removed++; 663 } 664 } 665 df->num_problems_defined -= removed; 666 667 /* Clear all of the flags. */ 668 df->changeable_flags = 0; 669 df_process_deferred_rescans (); 670 671 /* Set the focus back to the whole function. */ 672 if (df->blocks_to_analyze) 673 { 674 BITMAP_FREE (df->blocks_to_analyze); 675 df->blocks_to_analyze = NULL; 676 df_mark_solutions_dirty (); 677 df->analyze_subset = false; 678 } 679 680#ifdef ENABLE_DF_CHECKING 681 /* Verification will fail in DF_NO_INSN_RESCAN. */ 682 if (!(saved_flags & DF_NO_INSN_RESCAN)) 683 { 684 df_lr_verify_transfer_functions (); 685 if (df_live) 686 df_live_verify_transfer_functions (); 687 } 688 689#ifdef DF_DEBUG_CFG 690 df_set_clean_cfg (); 691#endif 692#endif 693 694#ifdef ENABLE_CHECKING 695 if (verify) 696 df->changeable_flags |= DF_VERIFY_SCHEDULED; 697#endif 698} 699 700 701/* Set up the dataflow instance for the entire back end. */ 702 703static unsigned int 704rest_of_handle_df_initialize (void) 705{ 706 gcc_assert (!df); 707 df = XCNEW (struct df_d); 708 df->changeable_flags = 0; 709 710 bitmap_obstack_initialize (&df_bitmap_obstack); 711 712 /* Set this to a conservative value. Stack_ptr_mod will compute it 713 correctly later. */ 714 crtl->sp_is_unchanging = 0; 715 716 df_scan_add_problem (); 717 df_scan_alloc (NULL); 718 719 /* These three problems are permanent. */ 720 df_lr_add_problem (); 721 if (optimize > 1) 722 df_live_add_problem (); 723 724 df->postorder = XNEWVEC (int, last_basic_block); 725 df->postorder_inverted = XNEWVEC (int, last_basic_block); 726 df->n_blocks = post_order_compute (df->postorder, true, true); 727 df->n_blocks_inverted = inverted_post_order_compute (df->postorder_inverted); 728 gcc_assert (df->n_blocks == df->n_blocks_inverted); 729 730 df->hard_regs_live_count = XNEWVEC (unsigned int, FIRST_PSEUDO_REGISTER); 731 memset (df->hard_regs_live_count, 0, 732 sizeof (unsigned int) * FIRST_PSEUDO_REGISTER); 733 734 df_hard_reg_init (); 735 /* After reload, some ports add certain bits to regs_ever_live so 736 this cannot be reset. */ 737 df_compute_regs_ever_live (true); 738 df_scan_blocks (); 739 df_compute_regs_ever_live (false); 740 return 0; 741} 742 743 744static bool 745gate_opt (void) 746{ 747 return optimize > 0; 748} 749 750 751struct rtl_opt_pass pass_df_initialize_opt = 752{ 753 { 754 RTL_PASS, 755 "dfinit", /* name */ 756 OPTGROUP_NONE, /* optinfo_flags */ 757 gate_opt, /* gate */ 758 rest_of_handle_df_initialize, /* execute */ 759 NULL, /* sub */ 760 NULL, /* next */ 761 0, /* static_pass_number */ 762 TV_DF_SCAN, /* tv_id */ 763 0, /* properties_required */ 764 0, /* properties_provided */ 765 0, /* properties_destroyed */ 766 0, /* todo_flags_start */ 767 0 /* todo_flags_finish */ 768 } 769}; 770 771 772static bool 773gate_no_opt (void) 774{ 775 return optimize == 0; 776} 777 778 779struct rtl_opt_pass pass_df_initialize_no_opt = 780{ 781 { 782 RTL_PASS, 783 "no-opt dfinit", /* name */ 784 OPTGROUP_NONE, /* optinfo_flags */ 785 gate_no_opt, /* gate */ 786 rest_of_handle_df_initialize, /* execute */ 787 NULL, /* sub */ 788 NULL, /* next */ 789 0, /* static_pass_number */ 790 TV_DF_SCAN, /* tv_id */ 791 0, /* properties_required */ 792 0, /* properties_provided */ 793 0, /* properties_destroyed */ 794 0, /* todo_flags_start */ 795 0 /* todo_flags_finish */ 796 } 797}; 798 799 800/* Free all the dataflow info and the DF structure. This should be 801 called from the df_finish macro which also NULLs the parm. */ 802 803static unsigned int 804rest_of_handle_df_finish (void) 805{ 806 int i; 807 808 gcc_assert (df); 809 810 for (i = 0; i < df->num_problems_defined; i++) 811 { 812 struct dataflow *dflow = df->problems_in_order[i]; 813 dflow->problem->free_fun (); 814 } 815 816 free (df->postorder); 817 free (df->postorder_inverted); 818 free (df->hard_regs_live_count); 819 free (df); 820 df = NULL; 821 822 bitmap_obstack_release (&df_bitmap_obstack); 823 return 0; 824} 825 826 827struct rtl_opt_pass pass_df_finish = 828{ 829 { 830 RTL_PASS, 831 "dfinish", /* name */ 832 OPTGROUP_NONE, /* optinfo_flags */ 833 NULL, /* gate */ 834 rest_of_handle_df_finish, /* execute */ 835 NULL, /* sub */ 836 NULL, /* next */ 837 0, /* static_pass_number */ 838 TV_NONE, /* tv_id */ 839 0, /* properties_required */ 840 0, /* properties_provided */ 841 0, /* properties_destroyed */ 842 0, /* todo_flags_start */ 843 0 /* todo_flags_finish */ 844 } 845}; 846 847 848 849 850 851/*---------------------------------------------------------------------------- 852 The general data flow analysis engine. 853----------------------------------------------------------------------------*/ 854 855/* Return time BB when it was visited for last time. */ 856#define BB_LAST_CHANGE_AGE(bb) ((ptrdiff_t)(bb)->aux) 857 858/* Helper function for df_worklist_dataflow. 859 Propagate the dataflow forward. 860 Given a BB_INDEX, do the dataflow propagation 861 and set bits on for successors in PENDING 862 if the out set of the dataflow has changed. 863 864 AGE specify time when BB was visited last time. 865 AGE of 0 means we are visiting for first time and need to 866 compute transfer function to initialize datastructures. 867 Otherwise we re-do transfer function only if something change 868 while computing confluence functions. 869 We need to compute confluence only of basic block that are younger 870 then last visit of the BB. 871 872 Return true if BB info has changed. This is always the case 873 in the first visit. */ 874 875static bool 876df_worklist_propagate_forward (struct dataflow *dataflow, 877 unsigned bb_index, 878 unsigned *bbindex_to_postorder, 879 bitmap pending, 880 sbitmap considered, 881 ptrdiff_t age) 882{ 883 edge e; 884 edge_iterator ei; 885 basic_block bb = BASIC_BLOCK (bb_index); 886 bool changed = !age; 887 888 /* Calculate <conf_op> of incoming edges. */ 889 if (EDGE_COUNT (bb->preds) > 0) 890 FOR_EACH_EDGE (e, ei, bb->preds) 891 { 892 if (age <= BB_LAST_CHANGE_AGE (e->src) 893 && bitmap_bit_p (considered, e->src->index)) 894 changed |= dataflow->problem->con_fun_n (e); 895 } 896 else if (dataflow->problem->con_fun_0) 897 dataflow->problem->con_fun_0 (bb); 898 899 if (changed 900 && dataflow->problem->trans_fun (bb_index)) 901 { 902 /* The out set of this block has changed. 903 Propagate to the outgoing blocks. */ 904 FOR_EACH_EDGE (e, ei, bb->succs) 905 { 906 unsigned ob_index = e->dest->index; 907 908 if (bitmap_bit_p (considered, ob_index)) 909 bitmap_set_bit (pending, bbindex_to_postorder[ob_index]); 910 } 911 return true; 912 } 913 return false; 914} 915 916 917/* Helper function for df_worklist_dataflow. 918 Propagate the dataflow backward. */ 919 920static bool 921df_worklist_propagate_backward (struct dataflow *dataflow, 922 unsigned bb_index, 923 unsigned *bbindex_to_postorder, 924 bitmap pending, 925 sbitmap considered, 926 ptrdiff_t age) 927{ 928 edge e; 929 edge_iterator ei; 930 basic_block bb = BASIC_BLOCK (bb_index); 931 bool changed = !age; 932 933 /* Calculate <conf_op> of incoming edges. */ 934 if (EDGE_COUNT (bb->succs) > 0) 935 FOR_EACH_EDGE (e, ei, bb->succs) 936 { 937 if (age <= BB_LAST_CHANGE_AGE (e->dest) 938 && bitmap_bit_p (considered, e->dest->index)) 939 changed |= dataflow->problem->con_fun_n (e); 940 } 941 else if (dataflow->problem->con_fun_0) 942 dataflow->problem->con_fun_0 (bb); 943 944 if (changed 945 && dataflow->problem->trans_fun (bb_index)) 946 { 947 /* The out set of this block has changed. 948 Propagate to the outgoing blocks. */ 949 FOR_EACH_EDGE (e, ei, bb->preds) 950 { 951 unsigned ob_index = e->src->index; 952 953 if (bitmap_bit_p (considered, ob_index)) 954 bitmap_set_bit (pending, bbindex_to_postorder[ob_index]); 955 } 956 return true; 957 } 958 return false; 959} 960 961/* Main dataflow solver loop. 962 963 DATAFLOW is problem we are solving, PENDING is worklist of basic blocks we 964 need to visit. 965 BLOCK_IN_POSTORDER is array of size N_BLOCKS specifying postorder in BBs and 966 BBINDEX_TO_POSTORDER is array mapping back BB->index to postorder possition. 967 PENDING will be freed. 968 969 The worklists are bitmaps indexed by postorder positions. 970 971 The function implements standard algorithm for dataflow solving with two 972 worklists (we are processing WORKLIST and storing new BBs to visit in 973 PENDING). 974 975 As an optimization we maintain ages when BB was changed (stored in bb->aux) 976 and when it was last visited (stored in last_visit_age). This avoids need 977 to re-do confluence function for edges to basic blocks whose source 978 did not change since destination was visited last time. */ 979 980static void 981df_worklist_dataflow_doublequeue (struct dataflow *dataflow, 982 bitmap pending, 983 sbitmap considered, 984 int *blocks_in_postorder, 985 unsigned *bbindex_to_postorder, 986 int n_blocks) 987{ 988 enum df_flow_dir dir = dataflow->problem->dir; 989 int dcount = 0; 990 bitmap worklist = BITMAP_ALLOC (&df_bitmap_obstack); 991 int age = 0; 992 bool changed; 993 vec<int> last_visit_age = vNULL; 994 int prev_age; 995 basic_block bb; 996 int i; 997 998 last_visit_age.safe_grow_cleared (n_blocks); 999 1000 /* Double-queueing. Worklist is for the current iteration, 1001 and pending is for the next. */ 1002 while (!bitmap_empty_p (pending)) 1003 { 1004 bitmap_iterator bi; 1005 unsigned int index; 1006 1007 /* Swap pending and worklist. */ 1008 bitmap temp = worklist; 1009 worklist = pending; 1010 pending = temp; 1011 1012 EXECUTE_IF_SET_IN_BITMAP (worklist, 0, index, bi) 1013 { 1014 unsigned bb_index; 1015 dcount++; 1016 1017 bitmap_clear_bit (pending, index); 1018 bb_index = blocks_in_postorder[index]; 1019 bb = BASIC_BLOCK (bb_index); 1020 prev_age = last_visit_age[index]; 1021 if (dir == DF_FORWARD) 1022 changed = df_worklist_propagate_forward (dataflow, bb_index, 1023 bbindex_to_postorder, 1024 pending, considered, 1025 prev_age); 1026 else 1027 changed = df_worklist_propagate_backward (dataflow, bb_index, 1028 bbindex_to_postorder, 1029 pending, considered, 1030 prev_age); 1031 last_visit_age[index] = ++age; 1032 if (changed) 1033 bb->aux = (void *)(ptrdiff_t)age; 1034 } 1035 bitmap_clear (worklist); 1036 } 1037 for (i = 0; i < n_blocks; i++) 1038 BASIC_BLOCK (blocks_in_postorder[i])->aux = NULL; 1039 1040 BITMAP_FREE (worklist); 1041 BITMAP_FREE (pending); 1042 last_visit_age.release (); 1043 1044 /* Dump statistics. */ 1045 if (dump_file) 1046 fprintf (dump_file, "df_worklist_dataflow_doublequeue:" 1047 "n_basic_blocks %d n_edges %d" 1048 " count %d (%5.2g)\n", 1049 n_basic_blocks, n_edges, 1050 dcount, dcount / (float)n_basic_blocks); 1051} 1052 1053/* Worklist-based dataflow solver. It uses sbitmap as a worklist, 1054 with "n"-th bit representing the n-th block in the reverse-postorder order. 1055 The solver is a double-queue algorithm similar to the "double stack" solver 1056 from Cooper, Harvey and Kennedy, "Iterative data-flow analysis, Revisited". 1057 The only significant difference is that the worklist in this implementation 1058 is always sorted in RPO of the CFG visiting direction. */ 1059 1060void 1061df_worklist_dataflow (struct dataflow *dataflow, 1062 bitmap blocks_to_consider, 1063 int *blocks_in_postorder, 1064 int n_blocks) 1065{ 1066 bitmap pending = BITMAP_ALLOC (&df_bitmap_obstack); 1067 sbitmap considered = sbitmap_alloc (last_basic_block); 1068 bitmap_iterator bi; 1069 unsigned int *bbindex_to_postorder; 1070 int i; 1071 unsigned int index; 1072 enum df_flow_dir dir = dataflow->problem->dir; 1073 1074 gcc_assert (dir != DF_NONE); 1075 1076 /* BBINDEX_TO_POSTORDER maps the bb->index to the reverse postorder. */ 1077 bbindex_to_postorder = 1078 (unsigned int *)xmalloc (last_basic_block * sizeof (unsigned int)); 1079 1080 /* Initialize the array to an out-of-bound value. */ 1081 for (i = 0; i < last_basic_block; i++) 1082 bbindex_to_postorder[i] = last_basic_block; 1083 1084 /* Initialize the considered map. */ 1085 bitmap_clear (considered); 1086 EXECUTE_IF_SET_IN_BITMAP (blocks_to_consider, 0, index, bi) 1087 { 1088 bitmap_set_bit (considered, index); 1089 } 1090 1091 /* Initialize the mapping of block index to postorder. */ 1092 for (i = 0; i < n_blocks; i++) 1093 { 1094 bbindex_to_postorder[blocks_in_postorder[i]] = i; 1095 /* Add all blocks to the worklist. */ 1096 bitmap_set_bit (pending, i); 1097 } 1098 1099 /* Initialize the problem. */ 1100 if (dataflow->problem->init_fun) 1101 dataflow->problem->init_fun (blocks_to_consider); 1102 1103 /* Solve it. */ 1104 df_worklist_dataflow_doublequeue (dataflow, pending, considered, 1105 blocks_in_postorder, 1106 bbindex_to_postorder, 1107 n_blocks); 1108 sbitmap_free (considered); 1109 free (bbindex_to_postorder); 1110} 1111 1112 1113/* Remove the entries not in BLOCKS from the LIST of length LEN, preserving 1114 the order of the remaining entries. Returns the length of the resulting 1115 list. */ 1116 1117static unsigned 1118df_prune_to_subcfg (int list[], unsigned len, bitmap blocks) 1119{ 1120 unsigned act, last; 1121 1122 for (act = 0, last = 0; act < len; act++) 1123 if (bitmap_bit_p (blocks, list[act])) 1124 list[last++] = list[act]; 1125 1126 return last; 1127} 1128 1129 1130/* Execute dataflow analysis on a single dataflow problem. 1131 1132 BLOCKS_TO_CONSIDER are the blocks whose solution can either be 1133 examined or will be computed. For calls from DF_ANALYZE, this is 1134 the set of blocks that has been passed to DF_SET_BLOCKS. 1135*/ 1136 1137void 1138df_analyze_problem (struct dataflow *dflow, 1139 bitmap blocks_to_consider, 1140 int *postorder, int n_blocks) 1141{ 1142 timevar_push (dflow->problem->tv_id); 1143 1144 /* (Re)Allocate the datastructures necessary to solve the problem. */ 1145 if (dflow->problem->alloc_fun) 1146 dflow->problem->alloc_fun (blocks_to_consider); 1147 1148#ifdef ENABLE_DF_CHECKING 1149 if (dflow->problem->verify_start_fun) 1150 dflow->problem->verify_start_fun (); 1151#endif 1152 1153 /* Set up the problem and compute the local information. */ 1154 if (dflow->problem->local_compute_fun) 1155 dflow->problem->local_compute_fun (blocks_to_consider); 1156 1157 /* Solve the equations. */ 1158 if (dflow->problem->dataflow_fun) 1159 dflow->problem->dataflow_fun (dflow, blocks_to_consider, 1160 postorder, n_blocks); 1161 1162 /* Massage the solution. */ 1163 if (dflow->problem->finalize_fun) 1164 dflow->problem->finalize_fun (blocks_to_consider); 1165 1166#ifdef ENABLE_DF_CHECKING 1167 if (dflow->problem->verify_end_fun) 1168 dflow->problem->verify_end_fun (); 1169#endif 1170 1171 timevar_pop (dflow->problem->tv_id); 1172 1173 dflow->computed = true; 1174} 1175 1176 1177/* Analyze dataflow info for the basic blocks specified by the bitmap 1178 BLOCKS, or for the whole CFG if BLOCKS is zero. */ 1179 1180void 1181df_analyze (void) 1182{ 1183 bitmap current_all_blocks = BITMAP_ALLOC (&df_bitmap_obstack); 1184 bool everything; 1185 int i; 1186 1187 free (df->postorder); 1188 free (df->postorder_inverted); 1189 df->postorder = XNEWVEC (int, last_basic_block); 1190 df->postorder_inverted = XNEWVEC (int, last_basic_block); 1191 df->n_blocks = post_order_compute (df->postorder, true, true); 1192 df->n_blocks_inverted = inverted_post_order_compute (df->postorder_inverted); 1193 1194 /* These should be the same. */ 1195 gcc_assert (df->n_blocks == df->n_blocks_inverted); 1196 1197 /* We need to do this before the df_verify_all because this is 1198 not kept incrementally up to date. */ 1199 df_compute_regs_ever_live (false); 1200 df_process_deferred_rescans (); 1201 1202 if (dump_file) 1203 fprintf (dump_file, "df_analyze called\n"); 1204 1205#ifndef ENABLE_DF_CHECKING 1206 if (df->changeable_flags & DF_VERIFY_SCHEDULED) 1207#endif 1208 df_verify (); 1209 1210 for (i = 0; i < df->n_blocks; i++) 1211 bitmap_set_bit (current_all_blocks, df->postorder[i]); 1212 1213#ifdef ENABLE_CHECKING 1214 /* Verify that POSTORDER_INVERTED only contains blocks reachable from 1215 the ENTRY block. */ 1216 for (i = 0; i < df->n_blocks_inverted; i++) 1217 gcc_assert (bitmap_bit_p (current_all_blocks, df->postorder_inverted[i])); 1218#endif 1219 1220 /* Make sure that we have pruned any unreachable blocks from these 1221 sets. */ 1222 if (df->analyze_subset) 1223 { 1224 everything = false; 1225 bitmap_and_into (df->blocks_to_analyze, current_all_blocks); 1226 df->n_blocks = df_prune_to_subcfg (df->postorder, 1227 df->n_blocks, df->blocks_to_analyze); 1228 df->n_blocks_inverted = df_prune_to_subcfg (df->postorder_inverted, 1229 df->n_blocks_inverted, 1230 df->blocks_to_analyze); 1231 BITMAP_FREE (current_all_blocks); 1232 } 1233 else 1234 { 1235 everything = true; 1236 df->blocks_to_analyze = current_all_blocks; 1237 current_all_blocks = NULL; 1238 } 1239 1240 /* Skip over the DF_SCAN problem. */ 1241 for (i = 1; i < df->num_problems_defined; i++) 1242 { 1243 struct dataflow *dflow = df->problems_in_order[i]; 1244 if (dflow->solutions_dirty) 1245 { 1246 if (dflow->problem->dir == DF_FORWARD) 1247 df_analyze_problem (dflow, 1248 df->blocks_to_analyze, 1249 df->postorder_inverted, 1250 df->n_blocks_inverted); 1251 else 1252 df_analyze_problem (dflow, 1253 df->blocks_to_analyze, 1254 df->postorder, 1255 df->n_blocks); 1256 } 1257 } 1258 1259 if (everything) 1260 { 1261 BITMAP_FREE (df->blocks_to_analyze); 1262 df->blocks_to_analyze = NULL; 1263 } 1264 1265#ifdef DF_DEBUG_CFG 1266 df_set_clean_cfg (); 1267#endif 1268} 1269 1270 1271/* Return the number of basic blocks from the last call to df_analyze. */ 1272 1273int 1274df_get_n_blocks (enum df_flow_dir dir) 1275{ 1276 gcc_assert (dir != DF_NONE); 1277 1278 if (dir == DF_FORWARD) 1279 { 1280 gcc_assert (df->postorder_inverted); 1281 return df->n_blocks_inverted; 1282 } 1283 1284 gcc_assert (df->postorder); 1285 return df->n_blocks; 1286} 1287 1288 1289/* Return a pointer to the array of basic blocks in the reverse postorder. 1290 Depending on the direction of the dataflow problem, 1291 it returns either the usual reverse postorder array 1292 or the reverse postorder of inverted traversal. */ 1293int * 1294df_get_postorder (enum df_flow_dir dir) 1295{ 1296 gcc_assert (dir != DF_NONE); 1297 1298 if (dir == DF_FORWARD) 1299 { 1300 gcc_assert (df->postorder_inverted); 1301 return df->postorder_inverted; 1302 } 1303 gcc_assert (df->postorder); 1304 return df->postorder; 1305} 1306 1307static struct df_problem user_problem; 1308static struct dataflow user_dflow; 1309 1310/* Interface for calling iterative dataflow with user defined 1311 confluence and transfer functions. All that is necessary is to 1312 supply DIR, a direction, CONF_FUN_0, a confluence function for 1313 blocks with no logical preds (or NULL), CONF_FUN_N, the normal 1314 confluence function, TRANS_FUN, the basic block transfer function, 1315 and BLOCKS, the set of blocks to examine, POSTORDER the blocks in 1316 postorder, and N_BLOCKS, the number of blocks in POSTORDER. */ 1317 1318void 1319df_simple_dataflow (enum df_flow_dir dir, 1320 df_init_function init_fun, 1321 df_confluence_function_0 con_fun_0, 1322 df_confluence_function_n con_fun_n, 1323 df_transfer_function trans_fun, 1324 bitmap blocks, int * postorder, int n_blocks) 1325{ 1326 memset (&user_problem, 0, sizeof (struct df_problem)); 1327 user_problem.dir = dir; 1328 user_problem.init_fun = init_fun; 1329 user_problem.con_fun_0 = con_fun_0; 1330 user_problem.con_fun_n = con_fun_n; 1331 user_problem.trans_fun = trans_fun; 1332 user_dflow.problem = &user_problem; 1333 df_worklist_dataflow (&user_dflow, blocks, postorder, n_blocks); 1334} 1335 1336 1337 1338/*---------------------------------------------------------------------------- 1339 Functions to support limited incremental change. 1340----------------------------------------------------------------------------*/ 1341 1342 1343/* Get basic block info. */ 1344 1345static void * 1346df_get_bb_info (struct dataflow *dflow, unsigned int index) 1347{ 1348 if (dflow->block_info == NULL) 1349 return NULL; 1350 if (index >= dflow->block_info_size) 1351 return NULL; 1352 return (void *)((char *)dflow->block_info 1353 + index * dflow->problem->block_info_elt_size); 1354} 1355 1356 1357/* Set basic block info. */ 1358 1359static void 1360df_set_bb_info (struct dataflow *dflow, unsigned int index, 1361 void *bb_info) 1362{ 1363 gcc_assert (dflow->block_info); 1364 memcpy ((char *)dflow->block_info 1365 + index * dflow->problem->block_info_elt_size, 1366 bb_info, dflow->problem->block_info_elt_size); 1367} 1368 1369 1370/* Clear basic block info. */ 1371 1372static void 1373df_clear_bb_info (struct dataflow *dflow, unsigned int index) 1374{ 1375 gcc_assert (dflow->block_info); 1376 gcc_assert (dflow->block_info_size > index); 1377 memset ((char *)dflow->block_info 1378 + index * dflow->problem->block_info_elt_size, 1379 0, dflow->problem->block_info_elt_size); 1380} 1381 1382 1383/* Mark the solutions as being out of date. */ 1384 1385void 1386df_mark_solutions_dirty (void) 1387{ 1388 if (df) 1389 { 1390 int p; 1391 for (p = 1; p < df->num_problems_defined; p++) 1392 df->problems_in_order[p]->solutions_dirty = true; 1393 } 1394} 1395 1396 1397/* Return true if BB needs it's transfer functions recomputed. */ 1398 1399bool 1400df_get_bb_dirty (basic_block bb) 1401{ 1402 return bitmap_bit_p ((df_live 1403 ? df_live : df_lr)->out_of_date_transfer_functions, 1404 bb->index); 1405} 1406 1407 1408/* Mark BB as needing it's transfer functions as being out of 1409 date. */ 1410 1411void 1412df_set_bb_dirty (basic_block bb) 1413{ 1414 bb->flags |= BB_MODIFIED; 1415 if (df) 1416 { 1417 int p; 1418 for (p = 1; p < df->num_problems_defined; p++) 1419 { 1420 struct dataflow *dflow = df->problems_in_order[p]; 1421 if (dflow->out_of_date_transfer_functions) 1422 bitmap_set_bit (dflow->out_of_date_transfer_functions, bb->index); 1423 } 1424 df_mark_solutions_dirty (); 1425 } 1426} 1427 1428 1429/* Grow the bb_info array. */ 1430 1431void 1432df_grow_bb_info (struct dataflow *dflow) 1433{ 1434 unsigned int new_size = last_basic_block + 1; 1435 if (dflow->block_info_size < new_size) 1436 { 1437 new_size += new_size / 4; 1438 dflow->block_info 1439 = (void *)XRESIZEVEC (char, (char *)dflow->block_info, 1440 new_size 1441 * dflow->problem->block_info_elt_size); 1442 memset ((char *)dflow->block_info 1443 + dflow->block_info_size 1444 * dflow->problem->block_info_elt_size, 1445 0, 1446 (new_size - dflow->block_info_size) 1447 * dflow->problem->block_info_elt_size); 1448 dflow->block_info_size = new_size; 1449 } 1450} 1451 1452 1453/* Clear the dirty bits. This is called from places that delete 1454 blocks. */ 1455static void 1456df_clear_bb_dirty (basic_block bb) 1457{ 1458 int p; 1459 for (p = 1; p < df->num_problems_defined; p++) 1460 { 1461 struct dataflow *dflow = df->problems_in_order[p]; 1462 if (dflow->out_of_date_transfer_functions) 1463 bitmap_clear_bit (dflow->out_of_date_transfer_functions, bb->index); 1464 } 1465} 1466 1467/* Called from the rtl_compact_blocks to reorganize the problems basic 1468 block info. */ 1469 1470void 1471df_compact_blocks (void) 1472{ 1473 int i, p; 1474 basic_block bb; 1475 void *problem_temps; 1476 bitmap_head tmp; 1477 1478 bitmap_initialize (&tmp, &df_bitmap_obstack); 1479 for (p = 0; p < df->num_problems_defined; p++) 1480 { 1481 struct dataflow *dflow = df->problems_in_order[p]; 1482 1483 /* Need to reorganize the out_of_date_transfer_functions for the 1484 dflow problem. */ 1485 if (dflow->out_of_date_transfer_functions) 1486 { 1487 bitmap_copy (&tmp, dflow->out_of_date_transfer_functions); 1488 bitmap_clear (dflow->out_of_date_transfer_functions); 1489 if (bitmap_bit_p (&tmp, ENTRY_BLOCK)) 1490 bitmap_set_bit (dflow->out_of_date_transfer_functions, ENTRY_BLOCK); 1491 if (bitmap_bit_p (&tmp, EXIT_BLOCK)) 1492 bitmap_set_bit (dflow->out_of_date_transfer_functions, EXIT_BLOCK); 1493 1494 i = NUM_FIXED_BLOCKS; 1495 FOR_EACH_BB (bb) 1496 { 1497 if (bitmap_bit_p (&tmp, bb->index)) 1498 bitmap_set_bit (dflow->out_of_date_transfer_functions, i); 1499 i++; 1500 } 1501 } 1502 1503 /* Now shuffle the block info for the problem. */ 1504 if (dflow->problem->free_bb_fun) 1505 { 1506 int size = last_basic_block * dflow->problem->block_info_elt_size; 1507 problem_temps = XNEWVAR (char, size); 1508 df_grow_bb_info (dflow); 1509 memcpy (problem_temps, dflow->block_info, size); 1510 1511 /* Copy the bb info from the problem tmps to the proper 1512 place in the block_info vector. Null out the copied 1513 item. The entry and exit blocks never move. */ 1514 i = NUM_FIXED_BLOCKS; 1515 FOR_EACH_BB (bb) 1516 { 1517 df_set_bb_info (dflow, i, 1518 (char *)problem_temps 1519 + bb->index * dflow->problem->block_info_elt_size); 1520 i++; 1521 } 1522 memset ((char *)dflow->block_info 1523 + i * dflow->problem->block_info_elt_size, 0, 1524 (last_basic_block - i) 1525 * dflow->problem->block_info_elt_size); 1526 free (problem_temps); 1527 } 1528 } 1529 1530 /* Shuffle the bits in the basic_block indexed arrays. */ 1531 1532 if (df->blocks_to_analyze) 1533 { 1534 if (bitmap_bit_p (&tmp, ENTRY_BLOCK)) 1535 bitmap_set_bit (df->blocks_to_analyze, ENTRY_BLOCK); 1536 if (bitmap_bit_p (&tmp, EXIT_BLOCK)) 1537 bitmap_set_bit (df->blocks_to_analyze, EXIT_BLOCK); 1538 bitmap_copy (&tmp, df->blocks_to_analyze); 1539 bitmap_clear (df->blocks_to_analyze); 1540 i = NUM_FIXED_BLOCKS; 1541 FOR_EACH_BB (bb) 1542 { 1543 if (bitmap_bit_p (&tmp, bb->index)) 1544 bitmap_set_bit (df->blocks_to_analyze, i); 1545 i++; 1546 } 1547 } 1548 1549 bitmap_clear (&tmp); 1550 1551 i = NUM_FIXED_BLOCKS; 1552 FOR_EACH_BB (bb) 1553 { 1554 SET_BASIC_BLOCK (i, bb); 1555 bb->index = i; 1556 i++; 1557 } 1558 1559 gcc_assert (i == n_basic_blocks); 1560 1561 for (; i < last_basic_block; i++) 1562 SET_BASIC_BLOCK (i, NULL); 1563 1564#ifdef DF_DEBUG_CFG 1565 if (!df_lr->solutions_dirty) 1566 df_set_clean_cfg (); 1567#endif 1568} 1569 1570 1571/* Shove NEW_BLOCK in at OLD_INDEX. Called from ifcvt to hack a 1572 block. There is no excuse for people to do this kind of thing. */ 1573 1574void 1575df_bb_replace (int old_index, basic_block new_block) 1576{ 1577 int new_block_index = new_block->index; 1578 int p; 1579 1580 if (dump_file) 1581 fprintf (dump_file, "shoving block %d into %d\n", new_block_index, old_index); 1582 1583 gcc_assert (df); 1584 gcc_assert (BASIC_BLOCK (old_index) == NULL); 1585 1586 for (p = 0; p < df->num_problems_defined; p++) 1587 { 1588 struct dataflow *dflow = df->problems_in_order[p]; 1589 if (dflow->block_info) 1590 { 1591 df_grow_bb_info (dflow); 1592 df_set_bb_info (dflow, old_index, 1593 df_get_bb_info (dflow, new_block_index)); 1594 } 1595 } 1596 1597 df_clear_bb_dirty (new_block); 1598 SET_BASIC_BLOCK (old_index, new_block); 1599 new_block->index = old_index; 1600 df_set_bb_dirty (BASIC_BLOCK (old_index)); 1601 SET_BASIC_BLOCK (new_block_index, NULL); 1602} 1603 1604 1605/* Free all of the per basic block dataflow from all of the problems. 1606 This is typically called before a basic block is deleted and the 1607 problem will be reanalyzed. */ 1608 1609void 1610df_bb_delete (int bb_index) 1611{ 1612 basic_block bb = BASIC_BLOCK (bb_index); 1613 int i; 1614 1615 if (!df) 1616 return; 1617 1618 for (i = 0; i < df->num_problems_defined; i++) 1619 { 1620 struct dataflow *dflow = df->problems_in_order[i]; 1621 if (dflow->problem->free_bb_fun) 1622 { 1623 void *bb_info = df_get_bb_info (dflow, bb_index); 1624 if (bb_info) 1625 { 1626 dflow->problem->free_bb_fun (bb, bb_info); 1627 df_clear_bb_info (dflow, bb_index); 1628 } 1629 } 1630 } 1631 df_clear_bb_dirty (bb); 1632 df_mark_solutions_dirty (); 1633} 1634 1635 1636/* Verify that there is a place for everything and everything is in 1637 its place. This is too expensive to run after every pass in the 1638 mainline. However this is an excellent debugging tool if the 1639 dataflow information is not being updated properly. You can just 1640 sprinkle calls in until you find the place that is changing an 1641 underlying structure without calling the proper updating 1642 routine. */ 1643 1644void 1645df_verify (void) 1646{ 1647 df_scan_verify (); 1648#ifdef ENABLE_DF_CHECKING 1649 df_lr_verify_transfer_functions (); 1650 if (df_live) 1651 df_live_verify_transfer_functions (); 1652#endif 1653} 1654 1655#ifdef DF_DEBUG_CFG 1656 1657/* Compute an array of ints that describes the cfg. This can be used 1658 to discover places where the cfg is modified by the appropriate 1659 calls have not been made to the keep df informed. The internals of 1660 this are unexciting, the key is that two instances of this can be 1661 compared to see if any changes have been made to the cfg. */ 1662 1663static int * 1664df_compute_cfg_image (void) 1665{ 1666 basic_block bb; 1667 int size = 2 + (2 * n_basic_blocks); 1668 int i; 1669 int * map; 1670 1671 FOR_ALL_BB (bb) 1672 { 1673 size += EDGE_COUNT (bb->succs); 1674 } 1675 1676 map = XNEWVEC (int, size); 1677 map[0] = size; 1678 i = 1; 1679 FOR_ALL_BB (bb) 1680 { 1681 edge_iterator ei; 1682 edge e; 1683 1684 map[i++] = bb->index; 1685 FOR_EACH_EDGE (e, ei, bb->succs) 1686 map[i++] = e->dest->index; 1687 map[i++] = -1; 1688 } 1689 map[i] = -1; 1690 return map; 1691} 1692 1693static int *saved_cfg = NULL; 1694 1695 1696/* This function compares the saved version of the cfg with the 1697 current cfg and aborts if the two are identical. The function 1698 silently returns if the cfg has been marked as dirty or the two are 1699 the same. */ 1700 1701void 1702df_check_cfg_clean (void) 1703{ 1704 int *new_map; 1705 1706 if (!df) 1707 return; 1708 1709 if (df_lr->solutions_dirty) 1710 return; 1711 1712 if (saved_cfg == NULL) 1713 return; 1714 1715 new_map = df_compute_cfg_image (); 1716 gcc_assert (memcmp (saved_cfg, new_map, saved_cfg[0] * sizeof (int)) == 0); 1717 free (new_map); 1718} 1719 1720 1721/* This function builds a cfg fingerprint and squirrels it away in 1722 saved_cfg. */ 1723 1724static void 1725df_set_clean_cfg (void) 1726{ 1727 free (saved_cfg); 1728 saved_cfg = df_compute_cfg_image (); 1729} 1730 1731#endif /* DF_DEBUG_CFG */ 1732/*---------------------------------------------------------------------------- 1733 PUBLIC INTERFACES TO QUERY INFORMATION. 1734----------------------------------------------------------------------------*/ 1735 1736 1737/* Return first def of REGNO within BB. */ 1738 1739df_ref 1740df_bb_regno_first_def_find (basic_block bb, unsigned int regno) 1741{ 1742 rtx insn; 1743 df_ref *def_rec; 1744 unsigned int uid; 1745 1746 FOR_BB_INSNS (bb, insn) 1747 { 1748 if (!INSN_P (insn)) 1749 continue; 1750 1751 uid = INSN_UID (insn); 1752 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++) 1753 { 1754 df_ref def = *def_rec; 1755 if (DF_REF_REGNO (def) == regno) 1756 return def; 1757 } 1758 } 1759 return NULL; 1760} 1761 1762 1763/* Return last def of REGNO within BB. */ 1764 1765df_ref 1766df_bb_regno_last_def_find (basic_block bb, unsigned int regno) 1767{ 1768 rtx insn; 1769 df_ref *def_rec; 1770 unsigned int uid; 1771 1772 FOR_BB_INSNS_REVERSE (bb, insn) 1773 { 1774 if (!INSN_P (insn)) 1775 continue; 1776 1777 uid = INSN_UID (insn); 1778 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++) 1779 { 1780 df_ref def = *def_rec; 1781 if (DF_REF_REGNO (def) == regno) 1782 return def; 1783 } 1784 } 1785 1786 return NULL; 1787} 1788 1789/* Finds the reference corresponding to the definition of REG in INSN. 1790 DF is the dataflow object. */ 1791 1792df_ref 1793df_find_def (rtx insn, rtx reg) 1794{ 1795 unsigned int uid; 1796 df_ref *def_rec; 1797 1798 if (GET_CODE (reg) == SUBREG) 1799 reg = SUBREG_REG (reg); 1800 gcc_assert (REG_P (reg)); 1801 1802 uid = INSN_UID (insn); 1803 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++) 1804 { 1805 df_ref def = *def_rec; 1806 if (rtx_equal_p (DF_REF_REAL_REG (def), reg)) 1807 return def; 1808 } 1809 1810 return NULL; 1811} 1812 1813 1814/* Return true if REG is defined in INSN, zero otherwise. */ 1815 1816bool 1817df_reg_defined (rtx insn, rtx reg) 1818{ 1819 return df_find_def (insn, reg) != NULL; 1820} 1821 1822 1823/* Finds the reference corresponding to the use of REG in INSN. 1824 DF is the dataflow object. */ 1825 1826df_ref 1827df_find_use (rtx insn, rtx reg) 1828{ 1829 unsigned int uid; 1830 df_ref *use_rec; 1831 1832 if (GET_CODE (reg) == SUBREG) 1833 reg = SUBREG_REG (reg); 1834 gcc_assert (REG_P (reg)); 1835 1836 uid = INSN_UID (insn); 1837 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++) 1838 { 1839 df_ref use = *use_rec; 1840 if (rtx_equal_p (DF_REF_REAL_REG (use), reg)) 1841 return use; 1842 } 1843 if (df->changeable_flags & DF_EQ_NOTES) 1844 for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++) 1845 { 1846 df_ref use = *use_rec; 1847 if (rtx_equal_p (DF_REF_REAL_REG (use), reg)) 1848 return use; 1849 } 1850 return NULL; 1851} 1852 1853 1854/* Return true if REG is referenced in INSN, zero otherwise. */ 1855 1856bool 1857df_reg_used (rtx insn, rtx reg) 1858{ 1859 return df_find_use (insn, reg) != NULL; 1860} 1861 1862 1863/*---------------------------------------------------------------------------- 1864 Debugging and printing functions. 1865----------------------------------------------------------------------------*/ 1866 1867/* Write information about registers and basic blocks into FILE. 1868 This is part of making a debugging dump. */ 1869 1870void 1871dump_regset (regset r, FILE *outf) 1872{ 1873 unsigned i; 1874 reg_set_iterator rsi; 1875 1876 if (r == NULL) 1877 { 1878 fputs (" (nil)", outf); 1879 return; 1880 } 1881 1882 EXECUTE_IF_SET_IN_REG_SET (r, 0, i, rsi) 1883 { 1884 fprintf (outf, " %d", i); 1885 if (i < FIRST_PSEUDO_REGISTER) 1886 fprintf (outf, " [%s]", 1887 reg_names[i]); 1888 } 1889} 1890 1891/* Print a human-readable representation of R on the standard error 1892 stream. This function is designed to be used from within the 1893 debugger. */ 1894extern void debug_regset (regset); 1895DEBUG_FUNCTION void 1896debug_regset (regset r) 1897{ 1898 dump_regset (r, stderr); 1899 putc ('\n', stderr); 1900} 1901 1902/* Write information about registers and basic blocks into FILE. 1903 This is part of making a debugging dump. */ 1904 1905void 1906df_print_regset (FILE *file, bitmap r) 1907{ 1908 unsigned int i; 1909 bitmap_iterator bi; 1910 1911 if (r == NULL) 1912 fputs (" (nil)", file); 1913 else 1914 { 1915 EXECUTE_IF_SET_IN_BITMAP (r, 0, i, bi) 1916 { 1917 fprintf (file, " %d", i); 1918 if (i < FIRST_PSEUDO_REGISTER) 1919 fprintf (file, " [%s]", reg_names[i]); 1920 } 1921 } 1922 fprintf (file, "\n"); 1923} 1924 1925 1926/* Write information about registers and basic blocks into FILE. The 1927 bitmap is in the form used by df_byte_lr. This is part of making a 1928 debugging dump. */ 1929 1930void 1931df_print_word_regset (FILE *file, bitmap r) 1932{ 1933 unsigned int max_reg = max_reg_num (); 1934 1935 if (r == NULL) 1936 fputs (" (nil)", file); 1937 else 1938 { 1939 unsigned int i; 1940 for (i = FIRST_PSEUDO_REGISTER; i < max_reg; i++) 1941 { 1942 bool found = (bitmap_bit_p (r, 2 * i) 1943 || bitmap_bit_p (r, 2 * i + 1)); 1944 if (found) 1945 { 1946 int word; 1947 const char * sep = ""; 1948 fprintf (file, " %d", i); 1949 fprintf (file, "("); 1950 for (word = 0; word < 2; word++) 1951 if (bitmap_bit_p (r, 2 * i + word)) 1952 { 1953 fprintf (file, "%s%d", sep, word); 1954 sep = ", "; 1955 } 1956 fprintf (file, ")"); 1957 } 1958 } 1959 } 1960 fprintf (file, "\n"); 1961} 1962 1963 1964/* Dump dataflow info. */ 1965 1966void 1967df_dump (FILE *file) 1968{ 1969 basic_block bb; 1970 df_dump_start (file); 1971 1972 FOR_ALL_BB (bb) 1973 { 1974 df_print_bb_index (bb, file); 1975 df_dump_top (bb, file); 1976 df_dump_bottom (bb, file); 1977 } 1978 1979 fprintf (file, "\n"); 1980} 1981 1982 1983/* Dump dataflow info for df->blocks_to_analyze. */ 1984 1985void 1986df_dump_region (FILE *file) 1987{ 1988 if (df->blocks_to_analyze) 1989 { 1990 bitmap_iterator bi; 1991 unsigned int bb_index; 1992 1993 fprintf (file, "\n\nstarting region dump\n"); 1994 df_dump_start (file); 1995 1996 EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi) 1997 { 1998 basic_block bb = BASIC_BLOCK (bb_index); 1999 dump_bb (file, bb, 0, TDF_DETAILS); 2000 } 2001 fprintf (file, "\n"); 2002 } 2003 else 2004 df_dump (file); 2005} 2006 2007 2008/* Dump the introductory information for each problem defined. */ 2009 2010void 2011df_dump_start (FILE *file) 2012{ 2013 int i; 2014 2015 if (!df || !file) 2016 return; 2017 2018 fprintf (file, "\n\n%s\n", current_function_name ()); 2019 fprintf (file, "\nDataflow summary:\n"); 2020 if (df->blocks_to_analyze) 2021 fprintf (file, "def_info->table_size = %d, use_info->table_size = %d\n", 2022 DF_DEFS_TABLE_SIZE (), DF_USES_TABLE_SIZE ()); 2023 2024 for (i = 0; i < df->num_problems_defined; i++) 2025 { 2026 struct dataflow *dflow = df->problems_in_order[i]; 2027 if (dflow->computed) 2028 { 2029 df_dump_problem_function fun = dflow->problem->dump_start_fun; 2030 if (fun) 2031 fun(file); 2032 } 2033 } 2034} 2035 2036 2037/* Dump the top or bottom of the block information for BB. */ 2038static void 2039df_dump_bb_problem_data (basic_block bb, FILE *file, bool top) 2040{ 2041 int i; 2042 2043 if (!df || !file) 2044 return; 2045 2046 for (i = 0; i < df->num_problems_defined; i++) 2047 { 2048 struct dataflow *dflow = df->problems_in_order[i]; 2049 if (dflow->computed) 2050 { 2051 df_dump_bb_problem_function bbfun; 2052 2053 if (top) 2054 bbfun = dflow->problem->dump_top_fun; 2055 else 2056 bbfun = dflow->problem->dump_bottom_fun; 2057 2058 if (bbfun) 2059 bbfun (bb, file); 2060 } 2061 } 2062} 2063 2064/* Dump the top of the block information for BB. */ 2065 2066void 2067df_dump_top (basic_block bb, FILE *file) 2068{ 2069 df_dump_bb_problem_data (bb, file, /*top=*/true); 2070} 2071 2072/* Dump the bottom of the block information for BB. */ 2073 2074void 2075df_dump_bottom (basic_block bb, FILE *file) 2076{ 2077 df_dump_bb_problem_data (bb, file, /*top=*/false); 2078} 2079 2080 2081/* Dump information about INSN just before or after dumping INSN itself. */ 2082static void 2083df_dump_insn_problem_data (const_rtx insn, FILE *file, bool top) 2084{ 2085 int i; 2086 2087 if (!df || !file) 2088 return; 2089 2090 for (i = 0; i < df->num_problems_defined; i++) 2091 { 2092 struct dataflow *dflow = df->problems_in_order[i]; 2093 if (dflow->computed) 2094 { 2095 df_dump_insn_problem_function insnfun; 2096 2097 if (top) 2098 insnfun = dflow->problem->dump_insn_top_fun; 2099 else 2100 insnfun = dflow->problem->dump_insn_bottom_fun; 2101 2102 if (insnfun) 2103 insnfun (insn, file); 2104 } 2105 } 2106} 2107 2108/* Dump information about INSN before dumping INSN itself. */ 2109 2110void 2111df_dump_insn_top (const_rtx insn, FILE *file) 2112{ 2113 df_dump_insn_problem_data (insn, file, /*top=*/true); 2114} 2115 2116/* Dump information about INSN after dumping INSN itself. */ 2117 2118void 2119df_dump_insn_bottom (const_rtx insn, FILE *file) 2120{ 2121 df_dump_insn_problem_data (insn, file, /*top=*/false); 2122} 2123 2124 2125static void 2126df_ref_dump (df_ref ref, FILE *file) 2127{ 2128 fprintf (file, "%c%d(%d)", 2129 DF_REF_REG_DEF_P (ref) 2130 ? 'd' 2131 : (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE) ? 'e' : 'u', 2132 DF_REF_ID (ref), 2133 DF_REF_REGNO (ref)); 2134} 2135 2136void 2137df_refs_chain_dump (df_ref *ref_rec, bool follow_chain, FILE *file) 2138{ 2139 fprintf (file, "{ "); 2140 while (*ref_rec) 2141 { 2142 df_ref ref = *ref_rec; 2143 df_ref_dump (ref, file); 2144 if (follow_chain) 2145 df_chain_dump (DF_REF_CHAIN (ref), file); 2146 ref_rec++; 2147 } 2148 fprintf (file, "}"); 2149} 2150 2151 2152/* Dump either a ref-def or reg-use chain. */ 2153 2154void 2155df_regs_chain_dump (df_ref ref, FILE *file) 2156{ 2157 fprintf (file, "{ "); 2158 while (ref) 2159 { 2160 df_ref_dump (ref, file); 2161 ref = DF_REF_NEXT_REG (ref); 2162 } 2163 fprintf (file, "}"); 2164} 2165 2166 2167static void 2168df_mws_dump (struct df_mw_hardreg **mws, FILE *file) 2169{ 2170 while (*mws) 2171 { 2172 fprintf (file, "mw %c r[%d..%d]\n", 2173 (DF_MWS_REG_DEF_P (*mws)) ? 'd' : 'u', 2174 (*mws)->start_regno, (*mws)->end_regno); 2175 mws++; 2176 } 2177} 2178 2179 2180static void 2181df_insn_uid_debug (unsigned int uid, 2182 bool follow_chain, FILE *file) 2183{ 2184 fprintf (file, "insn %d luid %d", 2185 uid, DF_INSN_UID_LUID (uid)); 2186 2187 if (DF_INSN_UID_DEFS (uid)) 2188 { 2189 fprintf (file, " defs "); 2190 df_refs_chain_dump (DF_INSN_UID_DEFS (uid), follow_chain, file); 2191 } 2192 2193 if (DF_INSN_UID_USES (uid)) 2194 { 2195 fprintf (file, " uses "); 2196 df_refs_chain_dump (DF_INSN_UID_USES (uid), follow_chain, file); 2197 } 2198 2199 if (DF_INSN_UID_EQ_USES (uid)) 2200 { 2201 fprintf (file, " eq uses "); 2202 df_refs_chain_dump (DF_INSN_UID_EQ_USES (uid), follow_chain, file); 2203 } 2204 2205 if (DF_INSN_UID_MWS (uid)) 2206 { 2207 fprintf (file, " mws "); 2208 df_mws_dump (DF_INSN_UID_MWS (uid), file); 2209 } 2210 fprintf (file, "\n"); 2211} 2212 2213 2214DEBUG_FUNCTION void 2215df_insn_debug (rtx insn, bool follow_chain, FILE *file) 2216{ 2217 df_insn_uid_debug (INSN_UID (insn), follow_chain, file); 2218} 2219 2220DEBUG_FUNCTION void 2221df_insn_debug_regno (rtx insn, FILE *file) 2222{ 2223 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn); 2224 2225 fprintf (file, "insn %d bb %d luid %d defs ", 2226 INSN_UID (insn), BLOCK_FOR_INSN (insn)->index, 2227 DF_INSN_INFO_LUID (insn_info)); 2228 df_refs_chain_dump (DF_INSN_INFO_DEFS (insn_info), false, file); 2229 2230 fprintf (file, " uses "); 2231 df_refs_chain_dump (DF_INSN_INFO_USES (insn_info), false, file); 2232 2233 fprintf (file, " eq_uses "); 2234 df_refs_chain_dump (DF_INSN_INFO_EQ_USES (insn_info), false, file); 2235 fprintf (file, "\n"); 2236} 2237 2238DEBUG_FUNCTION void 2239df_regno_debug (unsigned int regno, FILE *file) 2240{ 2241 fprintf (file, "reg %d defs ", regno); 2242 df_regs_chain_dump (DF_REG_DEF_CHAIN (regno), file); 2243 fprintf (file, " uses "); 2244 df_regs_chain_dump (DF_REG_USE_CHAIN (regno), file); 2245 fprintf (file, " eq_uses "); 2246 df_regs_chain_dump (DF_REG_EQ_USE_CHAIN (regno), file); 2247 fprintf (file, "\n"); 2248} 2249 2250 2251DEBUG_FUNCTION void 2252df_ref_debug (df_ref ref, FILE *file) 2253{ 2254 fprintf (file, "%c%d ", 2255 DF_REF_REG_DEF_P (ref) ? 'd' : 'u', 2256 DF_REF_ID (ref)); 2257 fprintf (file, "reg %d bb %d insn %d flag %#x type %#x ", 2258 DF_REF_REGNO (ref), 2259 DF_REF_BBNO (ref), 2260 DF_REF_IS_ARTIFICIAL (ref) ? -1 : DF_REF_INSN_UID (ref), 2261 DF_REF_FLAGS (ref), 2262 DF_REF_TYPE (ref)); 2263 if (DF_REF_LOC (ref)) 2264 { 2265 if (flag_dump_noaddr) 2266 fprintf (file, "loc #(#) chain "); 2267 else 2268 fprintf (file, "loc %p(%p) chain ", (void *)DF_REF_LOC (ref), 2269 (void *)*DF_REF_LOC (ref)); 2270 } 2271 else 2272 fprintf (file, "chain "); 2273 df_chain_dump (DF_REF_CHAIN (ref), file); 2274 fprintf (file, "\n"); 2275} 2276 2277/* Functions for debugging from GDB. */ 2278 2279DEBUG_FUNCTION void 2280debug_df_insn (rtx insn) 2281{ 2282 df_insn_debug (insn, true, stderr); 2283 debug_rtx (insn); 2284} 2285 2286 2287DEBUG_FUNCTION void 2288debug_df_reg (rtx reg) 2289{ 2290 df_regno_debug (REGNO (reg), stderr); 2291} 2292 2293 2294DEBUG_FUNCTION void 2295debug_df_regno (unsigned int regno) 2296{ 2297 df_regno_debug (regno, stderr); 2298} 2299 2300 2301DEBUG_FUNCTION void 2302debug_df_ref (df_ref ref) 2303{ 2304 df_ref_debug (ref, stderr); 2305} 2306 2307 2308DEBUG_FUNCTION void 2309debug_df_defno (unsigned int defno) 2310{ 2311 df_ref_debug (DF_DEFS_GET (defno), stderr); 2312} 2313 2314 2315DEBUG_FUNCTION void 2316debug_df_useno (unsigned int defno) 2317{ 2318 df_ref_debug (DF_USES_GET (defno), stderr); 2319} 2320 2321 2322DEBUG_FUNCTION void 2323debug_df_chain (struct df_link *link) 2324{ 2325 df_chain_dump (link, stderr); 2326 fputc ('\n', stderr); 2327} 2328