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