1169689Skan/* Allocation for dataflow support routines. 2169689Skan Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006 3169689Skan Free Software Foundation, Inc. 4169689Skan Originally contributed by Michael P. Hayes 5169689Skan (m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com) 6169689Skan Major rewrite contributed by Danny Berlin (dberlin@dberlin.org) 7169689Skan and Kenneth Zadeck (zadeck@naturalbridge.com). 8169689Skan 9169689SkanThis file is part of GCC. 10169689Skan 11169689SkanGCC is free software; you can redistribute it and/or modify it under 12169689Skanthe terms of the GNU General Public License as published by the Free 13169689SkanSoftware Foundation; either version 2, or (at your option) any later 14169689Skanversion. 15169689Skan 16169689SkanGCC is distributed in the hope that it will be useful, but WITHOUT ANY 17169689SkanWARRANTY; without even the implied warranty of MERCHANTABILITY or 18169689SkanFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 19169689Skanfor more details. 20169689Skan 21169689SkanYou should have received a copy of the GNU General Public License 22169689Skanalong with GCC; see the file COPYING. If not, write to the Free 23169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 24169689Skan02110-1301, USA. 25169689Skan*/ 26169689Skan 27169689Skan/* 28169689SkanOVERVIEW: 29169689Skan 30169689SkanThe files in this collection (df*.c,df.h) provide a general framework 31169689Skanfor solving dataflow problems. The global dataflow is performed using 32169689Skana good implementation of iterative dataflow analysis. 33169689Skan 34169689SkanThe file df-problems.c provides problem instance for the most common 35169689Skandataflow problems: reaching defs, upward exposed uses, live variables, 36169689Skanuninitialized variables, def-use chains, and use-def chains. However, 37169689Skanthe interface allows other dataflow problems to be defined as well. 38169689Skan 39169689Skan 40169689SkanUSAGE: 41169689Skan 42169689SkanHere is an example of using the dataflow routines. 43169689Skan 44169689Skan struct df *df; 45169689Skan 46169689Skan df = df_init (init_flags); 47169689Skan 48169689Skan df_add_problem (df, problem, flags); 49169689Skan 50169689Skan df_set_blocks (df, blocks); 51169689Skan 52169689Skan df_rescan_blocks (df, blocks); 53169689Skan 54169689Skan df_analyze (df); 55169689Skan 56169689Skan df_dump (df, stderr); 57169689Skan 58169689Skan df_finish (df); 59169689Skan 60169689Skan 61169689Skan 62169689SkanDF_INIT simply creates a poor man's object (df) that needs to be 63169689Skanpassed to all the dataflow routines. df_finish destroys this object 64169689Skanand frees up any allocated memory. 65169689Skan 66169689SkanThere are three flags that can be passed to df_init, each of these 67169689Skanflags controls the scanning of the rtl: 68169689Skan 69169689SkanDF_HARD_REGS means that the scanning is to build information about 70169689Skanboth pseudo registers and hardware registers. Without this 71169689Skaninformation, the problems will be solved only on pseudo registers. 72169689SkanDF_EQUIV_NOTES marks the uses present in EQUIV/EQUAL notes. 73169689SkanDF_SUBREGS return subregs rather than the inner reg. 74169689Skan 75169689Skan 76169689SkanDF_ADD_PROBLEM adds a problem, defined by an instance to struct 77169689Skandf_problem, to the set of problems solved in this instance of df. All 78169689Skancalls to add a problem for a given instance of df must occur before 79169689Skanthe first call to DF_RESCAN_BLOCKS, DF_SET_BLOCKS or DF_ANALYZE. 80169689Skan 81169689SkanFor all of the problems defined in df-problems.c, there are 82169689Skanconvenience functions named DF_*_ADD_PROBLEM. 83169689Skan 84169689Skan 85169689SkanProblems can be dependent on other problems. For instance, solving 86169689Skandef-use or use-def chains is dependent on solving reaching 87169689Skandefinitions. As long as these dependencies are listed in the problem 88169689Skandefinition, the order of adding the problems is not material. 89169689SkanOtherwise, the problems will be solved in the order of calls to 90169689Skandf_add_problem. Note that it is not necessary to have a problem. In 91169689Skanthat case, df will just be used to do the scanning. 92169689Skan 93169689Skan 94169689Skan 95169689SkanDF_SET_BLOCKS is an optional call used to define a region of the 96169689Skanfunction on which the analysis will be performed. The normal case is 97169689Skanto analyze the entire function and no call to df_set_blocks is made. 98169689Skan 99169689SkanWhen a subset is given, the analysis behaves as if the function only 100169689Skancontains those blocks and any edges that occur directly between the 101169689Skanblocks in the set. Care should be taken to call df_set_blocks right 102169689Skanbefore the call to analyze in order to eliminate the possibility that 103169689Skanoptimizations that reorder blocks invalidate the bitvector. 104169689Skan 105169689Skan 106169689Skan 107169689SkanDF_RESCAN_BLOCKS is an optional call that causes the scanner to be 108169689Skan (re)run over the set of blocks passed in. If blocks is NULL, the entire 109169689Skanfunction (or all of the blocks defined in df_set_blocks) is rescanned. 110169689SkanIf blocks contains blocks that were not defined in the call to 111169689Skandf_set_blocks, these blocks are added to the set of blocks. 112169689Skan 113169689Skan 114169689SkanDF_ANALYZE causes all of the defined problems to be (re)solved. It 115169689Skandoes not cause blocks to be (re)scanned at the rtl level unless no 116169689Skanprior call is made to df_rescan_blocks. When DF_ANALYZE is completes, 117169689Skanthe IN and OUT sets for each basic block contain the computer 118169689Skaninformation. The DF_*_BB_INFO macros can be used to access these 119169689Skanbitvectors. 120169689Skan 121169689Skan 122169689SkanDF_DUMP can then be called to dump the information produce to some 123169689Skanfile. 124169689Skan 125169689Skan 126169689Skan 127169689SkanDF_FINISH causes all of the datastructures to be cleaned up and freed. 128169689SkanThe df_instance is also freed and its pointer should be NULLed. 129169689Skan 130169689Skan 131169689Skan 132169689Skan 133169689SkanScanning produces a `struct df_ref' data structure (ref) is allocated 134169689Skanfor every register reference (def or use) and this records the insn 135169689Skanand bb the ref is found within. The refs are linked together in 136169689Skanchains of uses and defs for each insn and for each register. Each ref 137169689Skanalso has a chain field that links all the use refs for a def or all 138169689Skanthe def refs for a use. This is used to create use-def or def-use 139169689Skanchains. 140169689Skan 141169689SkanDifferent optimizations have different needs. Ultimately, only 142169689Skanregister allocation and schedulers should be using the bitmaps 143169689Skanproduced for the live register and uninitialized register problems. 144169689SkanThe rest of the backend should be upgraded to using and maintaining 145169689Skanthe linked information such as def use or use def chains. 146169689Skan 147169689Skan 148169689Skan 149169689SkanPHILOSOPHY: 150169689Skan 151169689SkanWhile incremental bitmaps are not worthwhile to maintain, incremental 152169689Skanchains may be perfectly reasonable. The fastest way to build chains 153169689Skanfrom scratch or after significant modifications is to build reaching 154169689Skandefinitions (RD) and build the chains from this. 155169689Skan 156169689SkanHowever, general algorithms for maintaining use-def or def-use chains 157169689Skanare not practical. The amount of work to recompute the chain any 158169689Skanchain after an arbitrary change is large. However, with a modest 159169689Skanamount of work it is generally possible to have the application that 160169689Skanuses the chains keep them up to date. The high level knowledge of 161169689Skanwhat is really happening is essential to crafting efficient 162169689Skanincremental algorithms. 163169689Skan 164169689SkanAs for the bit vector problems, there is no interface to give a set of 165169689Skanblocks over with to resolve the iteration. In general, restarting a 166169689Skandataflow iteration is difficult and expensive. Again, the best way to 167169689Skankeep the dataflow information up to data (if this is really what is 168169689Skanneeded) it to formulate a problem specific solution. 169169689Skan 170169689SkanThere are fine grained calls for creating and deleting references from 171169689Skaninstructions in df-scan.c. However, these are not currently connected 172169689Skanto the engine that resolves the dataflow equations. 173169689Skan 174169689Skan 175169689SkanDATA STRUCTURES: 176169689Skan 177169689SkanThe basic object is a DF_REF (reference) and this may either be a 178169689SkanDEF (definition) or a USE of a register. 179169689Skan 180169689SkanThese are linked into a variety of lists; namely reg-def, reg-use, 181169689Skaninsn-def, insn-use, def-use, and use-def lists. For example, the 182169689Skanreg-def lists contain all the locations that define a given register 183169689Skanwhile the insn-use lists contain all the locations that use a 184169689Skanregister. 185169689Skan 186169689SkanNote that the reg-def and reg-use chains are generally short for 187169689Skanpseudos and long for the hard registers. 188169689Skan 189169689SkanACCESSING REFS: 190169689Skan 191169689SkanThere are 4 ways to obtain access to refs: 192169689Skan 193169689Skan1) References are divided into two categories, REAL and ARTIFICIAL. 194169689Skan 195169689Skan REAL refs are associated with instructions. They are linked into 196169689Skan either in the insn's defs list (accessed by the DF_INSN_DEFS or 197169689Skan DF_INSN_UID_DEFS macros) or the insn's uses list (accessed by the 198169689Skan DF_INSN_USES or DF_INSN_UID_USES macros). These macros produce a 199169689Skan ref (or NULL), the rest of the list can be obtained by traversal of 200169689Skan the NEXT_REF field (accessed by the DF_REF_NEXT_REF macro.) There 201169689Skan is no significance to the ordering of the uses or refs in an 202169689Skan instruction. 203169689Skan 204169689Skan ARTIFICIAL refs are associated with basic blocks. The heads of 205169689Skan these lists can be accessed by calling get_artificial_defs or 206169689Skan get_artificial_uses for the particular basic block. Artificial 207169689Skan defs and uses are only there if DF_HARD_REGS was specified when the 208169689Skan df instance was created. 209169689Skan 210169689Skan Artificial defs and uses occur both at the beginning and ends of blocks. 211169689Skan 212169689Skan For blocks that area at the destination of eh edges, the 213169689Skan artificial uses and defs occur at the beginning. The defs relate 214169689Skan to the registers specified in EH_RETURN_DATA_REGNO and the uses 215169689Skan relate to the registers specified in ED_USES. Logically these 216169689Skan defs and uses should really occur along the eh edge, but there is 217169689Skan no convenient way to do this. Artificial edges that occur at the 218169689Skan beginning of the block have the DF_REF_AT_TOP flag set. 219169689Skan 220169689Skan Artificial uses occur at the end of all blocks. These arise from 221169689Skan the hard registers that are always live, such as the stack 222169689Skan register and are put there to keep the code from forgetting about 223169689Skan them. 224169689Skan 225169689Skan Artificial defs occur at the end of the entry block. These arise 226169689Skan from registers that are live at entry to the function. 227169689Skan 228169689Skan2) All of the uses and defs associated with each pseudo or hard 229169689Skan register are linked in a bidirectional chain. These are called 230169689Skan reg-use or reg_def chains. 231169689Skan 232169689Skan The first use (or def) for a register can be obtained using the 233169689Skan DF_REG_USE_GET macro (or DF_REG_DEF_GET macro). Subsequent uses 234169689Skan for the same regno can be obtained by following the next_reg field 235169689Skan of the ref. 236169689Skan 237169689Skan In previous versions of this code, these chains were ordered. It 238169689Skan has not been practical to continue this practice. 239169689Skan 240169689Skan3) If def-use or use-def chains are built, these can be traversed to 241169689Skan get to other refs. 242169689Skan 243169689Skan4) An array of all of the uses (and an array of all of the defs) can 244169689Skan be built. These arrays are indexed by the value in the id 245169689Skan structure. These arrays are only lazily kept up to date, and that 246169689Skan process can be expensive. To have these arrays built, call 247169689Skan df_reorganize_refs. Note that the values in the id field of a ref 248169689Skan may change across calls to df_analyze or df_reorganize refs. 249169689Skan 250169689Skan If the only use of this array is to find all of the refs, it is 251169689Skan better to traverse all of the registers and then traverse all of 252169689Skan reg-use or reg-def chains. 253169689Skan 254169689Skan 255169689Skan 256169689SkanNOTES: 257169689Skan 258169689SkanEmbedded addressing side-effects, such as POST_INC or PRE_INC, generate 259169689Skanboth a use and a def. These are both marked read/write to show that they 260169689Skanare dependent. For example, (set (reg 40) (mem (post_inc (reg 42)))) 261169689Skanwill generate a use of reg 42 followed by a def of reg 42 (both marked 262169689Skanread/write). Similarly, (set (reg 40) (mem (pre_dec (reg 41)))) 263169689Skangenerates a use of reg 41 then a def of reg 41 (both marked read/write), 264169689Skaneven though reg 41 is decremented before it is used for the memory 265169689Skanaddress in this second example. 266169689Skan 267169689SkanA set to a REG inside a ZERO_EXTRACT, or a set to a non-paradoxical SUBREG 268169689Skanfor which the number of word_mode units covered by the outer mode is 269169689Skansmaller than that covered by the inner mode, invokes a read-modify-write. 270169689Skanoperation. We generate both a use and a def and again mark them 271169689Skanread/write. 272169689Skan 273169689SkanParadoxical subreg writes do not leave a trace of the old content, so they 274169689Skanare write-only operations. 275169689Skan*/ 276169689Skan 277169689Skan 278169689Skan#include "config.h" 279169689Skan#include "system.h" 280169689Skan#include "coretypes.h" 281169689Skan#include "tm.h" 282169689Skan#include "rtl.h" 283169689Skan#include "tm_p.h" 284169689Skan#include "insn-config.h" 285169689Skan#include "recog.h" 286169689Skan#include "function.h" 287169689Skan#include "regs.h" 288169689Skan#include "output.h" 289169689Skan#include "alloc-pool.h" 290169689Skan#include "flags.h" 291169689Skan#include "hard-reg-set.h" 292169689Skan#include "basic-block.h" 293169689Skan#include "sbitmap.h" 294169689Skan#include "bitmap.h" 295169689Skan#include "timevar.h" 296169689Skan#include "df.h" 297169689Skan#include "tree-pass.h" 298169689Skan 299169689Skanstatic struct df *ddf = NULL; 300169689Skanstruct df *shared_df = NULL; 301169689Skan 302169689Skanstatic void *df_get_bb_info (struct dataflow *, unsigned int); 303169689Skanstatic void df_set_bb_info (struct dataflow *, unsigned int, void *); 304169689Skan/*---------------------------------------------------------------------------- 305169689Skan Functions to create, destroy and manipulate an instance of df. 306169689Skan----------------------------------------------------------------------------*/ 307169689Skan 308169689Skan 309169689Skan/* Initialize dataflow analysis and allocate and initialize dataflow 310169689Skan memory. */ 311169689Skan 312169689Skanstruct df * 313169689Skandf_init (int flags) 314169689Skan{ 315169689Skan struct df *df = XCNEW (struct df); 316169689Skan 317169689Skan /* This is executed once per compilation to initialize platform 318169689Skan specific data structures. */ 319169689Skan df_hard_reg_init (); 320169689Skan 321169689Skan /* All df instance must define the scanning problem. */ 322169689Skan df_scan_add_problem (df, flags); 323169689Skan ddf = df; 324169689Skan return df; 325169689Skan} 326169689Skan 327169689Skan/* Add PROBLEM to the DF instance. */ 328169689Skan 329169689Skanstruct dataflow * 330169689Skandf_add_problem (struct df *df, struct df_problem *problem, int flags) 331169689Skan{ 332169689Skan struct dataflow *dflow; 333169689Skan 334169689Skan /* First try to add the dependent problem. */ 335169689Skan if (problem->dependent_problem_fun) 336169689Skan (problem->dependent_problem_fun) (df, 0); 337169689Skan 338169689Skan /* Check to see if this problem has already been defined. If it 339169689Skan has, just return that instance, if not, add it to the end of the 340169689Skan vector. */ 341169689Skan dflow = df->problems_by_index[problem->id]; 342169689Skan if (dflow) 343169689Skan return dflow; 344169689Skan 345169689Skan /* Make a new one and add it to the end. */ 346169689Skan dflow = XCNEW (struct dataflow); 347169689Skan dflow->flags = flags; 348169689Skan dflow->df = df; 349169689Skan dflow->problem = problem; 350169689Skan df->problems_in_order[df->num_problems_defined++] = dflow; 351169689Skan df->problems_by_index[dflow->problem->id] = dflow; 352169689Skan 353169689Skan return dflow; 354169689Skan} 355169689Skan 356169689Skan 357169689Skan/* Set the MASK flags in the DFLOW problem. The old flags are 358169689Skan returned. If a flag is not allowed to be changed this will fail if 359169689Skan checking is enabled. */ 360169689Skanint 361169689Skandf_set_flags (struct dataflow *dflow, int mask) 362169689Skan{ 363169689Skan int old_flags = dflow->flags; 364169689Skan 365169689Skan gcc_assert (!(mask & (~dflow->problem->changeable_flags))); 366169689Skan 367169689Skan dflow->flags |= mask; 368169689Skan 369169689Skan return old_flags; 370169689Skan} 371169689Skan 372169689Skan/* Clear the MASK flags in the DFLOW problem. The old flags are 373169689Skan returned. If a flag is not allowed to be changed this will fail if 374169689Skan checking is enabled. */ 375169689Skanint 376169689Skandf_clear_flags (struct dataflow *dflow, int mask) 377169689Skan{ 378169689Skan int old_flags = dflow->flags; 379169689Skan 380169689Skan gcc_assert (!(mask & (~dflow->problem->changeable_flags))); 381169689Skan 382169689Skan dflow->flags &= !mask; 383169689Skan 384169689Skan return old_flags; 385169689Skan} 386169689Skan 387169689Skan/* Set the blocks that are to be considered for analysis. If this is 388169689Skan not called or is called with null, the entire function in 389169689Skan analyzed. */ 390169689Skan 391169689Skanvoid 392169689Skandf_set_blocks (struct df *df, bitmap blocks) 393169689Skan{ 394169689Skan if (blocks) 395169689Skan { 396169689Skan if (df->blocks_to_analyze) 397169689Skan { 398169689Skan int p; 399169689Skan bitmap diff = BITMAP_ALLOC (NULL); 400169689Skan bitmap_and_compl (diff, df->blocks_to_analyze, blocks); 401169689Skan for (p = df->num_problems_defined - 1; p >= 0 ;p--) 402169689Skan { 403169689Skan struct dataflow *dflow = df->problems_in_order[p]; 404169689Skan if (dflow->problem->reset_fun) 405169689Skan dflow->problem->reset_fun (dflow, df->blocks_to_analyze); 406169689Skan else if (dflow->problem->free_bb_fun) 407169689Skan { 408169689Skan bitmap_iterator bi; 409169689Skan unsigned int bb_index; 410169689Skan 411169689Skan EXECUTE_IF_SET_IN_BITMAP (diff, 0, bb_index, bi) 412169689Skan { 413169689Skan basic_block bb = BASIC_BLOCK (bb_index); 414169689Skan if (bb) 415169689Skan { 416169689Skan dflow->problem->free_bb_fun 417169689Skan (dflow, bb, df_get_bb_info (dflow, bb_index)); 418169689Skan df_set_bb_info (dflow, bb_index, NULL); 419169689Skan } 420169689Skan } 421169689Skan } 422169689Skan } 423169689Skan 424169689Skan BITMAP_FREE (diff); 425169689Skan } 426169689Skan else 427169689Skan { 428169689Skan /* If we have not actually run scanning before, do not try 429169689Skan to clear anything. */ 430169689Skan struct dataflow *scan_dflow = df->problems_by_index [DF_SCAN]; 431169689Skan if (scan_dflow->problem_data) 432169689Skan { 433169689Skan bitmap blocks_to_reset = NULL; 434169689Skan int p; 435169689Skan for (p = df->num_problems_defined - 1; p >= 0 ;p--) 436169689Skan { 437169689Skan struct dataflow *dflow = df->problems_in_order[p]; 438169689Skan if (dflow->problem->reset_fun) 439169689Skan { 440169689Skan if (!blocks_to_reset) 441169689Skan { 442169689Skan basic_block bb; 443169689Skan blocks_to_reset = BITMAP_ALLOC (NULL); 444169689Skan FOR_ALL_BB(bb) 445169689Skan { 446169689Skan bitmap_set_bit (blocks_to_reset, bb->index); 447169689Skan } 448169689Skan } 449169689Skan dflow->problem->reset_fun (dflow, blocks_to_reset); 450169689Skan } 451169689Skan } 452169689Skan if (blocks_to_reset) 453169689Skan BITMAP_FREE (blocks_to_reset); 454169689Skan } 455169689Skan df->blocks_to_analyze = BITMAP_ALLOC (NULL); 456169689Skan } 457169689Skan bitmap_copy (df->blocks_to_analyze, blocks); 458169689Skan } 459169689Skan else 460169689Skan { 461169689Skan if (df->blocks_to_analyze) 462169689Skan { 463169689Skan BITMAP_FREE (df->blocks_to_analyze); 464169689Skan df->blocks_to_analyze = NULL; 465169689Skan } 466169689Skan } 467169689Skan} 468169689Skan 469169689Skan 470169689Skan/* Free all of the per basic block dataflow from all of the problems. 471169689Skan This is typically called before a basic block is deleted and the 472169689Skan problem will be reanalyzed. */ 473169689Skan 474169689Skanvoid 475169689Skandf_delete_basic_block (struct df *df, int bb_index) 476169689Skan{ 477169689Skan basic_block bb = BASIC_BLOCK (bb_index); 478169689Skan int i; 479169689Skan 480169689Skan for (i = 0; i < df->num_problems_defined; i++) 481169689Skan { 482169689Skan struct dataflow *dflow = df->problems_in_order[i]; 483169689Skan if (dflow->problem->free_bb_fun) 484169689Skan dflow->problem->free_bb_fun 485169689Skan (dflow, bb, df_get_bb_info (dflow, bb_index)); 486169689Skan } 487169689Skan} 488169689Skan 489169689Skan 490169689Skan/* Free all the dataflow info and the DF structure. This should be 491169689Skan called from the df_finish macro which also NULLs the parm. */ 492169689Skan 493169689Skanvoid 494169689Skandf_finish1 (struct df *df) 495169689Skan{ 496169689Skan int i; 497169689Skan 498169689Skan for (i = 0; i < df->num_problems_defined; i++) 499169689Skan df->problems_in_order[i]->problem->free_fun (df->problems_in_order[i]); 500169689Skan 501169689Skan free (df); 502169689Skan} 503169689Skan 504169689Skan 505169689Skan/*---------------------------------------------------------------------------- 506169689Skan The general data flow analysis engine. 507169689Skan----------------------------------------------------------------------------*/ 508169689Skan 509169689Skan 510169689Skan/* Hybrid search algorithm from "Implementation Techniques for 511169689Skan Efficient Data-Flow Analysis of Large Programs". */ 512169689Skan 513169689Skanstatic void 514169689Skandf_hybrid_search_forward (basic_block bb, 515169689Skan struct dataflow *dataflow, 516169689Skan bool single_pass) 517169689Skan{ 518169689Skan int result_changed; 519169689Skan int i = bb->index; 520169689Skan edge e; 521169689Skan edge_iterator ei; 522169689Skan 523169689Skan SET_BIT (dataflow->visited, bb->index); 524169689Skan gcc_assert (TEST_BIT (dataflow->pending, bb->index)); 525169689Skan RESET_BIT (dataflow->pending, i); 526169689Skan 527169689Skan /* Calculate <conf_op> of predecessor_outs. */ 528169689Skan if (EDGE_COUNT (bb->preds) > 0) 529169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 530169689Skan { 531169689Skan if (!TEST_BIT (dataflow->considered, e->src->index)) 532169689Skan continue; 533169689Skan 534169689Skan dataflow->problem->con_fun_n (dataflow, e); 535169689Skan } 536169689Skan else if (dataflow->problem->con_fun_0) 537169689Skan dataflow->problem->con_fun_0 (dataflow, bb); 538169689Skan 539169689Skan result_changed = dataflow->problem->trans_fun (dataflow, i); 540169689Skan 541169689Skan if (!result_changed || single_pass) 542169689Skan return; 543169689Skan 544169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 545169689Skan { 546169689Skan if (e->dest->index == i) 547169689Skan continue; 548169689Skan if (!TEST_BIT (dataflow->considered, e->dest->index)) 549169689Skan continue; 550169689Skan SET_BIT (dataflow->pending, e->dest->index); 551169689Skan } 552169689Skan 553169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 554169689Skan { 555169689Skan if (e->dest->index == i) 556169689Skan continue; 557169689Skan 558169689Skan if (!TEST_BIT (dataflow->considered, e->dest->index)) 559169689Skan continue; 560169689Skan if (!TEST_BIT (dataflow->visited, e->dest->index)) 561169689Skan df_hybrid_search_forward (e->dest, dataflow, single_pass); 562169689Skan } 563169689Skan} 564169689Skan 565169689Skanstatic void 566169689Skandf_hybrid_search_backward (basic_block bb, 567169689Skan struct dataflow *dataflow, 568169689Skan bool single_pass) 569169689Skan{ 570169689Skan int result_changed; 571169689Skan int i = bb->index; 572169689Skan edge e; 573169689Skan edge_iterator ei; 574169689Skan 575169689Skan SET_BIT (dataflow->visited, bb->index); 576169689Skan gcc_assert (TEST_BIT (dataflow->pending, bb->index)); 577169689Skan RESET_BIT (dataflow->pending, i); 578169689Skan 579169689Skan /* Calculate <conf_op> of predecessor_outs. */ 580169689Skan if (EDGE_COUNT (bb->succs) > 0) 581169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 582169689Skan { 583169689Skan if (!TEST_BIT (dataflow->considered, e->dest->index)) 584169689Skan continue; 585169689Skan 586169689Skan dataflow->problem->con_fun_n (dataflow, e); 587169689Skan } 588169689Skan else if (dataflow->problem->con_fun_0) 589169689Skan dataflow->problem->con_fun_0 (dataflow, bb); 590169689Skan 591169689Skan result_changed = dataflow->problem->trans_fun (dataflow, i); 592169689Skan 593169689Skan if (!result_changed || single_pass) 594169689Skan return; 595169689Skan 596169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 597169689Skan { 598169689Skan if (e->src->index == i) 599169689Skan continue; 600169689Skan 601169689Skan if (!TEST_BIT (dataflow->considered, e->src->index)) 602169689Skan continue; 603169689Skan 604169689Skan SET_BIT (dataflow->pending, e->src->index); 605169689Skan } 606169689Skan 607169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 608169689Skan { 609169689Skan if (e->src->index == i) 610169689Skan continue; 611169689Skan 612169689Skan if (!TEST_BIT (dataflow->considered, e->src->index)) 613169689Skan continue; 614169689Skan 615169689Skan if (!TEST_BIT (dataflow->visited, e->src->index)) 616169689Skan df_hybrid_search_backward (e->src, dataflow, single_pass); 617169689Skan } 618169689Skan} 619169689Skan 620169689Skan 621169689Skan/* This function will perform iterative bitvector dataflow described 622169689Skan by DATAFLOW, producing the in and out sets. Only the part of the 623169689Skan cfg induced by blocks in DATAFLOW->order is taken into account. 624169689Skan 625169689Skan SINGLE_PASS is true if you just want to make one pass over the 626169689Skan blocks. */ 627169689Skan 628169689Skanvoid 629169689Skandf_iterative_dataflow (struct dataflow *dataflow, 630169689Skan bitmap blocks_to_consider, bitmap blocks_to_init, 631169689Skan int *blocks_in_postorder, int n_blocks, 632169689Skan bool single_pass) 633169689Skan{ 634169689Skan unsigned int idx; 635169689Skan int i; 636169689Skan sbitmap visited = sbitmap_alloc (last_basic_block); 637169689Skan sbitmap pending = sbitmap_alloc (last_basic_block); 638169689Skan sbitmap considered = sbitmap_alloc (last_basic_block); 639169689Skan bitmap_iterator bi; 640169689Skan 641169689Skan dataflow->visited = visited; 642169689Skan dataflow->pending = pending; 643169689Skan dataflow->considered = considered; 644169689Skan 645169689Skan sbitmap_zero (visited); 646169689Skan sbitmap_zero (pending); 647169689Skan sbitmap_zero (considered); 648169689Skan 649169689Skan gcc_assert (dataflow->problem->dir); 650169689Skan 651169689Skan EXECUTE_IF_SET_IN_BITMAP (blocks_to_consider, 0, idx, bi) 652169689Skan { 653169689Skan SET_BIT (considered, idx); 654169689Skan } 655169689Skan 656169689Skan for (i = 0; i < n_blocks; i++) 657169689Skan { 658169689Skan idx = blocks_in_postorder[i]; 659169689Skan SET_BIT (pending, idx); 660169689Skan }; 661169689Skan 662169689Skan dataflow->problem->init_fun (dataflow, blocks_to_init); 663169689Skan 664169689Skan while (1) 665169689Skan { 666169689Skan 667169689Skan /* For forward problems, you want to pass in reverse postorder 668169689Skan and for backward problems you want postorder. This has been 669169689Skan shown to be as good as you can do by several people, the 670169689Skan first being Mathew Hecht in his phd dissertation. 671169689Skan 672169689Skan The nodes are passed into this function in postorder. */ 673169689Skan 674169689Skan if (dataflow->problem->dir == DF_FORWARD) 675169689Skan { 676169689Skan for (i = n_blocks - 1 ; i >= 0 ; i--) 677169689Skan { 678169689Skan idx = blocks_in_postorder[i]; 679169689Skan 680169689Skan if (TEST_BIT (pending, idx) && !TEST_BIT (visited, idx)) 681169689Skan df_hybrid_search_forward (BASIC_BLOCK (idx), dataflow, single_pass); 682169689Skan } 683169689Skan } 684169689Skan else 685169689Skan { 686169689Skan for (i = 0; i < n_blocks; i++) 687169689Skan { 688169689Skan idx = blocks_in_postorder[i]; 689169689Skan 690169689Skan if (TEST_BIT (pending, idx) && !TEST_BIT (visited, idx)) 691169689Skan df_hybrid_search_backward (BASIC_BLOCK (idx), dataflow, single_pass); 692169689Skan } 693169689Skan } 694169689Skan 695169689Skan if (sbitmap_first_set_bit (pending) == -1) 696169689Skan break; 697169689Skan 698169689Skan sbitmap_zero (visited); 699169689Skan } 700169689Skan 701169689Skan sbitmap_free (pending); 702169689Skan sbitmap_free (visited); 703169689Skan sbitmap_free (considered); 704169689Skan} 705169689Skan 706169689Skan 707169689Skan/* Remove the entries not in BLOCKS from the LIST of length LEN, preserving 708169689Skan the order of the remaining entries. Returns the length of the resulting 709169689Skan list. */ 710169689Skan 711169689Skanstatic unsigned 712169689Skandf_prune_to_subcfg (int list[], unsigned len, bitmap blocks) 713169689Skan{ 714169689Skan unsigned act, last; 715169689Skan 716169689Skan for (act = 0, last = 0; act < len; act++) 717169689Skan if (bitmap_bit_p (blocks, list[act])) 718169689Skan list[last++] = list[act]; 719169689Skan 720169689Skan return last; 721169689Skan} 722169689Skan 723169689Skan 724169689Skan/* Execute dataflow analysis on a single dataflow problem. 725169689Skan 726169689Skan There are three sets of blocks passed in: 727169689Skan 728169689Skan BLOCKS_TO_CONSIDER are the blocks whose solution can either be 729169689Skan examined or will be computed. For calls from DF_ANALYZE, this is 730169689Skan the set of blocks that has been passed to DF_SET_BLOCKS. For calls 731169689Skan from DF_ANALYZE_SIMPLE_CHANGE_SOME_BLOCKS, this is the set of 732169689Skan blocks in the fringe (the set of blocks passed in plus the set of 733169689Skan immed preds and succs of those blocks). 734169689Skan 735169689Skan BLOCKS_TO_INIT are the blocks whose solution will be changed by 736169689Skan this iteration. For calls from DF_ANALYZE, this is the set of 737169689Skan blocks that has been passed to DF_SET_BLOCKS. For calls from 738169689Skan DF_ANALYZE_SIMPLE_CHANGE_SOME_BLOCKS, this is the set of blocks 739169689Skan passed in. 740169689Skan 741169689Skan BLOCKS_TO_SCAN are the set of blocks that need to be rescanned. 742169689Skan For calls from DF_ANALYZE, this is the accumulated set of blocks 743169689Skan that has been passed to DF_RESCAN_BLOCKS since the last call to 744169689Skan DF_ANALYZE. For calls from DF_ANALYZE_SIMPLE_CHANGE_SOME_BLOCKS, 745169689Skan this is the set of blocks passed in. 746169689Skan 747169689Skan blocks_to_consider blocks_to_init blocks_to_scan 748169689Skan full redo all all all 749169689Skan partial redo all all sub 750169689Skan small fixup fringe sub sub 751169689Skan*/ 752169689Skan 753169689Skanvoid 754169689Skandf_analyze_problem (struct dataflow *dflow, 755169689Skan bitmap blocks_to_consider, 756169689Skan bitmap blocks_to_init, 757169689Skan bitmap blocks_to_scan, 758169689Skan int *postorder, int n_blocks, bool single_pass) 759169689Skan{ 760169689Skan /* (Re)Allocate the datastructures necessary to solve the problem. */ 761169689Skan if (dflow->problem->alloc_fun) 762169689Skan dflow->problem->alloc_fun (dflow, blocks_to_scan, blocks_to_init); 763169689Skan 764169689Skan /* Set up the problem and compute the local information. This 765169689Skan function is passed both the blocks_to_consider and the 766169689Skan blocks_to_scan because the RD and RU problems require the entire 767169689Skan function to be rescanned if they are going to be updated. */ 768169689Skan if (dflow->problem->local_compute_fun) 769169689Skan dflow->problem->local_compute_fun (dflow, blocks_to_consider, blocks_to_scan); 770169689Skan 771169689Skan /* Solve the equations. */ 772169689Skan if (dflow->problem->dataflow_fun) 773169689Skan dflow->problem->dataflow_fun (dflow, blocks_to_consider, blocks_to_init, 774169689Skan postorder, n_blocks, single_pass); 775169689Skan 776169689Skan /* Massage the solution. */ 777169689Skan if (dflow->problem->finalize_fun) 778169689Skan dflow->problem->finalize_fun (dflow, blocks_to_consider); 779169689Skan} 780169689Skan 781169689Skan 782169689Skan/* Analyze dataflow info for the basic blocks specified by the bitmap 783169689Skan BLOCKS, or for the whole CFG if BLOCKS is zero. */ 784169689Skan 785169689Skanvoid 786169689Skandf_analyze (struct df *df) 787169689Skan{ 788169689Skan int *postorder = XNEWVEC (int, last_basic_block); 789169689Skan bitmap current_all_blocks = BITMAP_ALLOC (NULL); 790169689Skan int n_blocks; 791169689Skan int i; 792169689Skan bool everything; 793169689Skan 794169689Skan n_blocks = post_order_compute (postorder, true); 795169689Skan 796169689Skan if (n_blocks != n_basic_blocks) 797169689Skan delete_unreachable_blocks (); 798169689Skan 799169689Skan for (i = 0; i < n_blocks; i++) 800169689Skan bitmap_set_bit (current_all_blocks, postorder[i]); 801169689Skan 802169689Skan /* No one called df_rescan_blocks, so do it. */ 803169689Skan if (!df->blocks_to_scan) 804169689Skan df_rescan_blocks (df, NULL); 805169689Skan 806169689Skan /* Make sure that we have pruned any unreachable blocks from these 807169689Skan sets. */ 808169689Skan bitmap_and_into (df->blocks_to_scan, current_all_blocks); 809169689Skan 810169689Skan if (df->blocks_to_analyze) 811169689Skan { 812169689Skan everything = false; 813169689Skan bitmap_and_into (df->blocks_to_analyze, current_all_blocks); 814169689Skan n_blocks = df_prune_to_subcfg (postorder, n_blocks, df->blocks_to_analyze); 815169689Skan BITMAP_FREE (current_all_blocks); 816169689Skan } 817169689Skan else 818169689Skan { 819169689Skan everything = true; 820169689Skan df->blocks_to_analyze = current_all_blocks; 821169689Skan current_all_blocks = NULL; 822169689Skan } 823169689Skan 824169689Skan /* Skip over the DF_SCAN problem. */ 825169689Skan for (i = 1; i < df->num_problems_defined; i++) 826169689Skan df_analyze_problem (df->problems_in_order[i], 827169689Skan df->blocks_to_analyze, df->blocks_to_analyze, 828169689Skan df->blocks_to_scan, 829169689Skan postorder, n_blocks, false); 830169689Skan 831169689Skan if (everything) 832169689Skan { 833169689Skan BITMAP_FREE (df->blocks_to_analyze); 834169689Skan df->blocks_to_analyze = NULL; 835169689Skan } 836169689Skan 837169689Skan BITMAP_FREE (df->blocks_to_scan); 838169689Skan df->blocks_to_scan = NULL; 839169689Skan free (postorder); 840169689Skan} 841169689Skan 842169689Skan 843169689Skan 844169689Skan/*---------------------------------------------------------------------------- 845169689Skan Functions to support limited incremental change. 846169689Skan----------------------------------------------------------------------------*/ 847169689Skan 848169689Skan 849169689Skan/* Get basic block info. */ 850169689Skan 851169689Skanstatic void * 852169689Skandf_get_bb_info (struct dataflow *dflow, unsigned int index) 853169689Skan{ 854169689Skan return (struct df_scan_bb_info *) dflow->block_info[index]; 855169689Skan} 856169689Skan 857169689Skan 858169689Skan/* Set basic block info. */ 859169689Skan 860169689Skanstatic void 861169689Skandf_set_bb_info (struct dataflow *dflow, unsigned int index, 862169689Skan void *bb_info) 863169689Skan{ 864169689Skan dflow->block_info[index] = bb_info; 865169689Skan} 866169689Skan 867169689Skan 868169689Skan/* Called from the rtl_compact_blocks to reorganize the problems basic 869169689Skan block info. */ 870169689Skan 871169689Skanvoid 872169689Skandf_compact_blocks (struct df *df) 873169689Skan{ 874169689Skan int i, p; 875169689Skan basic_block bb; 876169689Skan void **problem_temps; 877169689Skan int size = last_basic_block *sizeof (void *); 878169689Skan problem_temps = xmalloc (size); 879169689Skan 880169689Skan for (p = 0; p < df->num_problems_defined; p++) 881169689Skan { 882169689Skan struct dataflow *dflow = df->problems_in_order[p]; 883169689Skan if (dflow->problem->free_bb_fun) 884169689Skan { 885169689Skan df_grow_bb_info (dflow); 886169689Skan memcpy (problem_temps, dflow->block_info, size); 887169689Skan 888169689Skan /* Copy the bb info from the problem tmps to the proper 889169689Skan place in the block_info vector. Null out the copied 890169689Skan item. */ 891169689Skan i = NUM_FIXED_BLOCKS; 892169689Skan FOR_EACH_BB (bb) 893169689Skan { 894169689Skan df_set_bb_info (dflow, i, problem_temps[bb->index]); 895169689Skan problem_temps[bb->index] = NULL; 896169689Skan i++; 897169689Skan } 898169689Skan memset (dflow->block_info + i, 0, 899169689Skan (last_basic_block - i) *sizeof (void *)); 900169689Skan 901169689Skan /* Free any block infos that were not copied (and NULLed). 902169689Skan These are from orphaned blocks. */ 903169689Skan for (i = NUM_FIXED_BLOCKS; i < last_basic_block; i++) 904169689Skan { 905169689Skan basic_block bb = BASIC_BLOCK (i); 906169689Skan if (problem_temps[i] && bb) 907169689Skan dflow->problem->free_bb_fun 908169689Skan (dflow, bb, problem_temps[i]); 909169689Skan } 910169689Skan } 911169689Skan } 912169689Skan 913169689Skan free (problem_temps); 914169689Skan 915169689Skan i = NUM_FIXED_BLOCKS; 916169689Skan FOR_EACH_BB (bb) 917169689Skan { 918169689Skan SET_BASIC_BLOCK (i, bb); 919169689Skan bb->index = i; 920169689Skan i++; 921169689Skan } 922169689Skan 923169689Skan gcc_assert (i == n_basic_blocks); 924169689Skan 925169689Skan for (; i < last_basic_block; i++) 926169689Skan SET_BASIC_BLOCK (i, NULL); 927169689Skan} 928169689Skan 929169689Skan 930169689Skan/* Shove NEW_BLOCK in at OLD_INDEX. Called from if-cvt to hack a 931169689Skan block. There is no excuse for people to do this kind of thing. */ 932169689Skan 933169689Skanvoid 934169689Skandf_bb_replace (struct df *df, int old_index, basic_block new_block) 935169689Skan{ 936169689Skan int p; 937169689Skan 938169689Skan for (p = 0; p < df->num_problems_defined; p++) 939169689Skan { 940169689Skan struct dataflow *dflow = df->problems_in_order[p]; 941169689Skan if (dflow->block_info) 942169689Skan { 943169689Skan void *temp; 944169689Skan 945169689Skan df_grow_bb_info (dflow); 946169689Skan 947169689Skan /* The old switcheroo. */ 948169689Skan 949169689Skan temp = df_get_bb_info (dflow, old_index); 950169689Skan df_set_bb_info (dflow, old_index, 951169689Skan df_get_bb_info (dflow, new_block->index)); 952169689Skan df_set_bb_info (dflow, new_block->index, temp); 953169689Skan } 954169689Skan } 955169689Skan 956169689Skan SET_BASIC_BLOCK (old_index, new_block); 957169689Skan new_block->index = old_index; 958169689Skan} 959169689Skan 960169689Skan/*---------------------------------------------------------------------------- 961169689Skan PUBLIC INTERFACES TO QUERY INFORMATION. 962169689Skan----------------------------------------------------------------------------*/ 963169689Skan 964169689Skan 965169689Skan/* Return last use of REGNO within BB. */ 966169689Skan 967169689Skanstruct df_ref * 968169689Skandf_bb_regno_last_use_find (struct df *df, basic_block bb, unsigned int regno) 969169689Skan{ 970169689Skan rtx insn; 971169689Skan struct df_ref *use; 972169689Skan unsigned int uid; 973169689Skan 974169689Skan FOR_BB_INSNS_REVERSE (bb, insn) 975169689Skan { 976169689Skan if (!INSN_P (insn)) 977169689Skan continue; 978169689Skan 979169689Skan uid = INSN_UID (insn); 980169689Skan for (use = DF_INSN_UID_GET (df, uid)->uses; use; use = use->next_ref) 981169689Skan if (DF_REF_REGNO (use) == regno) 982169689Skan return use; 983169689Skan } 984169689Skan return NULL; 985169689Skan} 986169689Skan 987169689Skan 988169689Skan/* Return first def of REGNO within BB. */ 989169689Skan 990169689Skanstruct df_ref * 991169689Skandf_bb_regno_first_def_find (struct df *df, basic_block bb, unsigned int regno) 992169689Skan{ 993169689Skan rtx insn; 994169689Skan struct df_ref *def; 995169689Skan unsigned int uid; 996169689Skan 997169689Skan FOR_BB_INSNS (bb, insn) 998169689Skan { 999169689Skan if (!INSN_P (insn)) 1000169689Skan continue; 1001169689Skan 1002169689Skan uid = INSN_UID (insn); 1003169689Skan for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref) 1004169689Skan if (DF_REF_REGNO (def) == regno) 1005169689Skan return def; 1006169689Skan } 1007169689Skan return NULL; 1008169689Skan} 1009169689Skan 1010169689Skan 1011169689Skan/* Return last def of REGNO within BB. */ 1012169689Skan 1013169689Skanstruct df_ref * 1014169689Skandf_bb_regno_last_def_find (struct df *df, basic_block bb, unsigned int regno) 1015169689Skan{ 1016169689Skan rtx insn; 1017169689Skan struct df_ref *def; 1018169689Skan unsigned int uid; 1019169689Skan 1020169689Skan FOR_BB_INSNS_REVERSE (bb, insn) 1021169689Skan { 1022169689Skan if (!INSN_P (insn)) 1023169689Skan continue; 1024169689Skan 1025169689Skan uid = INSN_UID (insn); 1026169689Skan for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref) 1027169689Skan if (DF_REF_REGNO (def) == regno) 1028169689Skan return def; 1029169689Skan } 1030169689Skan 1031169689Skan return NULL; 1032169689Skan} 1033169689Skan 1034169689Skan/* Return true if INSN defines REGNO. */ 1035169689Skan 1036169689Skanbool 1037169689Skandf_insn_regno_def_p (struct df *df, rtx insn, unsigned int regno) 1038169689Skan{ 1039169689Skan unsigned int uid; 1040169689Skan struct df_ref *def; 1041169689Skan 1042169689Skan uid = INSN_UID (insn); 1043169689Skan for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref) 1044169689Skan if (DF_REF_REGNO (def) == regno) 1045169689Skan return true; 1046169689Skan 1047169689Skan return false; 1048169689Skan} 1049169689Skan 1050169689Skan 1051169689Skan/* Finds the reference corresponding to the definition of REG in INSN. 1052169689Skan DF is the dataflow object. */ 1053169689Skan 1054169689Skanstruct df_ref * 1055169689Skandf_find_def (struct df *df, rtx insn, rtx reg) 1056169689Skan{ 1057169689Skan unsigned int uid; 1058169689Skan struct df_ref *def; 1059169689Skan 1060169689Skan if (GET_CODE (reg) == SUBREG) 1061169689Skan reg = SUBREG_REG (reg); 1062169689Skan gcc_assert (REG_P (reg)); 1063169689Skan 1064169689Skan uid = INSN_UID (insn); 1065169689Skan for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref) 1066169689Skan if (rtx_equal_p (DF_REF_REAL_REG (def), reg)) 1067169689Skan return def; 1068169689Skan 1069169689Skan return NULL; 1070169689Skan} 1071169689Skan 1072169689Skan 1073169689Skan/* Return true if REG is defined in INSN, zero otherwise. */ 1074169689Skan 1075169689Skanbool 1076169689Skandf_reg_defined (struct df *df, rtx insn, rtx reg) 1077169689Skan{ 1078169689Skan return df_find_def (df, insn, reg) != NULL; 1079169689Skan} 1080169689Skan 1081169689Skan 1082169689Skan/* Finds the reference corresponding to the use of REG in INSN. 1083169689Skan DF is the dataflow object. */ 1084169689Skan 1085169689Skanstruct df_ref * 1086169689Skandf_find_use (struct df *df, rtx insn, rtx reg) 1087169689Skan{ 1088169689Skan unsigned int uid; 1089169689Skan struct df_ref *use; 1090169689Skan 1091169689Skan if (GET_CODE (reg) == SUBREG) 1092169689Skan reg = SUBREG_REG (reg); 1093169689Skan gcc_assert (REG_P (reg)); 1094169689Skan 1095169689Skan uid = INSN_UID (insn); 1096169689Skan for (use = DF_INSN_UID_GET (df, uid)->uses; use; use = use->next_ref) 1097169689Skan if (rtx_equal_p (DF_REF_REAL_REG (use), reg)) 1098169689Skan return use; 1099169689Skan 1100169689Skan return NULL; 1101169689Skan} 1102169689Skan 1103169689Skan 1104169689Skan/* Return true if REG is referenced in INSN, zero otherwise. */ 1105169689Skan 1106169689Skanbool 1107169689Skandf_reg_used (struct df *df, rtx insn, rtx reg) 1108169689Skan{ 1109169689Skan return df_find_use (df, insn, reg) != NULL; 1110169689Skan} 1111169689Skan 1112169689Skan 1113169689Skan/*---------------------------------------------------------------------------- 1114169689Skan Debugging and printing functions. 1115169689Skan----------------------------------------------------------------------------*/ 1116169689Skan 1117169689Skan/* Dump dataflow info. */ 1118169689Skanvoid 1119169689Skandf_dump (struct df *df, FILE *file) 1120169689Skan{ 1121169689Skan int i; 1122169689Skan 1123169689Skan if (!df || !file) 1124169689Skan return; 1125169689Skan 1126169689Skan fprintf (file, "\n\n%s\n", current_function_name ()); 1127169689Skan fprintf (file, "\nDataflow summary:\n"); 1128169689Skan fprintf (file, "def_info->bitmap_size = %d, use_info->bitmap_size = %d\n", 1129169689Skan df->def_info.bitmap_size, df->use_info.bitmap_size); 1130169689Skan 1131169689Skan for (i = 0; i < df->num_problems_defined; i++) 1132169689Skan df->problems_in_order[i]->problem->dump_fun (df->problems_in_order[i], file); 1133169689Skan 1134169689Skan fprintf (file, "\n"); 1135169689Skan} 1136169689Skan 1137169689Skan 1138169689Skanvoid 1139169689Skandf_refs_chain_dump (struct df_ref *ref, bool follow_chain, FILE *file) 1140169689Skan{ 1141169689Skan fprintf (file, "{ "); 1142169689Skan while (ref) 1143169689Skan { 1144169689Skan fprintf (file, "%c%d(%d) ", 1145169689Skan DF_REF_REG_DEF_P (ref) ? 'd' : 'u', 1146169689Skan DF_REF_ID (ref), 1147169689Skan DF_REF_REGNO (ref)); 1148169689Skan if (follow_chain) 1149169689Skan df_chain_dump (DF_REF_CHAIN (ref), file); 1150169689Skan ref = ref->next_ref; 1151169689Skan } 1152169689Skan fprintf (file, "}"); 1153169689Skan} 1154169689Skan 1155169689Skan 1156169689Skan/* Dump either a ref-def or reg-use chain. */ 1157169689Skan 1158169689Skanvoid 1159169689Skandf_regs_chain_dump (struct df *df ATTRIBUTE_UNUSED, struct df_ref *ref, FILE *file) 1160169689Skan{ 1161169689Skan fprintf (file, "{ "); 1162169689Skan while (ref) 1163169689Skan { 1164169689Skan fprintf (file, "%c%d(%d) ", 1165169689Skan DF_REF_REG_DEF_P (ref) ? 'd' : 'u', 1166169689Skan DF_REF_ID (ref), 1167169689Skan DF_REF_REGNO (ref)); 1168169689Skan ref = ref->next_reg; 1169169689Skan } 1170169689Skan fprintf (file, "}"); 1171169689Skan} 1172169689Skan 1173169689Skan 1174169689Skanstatic void 1175169689Skandf_mws_dump (struct df_mw_hardreg *mws, FILE *file) 1176169689Skan{ 1177169689Skan while (mws) 1178169689Skan { 1179169689Skan struct df_link *regs = mws->regs; 1180169689Skan fprintf (file, "%c%d(", 1181169689Skan (mws->type == DF_REF_REG_DEF) ? 'd' : 'u', 1182169689Skan DF_REF_REGNO (regs->ref)); 1183169689Skan while (regs) 1184169689Skan { 1185169689Skan fprintf (file, "%d ", DF_REF_REGNO (regs->ref)); 1186169689Skan regs = regs->next; 1187169689Skan } 1188169689Skan 1189169689Skan fprintf (file, ") "); 1190169689Skan mws = mws->next; 1191169689Skan } 1192169689Skan} 1193169689Skan 1194169689Skan 1195169689Skanstatic void 1196169689Skandf_insn_uid_debug (struct df *df, unsigned int uid, 1197169689Skan bool follow_chain, FILE *file) 1198169689Skan{ 1199169689Skan int bbi; 1200169689Skan 1201169689Skan if (DF_INSN_UID_DEFS (df, uid)) 1202169689Skan bbi = DF_REF_BBNO (DF_INSN_UID_DEFS (df, uid)); 1203169689Skan else if (DF_INSN_UID_USES(df, uid)) 1204169689Skan bbi = DF_REF_BBNO (DF_INSN_UID_USES (df, uid)); 1205169689Skan else 1206169689Skan bbi = -1; 1207169689Skan 1208169689Skan fprintf (file, "insn %d bb %d luid %d", 1209169689Skan uid, bbi, DF_INSN_UID_LUID (df, uid)); 1210169689Skan 1211169689Skan if (DF_INSN_UID_DEFS (df, uid)) 1212169689Skan { 1213169689Skan fprintf (file, " defs "); 1214169689Skan df_refs_chain_dump (DF_INSN_UID_DEFS (df, uid), follow_chain, file); 1215169689Skan } 1216169689Skan 1217169689Skan if (DF_INSN_UID_USES (df, uid)) 1218169689Skan { 1219169689Skan fprintf (file, " uses "); 1220169689Skan df_refs_chain_dump (DF_INSN_UID_USES (df, uid), follow_chain, file); 1221169689Skan } 1222169689Skan 1223169689Skan if (DF_INSN_UID_MWS (df, uid)) 1224169689Skan { 1225169689Skan fprintf (file, " mws "); 1226169689Skan df_mws_dump (DF_INSN_UID_MWS (df, uid), file); 1227169689Skan } 1228169689Skan fprintf (file, "\n"); 1229169689Skan} 1230169689Skan 1231169689Skan 1232169689Skanvoid 1233169689Skandf_insn_debug (struct df *df, rtx insn, bool follow_chain, FILE *file) 1234169689Skan{ 1235169689Skan df_insn_uid_debug (df, INSN_UID (insn), follow_chain, file); 1236169689Skan} 1237169689Skan 1238169689Skanvoid 1239169689Skandf_insn_debug_regno (struct df *df, rtx insn, FILE *file) 1240169689Skan{ 1241169689Skan unsigned int uid; 1242169689Skan int bbi; 1243169689Skan 1244169689Skan uid = INSN_UID (insn); 1245169689Skan if (DF_INSN_UID_DEFS (df, uid)) 1246169689Skan bbi = DF_REF_BBNO (DF_INSN_UID_DEFS (df, uid)); 1247169689Skan else if (DF_INSN_UID_USES(df, uid)) 1248169689Skan bbi = DF_REF_BBNO (DF_INSN_UID_USES (df, uid)); 1249169689Skan else 1250169689Skan bbi = -1; 1251169689Skan 1252169689Skan fprintf (file, "insn %d bb %d luid %d defs ", 1253169689Skan uid, bbi, DF_INSN_LUID (df, insn)); 1254169689Skan df_regs_chain_dump (df, DF_INSN_UID_DEFS (df, uid), file); 1255169689Skan 1256169689Skan fprintf (file, " uses "); 1257169689Skan df_regs_chain_dump (df, DF_INSN_UID_USES (df, uid), file); 1258169689Skan fprintf (file, "\n"); 1259169689Skan} 1260169689Skan 1261169689Skanvoid 1262169689Skandf_regno_debug (struct df *df, unsigned int regno, FILE *file) 1263169689Skan{ 1264169689Skan fprintf (file, "reg %d defs ", regno); 1265169689Skan df_regs_chain_dump (df, DF_REG_DEF_GET (df, regno)->reg_chain, file); 1266169689Skan fprintf (file, " uses "); 1267169689Skan df_regs_chain_dump (df, DF_REG_USE_GET (df, regno)->reg_chain, file); 1268169689Skan fprintf (file, "\n"); 1269169689Skan} 1270169689Skan 1271169689Skan 1272169689Skanvoid 1273169689Skandf_ref_debug (struct df_ref *ref, FILE *file) 1274169689Skan{ 1275169689Skan fprintf (file, "%c%d ", 1276169689Skan DF_REF_REG_DEF_P (ref) ? 'd' : 'u', 1277169689Skan DF_REF_ID (ref)); 1278169689Skan fprintf (file, "reg %d bb %d insn %d flag %x chain ", 1279169689Skan DF_REF_REGNO (ref), 1280169689Skan DF_REF_BBNO (ref), 1281169689Skan DF_REF_INSN (ref) ? INSN_UID (DF_REF_INSN (ref)) : -1, 1282169689Skan DF_REF_FLAGS (ref)); 1283169689Skan df_chain_dump (DF_REF_CHAIN (ref), file); 1284169689Skan fprintf (file, "\n"); 1285169689Skan} 1286169689Skan 1287169689Skan/* Functions for debugging from GDB. */ 1288169689Skan 1289169689Skanvoid 1290169689Skandebug_df_insn (rtx insn) 1291169689Skan{ 1292169689Skan df_insn_debug (ddf, insn, true, stderr); 1293169689Skan debug_rtx (insn); 1294169689Skan} 1295169689Skan 1296169689Skan 1297169689Skanvoid 1298169689Skandebug_df_reg (rtx reg) 1299169689Skan{ 1300169689Skan df_regno_debug (ddf, REGNO (reg), stderr); 1301169689Skan} 1302169689Skan 1303169689Skan 1304169689Skanvoid 1305169689Skandebug_df_regno (unsigned int regno) 1306169689Skan{ 1307169689Skan df_regno_debug (ddf, regno, stderr); 1308169689Skan} 1309169689Skan 1310169689Skan 1311169689Skanvoid 1312169689Skandebug_df_ref (struct df_ref *ref) 1313169689Skan{ 1314169689Skan df_ref_debug (ref, stderr); 1315169689Skan} 1316169689Skan 1317169689Skan 1318169689Skanvoid 1319169689Skandebug_df_defno (unsigned int defno) 1320169689Skan{ 1321169689Skan df_ref_debug (DF_DEFS_GET (ddf, defno), stderr); 1322169689Skan} 1323169689Skan 1324169689Skan 1325169689Skanvoid 1326169689Skandebug_df_useno (unsigned int defno) 1327169689Skan{ 1328169689Skan df_ref_debug (DF_USES_GET (ddf, defno), stderr); 1329169689Skan} 1330169689Skan 1331169689Skan 1332169689Skanvoid 1333169689Skandebug_df_chain (struct df_link *link) 1334169689Skan{ 1335169689Skan df_chain_dump (link, stderr); 1336169689Skan fputc ('\n', stderr); 1337169689Skan} 1338