df-core.c revision 1.9
1/* Allocation for dataflow support routines. 2 Copyright (C) 1999-2017 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 rtx iterators 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 are 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 EH_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 defs 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 "backend.h" 381#include "rtl.h" 382#include "df.h" 383#include "memmodel.h" 384#include "emit-rtl.h" 385#include "cfganal.h" 386#include "tree-pass.h" 387#include "cfgloop.h" 388 389static void *df_get_bb_info (struct dataflow *, unsigned int); 390static void df_set_bb_info (struct dataflow *, unsigned int, void *); 391static void df_clear_bb_info (struct dataflow *, unsigned int); 392#ifdef DF_DEBUG_CFG 393static void df_set_clean_cfg (void); 394#endif 395 396/* The obstack on which regsets are allocated. */ 397struct bitmap_obstack reg_obstack; 398 399/* An obstack for bitmap not related to specific dataflow problems. 400 This obstack should e.g. be used for bitmaps with a short life time 401 such as temporary bitmaps. */ 402 403bitmap_obstack df_bitmap_obstack; 404 405 406/*---------------------------------------------------------------------------- 407 Functions to create, destroy and manipulate an instance of df. 408----------------------------------------------------------------------------*/ 409 410struct df_d *df; 411 412/* Add PROBLEM (and any dependent problems) to the DF instance. */ 413 414void 415df_add_problem (const struct df_problem *problem) 416{ 417 struct dataflow *dflow; 418 int i; 419 420 /* First try to add the dependent problem. */ 421 if (problem->dependent_problem) 422 df_add_problem (problem->dependent_problem); 423 424 /* Check to see if this problem has already been defined. If it 425 has, just return that instance, if not, add it to the end of the 426 vector. */ 427 dflow = df->problems_by_index[problem->id]; 428 if (dflow) 429 return; 430 431 /* Make a new one and add it to the end. */ 432 dflow = XCNEW (struct dataflow); 433 dflow->problem = problem; 434 dflow->computed = false; 435 dflow->solutions_dirty = true; 436 df->problems_by_index[dflow->problem->id] = dflow; 437 438 /* Keep the defined problems ordered by index. This solves the 439 problem that RI will use the information from UREC if UREC has 440 been defined, or from LIVE if LIVE is defined and otherwise LR. 441 However for this to work, the computation of RI must be pushed 442 after which ever of those problems is defined, but we do not 443 require any of those except for LR to have actually been 444 defined. */ 445 df->num_problems_defined++; 446 for (i = df->num_problems_defined - 2; i >= 0; i--) 447 { 448 if (problem->id < df->problems_in_order[i]->problem->id) 449 df->problems_in_order[i+1] = df->problems_in_order[i]; 450 else 451 { 452 df->problems_in_order[i+1] = dflow; 453 return; 454 } 455 } 456 df->problems_in_order[0] = dflow; 457} 458 459 460/* Set the MASK flags in the DFLOW problem. The old flags are 461 returned. If a flag is not allowed to be changed this will fail if 462 checking is enabled. */ 463int 464df_set_flags (int changeable_flags) 465{ 466 int old_flags = df->changeable_flags; 467 df->changeable_flags |= changeable_flags; 468 return old_flags; 469} 470 471 472/* Clear the MASK flags in the DFLOW problem. The old flags are 473 returned. If a flag is not allowed to be changed this will fail if 474 checking is enabled. */ 475int 476df_clear_flags (int changeable_flags) 477{ 478 int old_flags = df->changeable_flags; 479 df->changeable_flags &= ~changeable_flags; 480 return old_flags; 481} 482 483 484/* Set the blocks that are to be considered for analysis. If this is 485 not called or is called with null, the entire function in 486 analyzed. */ 487 488void 489df_set_blocks (bitmap blocks) 490{ 491 if (blocks) 492 { 493 if (dump_file) 494 bitmap_print (dump_file, blocks, "setting blocks to analyze ", "\n"); 495 if (df->blocks_to_analyze) 496 { 497 /* This block is called to change the focus from one subset 498 to another. */ 499 int p; 500 bitmap_head diff; 501 bitmap_initialize (&diff, &df_bitmap_obstack); 502 bitmap_and_compl (&diff, df->blocks_to_analyze, blocks); 503 for (p = 0; p < df->num_problems_defined; p++) 504 { 505 struct dataflow *dflow = df->problems_in_order[p]; 506 if (dflow->optional_p && dflow->problem->reset_fun) 507 dflow->problem->reset_fun (df->blocks_to_analyze); 508 else if (dflow->problem->free_blocks_on_set_blocks) 509 { 510 bitmap_iterator bi; 511 unsigned int bb_index; 512 513 EXECUTE_IF_SET_IN_BITMAP (&diff, 0, bb_index, bi) 514 { 515 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index); 516 if (bb) 517 { 518 void *bb_info = df_get_bb_info (dflow, bb_index); 519 dflow->problem->free_bb_fun (bb, bb_info); 520 df_clear_bb_info (dflow, bb_index); 521 } 522 } 523 } 524 } 525 526 bitmap_clear (&diff); 527 } 528 else 529 { 530 /* This block of code is executed to change the focus from 531 the entire function to a subset. */ 532 bitmap_head blocks_to_reset; 533 bool initialized = false; 534 int p; 535 for (p = 0; p < df->num_problems_defined; p++) 536 { 537 struct dataflow *dflow = df->problems_in_order[p]; 538 if (dflow->optional_p && dflow->problem->reset_fun) 539 { 540 if (!initialized) 541 { 542 basic_block bb; 543 bitmap_initialize (&blocks_to_reset, &df_bitmap_obstack); 544 FOR_ALL_BB_FN (bb, cfun) 545 { 546 bitmap_set_bit (&blocks_to_reset, bb->index); 547 } 548 } 549 dflow->problem->reset_fun (&blocks_to_reset); 550 } 551 } 552 if (initialized) 553 bitmap_clear (&blocks_to_reset); 554 555 df->blocks_to_analyze = BITMAP_ALLOC (&df_bitmap_obstack); 556 } 557 bitmap_copy (df->blocks_to_analyze, blocks); 558 df->analyze_subset = true; 559 } 560 else 561 { 562 /* This block is executed to reset the focus to the entire 563 function. */ 564 if (dump_file) 565 fprintf (dump_file, "clearing blocks_to_analyze\n"); 566 if (df->blocks_to_analyze) 567 { 568 BITMAP_FREE (df->blocks_to_analyze); 569 df->blocks_to_analyze = NULL; 570 } 571 df->analyze_subset = false; 572 } 573 574 /* Setting the blocks causes the refs to be unorganized since only 575 the refs in the blocks are seen. */ 576 df_maybe_reorganize_def_refs (DF_REF_ORDER_NO_TABLE); 577 df_maybe_reorganize_use_refs (DF_REF_ORDER_NO_TABLE); 578 df_mark_solutions_dirty (); 579} 580 581 582/* Delete a DFLOW problem (and any problems that depend on this 583 problem). */ 584 585void 586df_remove_problem (struct dataflow *dflow) 587{ 588 const struct df_problem *problem; 589 int i; 590 591 if (!dflow) 592 return; 593 594 problem = dflow->problem; 595 gcc_assert (problem->remove_problem_fun); 596 597 /* Delete any problems that depended on this problem first. */ 598 for (i = 0; i < df->num_problems_defined; i++) 599 if (df->problems_in_order[i]->problem->dependent_problem == problem) 600 df_remove_problem (df->problems_in_order[i]); 601 602 /* Now remove this problem. */ 603 for (i = 0; i < df->num_problems_defined; i++) 604 if (df->problems_in_order[i] == dflow) 605 { 606 int j; 607 for (j = i + 1; j < df->num_problems_defined; j++) 608 df->problems_in_order[j-1] = df->problems_in_order[j]; 609 df->problems_in_order[j-1] = NULL; 610 df->num_problems_defined--; 611 break; 612 } 613 614 (problem->remove_problem_fun) (); 615 df->problems_by_index[problem->id] = NULL; 616} 617 618 619/* Remove all of the problems that are not permanent. Scanning, LR 620 and (at -O2 or higher) LIVE are permanent, the rest are removable. 621 Also clear all of the changeable_flags. */ 622 623void 624df_finish_pass (bool verify ATTRIBUTE_UNUSED) 625{ 626 int i; 627 628#ifdef ENABLE_DF_CHECKING 629 int saved_flags; 630#endif 631 632 if (!df) 633 return; 634 635 df_maybe_reorganize_def_refs (DF_REF_ORDER_NO_TABLE); 636 df_maybe_reorganize_use_refs (DF_REF_ORDER_NO_TABLE); 637 638#ifdef ENABLE_DF_CHECKING 639 saved_flags = df->changeable_flags; 640#endif 641 642 /* We iterate over problems by index as each problem removed will 643 lead to problems_in_order to be reordered. */ 644 for (i = 0; i < DF_LAST_PROBLEM_PLUS1; i++) 645 { 646 struct dataflow *dflow = df->problems_by_index[i]; 647 648 if (dflow && dflow->optional_p) 649 df_remove_problem (dflow); 650 } 651 652 /* Clear all of the flags. */ 653 df->changeable_flags = 0; 654 df_process_deferred_rescans (); 655 656 /* Set the focus back to the whole function. */ 657 if (df->blocks_to_analyze) 658 { 659 BITMAP_FREE (df->blocks_to_analyze); 660 df->blocks_to_analyze = NULL; 661 df_mark_solutions_dirty (); 662 df->analyze_subset = false; 663 } 664 665#ifdef ENABLE_DF_CHECKING 666 /* Verification will fail in DF_NO_INSN_RESCAN. */ 667 if (!(saved_flags & DF_NO_INSN_RESCAN)) 668 { 669 df_lr_verify_transfer_functions (); 670 if (df_live) 671 df_live_verify_transfer_functions (); 672 } 673 674#ifdef DF_DEBUG_CFG 675 df_set_clean_cfg (); 676#endif 677#endif 678 679 if (flag_checking && verify) 680 df->changeable_flags |= DF_VERIFY_SCHEDULED; 681} 682 683 684/* Set up the dataflow instance for the entire back end. */ 685 686static unsigned int 687rest_of_handle_df_initialize (void) 688{ 689 gcc_assert (!df); 690 df = XCNEW (struct df_d); 691 df->changeable_flags = 0; 692 693 bitmap_obstack_initialize (&df_bitmap_obstack); 694 695 /* Set this to a conservative value. Stack_ptr_mod will compute it 696 correctly later. */ 697 crtl->sp_is_unchanging = 0; 698 699 df_scan_add_problem (); 700 df_scan_alloc (NULL); 701 702 /* These three problems are permanent. */ 703 df_lr_add_problem (); 704 if (optimize > 1) 705 df_live_add_problem (); 706 707 df->postorder = XNEWVEC (int, last_basic_block_for_fn (cfun)); 708 df->postorder_inverted = XNEWVEC (int, last_basic_block_for_fn (cfun)); 709 df->n_blocks = post_order_compute (df->postorder, true, true); 710 df->n_blocks_inverted = inverted_post_order_compute (df->postorder_inverted); 711 gcc_assert (df->n_blocks == df->n_blocks_inverted); 712 713 df->hard_regs_live_count = XCNEWVEC (unsigned int, FIRST_PSEUDO_REGISTER); 714 715 df_hard_reg_init (); 716 /* After reload, some ports add certain bits to regs_ever_live so 717 this cannot be reset. */ 718 df_compute_regs_ever_live (true); 719 df_scan_blocks (); 720 df_compute_regs_ever_live (false); 721 return 0; 722} 723 724 725namespace { 726 727const pass_data pass_data_df_initialize_opt = 728{ 729 RTL_PASS, /* type */ 730 "dfinit", /* name */ 731 OPTGROUP_NONE, /* optinfo_flags */ 732 TV_DF_SCAN, /* tv_id */ 733 0, /* properties_required */ 734 0, /* properties_provided */ 735 0, /* properties_destroyed */ 736 0, /* todo_flags_start */ 737 0, /* todo_flags_finish */ 738}; 739 740class pass_df_initialize_opt : public rtl_opt_pass 741{ 742public: 743 pass_df_initialize_opt (gcc::context *ctxt) 744 : rtl_opt_pass (pass_data_df_initialize_opt, ctxt) 745 {} 746 747 /* opt_pass methods: */ 748 virtual bool gate (function *) { return optimize > 0; } 749 virtual unsigned int execute (function *) 750 { 751 return rest_of_handle_df_initialize (); 752 } 753 754}; // class pass_df_initialize_opt 755 756} // anon namespace 757 758rtl_opt_pass * 759make_pass_df_initialize_opt (gcc::context *ctxt) 760{ 761 return new pass_df_initialize_opt (ctxt); 762} 763 764 765namespace { 766 767const pass_data pass_data_df_initialize_no_opt = 768{ 769 RTL_PASS, /* type */ 770 "no-opt dfinit", /* name */ 771 OPTGROUP_NONE, /* optinfo_flags */ 772 TV_DF_SCAN, /* tv_id */ 773 0, /* properties_required */ 774 0, /* properties_provided */ 775 0, /* properties_destroyed */ 776 0, /* todo_flags_start */ 777 0, /* todo_flags_finish */ 778}; 779 780class pass_df_initialize_no_opt : public rtl_opt_pass 781{ 782public: 783 pass_df_initialize_no_opt (gcc::context *ctxt) 784 : rtl_opt_pass (pass_data_df_initialize_no_opt, ctxt) 785 {} 786 787 /* opt_pass methods: */ 788 virtual bool gate (function *) { return optimize == 0; } 789 virtual unsigned int execute (function *) 790 { 791 return rest_of_handle_df_initialize (); 792 } 793 794}; // class pass_df_initialize_no_opt 795 796} // anon namespace 797 798rtl_opt_pass * 799make_pass_df_initialize_no_opt (gcc::context *ctxt) 800{ 801 return new pass_df_initialize_no_opt (ctxt); 802} 803 804 805/* Free all the dataflow info and the DF structure. This should be 806 called from the df_finish macro which also NULLs the parm. */ 807 808static unsigned int 809rest_of_handle_df_finish (void) 810{ 811 int i; 812 813 gcc_assert (df); 814 815 for (i = 0; i < df->num_problems_defined; i++) 816 { 817 struct dataflow *dflow = df->problems_in_order[i]; 818 dflow->problem->free_fun (); 819 } 820 821 free (df->postorder); 822 free (df->postorder_inverted); 823 free (df->hard_regs_live_count); 824 free (df); 825 df = NULL; 826 827 bitmap_obstack_release (&df_bitmap_obstack); 828 return 0; 829} 830 831 832namespace { 833 834const pass_data pass_data_df_finish = 835{ 836 RTL_PASS, /* type */ 837 "dfinish", /* name */ 838 OPTGROUP_NONE, /* optinfo_flags */ 839 TV_NONE, /* tv_id */ 840 0, /* properties_required */ 841 0, /* properties_provided */ 842 0, /* properties_destroyed */ 843 0, /* todo_flags_start */ 844 0, /* todo_flags_finish */ 845}; 846 847class pass_df_finish : public rtl_opt_pass 848{ 849public: 850 pass_df_finish (gcc::context *ctxt) 851 : rtl_opt_pass (pass_data_df_finish, ctxt) 852 {} 853 854 /* opt_pass methods: */ 855 virtual unsigned int execute (function *) 856 { 857 return rest_of_handle_df_finish (); 858 } 859 860}; // class pass_df_finish 861 862} // anon namespace 863 864rtl_opt_pass * 865make_pass_df_finish (gcc::context *ctxt) 866{ 867 return new pass_df_finish (ctxt); 868} 869 870 871 872 873 874/*---------------------------------------------------------------------------- 875 The general data flow analysis engine. 876----------------------------------------------------------------------------*/ 877 878/* Return time BB when it was visited for last time. */ 879#define BB_LAST_CHANGE_AGE(bb) ((ptrdiff_t)(bb)->aux) 880 881/* Helper function for df_worklist_dataflow. 882 Propagate the dataflow forward. 883 Given a BB_INDEX, do the dataflow propagation 884 and set bits on for successors in PENDING 885 if the out set of the dataflow has changed. 886 887 AGE specify time when BB was visited last time. 888 AGE of 0 means we are visiting for first time and need to 889 compute transfer function to initialize datastructures. 890 Otherwise we re-do transfer function only if something change 891 while computing confluence functions. 892 We need to compute confluence only of basic block that are younger 893 then last visit of the BB. 894 895 Return true if BB info has changed. This is always the case 896 in the first visit. */ 897 898static bool 899df_worklist_propagate_forward (struct dataflow *dataflow, 900 unsigned bb_index, 901 unsigned *bbindex_to_postorder, 902 bitmap pending, 903 sbitmap considered, 904 ptrdiff_t age) 905{ 906 edge e; 907 edge_iterator ei; 908 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index); 909 bool changed = !age; 910 911 /* Calculate <conf_op> of incoming edges. */ 912 if (EDGE_COUNT (bb->preds) > 0) 913 FOR_EACH_EDGE (e, ei, bb->preds) 914 { 915 if (age <= BB_LAST_CHANGE_AGE (e->src) 916 && bitmap_bit_p (considered, e->src->index)) 917 changed |= dataflow->problem->con_fun_n (e); 918 } 919 else if (dataflow->problem->con_fun_0) 920 dataflow->problem->con_fun_0 (bb); 921 922 if (changed 923 && dataflow->problem->trans_fun (bb_index)) 924 { 925 /* The out set of this block has changed. 926 Propagate to the outgoing blocks. */ 927 FOR_EACH_EDGE (e, ei, bb->succs) 928 { 929 unsigned ob_index = e->dest->index; 930 931 if (bitmap_bit_p (considered, ob_index)) 932 bitmap_set_bit (pending, bbindex_to_postorder[ob_index]); 933 } 934 return true; 935 } 936 return false; 937} 938 939 940/* Helper function for df_worklist_dataflow. 941 Propagate the dataflow backward. */ 942 943static bool 944df_worklist_propagate_backward (struct dataflow *dataflow, 945 unsigned bb_index, 946 unsigned *bbindex_to_postorder, 947 bitmap pending, 948 sbitmap considered, 949 ptrdiff_t age) 950{ 951 edge e; 952 edge_iterator ei; 953 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index); 954 bool changed = !age; 955 956 /* Calculate <conf_op> of incoming edges. */ 957 if (EDGE_COUNT (bb->succs) > 0) 958 FOR_EACH_EDGE (e, ei, bb->succs) 959 { 960 if (age <= BB_LAST_CHANGE_AGE (e->dest) 961 && bitmap_bit_p (considered, e->dest->index)) 962 changed |= dataflow->problem->con_fun_n (e); 963 } 964 else if (dataflow->problem->con_fun_0) 965 dataflow->problem->con_fun_0 (bb); 966 967 if (changed 968 && dataflow->problem->trans_fun (bb_index)) 969 { 970 /* The out set of this block has changed. 971 Propagate to the outgoing blocks. */ 972 FOR_EACH_EDGE (e, ei, bb->preds) 973 { 974 unsigned ob_index = e->src->index; 975 976 if (bitmap_bit_p (considered, ob_index)) 977 bitmap_set_bit (pending, bbindex_to_postorder[ob_index]); 978 } 979 return true; 980 } 981 return false; 982} 983 984/* Main dataflow solver loop. 985 986 DATAFLOW is problem we are solving, PENDING is worklist of basic blocks we 987 need to visit. 988 BLOCK_IN_POSTORDER is array of size N_BLOCKS specifying postorder in BBs and 989 BBINDEX_TO_POSTORDER is array mapping back BB->index to postorder position. 990 PENDING will be freed. 991 992 The worklists are bitmaps indexed by postorder positions. 993 994 The function implements standard algorithm for dataflow solving with two 995 worklists (we are processing WORKLIST and storing new BBs to visit in 996 PENDING). 997 998 As an optimization we maintain ages when BB was changed (stored in bb->aux) 999 and when it was last visited (stored in last_visit_age). This avoids need 1000 to re-do confluence function for edges to basic blocks whose source 1001 did not change since destination was visited last time. */ 1002 1003static void 1004df_worklist_dataflow_doublequeue (struct dataflow *dataflow, 1005 bitmap pending, 1006 sbitmap considered, 1007 int *blocks_in_postorder, 1008 unsigned *bbindex_to_postorder, 1009 int n_blocks) 1010{ 1011 enum df_flow_dir dir = dataflow->problem->dir; 1012 int dcount = 0; 1013 bitmap worklist = BITMAP_ALLOC (&df_bitmap_obstack); 1014 int age = 0; 1015 bool changed; 1016 vec<int> last_visit_age = vNULL; 1017 int prev_age; 1018 basic_block bb; 1019 int i; 1020 1021 last_visit_age.safe_grow_cleared (n_blocks); 1022 1023 /* Double-queueing. Worklist is for the current iteration, 1024 and pending is for the next. */ 1025 while (!bitmap_empty_p (pending)) 1026 { 1027 bitmap_iterator bi; 1028 unsigned int index; 1029 1030 std::swap (pending, worklist); 1031 1032 EXECUTE_IF_SET_IN_BITMAP (worklist, 0, index, bi) 1033 { 1034 unsigned bb_index; 1035 dcount++; 1036 1037 bitmap_clear_bit (pending, index); 1038 bb_index = blocks_in_postorder[index]; 1039 bb = BASIC_BLOCK_FOR_FN (cfun, bb_index); 1040 prev_age = last_visit_age[index]; 1041 if (dir == DF_FORWARD) 1042 changed = df_worklist_propagate_forward (dataflow, bb_index, 1043 bbindex_to_postorder, 1044 pending, considered, 1045 prev_age); 1046 else 1047 changed = df_worklist_propagate_backward (dataflow, bb_index, 1048 bbindex_to_postorder, 1049 pending, considered, 1050 prev_age); 1051 last_visit_age[index] = ++age; 1052 if (changed) 1053 bb->aux = (void *)(ptrdiff_t)age; 1054 } 1055 bitmap_clear (worklist); 1056 } 1057 for (i = 0; i < n_blocks; i++) 1058 BASIC_BLOCK_FOR_FN (cfun, blocks_in_postorder[i])->aux = NULL; 1059 1060 BITMAP_FREE (worklist); 1061 BITMAP_FREE (pending); 1062 last_visit_age.release (); 1063 1064 /* Dump statistics. */ 1065 if (dump_file) 1066 fprintf (dump_file, "df_worklist_dataflow_doublequeue:" 1067 " n_basic_blocks %d n_edges %d" 1068 " count %d (%5.2g)\n", 1069 n_basic_blocks_for_fn (cfun), n_edges_for_fn (cfun), 1070 dcount, dcount / (float)n_basic_blocks_for_fn (cfun)); 1071} 1072 1073/* Worklist-based dataflow solver. It uses sbitmap as a worklist, 1074 with "n"-th bit representing the n-th block in the reverse-postorder order. 1075 The solver is a double-queue algorithm similar to the "double stack" solver 1076 from Cooper, Harvey and Kennedy, "Iterative data-flow analysis, Revisited". 1077 The only significant difference is that the worklist in this implementation 1078 is always sorted in RPO of the CFG visiting direction. */ 1079 1080void 1081df_worklist_dataflow (struct dataflow *dataflow, 1082 bitmap blocks_to_consider, 1083 int *blocks_in_postorder, 1084 int n_blocks) 1085{ 1086 bitmap pending = BITMAP_ALLOC (&df_bitmap_obstack); 1087 bitmap_iterator bi; 1088 unsigned int *bbindex_to_postorder; 1089 int i; 1090 unsigned int index; 1091 enum df_flow_dir dir = dataflow->problem->dir; 1092 1093 gcc_assert (dir != DF_NONE); 1094 1095 /* BBINDEX_TO_POSTORDER maps the bb->index to the reverse postorder. */ 1096 bbindex_to_postorder = XNEWVEC (unsigned int, 1097 last_basic_block_for_fn (cfun)); 1098 1099 /* Initialize the array to an out-of-bound value. */ 1100 for (i = 0; i < last_basic_block_for_fn (cfun); i++) 1101 bbindex_to_postorder[i] = last_basic_block_for_fn (cfun); 1102 1103 /* Initialize the considered map. */ 1104 auto_sbitmap considered (last_basic_block_for_fn (cfun)); 1105 bitmap_clear (considered); 1106 EXECUTE_IF_SET_IN_BITMAP (blocks_to_consider, 0, index, bi) 1107 { 1108 bitmap_set_bit (considered, index); 1109 } 1110 1111 /* Initialize the mapping of block index to postorder. */ 1112 for (i = 0; i < n_blocks; i++) 1113 { 1114 bbindex_to_postorder[blocks_in_postorder[i]] = i; 1115 /* Add all blocks to the worklist. */ 1116 bitmap_set_bit (pending, i); 1117 } 1118 1119 /* Initialize the problem. */ 1120 if (dataflow->problem->init_fun) 1121 dataflow->problem->init_fun (blocks_to_consider); 1122 1123 /* Solve it. */ 1124 df_worklist_dataflow_doublequeue (dataflow, pending, considered, 1125 blocks_in_postorder, 1126 bbindex_to_postorder, 1127 n_blocks); 1128 free (bbindex_to_postorder); 1129} 1130 1131 1132/* Remove the entries not in BLOCKS from the LIST of length LEN, preserving 1133 the order of the remaining entries. Returns the length of the resulting 1134 list. */ 1135 1136static unsigned 1137df_prune_to_subcfg (int list[], unsigned len, bitmap blocks) 1138{ 1139 unsigned act, last; 1140 1141 for (act = 0, last = 0; act < len; act++) 1142 if (bitmap_bit_p (blocks, list[act])) 1143 list[last++] = list[act]; 1144 1145 return last; 1146} 1147 1148 1149/* Execute dataflow analysis on a single dataflow problem. 1150 1151 BLOCKS_TO_CONSIDER are the blocks whose solution can either be 1152 examined or will be computed. For calls from DF_ANALYZE, this is 1153 the set of blocks that has been passed to DF_SET_BLOCKS. 1154*/ 1155 1156void 1157df_analyze_problem (struct dataflow *dflow, 1158 bitmap blocks_to_consider, 1159 int *postorder, int n_blocks) 1160{ 1161 timevar_push (dflow->problem->tv_id); 1162 1163 /* (Re)Allocate the datastructures necessary to solve the problem. */ 1164 if (dflow->problem->alloc_fun) 1165 dflow->problem->alloc_fun (blocks_to_consider); 1166 1167#ifdef ENABLE_DF_CHECKING 1168 if (dflow->problem->verify_start_fun) 1169 dflow->problem->verify_start_fun (); 1170#endif 1171 1172 /* Set up the problem and compute the local information. */ 1173 if (dflow->problem->local_compute_fun) 1174 dflow->problem->local_compute_fun (blocks_to_consider); 1175 1176 /* Solve the equations. */ 1177 if (dflow->problem->dataflow_fun) 1178 dflow->problem->dataflow_fun (dflow, blocks_to_consider, 1179 postorder, n_blocks); 1180 1181 /* Massage the solution. */ 1182 if (dflow->problem->finalize_fun) 1183 dflow->problem->finalize_fun (blocks_to_consider); 1184 1185#ifdef ENABLE_DF_CHECKING 1186 if (dflow->problem->verify_end_fun) 1187 dflow->problem->verify_end_fun (); 1188#endif 1189 1190 timevar_pop (dflow->problem->tv_id); 1191 1192 dflow->computed = true; 1193} 1194 1195 1196/* Analyze dataflow info. */ 1197 1198static void 1199df_analyze_1 (void) 1200{ 1201 int i; 1202 1203 /* These should be the same. */ 1204 gcc_assert (df->n_blocks == df->n_blocks_inverted); 1205 1206 /* We need to do this before the df_verify_all because this is 1207 not kept incrementally up to date. */ 1208 df_compute_regs_ever_live (false); 1209 df_process_deferred_rescans (); 1210 1211 if (dump_file) 1212 fprintf (dump_file, "df_analyze called\n"); 1213 1214#ifndef ENABLE_DF_CHECKING 1215 if (df->changeable_flags & DF_VERIFY_SCHEDULED) 1216#endif 1217 df_verify (); 1218 1219 /* Skip over the DF_SCAN problem. */ 1220 for (i = 1; i < df->num_problems_defined; i++) 1221 { 1222 struct dataflow *dflow = df->problems_in_order[i]; 1223 if (dflow->solutions_dirty) 1224 { 1225 if (dflow->problem->dir == DF_FORWARD) 1226 df_analyze_problem (dflow, 1227 df->blocks_to_analyze, 1228 df->postorder_inverted, 1229 df->n_blocks_inverted); 1230 else 1231 df_analyze_problem (dflow, 1232 df->blocks_to_analyze, 1233 df->postorder, 1234 df->n_blocks); 1235 } 1236 } 1237 1238 if (!df->analyze_subset) 1239 { 1240 BITMAP_FREE (df->blocks_to_analyze); 1241 df->blocks_to_analyze = NULL; 1242 } 1243 1244#ifdef DF_DEBUG_CFG 1245 df_set_clean_cfg (); 1246#endif 1247} 1248 1249/* Analyze dataflow info. */ 1250 1251void 1252df_analyze (void) 1253{ 1254 bitmap current_all_blocks = BITMAP_ALLOC (&df_bitmap_obstack); 1255 int i; 1256 1257 free (df->postorder); 1258 free (df->postorder_inverted); 1259 df->postorder = XNEWVEC (int, last_basic_block_for_fn (cfun)); 1260 df->postorder_inverted = XNEWVEC (int, last_basic_block_for_fn (cfun)); 1261 df->n_blocks = post_order_compute (df->postorder, true, true); 1262 df->n_blocks_inverted = inverted_post_order_compute (df->postorder_inverted); 1263 1264 for (i = 0; i < df->n_blocks; i++) 1265 bitmap_set_bit (current_all_blocks, df->postorder[i]); 1266 1267 if (flag_checking) 1268 { 1269 /* Verify that POSTORDER_INVERTED only contains blocks reachable from 1270 the ENTRY block. */ 1271 for (i = 0; i < df->n_blocks_inverted; i++) 1272 gcc_assert (bitmap_bit_p (current_all_blocks, 1273 df->postorder_inverted[i])); 1274 } 1275 1276 /* Make sure that we have pruned any unreachable blocks from these 1277 sets. */ 1278 if (df->analyze_subset) 1279 { 1280 bitmap_and_into (df->blocks_to_analyze, current_all_blocks); 1281 df->n_blocks = df_prune_to_subcfg (df->postorder, 1282 df->n_blocks, df->blocks_to_analyze); 1283 df->n_blocks_inverted = df_prune_to_subcfg (df->postorder_inverted, 1284 df->n_blocks_inverted, 1285 df->blocks_to_analyze); 1286 BITMAP_FREE (current_all_blocks); 1287 } 1288 else 1289 { 1290 df->blocks_to_analyze = current_all_blocks; 1291 current_all_blocks = NULL; 1292 } 1293 1294 df_analyze_1 (); 1295} 1296 1297/* Compute the reverse top sort order of the sub-CFG specified by LOOP. 1298 Returns the number of blocks which is always loop->num_nodes. */ 1299 1300static int 1301loop_post_order_compute (int *post_order, struct loop *loop) 1302{ 1303 edge_iterator *stack; 1304 int sp; 1305 int post_order_num = 0; 1306 bitmap visited; 1307 1308 /* Allocate stack for back-tracking up CFG. */ 1309 stack = XNEWVEC (edge_iterator, loop->num_nodes + 1); 1310 sp = 0; 1311 1312 /* Allocate bitmap to track nodes that have been visited. */ 1313 visited = BITMAP_ALLOC (NULL); 1314 1315 /* Push the first edge on to the stack. */ 1316 stack[sp++] = ei_start (loop_preheader_edge (loop)->src->succs); 1317 1318 while (sp) 1319 { 1320 edge_iterator ei; 1321 basic_block src; 1322 basic_block dest; 1323 1324 /* Look at the edge on the top of the stack. */ 1325 ei = stack[sp - 1]; 1326 src = ei_edge (ei)->src; 1327 dest = ei_edge (ei)->dest; 1328 1329 /* Check if the edge destination has been visited yet and mark it 1330 if not so. */ 1331 if (flow_bb_inside_loop_p (loop, dest) 1332 && bitmap_set_bit (visited, dest->index)) 1333 { 1334 if (EDGE_COUNT (dest->succs) > 0) 1335 /* Since the DEST node has been visited for the first 1336 time, check its successors. */ 1337 stack[sp++] = ei_start (dest->succs); 1338 else 1339 post_order[post_order_num++] = dest->index; 1340 } 1341 else 1342 { 1343 if (ei_one_before_end_p (ei) 1344 && src != loop_preheader_edge (loop)->src) 1345 post_order[post_order_num++] = src->index; 1346 1347 if (!ei_one_before_end_p (ei)) 1348 ei_next (&stack[sp - 1]); 1349 else 1350 sp--; 1351 } 1352 } 1353 1354 free (stack); 1355 BITMAP_FREE (visited); 1356 1357 return post_order_num; 1358} 1359 1360/* Compute the reverse top sort order of the inverted sub-CFG specified 1361 by LOOP. Returns the number of blocks which is always loop->num_nodes. */ 1362 1363static int 1364loop_inverted_post_order_compute (int *post_order, struct loop *loop) 1365{ 1366 basic_block bb; 1367 edge_iterator *stack; 1368 int sp; 1369 int post_order_num = 0; 1370 bitmap visited; 1371 1372 /* Allocate stack for back-tracking up CFG. */ 1373 stack = XNEWVEC (edge_iterator, loop->num_nodes + 1); 1374 sp = 0; 1375 1376 /* Allocate bitmap to track nodes that have been visited. */ 1377 visited = BITMAP_ALLOC (NULL); 1378 1379 /* Put all latches into the initial work list. In theory we'd want 1380 to start from loop exits but then we'd have the special case of 1381 endless loops. It doesn't really matter for DF iteration order and 1382 handling latches last is probably even better. */ 1383 stack[sp++] = ei_start (loop->header->preds); 1384 bitmap_set_bit (visited, loop->header->index); 1385 1386 /* The inverted traversal loop. */ 1387 while (sp) 1388 { 1389 edge_iterator ei; 1390 basic_block pred; 1391 1392 /* Look at the edge on the top of the stack. */ 1393 ei = stack[sp - 1]; 1394 bb = ei_edge (ei)->dest; 1395 pred = ei_edge (ei)->src; 1396 1397 /* Check if the predecessor has been visited yet and mark it 1398 if not so. */ 1399 if (flow_bb_inside_loop_p (loop, pred) 1400 && bitmap_set_bit (visited, pred->index)) 1401 { 1402 if (EDGE_COUNT (pred->preds) > 0) 1403 /* Since the predecessor node has been visited for the first 1404 time, check its predecessors. */ 1405 stack[sp++] = ei_start (pred->preds); 1406 else 1407 post_order[post_order_num++] = pred->index; 1408 } 1409 else 1410 { 1411 if (flow_bb_inside_loop_p (loop, bb) 1412 && ei_one_before_end_p (ei)) 1413 post_order[post_order_num++] = bb->index; 1414 1415 if (!ei_one_before_end_p (ei)) 1416 ei_next (&stack[sp - 1]); 1417 else 1418 sp--; 1419 } 1420 } 1421 1422 free (stack); 1423 BITMAP_FREE (visited); 1424 return post_order_num; 1425} 1426 1427 1428/* Analyze dataflow info for the basic blocks contained in LOOP. */ 1429 1430void 1431df_analyze_loop (struct loop *loop) 1432{ 1433 free (df->postorder); 1434 free (df->postorder_inverted); 1435 1436 df->postorder = XNEWVEC (int, loop->num_nodes); 1437 df->postorder_inverted = XNEWVEC (int, loop->num_nodes); 1438 df->n_blocks = loop_post_order_compute (df->postorder, loop); 1439 df->n_blocks_inverted 1440 = loop_inverted_post_order_compute (df->postorder_inverted, loop); 1441 gcc_assert ((unsigned) df->n_blocks == loop->num_nodes); 1442 gcc_assert ((unsigned) df->n_blocks_inverted == loop->num_nodes); 1443 1444 bitmap blocks = BITMAP_ALLOC (&df_bitmap_obstack); 1445 for (int i = 0; i < df->n_blocks; ++i) 1446 bitmap_set_bit (blocks, df->postorder[i]); 1447 df_set_blocks (blocks); 1448 BITMAP_FREE (blocks); 1449 1450 df_analyze_1 (); 1451} 1452 1453 1454/* Return the number of basic blocks from the last call to df_analyze. */ 1455 1456int 1457df_get_n_blocks (enum df_flow_dir dir) 1458{ 1459 gcc_assert (dir != DF_NONE); 1460 1461 if (dir == DF_FORWARD) 1462 { 1463 gcc_assert (df->postorder_inverted); 1464 return df->n_blocks_inverted; 1465 } 1466 1467 gcc_assert (df->postorder); 1468 return df->n_blocks; 1469} 1470 1471 1472/* Return a pointer to the array of basic blocks in the reverse postorder. 1473 Depending on the direction of the dataflow problem, 1474 it returns either the usual reverse postorder array 1475 or the reverse postorder of inverted traversal. */ 1476int * 1477df_get_postorder (enum df_flow_dir dir) 1478{ 1479 gcc_assert (dir != DF_NONE); 1480 1481 if (dir == DF_FORWARD) 1482 { 1483 gcc_assert (df->postorder_inverted); 1484 return df->postorder_inverted; 1485 } 1486 gcc_assert (df->postorder); 1487 return df->postorder; 1488} 1489 1490static struct df_problem user_problem; 1491static struct dataflow user_dflow; 1492 1493/* Interface for calling iterative dataflow with user defined 1494 confluence and transfer functions. All that is necessary is to 1495 supply DIR, a direction, CONF_FUN_0, a confluence function for 1496 blocks with no logical preds (or NULL), CONF_FUN_N, the normal 1497 confluence function, TRANS_FUN, the basic block transfer function, 1498 and BLOCKS, the set of blocks to examine, POSTORDER the blocks in 1499 postorder, and N_BLOCKS, the number of blocks in POSTORDER. */ 1500 1501void 1502df_simple_dataflow (enum df_flow_dir dir, 1503 df_init_function init_fun, 1504 df_confluence_function_0 con_fun_0, 1505 df_confluence_function_n con_fun_n, 1506 df_transfer_function trans_fun, 1507 bitmap blocks, int * postorder, int n_blocks) 1508{ 1509 memset (&user_problem, 0, sizeof (struct df_problem)); 1510 user_problem.dir = dir; 1511 user_problem.init_fun = init_fun; 1512 user_problem.con_fun_0 = con_fun_0; 1513 user_problem.con_fun_n = con_fun_n; 1514 user_problem.trans_fun = trans_fun; 1515 user_dflow.problem = &user_problem; 1516 df_worklist_dataflow (&user_dflow, blocks, postorder, n_blocks); 1517} 1518 1519 1520 1521/*---------------------------------------------------------------------------- 1522 Functions to support limited incremental change. 1523----------------------------------------------------------------------------*/ 1524 1525 1526/* Get basic block info. */ 1527 1528static void * 1529df_get_bb_info (struct dataflow *dflow, unsigned int index) 1530{ 1531 if (dflow->block_info == NULL) 1532 return NULL; 1533 if (index >= dflow->block_info_size) 1534 return NULL; 1535 return (void *)((char *)dflow->block_info 1536 + index * dflow->problem->block_info_elt_size); 1537} 1538 1539 1540/* Set basic block info. */ 1541 1542static void 1543df_set_bb_info (struct dataflow *dflow, unsigned int index, 1544 void *bb_info) 1545{ 1546 gcc_assert (dflow->block_info); 1547 memcpy ((char *)dflow->block_info 1548 + index * dflow->problem->block_info_elt_size, 1549 bb_info, dflow->problem->block_info_elt_size); 1550} 1551 1552 1553/* Clear basic block info. */ 1554 1555static void 1556df_clear_bb_info (struct dataflow *dflow, unsigned int index) 1557{ 1558 gcc_assert (dflow->block_info); 1559 gcc_assert (dflow->block_info_size > index); 1560 memset ((char *)dflow->block_info 1561 + index * dflow->problem->block_info_elt_size, 1562 0, dflow->problem->block_info_elt_size); 1563} 1564 1565 1566/* Mark the solutions as being out of date. */ 1567 1568void 1569df_mark_solutions_dirty (void) 1570{ 1571 if (df) 1572 { 1573 int p; 1574 for (p = 1; p < df->num_problems_defined; p++) 1575 df->problems_in_order[p]->solutions_dirty = true; 1576 } 1577} 1578 1579 1580/* Return true if BB needs it's transfer functions recomputed. */ 1581 1582bool 1583df_get_bb_dirty (basic_block bb) 1584{ 1585 return bitmap_bit_p ((df_live 1586 ? df_live : df_lr)->out_of_date_transfer_functions, 1587 bb->index); 1588} 1589 1590 1591/* Mark BB as needing it's transfer functions as being out of 1592 date. */ 1593 1594void 1595df_set_bb_dirty (basic_block bb) 1596{ 1597 bb->flags |= BB_MODIFIED; 1598 if (df) 1599 { 1600 int p; 1601 for (p = 1; p < df->num_problems_defined; p++) 1602 { 1603 struct dataflow *dflow = df->problems_in_order[p]; 1604 if (dflow->out_of_date_transfer_functions) 1605 bitmap_set_bit (dflow->out_of_date_transfer_functions, bb->index); 1606 } 1607 df_mark_solutions_dirty (); 1608 } 1609} 1610 1611 1612/* Grow the bb_info array. */ 1613 1614void 1615df_grow_bb_info (struct dataflow *dflow) 1616{ 1617 unsigned int new_size = last_basic_block_for_fn (cfun) + 1; 1618 if (dflow->block_info_size < new_size) 1619 { 1620 new_size += new_size / 4; 1621 dflow->block_info 1622 = (void *)XRESIZEVEC (char, (char *)dflow->block_info, 1623 new_size 1624 * dflow->problem->block_info_elt_size); 1625 memset ((char *)dflow->block_info 1626 + dflow->block_info_size 1627 * dflow->problem->block_info_elt_size, 1628 0, 1629 (new_size - dflow->block_info_size) 1630 * dflow->problem->block_info_elt_size); 1631 dflow->block_info_size = new_size; 1632 } 1633} 1634 1635 1636/* Clear the dirty bits. This is called from places that delete 1637 blocks. */ 1638static void 1639df_clear_bb_dirty (basic_block bb) 1640{ 1641 int p; 1642 for (p = 1; p < df->num_problems_defined; p++) 1643 { 1644 struct dataflow *dflow = df->problems_in_order[p]; 1645 if (dflow->out_of_date_transfer_functions) 1646 bitmap_clear_bit (dflow->out_of_date_transfer_functions, bb->index); 1647 } 1648} 1649 1650/* Called from the rtl_compact_blocks to reorganize the problems basic 1651 block info. */ 1652 1653void 1654df_compact_blocks (void) 1655{ 1656 int i, p; 1657 basic_block bb; 1658 void *problem_temps; 1659 bitmap_head tmp; 1660 1661 bitmap_initialize (&tmp, &df_bitmap_obstack); 1662 for (p = 0; p < df->num_problems_defined; p++) 1663 { 1664 struct dataflow *dflow = df->problems_in_order[p]; 1665 1666 /* Need to reorganize the out_of_date_transfer_functions for the 1667 dflow problem. */ 1668 if (dflow->out_of_date_transfer_functions) 1669 { 1670 bitmap_copy (&tmp, dflow->out_of_date_transfer_functions); 1671 bitmap_clear (dflow->out_of_date_transfer_functions); 1672 if (bitmap_bit_p (&tmp, ENTRY_BLOCK)) 1673 bitmap_set_bit (dflow->out_of_date_transfer_functions, ENTRY_BLOCK); 1674 if (bitmap_bit_p (&tmp, EXIT_BLOCK)) 1675 bitmap_set_bit (dflow->out_of_date_transfer_functions, EXIT_BLOCK); 1676 1677 i = NUM_FIXED_BLOCKS; 1678 FOR_EACH_BB_FN (bb, cfun) 1679 { 1680 if (bitmap_bit_p (&tmp, bb->index)) 1681 bitmap_set_bit (dflow->out_of_date_transfer_functions, i); 1682 i++; 1683 } 1684 } 1685 1686 /* Now shuffle the block info for the problem. */ 1687 if (dflow->problem->free_bb_fun) 1688 { 1689 int size = (last_basic_block_for_fn (cfun) 1690 * dflow->problem->block_info_elt_size); 1691 problem_temps = XNEWVAR (char, size); 1692 df_grow_bb_info (dflow); 1693 memcpy (problem_temps, dflow->block_info, size); 1694 1695 /* Copy the bb info from the problem tmps to the proper 1696 place in the block_info vector. Null out the copied 1697 item. The entry and exit blocks never move. */ 1698 i = NUM_FIXED_BLOCKS; 1699 FOR_EACH_BB_FN (bb, cfun) 1700 { 1701 df_set_bb_info (dflow, i, 1702 (char *)problem_temps 1703 + bb->index * dflow->problem->block_info_elt_size); 1704 i++; 1705 } 1706 memset ((char *)dflow->block_info 1707 + i * dflow->problem->block_info_elt_size, 0, 1708 (last_basic_block_for_fn (cfun) - i) 1709 * dflow->problem->block_info_elt_size); 1710 free (problem_temps); 1711 } 1712 } 1713 1714 /* Shuffle the bits in the basic_block indexed arrays. */ 1715 1716 if (df->blocks_to_analyze) 1717 { 1718 if (bitmap_bit_p (&tmp, ENTRY_BLOCK)) 1719 bitmap_set_bit (df->blocks_to_analyze, ENTRY_BLOCK); 1720 if (bitmap_bit_p (&tmp, EXIT_BLOCK)) 1721 bitmap_set_bit (df->blocks_to_analyze, EXIT_BLOCK); 1722 bitmap_copy (&tmp, df->blocks_to_analyze); 1723 bitmap_clear (df->blocks_to_analyze); 1724 i = NUM_FIXED_BLOCKS; 1725 FOR_EACH_BB_FN (bb, cfun) 1726 { 1727 if (bitmap_bit_p (&tmp, bb->index)) 1728 bitmap_set_bit (df->blocks_to_analyze, i); 1729 i++; 1730 } 1731 } 1732 1733 bitmap_clear (&tmp); 1734 1735 i = NUM_FIXED_BLOCKS; 1736 FOR_EACH_BB_FN (bb, cfun) 1737 { 1738 SET_BASIC_BLOCK_FOR_FN (cfun, i, bb); 1739 bb->index = i; 1740 i++; 1741 } 1742 1743 gcc_assert (i == n_basic_blocks_for_fn (cfun)); 1744 1745 for (; i < last_basic_block_for_fn (cfun); i++) 1746 SET_BASIC_BLOCK_FOR_FN (cfun, i, NULL); 1747 1748#ifdef DF_DEBUG_CFG 1749 if (!df_lr->solutions_dirty) 1750 df_set_clean_cfg (); 1751#endif 1752} 1753 1754 1755/* Shove NEW_BLOCK in at OLD_INDEX. Called from ifcvt to hack a 1756 block. There is no excuse for people to do this kind of thing. */ 1757 1758void 1759df_bb_replace (int old_index, basic_block new_block) 1760{ 1761 int new_block_index = new_block->index; 1762 int p; 1763 1764 if (dump_file) 1765 fprintf (dump_file, "shoving block %d into %d\n", new_block_index, old_index); 1766 1767 gcc_assert (df); 1768 gcc_assert (BASIC_BLOCK_FOR_FN (cfun, old_index) == NULL); 1769 1770 for (p = 0; p < df->num_problems_defined; p++) 1771 { 1772 struct dataflow *dflow = df->problems_in_order[p]; 1773 if (dflow->block_info) 1774 { 1775 df_grow_bb_info (dflow); 1776 df_set_bb_info (dflow, old_index, 1777 df_get_bb_info (dflow, new_block_index)); 1778 } 1779 } 1780 1781 df_clear_bb_dirty (new_block); 1782 SET_BASIC_BLOCK_FOR_FN (cfun, old_index, new_block); 1783 new_block->index = old_index; 1784 df_set_bb_dirty (BASIC_BLOCK_FOR_FN (cfun, old_index)); 1785 SET_BASIC_BLOCK_FOR_FN (cfun, new_block_index, NULL); 1786} 1787 1788 1789/* Free all of the per basic block dataflow from all of the problems. 1790 This is typically called before a basic block is deleted and the 1791 problem will be reanalyzed. */ 1792 1793void 1794df_bb_delete (int bb_index) 1795{ 1796 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index); 1797 int i; 1798 1799 if (!df) 1800 return; 1801 1802 for (i = 0; i < df->num_problems_defined; i++) 1803 { 1804 struct dataflow *dflow = df->problems_in_order[i]; 1805 if (dflow->problem->free_bb_fun) 1806 { 1807 void *bb_info = df_get_bb_info (dflow, bb_index); 1808 if (bb_info) 1809 { 1810 dflow->problem->free_bb_fun (bb, bb_info); 1811 df_clear_bb_info (dflow, bb_index); 1812 } 1813 } 1814 } 1815 df_clear_bb_dirty (bb); 1816 df_mark_solutions_dirty (); 1817} 1818 1819 1820/* Verify that there is a place for everything and everything is in 1821 its place. This is too expensive to run after every pass in the 1822 mainline. However this is an excellent debugging tool if the 1823 dataflow information is not being updated properly. You can just 1824 sprinkle calls in until you find the place that is changing an 1825 underlying structure without calling the proper updating 1826 routine. */ 1827 1828void 1829df_verify (void) 1830{ 1831 df_scan_verify (); 1832#ifdef ENABLE_DF_CHECKING 1833 df_lr_verify_transfer_functions (); 1834 if (df_live) 1835 df_live_verify_transfer_functions (); 1836#endif 1837 df->changeable_flags &= ~DF_VERIFY_SCHEDULED; 1838} 1839 1840#ifdef DF_DEBUG_CFG 1841 1842/* Compute an array of ints that describes the cfg. This can be used 1843 to discover places where the cfg is modified by the appropriate 1844 calls have not been made to the keep df informed. The internals of 1845 this are unexciting, the key is that two instances of this can be 1846 compared to see if any changes have been made to the cfg. */ 1847 1848static int * 1849df_compute_cfg_image (void) 1850{ 1851 basic_block bb; 1852 int size = 2 + (2 * n_basic_blocks_for_fn (cfun)); 1853 int i; 1854 int * map; 1855 1856 FOR_ALL_BB_FN (bb, cfun) 1857 { 1858 size += EDGE_COUNT (bb->succs); 1859 } 1860 1861 map = XNEWVEC (int, size); 1862 map[0] = size; 1863 i = 1; 1864 FOR_ALL_BB_FN (bb, cfun) 1865 { 1866 edge_iterator ei; 1867 edge e; 1868 1869 map[i++] = bb->index; 1870 FOR_EACH_EDGE (e, ei, bb->succs) 1871 map[i++] = e->dest->index; 1872 map[i++] = -1; 1873 } 1874 map[i] = -1; 1875 return map; 1876} 1877 1878static int *saved_cfg = NULL; 1879 1880 1881/* This function compares the saved version of the cfg with the 1882 current cfg and aborts if the two are identical. The function 1883 silently returns if the cfg has been marked as dirty or the two are 1884 the same. */ 1885 1886void 1887df_check_cfg_clean (void) 1888{ 1889 int *new_map; 1890 1891 if (!df) 1892 return; 1893 1894 if (df_lr->solutions_dirty) 1895 return; 1896 1897 if (saved_cfg == NULL) 1898 return; 1899 1900 new_map = df_compute_cfg_image (); 1901 gcc_assert (memcmp (saved_cfg, new_map, saved_cfg[0] * sizeof (int)) == 0); 1902 free (new_map); 1903} 1904 1905 1906/* This function builds a cfg fingerprint and squirrels it away in 1907 saved_cfg. */ 1908 1909static void 1910df_set_clean_cfg (void) 1911{ 1912 free (saved_cfg); 1913 saved_cfg = df_compute_cfg_image (); 1914} 1915 1916#endif /* DF_DEBUG_CFG */ 1917/*---------------------------------------------------------------------------- 1918 PUBLIC INTERFACES TO QUERY INFORMATION. 1919----------------------------------------------------------------------------*/ 1920 1921 1922/* Return first def of REGNO within BB. */ 1923 1924df_ref 1925df_bb_regno_first_def_find (basic_block bb, unsigned int regno) 1926{ 1927 rtx_insn *insn; 1928 df_ref def; 1929 1930 FOR_BB_INSNS (bb, insn) 1931 { 1932 if (!INSN_P (insn)) 1933 continue; 1934 1935 FOR_EACH_INSN_DEF (def, insn) 1936 if (DF_REF_REGNO (def) == regno) 1937 return def; 1938 } 1939 return NULL; 1940} 1941 1942 1943/* Return last def of REGNO within BB. */ 1944 1945df_ref 1946df_bb_regno_last_def_find (basic_block bb, unsigned int regno) 1947{ 1948 rtx_insn *insn; 1949 df_ref def; 1950 1951 FOR_BB_INSNS_REVERSE (bb, insn) 1952 { 1953 if (!INSN_P (insn)) 1954 continue; 1955 1956 FOR_EACH_INSN_DEF (def, insn) 1957 if (DF_REF_REGNO (def) == regno) 1958 return def; 1959 } 1960 1961 return NULL; 1962} 1963 1964/* Finds the reference corresponding to the definition of REG in INSN. 1965 DF is the dataflow object. */ 1966 1967df_ref 1968df_find_def (rtx_insn *insn, rtx reg) 1969{ 1970 df_ref def; 1971 1972 if (GET_CODE (reg) == SUBREG) 1973 reg = SUBREG_REG (reg); 1974 gcc_assert (REG_P (reg)); 1975 1976 FOR_EACH_INSN_DEF (def, insn) 1977 if (DF_REF_REGNO (def) == REGNO (reg)) 1978 return def; 1979 1980 return NULL; 1981} 1982 1983 1984/* Return true if REG is defined in INSN, zero otherwise. */ 1985 1986bool 1987df_reg_defined (rtx_insn *insn, rtx reg) 1988{ 1989 return df_find_def (insn, reg) != NULL; 1990} 1991 1992 1993/* Finds the reference corresponding to the use of REG in INSN. 1994 DF is the dataflow object. */ 1995 1996df_ref 1997df_find_use (rtx_insn *insn, rtx reg) 1998{ 1999 df_ref use; 2000 2001 if (GET_CODE (reg) == SUBREG) 2002 reg = SUBREG_REG (reg); 2003 gcc_assert (REG_P (reg)); 2004 2005 df_insn_info *insn_info = DF_INSN_INFO_GET (insn); 2006 FOR_EACH_INSN_INFO_USE (use, insn_info) 2007 if (DF_REF_REGNO (use) == REGNO (reg)) 2008 return use; 2009 if (df->changeable_flags & DF_EQ_NOTES) 2010 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info) 2011 if (DF_REF_REGNO (use) == REGNO (reg)) 2012 return use; 2013 return NULL; 2014} 2015 2016 2017/* Return true if REG is referenced in INSN, zero otherwise. */ 2018 2019bool 2020df_reg_used (rtx_insn *insn, rtx reg) 2021{ 2022 return df_find_use (insn, reg) != NULL; 2023} 2024 2025 2026/*---------------------------------------------------------------------------- 2027 Debugging and printing functions. 2028----------------------------------------------------------------------------*/ 2029 2030/* Write information about registers and basic blocks into FILE. 2031 This is part of making a debugging dump. */ 2032 2033void 2034dump_regset (regset r, FILE *outf) 2035{ 2036 unsigned i; 2037 reg_set_iterator rsi; 2038 2039 if (r == NULL) 2040 { 2041 fputs (" (nil)", outf); 2042 return; 2043 } 2044 2045 EXECUTE_IF_SET_IN_REG_SET (r, 0, i, rsi) 2046 { 2047 fprintf (outf, " %d", i); 2048 if (i < FIRST_PSEUDO_REGISTER) 2049 fprintf (outf, " [%s]", 2050 reg_names[i]); 2051 } 2052} 2053 2054/* Print a human-readable representation of R on the standard error 2055 stream. This function is designed to be used from within the 2056 debugger. */ 2057extern void debug_regset (regset); 2058DEBUG_FUNCTION void 2059debug_regset (regset r) 2060{ 2061 dump_regset (r, stderr); 2062 putc ('\n', stderr); 2063} 2064 2065/* Write information about registers and basic blocks into FILE. 2066 This is part of making a debugging dump. */ 2067 2068void 2069df_print_regset (FILE *file, bitmap r) 2070{ 2071 unsigned int i; 2072 bitmap_iterator bi; 2073 2074 if (r == NULL) 2075 fputs (" (nil)", file); 2076 else 2077 { 2078 EXECUTE_IF_SET_IN_BITMAP (r, 0, i, bi) 2079 { 2080 fprintf (file, " %d", i); 2081 if (i < FIRST_PSEUDO_REGISTER) 2082 fprintf (file, " [%s]", reg_names[i]); 2083 } 2084 } 2085 fprintf (file, "\n"); 2086} 2087 2088 2089/* Write information about registers and basic blocks into FILE. The 2090 bitmap is in the form used by df_byte_lr. This is part of making a 2091 debugging dump. */ 2092 2093void 2094df_print_word_regset (FILE *file, bitmap r) 2095{ 2096 unsigned int max_reg = max_reg_num (); 2097 2098 if (r == NULL) 2099 fputs (" (nil)", file); 2100 else 2101 { 2102 unsigned int i; 2103 for (i = FIRST_PSEUDO_REGISTER; i < max_reg; i++) 2104 { 2105 bool found = (bitmap_bit_p (r, 2 * i) 2106 || bitmap_bit_p (r, 2 * i + 1)); 2107 if (found) 2108 { 2109 int word; 2110 const char * sep = ""; 2111 fprintf (file, " %d", i); 2112 fprintf (file, "("); 2113 for (word = 0; word < 2; word++) 2114 if (bitmap_bit_p (r, 2 * i + word)) 2115 { 2116 fprintf (file, "%s%d", sep, word); 2117 sep = ", "; 2118 } 2119 fprintf (file, ")"); 2120 } 2121 } 2122 } 2123 fprintf (file, "\n"); 2124} 2125 2126 2127/* Dump dataflow info. */ 2128 2129void 2130df_dump (FILE *file) 2131{ 2132 basic_block bb; 2133 df_dump_start (file); 2134 2135 FOR_ALL_BB_FN (bb, cfun) 2136 { 2137 df_print_bb_index (bb, file); 2138 df_dump_top (bb, file); 2139 df_dump_bottom (bb, file); 2140 } 2141 2142 fprintf (file, "\n"); 2143} 2144 2145 2146/* Dump dataflow info for df->blocks_to_analyze. */ 2147 2148void 2149df_dump_region (FILE *file) 2150{ 2151 if (df->blocks_to_analyze) 2152 { 2153 bitmap_iterator bi; 2154 unsigned int bb_index; 2155 2156 fprintf (file, "\n\nstarting region dump\n"); 2157 df_dump_start (file); 2158 2159 EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi) 2160 { 2161 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index); 2162 dump_bb (file, bb, 0, TDF_DETAILS); 2163 } 2164 fprintf (file, "\n"); 2165 } 2166 else 2167 df_dump (file); 2168} 2169 2170 2171/* Dump the introductory information for each problem defined. */ 2172 2173void 2174df_dump_start (FILE *file) 2175{ 2176 int i; 2177 2178 if (!df || !file) 2179 return; 2180 2181 fprintf (file, "\n\n%s\n", current_function_name ()); 2182 fprintf (file, "\nDataflow summary:\n"); 2183 if (df->blocks_to_analyze) 2184 fprintf (file, "def_info->table_size = %d, use_info->table_size = %d\n", 2185 DF_DEFS_TABLE_SIZE (), DF_USES_TABLE_SIZE ()); 2186 2187 for (i = 0; i < df->num_problems_defined; i++) 2188 { 2189 struct dataflow *dflow = df->problems_in_order[i]; 2190 if (dflow->computed) 2191 { 2192 df_dump_problem_function fun = dflow->problem->dump_start_fun; 2193 if (fun) 2194 fun (file); 2195 } 2196 } 2197} 2198 2199 2200/* Dump the top or bottom of the block information for BB. */ 2201static void 2202df_dump_bb_problem_data (basic_block bb, FILE *file, bool top) 2203{ 2204 int i; 2205 2206 if (!df || !file) 2207 return; 2208 2209 for (i = 0; i < df->num_problems_defined; i++) 2210 { 2211 struct dataflow *dflow = df->problems_in_order[i]; 2212 if (dflow->computed) 2213 { 2214 df_dump_bb_problem_function bbfun; 2215 2216 if (top) 2217 bbfun = dflow->problem->dump_top_fun; 2218 else 2219 bbfun = dflow->problem->dump_bottom_fun; 2220 2221 if (bbfun) 2222 bbfun (bb, file); 2223 } 2224 } 2225} 2226 2227/* Dump the top of the block information for BB. */ 2228 2229void 2230df_dump_top (basic_block bb, FILE *file) 2231{ 2232 df_dump_bb_problem_data (bb, file, /*top=*/true); 2233} 2234 2235/* Dump the bottom of the block information for BB. */ 2236 2237void 2238df_dump_bottom (basic_block bb, FILE *file) 2239{ 2240 df_dump_bb_problem_data (bb, file, /*top=*/false); 2241} 2242 2243 2244/* Dump information about INSN just before or after dumping INSN itself. */ 2245static void 2246df_dump_insn_problem_data (const rtx_insn *insn, FILE *file, bool top) 2247{ 2248 int i; 2249 2250 if (!df || !file) 2251 return; 2252 2253 for (i = 0; i < df->num_problems_defined; i++) 2254 { 2255 struct dataflow *dflow = df->problems_in_order[i]; 2256 if (dflow->computed) 2257 { 2258 df_dump_insn_problem_function insnfun; 2259 2260 if (top) 2261 insnfun = dflow->problem->dump_insn_top_fun; 2262 else 2263 insnfun = dflow->problem->dump_insn_bottom_fun; 2264 2265 if (insnfun) 2266 insnfun (insn, file); 2267 } 2268 } 2269} 2270 2271/* Dump information about INSN before dumping INSN itself. */ 2272 2273void 2274df_dump_insn_top (const rtx_insn *insn, FILE *file) 2275{ 2276 df_dump_insn_problem_data (insn, file, /*top=*/true); 2277} 2278 2279/* Dump information about INSN after dumping INSN itself. */ 2280 2281void 2282df_dump_insn_bottom (const rtx_insn *insn, FILE *file) 2283{ 2284 df_dump_insn_problem_data (insn, file, /*top=*/false); 2285} 2286 2287 2288static void 2289df_ref_dump (df_ref ref, FILE *file) 2290{ 2291 fprintf (file, "%c%d(%d)", 2292 DF_REF_REG_DEF_P (ref) 2293 ? 'd' 2294 : (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE) ? 'e' : 'u', 2295 DF_REF_ID (ref), 2296 DF_REF_REGNO (ref)); 2297} 2298 2299void 2300df_refs_chain_dump (df_ref ref, bool follow_chain, FILE *file) 2301{ 2302 fprintf (file, "{ "); 2303 for (; ref; ref = DF_REF_NEXT_LOC (ref)) 2304 { 2305 df_ref_dump (ref, file); 2306 if (follow_chain) 2307 df_chain_dump (DF_REF_CHAIN (ref), file); 2308 } 2309 fprintf (file, "}"); 2310} 2311 2312 2313/* Dump either a ref-def or reg-use chain. */ 2314 2315void 2316df_regs_chain_dump (df_ref ref, FILE *file) 2317{ 2318 fprintf (file, "{ "); 2319 while (ref) 2320 { 2321 df_ref_dump (ref, file); 2322 ref = DF_REF_NEXT_REG (ref); 2323 } 2324 fprintf (file, "}"); 2325} 2326 2327 2328static void 2329df_mws_dump (struct df_mw_hardreg *mws, FILE *file) 2330{ 2331 for (; mws; mws = DF_MWS_NEXT (mws)) 2332 fprintf (file, "mw %c r[%d..%d]\n", 2333 DF_MWS_REG_DEF_P (mws) ? 'd' : 'u', 2334 mws->start_regno, mws->end_regno); 2335} 2336 2337 2338static void 2339df_insn_uid_debug (unsigned int uid, 2340 bool follow_chain, FILE *file) 2341{ 2342 fprintf (file, "insn %d luid %d", 2343 uid, DF_INSN_UID_LUID (uid)); 2344 2345 if (DF_INSN_UID_DEFS (uid)) 2346 { 2347 fprintf (file, " defs "); 2348 df_refs_chain_dump (DF_INSN_UID_DEFS (uid), follow_chain, file); 2349 } 2350 2351 if (DF_INSN_UID_USES (uid)) 2352 { 2353 fprintf (file, " uses "); 2354 df_refs_chain_dump (DF_INSN_UID_USES (uid), follow_chain, file); 2355 } 2356 2357 if (DF_INSN_UID_EQ_USES (uid)) 2358 { 2359 fprintf (file, " eq uses "); 2360 df_refs_chain_dump (DF_INSN_UID_EQ_USES (uid), follow_chain, file); 2361 } 2362 2363 if (DF_INSN_UID_MWS (uid)) 2364 { 2365 fprintf (file, " mws "); 2366 df_mws_dump (DF_INSN_UID_MWS (uid), file); 2367 } 2368 fprintf (file, "\n"); 2369} 2370 2371 2372DEBUG_FUNCTION void 2373df_insn_debug (rtx_insn *insn, bool follow_chain, FILE *file) 2374{ 2375 df_insn_uid_debug (INSN_UID (insn), follow_chain, file); 2376} 2377 2378DEBUG_FUNCTION void 2379df_insn_debug_regno (rtx_insn *insn, FILE *file) 2380{ 2381 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn); 2382 2383 fprintf (file, "insn %d bb %d luid %d defs ", 2384 INSN_UID (insn), BLOCK_FOR_INSN (insn)->index, 2385 DF_INSN_INFO_LUID (insn_info)); 2386 df_refs_chain_dump (DF_INSN_INFO_DEFS (insn_info), false, file); 2387 2388 fprintf (file, " uses "); 2389 df_refs_chain_dump (DF_INSN_INFO_USES (insn_info), false, file); 2390 2391 fprintf (file, " eq_uses "); 2392 df_refs_chain_dump (DF_INSN_INFO_EQ_USES (insn_info), false, file); 2393 fprintf (file, "\n"); 2394} 2395 2396DEBUG_FUNCTION void 2397df_regno_debug (unsigned int regno, FILE *file) 2398{ 2399 fprintf (file, "reg %d defs ", regno); 2400 df_regs_chain_dump (DF_REG_DEF_CHAIN (regno), file); 2401 fprintf (file, " uses "); 2402 df_regs_chain_dump (DF_REG_USE_CHAIN (regno), file); 2403 fprintf (file, " eq_uses "); 2404 df_regs_chain_dump (DF_REG_EQ_USE_CHAIN (regno), file); 2405 fprintf (file, "\n"); 2406} 2407 2408 2409DEBUG_FUNCTION void 2410df_ref_debug (df_ref ref, FILE *file) 2411{ 2412 fprintf (file, "%c%d ", 2413 DF_REF_REG_DEF_P (ref) ? 'd' : 'u', 2414 DF_REF_ID (ref)); 2415 fprintf (file, "reg %d bb %d insn %d flag %#x type %#x ", 2416 DF_REF_REGNO (ref), 2417 DF_REF_BBNO (ref), 2418 DF_REF_IS_ARTIFICIAL (ref) ? -1 : DF_REF_INSN_UID (ref), 2419 DF_REF_FLAGS (ref), 2420 DF_REF_TYPE (ref)); 2421 if (DF_REF_LOC (ref)) 2422 { 2423 if (flag_dump_noaddr) 2424 fprintf (file, "loc #(#) chain "); 2425 else 2426 fprintf (file, "loc %p(%p) chain ", (void *)DF_REF_LOC (ref), 2427 (void *)*DF_REF_LOC (ref)); 2428 } 2429 else 2430 fprintf (file, "chain "); 2431 df_chain_dump (DF_REF_CHAIN (ref), file); 2432 fprintf (file, "\n"); 2433} 2434 2435/* Functions for debugging from GDB. */ 2436 2437DEBUG_FUNCTION void 2438debug_df_insn (rtx_insn *insn) 2439{ 2440 df_insn_debug (insn, true, stderr); 2441 debug_rtx (insn); 2442} 2443 2444 2445DEBUG_FUNCTION void 2446debug_df_reg (rtx reg) 2447{ 2448 df_regno_debug (REGNO (reg), stderr); 2449} 2450 2451 2452DEBUG_FUNCTION void 2453debug_df_regno (unsigned int regno) 2454{ 2455 df_regno_debug (regno, stderr); 2456} 2457 2458 2459DEBUG_FUNCTION void 2460debug_df_ref (df_ref ref) 2461{ 2462 df_ref_debug (ref, stderr); 2463} 2464 2465 2466DEBUG_FUNCTION void 2467debug_df_defno (unsigned int defno) 2468{ 2469 df_ref_debug (DF_DEFS_GET (defno), stderr); 2470} 2471 2472 2473DEBUG_FUNCTION void 2474debug_df_useno (unsigned int defno) 2475{ 2476 df_ref_debug (DF_USES_GET (defno), stderr); 2477} 2478 2479 2480DEBUG_FUNCTION void 2481debug_df_chain (struct df_link *link) 2482{ 2483 df_chain_dump (link, stderr); 2484 fputc ('\n', stderr); 2485} 2486