1/* Allocation for dataflow support routines. 2 Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006 3 Free Software Foundation, Inc. 4 Originally contributed by Michael P. Hayes 5 (m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com) 6 Major rewrite contributed by Danny Berlin (dberlin@dberlin.org) 7 and Kenneth Zadeck (zadeck@naturalbridge.com). 8 9This file is part of GCC. 10 11GCC is free software; you can redistribute it and/or modify it under 12the terms of the GNU General Public License as published by the Free 13Software Foundation; either version 2, or (at your option) any later 14version. 15 16GCC is distributed in the hope that it will be useful, but WITHOUT ANY 17WARRANTY; without even the implied warranty of MERCHANTABILITY or 18FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 19for more details. 20 21You should have received a copy of the GNU General Public License 22along with GCC; see the file COPYING. If not, write to the Free 23Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 2402110-1301, USA. 25*/ 26 27/* 28OVERVIEW: 29 30The files in this collection (df*.c,df.h) provide a general framework 31for solving dataflow problems. The global dataflow is performed using 32a good implementation of iterative dataflow analysis. 33 34The file df-problems.c provides problem instance for the most common 35dataflow problems: reaching defs, upward exposed uses, live variables, 36uninitialized variables, def-use chains, and use-def chains. However, 37the interface allows other dataflow problems to be defined as well. 38 39 40USAGE: 41 42Here is an example of using the dataflow routines. 43 44 struct df *df; 45 46 df = df_init (init_flags); 47 48 df_add_problem (df, problem, flags); 49 50 df_set_blocks (df, blocks); 51 52 df_rescan_blocks (df, blocks); 53 54 df_analyze (df); 55 56 df_dump (df, stderr); 57 58 df_finish (df); 59 60 61 62DF_INIT simply creates a poor man's object (df) that needs to be 63passed to all the dataflow routines. df_finish destroys this object 64and frees up any allocated memory. 65 66There are three flags that can be passed to df_init, each of these 67flags controls the scanning of the rtl: 68 69DF_HARD_REGS means that the scanning is to build information about 70both pseudo registers and hardware registers. Without this 71information, the problems will be solved only on pseudo registers. 72DF_EQUIV_NOTES marks the uses present in EQUIV/EQUAL notes. 73DF_SUBREGS return subregs rather than the inner reg. 74 75 76DF_ADD_PROBLEM adds a problem, defined by an instance to struct 77df_problem, to the set of problems solved in this instance of df. All 78calls to add a problem for a given instance of df must occur before 79the first call to DF_RESCAN_BLOCKS, DF_SET_BLOCKS or DF_ANALYZE. 80 81For all of the problems defined in df-problems.c, there are 82convenience functions named DF_*_ADD_PROBLEM. 83 84 85Problems can be dependent on other problems. For instance, solving 86def-use or use-def chains is dependent on solving reaching 87definitions. As long as these dependencies are listed in the problem 88definition, the order of adding the problems is not material. 89Otherwise, the problems will be solved in the order of calls to 90df_add_problem. Note that it is not necessary to have a problem. In 91that case, df will just be used to do the scanning. 92 93 94 95DF_SET_BLOCKS is an optional call used to define a region of the 96function on which the analysis will be performed. The normal case is 97to analyze the entire function and no call to df_set_blocks is made. 98 99When a subset is given, the analysis behaves as if the function only 100contains those blocks and any edges that occur directly between the 101blocks in the set. Care should be taken to call df_set_blocks right 102before the call to analyze in order to eliminate the possibility that 103optimizations that reorder blocks invalidate the bitvector. 104 105 106 107DF_RESCAN_BLOCKS is an optional call that causes the scanner to be 108 (re)run over the set of blocks passed in. If blocks is NULL, the entire 109function (or all of the blocks defined in df_set_blocks) is rescanned. 110If blocks contains blocks that were not defined in the call to 111df_set_blocks, these blocks are added to the set of blocks. 112 113 114DF_ANALYZE causes all of the defined problems to be (re)solved. It 115does not cause blocks to be (re)scanned at the rtl level unless no 116prior call is made to df_rescan_blocks. When DF_ANALYZE is completes, 117the IN and OUT sets for each basic block contain the computer 118information. The DF_*_BB_INFO macros can be used to access these 119bitvectors. 120 121 122DF_DUMP can then be called to dump the information produce to some 123file. 124 125 126 127DF_FINISH causes all of the datastructures to be cleaned up and freed. 128The df_instance is also freed and its pointer should be NULLed. 129 130 131 132 133Scanning produces a `struct df_ref' data structure (ref) is allocated 134for every register reference (def or use) and this records the insn 135and bb the ref is found within. The refs are linked together in 136chains of uses and defs for each insn and for each register. Each ref 137also has a chain field that links all the use refs for a def or all 138the def refs for a use. This is used to create use-def or def-use 139chains. 140 141Different optimizations have different needs. Ultimately, only 142register allocation and schedulers should be using the bitmaps 143produced for the live register and uninitialized register problems. 144The rest of the backend should be upgraded to using and maintaining 145the linked information such as def use or use def chains. 146 147 148 149PHILOSOPHY: 150 151While incremental bitmaps are not worthwhile to maintain, incremental 152chains may be perfectly reasonable. The fastest way to build chains 153from scratch or after significant modifications is to build reaching 154definitions (RD) and build the chains from this. 155 156However, general algorithms for maintaining use-def or def-use chains 157are not practical. The amount of work to recompute the chain any 158chain after an arbitrary change is large. However, with a modest 159amount of work it is generally possible to have the application that 160uses the chains keep them up to date. The high level knowledge of 161what is really happening is essential to crafting efficient 162incremental algorithms. 163 164As for the bit vector problems, there is no interface to give a set of 165blocks over with to resolve the iteration. In general, restarting a 166dataflow iteration is difficult and expensive. Again, the best way to 167keep the dataflow information up to data (if this is really what is 168needed) it to formulate a problem specific solution. 169 170There are fine grained calls for creating and deleting references from 171instructions in df-scan.c. However, these are not currently connected 172to the engine that resolves the dataflow equations. 173 174 175DATA STRUCTURES: 176 177The basic object is a DF_REF (reference) and this may either be a 178DEF (definition) or a USE of a register. 179 180These are linked into a variety of lists; namely reg-def, reg-use, 181insn-def, insn-use, def-use, and use-def lists. For example, the 182reg-def lists contain all the locations that define a given register 183while the insn-use lists contain all the locations that use a 184register. 185 186Note that the reg-def and reg-use chains are generally short for 187pseudos and long for the hard registers. 188 189ACCESSING REFS: 190 191There are 4 ways to obtain access to refs: 192 1931) References are divided into two categories, REAL and ARTIFICIAL. 194 195 REAL refs are associated with instructions. They are linked into 196 either in the insn's defs list (accessed by the DF_INSN_DEFS or 197 DF_INSN_UID_DEFS macros) or the insn's uses list (accessed by the 198 DF_INSN_USES or DF_INSN_UID_USES macros). These macros produce a 199 ref (or NULL), the rest of the list can be obtained by traversal of 200 the NEXT_REF field (accessed by the DF_REF_NEXT_REF macro.) There 201 is no significance to the ordering of the uses or refs in an 202 instruction. 203 204 ARTIFICIAL refs are associated with basic blocks. The heads of 205 these lists can be accessed by calling get_artificial_defs or 206 get_artificial_uses for the particular basic block. Artificial 207 defs and uses are only there if DF_HARD_REGS was specified when the 208 df instance was created. 209 210 Artificial defs and uses occur both at the beginning and ends of blocks. 211 212 For blocks that area at the destination of eh edges, the 213 artificial uses and defs occur at the beginning. The defs relate 214 to the registers specified in EH_RETURN_DATA_REGNO and the uses 215 relate to the registers specified in ED_USES. Logically these 216 defs and uses should really occur along the eh edge, but there is 217 no convenient way to do this. Artificial edges that occur at the 218 beginning of the block have the DF_REF_AT_TOP flag set. 219 220 Artificial uses occur at the end of all blocks. These arise from 221 the hard registers that are always live, such as the stack 222 register and are put there to keep the code from forgetting about 223 them. 224 225 Artificial defs occur at the end of the entry block. These arise 226 from registers that are live at entry to the function. 227 2282) All of the uses and defs associated with each pseudo or hard 229 register are linked in a bidirectional chain. These are called 230 reg-use or reg_def chains. 231 232 The first use (or def) for a register can be obtained using the 233 DF_REG_USE_GET macro (or DF_REG_DEF_GET macro). Subsequent uses 234 for the same regno can be obtained by following the next_reg field 235 of the ref. 236 237 In previous versions of this code, these chains were ordered. It 238 has not been practical to continue this practice. 239 2403) If def-use or use-def chains are built, these can be traversed to 241 get to other refs. 242 2434) An array of all of the uses (and an array of all of the defs) can 244 be built. These arrays are indexed by the value in the id 245 structure. These arrays are only lazily kept up to date, and that 246 process can be expensive. To have these arrays built, call 247 df_reorganize_refs. Note that the values in the id field of a ref 248 may change across calls to df_analyze or df_reorganize refs. 249 250 If the only use of this array is to find all of the refs, it is 251 better to traverse all of the registers and then traverse all of 252 reg-use or reg-def chains. 253 254 255 256NOTES: 257 258Embedded addressing side-effects, such as POST_INC or PRE_INC, generate 259both a use and a def. These are both marked read/write to show that they 260are dependent. For example, (set (reg 40) (mem (post_inc (reg 42)))) 261will generate a use of reg 42 followed by a def of reg 42 (both marked 262read/write). Similarly, (set (reg 40) (mem (pre_dec (reg 41)))) 263generates a use of reg 41 then a def of reg 41 (both marked read/write), 264even though reg 41 is decremented before it is used for the memory 265address in this second example. 266 267A set to a REG inside a ZERO_EXTRACT, or a set to a non-paradoxical SUBREG 268for which the number of word_mode units covered by the outer mode is 269smaller than that covered by the inner mode, invokes a read-modify-write. 270operation. We generate both a use and a def and again mark them 271read/write. 272 273Paradoxical subreg writes do not leave a trace of the old content, so they 274are write-only operations. 275*/ 276 277 278#include "config.h" 279#include "system.h" 280#include "coretypes.h" 281#include "tm.h" 282#include "rtl.h" 283#include "tm_p.h" 284#include "insn-config.h" 285#include "recog.h" 286#include "function.h" 287#include "regs.h" 288#include "output.h" 289#include "alloc-pool.h" 290#include "flags.h" 291#include "hard-reg-set.h" 292#include "basic-block.h" 293#include "sbitmap.h" 294#include "bitmap.h" 295#include "timevar.h" 296#include "df.h" 297#include "tree-pass.h" 298 299static struct df *ddf = NULL; 300struct df *shared_df = NULL; 301 302static void *df_get_bb_info (struct dataflow *, unsigned int); 303static void df_set_bb_info (struct dataflow *, unsigned int, void *); 304/*---------------------------------------------------------------------------- 305 Functions to create, destroy and manipulate an instance of df. 306----------------------------------------------------------------------------*/ 307 308 309/* Initialize dataflow analysis and allocate and initialize dataflow 310 memory. */ 311 312struct df * 313df_init (int flags) 314{ 315 struct df *df = XCNEW (struct df); 316 317 /* This is executed once per compilation to initialize platform 318 specific data structures. */ 319 df_hard_reg_init (); 320 321 /* All df instance must define the scanning problem. */ 322 df_scan_add_problem (df, flags); 323 ddf = df; 324 return df; 325} 326 327/* Add PROBLEM to the DF instance. */ 328 329struct dataflow * 330df_add_problem (struct df *df, struct df_problem *problem, int flags) 331{ 332 struct dataflow *dflow; 333 334 /* First try to add the dependent problem. */ 335 if (problem->dependent_problem_fun) 336 (problem->dependent_problem_fun) (df, 0); 337 338 /* Check to see if this problem has already been defined. If it 339 has, just return that instance, if not, add it to the end of the 340 vector. */ 341 dflow = df->problems_by_index[problem->id]; 342 if (dflow) 343 return dflow; 344 345 /* Make a new one and add it to the end. */ 346 dflow = XCNEW (struct dataflow); 347 dflow->flags = flags; 348 dflow->df = df; 349 dflow->problem = problem; 350 df->problems_in_order[df->num_problems_defined++] = dflow; 351 df->problems_by_index[dflow->problem->id] = dflow; 352 353 return dflow; 354} 355 356 357/* Set the MASK flags in the DFLOW problem. The old flags are 358 returned. If a flag is not allowed to be changed this will fail if 359 checking is enabled. */ 360int 361df_set_flags (struct dataflow *dflow, int mask) 362{ 363 int old_flags = dflow->flags; 364 365 gcc_assert (!(mask & (~dflow->problem->changeable_flags))); 366 367 dflow->flags |= mask; 368 369 return old_flags; 370} 371 372/* Clear the MASK flags in the DFLOW problem. The old flags are 373 returned. If a flag is not allowed to be changed this will fail if 374 checking is enabled. */ 375int 376df_clear_flags (struct dataflow *dflow, int mask) 377{ 378 int old_flags = dflow->flags; 379 380 gcc_assert (!(mask & (~dflow->problem->changeable_flags))); 381 382 dflow->flags &= !mask; 383 384 return old_flags; 385} 386 387/* Set the blocks that are to be considered for analysis. If this is 388 not called or is called with null, the entire function in 389 analyzed. */ 390 391void 392df_set_blocks (struct df *df, bitmap blocks) 393{ 394 if (blocks) 395 { 396 if (df->blocks_to_analyze) 397 { 398 int p; 399 bitmap diff = BITMAP_ALLOC (NULL); 400 bitmap_and_compl (diff, df->blocks_to_analyze, blocks); 401 for (p = df->num_problems_defined - 1; p >= 0 ;p--) 402 { 403 struct dataflow *dflow = df->problems_in_order[p]; 404 if (dflow->problem->reset_fun) 405 dflow->problem->reset_fun (dflow, df->blocks_to_analyze); 406 else if (dflow->problem->free_bb_fun) 407 { 408 bitmap_iterator bi; 409 unsigned int bb_index; 410 411 EXECUTE_IF_SET_IN_BITMAP (diff, 0, bb_index, bi) 412 { 413 basic_block bb = BASIC_BLOCK (bb_index); 414 if (bb) 415 { 416 dflow->problem->free_bb_fun 417 (dflow, bb, df_get_bb_info (dflow, bb_index)); 418 df_set_bb_info (dflow, bb_index, NULL); 419 } 420 } 421 } 422 } 423 424 BITMAP_FREE (diff); 425 } 426 else 427 { 428 /* If we have not actually run scanning before, do not try 429 to clear anything. */ 430 struct dataflow *scan_dflow = df->problems_by_index [DF_SCAN]; 431 if (scan_dflow->problem_data) 432 { 433 bitmap blocks_to_reset = NULL; 434 int p; 435 for (p = df->num_problems_defined - 1; p >= 0 ;p--) 436 { 437 struct dataflow *dflow = df->problems_in_order[p]; 438 if (dflow->problem->reset_fun) 439 { 440 if (!blocks_to_reset) 441 { 442 basic_block bb; 443 blocks_to_reset = BITMAP_ALLOC (NULL); 444 FOR_ALL_BB(bb) 445 { 446 bitmap_set_bit (blocks_to_reset, bb->index); 447 } 448 } 449 dflow->problem->reset_fun (dflow, blocks_to_reset); 450 } 451 } 452 if (blocks_to_reset) 453 BITMAP_FREE (blocks_to_reset); 454 } 455 df->blocks_to_analyze = BITMAP_ALLOC (NULL); 456 } 457 bitmap_copy (df->blocks_to_analyze, blocks); 458 } 459 else 460 { 461 if (df->blocks_to_analyze) 462 { 463 BITMAP_FREE (df->blocks_to_analyze); 464 df->blocks_to_analyze = NULL; 465 } 466 } 467} 468 469 470/* Free all of the per basic block dataflow from all of the problems. 471 This is typically called before a basic block is deleted and the 472 problem will be reanalyzed. */ 473 474void 475df_delete_basic_block (struct df *df, int bb_index) 476{ 477 basic_block bb = BASIC_BLOCK (bb_index); 478 int i; 479 480 for (i = 0; i < df->num_problems_defined; i++) 481 { 482 struct dataflow *dflow = df->problems_in_order[i]; 483 if (dflow->problem->free_bb_fun) 484 dflow->problem->free_bb_fun 485 (dflow, bb, df_get_bb_info (dflow, bb_index)); 486 } 487} 488 489 490/* Free all the dataflow info and the DF structure. This should be 491 called from the df_finish macro which also NULLs the parm. */ 492 493void 494df_finish1 (struct df *df) 495{ 496 int i; 497 498 for (i = 0; i < df->num_problems_defined; i++) 499 df->problems_in_order[i]->problem->free_fun (df->problems_in_order[i]); 500 501 free (df); 502} 503 504 505/*---------------------------------------------------------------------------- 506 The general data flow analysis engine. 507----------------------------------------------------------------------------*/ 508 509 510/* Hybrid search algorithm from "Implementation Techniques for 511 Efficient Data-Flow Analysis of Large Programs". */ 512 513static void 514df_hybrid_search_forward (basic_block bb, 515 struct dataflow *dataflow, 516 bool single_pass) 517{ 518 int result_changed; 519 int i = bb->index; 520 edge e; 521 edge_iterator ei; 522 523 SET_BIT (dataflow->visited, bb->index); 524 gcc_assert (TEST_BIT (dataflow->pending, bb->index)); 525 RESET_BIT (dataflow->pending, i); 526 527 /* Calculate <conf_op> of predecessor_outs. */ 528 if (EDGE_COUNT (bb->preds) > 0) 529 FOR_EACH_EDGE (e, ei, bb->preds) 530 { 531 if (!TEST_BIT (dataflow->considered, e->src->index)) 532 continue; 533 534 dataflow->problem->con_fun_n (dataflow, e); 535 } 536 else if (dataflow->problem->con_fun_0) 537 dataflow->problem->con_fun_0 (dataflow, bb); 538 539 result_changed = dataflow->problem->trans_fun (dataflow, i); 540 541 if (!result_changed || single_pass) 542 return; 543 544 FOR_EACH_EDGE (e, ei, bb->succs) 545 { 546 if (e->dest->index == i) 547 continue; 548 if (!TEST_BIT (dataflow->considered, e->dest->index)) 549 continue; 550 SET_BIT (dataflow->pending, e->dest->index); 551 } 552 553 FOR_EACH_EDGE (e, ei, bb->succs) 554 { 555 if (e->dest->index == i) 556 continue; 557 558 if (!TEST_BIT (dataflow->considered, e->dest->index)) 559 continue; 560 if (!TEST_BIT (dataflow->visited, e->dest->index)) 561 df_hybrid_search_forward (e->dest, dataflow, single_pass); 562 } 563} 564 565static void 566df_hybrid_search_backward (basic_block bb, 567 struct dataflow *dataflow, 568 bool single_pass) 569{ 570 int result_changed; 571 int i = bb->index; 572 edge e; 573 edge_iterator ei; 574 575 SET_BIT (dataflow->visited, bb->index); 576 gcc_assert (TEST_BIT (dataflow->pending, bb->index)); 577 RESET_BIT (dataflow->pending, i); 578 579 /* Calculate <conf_op> of predecessor_outs. */ 580 if (EDGE_COUNT (bb->succs) > 0) 581 FOR_EACH_EDGE (e, ei, bb->succs) 582 { 583 if (!TEST_BIT (dataflow->considered, e->dest->index)) 584 continue; 585 586 dataflow->problem->con_fun_n (dataflow, e); 587 } 588 else if (dataflow->problem->con_fun_0) 589 dataflow->problem->con_fun_0 (dataflow, bb); 590 591 result_changed = dataflow->problem->trans_fun (dataflow, i); 592 593 if (!result_changed || single_pass) 594 return; 595 596 FOR_EACH_EDGE (e, ei, bb->preds) 597 { 598 if (e->src->index == i) 599 continue; 600 601 if (!TEST_BIT (dataflow->considered, e->src->index)) 602 continue; 603 604 SET_BIT (dataflow->pending, e->src->index); 605 } 606 607 FOR_EACH_EDGE (e, ei, bb->preds) 608 { 609 if (e->src->index == i) 610 continue; 611 612 if (!TEST_BIT (dataflow->considered, e->src->index)) 613 continue; 614 615 if (!TEST_BIT (dataflow->visited, e->src->index)) 616 df_hybrid_search_backward (e->src, dataflow, single_pass); 617 } 618} 619 620 621/* This function will perform iterative bitvector dataflow described 622 by DATAFLOW, producing the in and out sets. Only the part of the 623 cfg induced by blocks in DATAFLOW->order is taken into account. 624 625 SINGLE_PASS is true if you just want to make one pass over the 626 blocks. */ 627 628void 629df_iterative_dataflow (struct dataflow *dataflow, 630 bitmap blocks_to_consider, bitmap blocks_to_init, 631 int *blocks_in_postorder, int n_blocks, 632 bool single_pass) 633{ 634 unsigned int idx; 635 int i; 636 sbitmap visited = sbitmap_alloc (last_basic_block); 637 sbitmap pending = sbitmap_alloc (last_basic_block); 638 sbitmap considered = sbitmap_alloc (last_basic_block); 639 bitmap_iterator bi; 640 641 dataflow->visited = visited; 642 dataflow->pending = pending; 643 dataflow->considered = considered; 644 645 sbitmap_zero (visited); 646 sbitmap_zero (pending); 647 sbitmap_zero (considered); 648 649 gcc_assert (dataflow->problem->dir); 650 651 EXECUTE_IF_SET_IN_BITMAP (blocks_to_consider, 0, idx, bi) 652 { 653 SET_BIT (considered, idx); 654 } 655 656 for (i = 0; i < n_blocks; i++) 657 { 658 idx = blocks_in_postorder[i]; 659 SET_BIT (pending, idx); 660 }; 661 662 dataflow->problem->init_fun (dataflow, blocks_to_init); 663 664 while (1) 665 { 666 667 /* For forward problems, you want to pass in reverse postorder 668 and for backward problems you want postorder. This has been 669 shown to be as good as you can do by several people, the 670 first being Mathew Hecht in his phd dissertation. 671 672 The nodes are passed into this function in postorder. */ 673 674 if (dataflow->problem->dir == DF_FORWARD) 675 { 676 for (i = n_blocks - 1 ; i >= 0 ; i--) 677 { 678 idx = blocks_in_postorder[i]; 679 680 if (TEST_BIT (pending, idx) && !TEST_BIT (visited, idx)) 681 df_hybrid_search_forward (BASIC_BLOCK (idx), dataflow, single_pass); 682 } 683 } 684 else 685 { 686 for (i = 0; i < n_blocks; i++) 687 { 688 idx = blocks_in_postorder[i]; 689 690 if (TEST_BIT (pending, idx) && !TEST_BIT (visited, idx)) 691 df_hybrid_search_backward (BASIC_BLOCK (idx), dataflow, single_pass); 692 } 693 } 694 695 if (sbitmap_first_set_bit (pending) == -1) 696 break; 697 698 sbitmap_zero (visited); 699 } 700 701 sbitmap_free (pending); 702 sbitmap_free (visited); 703 sbitmap_free (considered); 704} 705 706 707/* Remove the entries not in BLOCKS from the LIST of length LEN, preserving 708 the order of the remaining entries. Returns the length of the resulting 709 list. */ 710 711static unsigned 712df_prune_to_subcfg (int list[], unsigned len, bitmap blocks) 713{ 714 unsigned act, last; 715 716 for (act = 0, last = 0; act < len; act++) 717 if (bitmap_bit_p (blocks, list[act])) 718 list[last++] = list[act]; 719 720 return last; 721} 722 723 724/* Execute dataflow analysis on a single dataflow problem. 725 726 There are three sets of blocks passed in: 727 728 BLOCKS_TO_CONSIDER are the blocks whose solution can either be 729 examined or will be computed. For calls from DF_ANALYZE, this is 730 the set of blocks that has been passed to DF_SET_BLOCKS. For calls 731 from DF_ANALYZE_SIMPLE_CHANGE_SOME_BLOCKS, this is the set of 732 blocks in the fringe (the set of blocks passed in plus the set of 733 immed preds and succs of those blocks). 734 735 BLOCKS_TO_INIT are the blocks whose solution will be changed by 736 this iteration. For calls from DF_ANALYZE, this is the set of 737 blocks that has been passed to DF_SET_BLOCKS. For calls from 738 DF_ANALYZE_SIMPLE_CHANGE_SOME_BLOCKS, this is the set of blocks 739 passed in. 740 741 BLOCKS_TO_SCAN are the set of blocks that need to be rescanned. 742 For calls from DF_ANALYZE, this is the accumulated set of blocks 743 that has been passed to DF_RESCAN_BLOCKS since the last call to 744 DF_ANALYZE. For calls from DF_ANALYZE_SIMPLE_CHANGE_SOME_BLOCKS, 745 this is the set of blocks passed in. 746 747 blocks_to_consider blocks_to_init blocks_to_scan 748 full redo all all all 749 partial redo all all sub 750 small fixup fringe sub sub 751*/ 752 753void 754df_analyze_problem (struct dataflow *dflow, 755 bitmap blocks_to_consider, 756 bitmap blocks_to_init, 757 bitmap blocks_to_scan, 758 int *postorder, int n_blocks, bool single_pass) 759{ 760 /* (Re)Allocate the datastructures necessary to solve the problem. */ 761 if (dflow->problem->alloc_fun) 762 dflow->problem->alloc_fun (dflow, blocks_to_scan, blocks_to_init); 763 764 /* Set up the problem and compute the local information. This 765 function is passed both the blocks_to_consider and the 766 blocks_to_scan because the RD and RU problems require the entire 767 function to be rescanned if they are going to be updated. */ 768 if (dflow->problem->local_compute_fun) 769 dflow->problem->local_compute_fun (dflow, blocks_to_consider, blocks_to_scan); 770 771 /* Solve the equations. */ 772 if (dflow->problem->dataflow_fun) 773 dflow->problem->dataflow_fun (dflow, blocks_to_consider, blocks_to_init, 774 postorder, n_blocks, single_pass); 775 776 /* Massage the solution. */ 777 if (dflow->problem->finalize_fun) 778 dflow->problem->finalize_fun (dflow, blocks_to_consider); 779} 780 781 782/* Analyze dataflow info for the basic blocks specified by the bitmap 783 BLOCKS, or for the whole CFG if BLOCKS is zero. */ 784 785void 786df_analyze (struct df *df) 787{ 788 int *postorder = XNEWVEC (int, last_basic_block); 789 bitmap current_all_blocks = BITMAP_ALLOC (NULL); 790 int n_blocks; 791 int i; 792 bool everything; 793 794 n_blocks = post_order_compute (postorder, true); 795 796 if (n_blocks != n_basic_blocks) 797 delete_unreachable_blocks (); 798 799 for (i = 0; i < n_blocks; i++) 800 bitmap_set_bit (current_all_blocks, postorder[i]); 801 802 /* No one called df_rescan_blocks, so do it. */ 803 if (!df->blocks_to_scan) 804 df_rescan_blocks (df, NULL); 805 806 /* Make sure that we have pruned any unreachable blocks from these 807 sets. */ 808 bitmap_and_into (df->blocks_to_scan, current_all_blocks); 809 810 if (df->blocks_to_analyze) 811 { 812 everything = false; 813 bitmap_and_into (df->blocks_to_analyze, current_all_blocks); 814 n_blocks = df_prune_to_subcfg (postorder, n_blocks, df->blocks_to_analyze); 815 BITMAP_FREE (current_all_blocks); 816 } 817 else 818 { 819 everything = true; 820 df->blocks_to_analyze = current_all_blocks; 821 current_all_blocks = NULL; 822 } 823 824 /* Skip over the DF_SCAN problem. */ 825 for (i = 1; i < df->num_problems_defined; i++) 826 df_analyze_problem (df->problems_in_order[i], 827 df->blocks_to_analyze, df->blocks_to_analyze, 828 df->blocks_to_scan, 829 postorder, n_blocks, false); 830 831 if (everything) 832 { 833 BITMAP_FREE (df->blocks_to_analyze); 834 df->blocks_to_analyze = NULL; 835 } 836 837 BITMAP_FREE (df->blocks_to_scan); 838 df->blocks_to_scan = NULL; 839 free (postorder); 840} 841 842 843 844/*---------------------------------------------------------------------------- 845 Functions to support limited incremental change. 846----------------------------------------------------------------------------*/ 847 848 849/* Get basic block info. */ 850 851static void * 852df_get_bb_info (struct dataflow *dflow, unsigned int index) 853{ 854 return (struct df_scan_bb_info *) dflow->block_info[index]; 855} 856 857 858/* Set basic block info. */ 859 860static void 861df_set_bb_info (struct dataflow *dflow, unsigned int index, 862 void *bb_info) 863{ 864 dflow->block_info[index] = bb_info; 865} 866 867 868/* Called from the rtl_compact_blocks to reorganize the problems basic 869 block info. */ 870 871void 872df_compact_blocks (struct df *df) 873{ 874 int i, p; 875 basic_block bb; 876 void **problem_temps; 877 int size = last_basic_block *sizeof (void *); 878 problem_temps = xmalloc (size); 879 880 for (p = 0; p < df->num_problems_defined; p++) 881 { 882 struct dataflow *dflow = df->problems_in_order[p]; 883 if (dflow->problem->free_bb_fun) 884 { 885 df_grow_bb_info (dflow); 886 memcpy (problem_temps, dflow->block_info, size); 887 888 /* Copy the bb info from the problem tmps to the proper 889 place in the block_info vector. Null out the copied 890 item. */ 891 i = NUM_FIXED_BLOCKS; 892 FOR_EACH_BB (bb) 893 { 894 df_set_bb_info (dflow, i, problem_temps[bb->index]); 895 problem_temps[bb->index] = NULL; 896 i++; 897 } 898 memset (dflow->block_info + i, 0, 899 (last_basic_block - i) *sizeof (void *)); 900 901 /* Free any block infos that were not copied (and NULLed). 902 These are from orphaned blocks. */ 903 for (i = NUM_FIXED_BLOCKS; i < last_basic_block; i++) 904 { 905 basic_block bb = BASIC_BLOCK (i); 906 if (problem_temps[i] && bb) 907 dflow->problem->free_bb_fun 908 (dflow, bb, problem_temps[i]); 909 } 910 } 911 } 912 913 free (problem_temps); 914 915 i = NUM_FIXED_BLOCKS; 916 FOR_EACH_BB (bb) 917 { 918 SET_BASIC_BLOCK (i, bb); 919 bb->index = i; 920 i++; 921 } 922 923 gcc_assert (i == n_basic_blocks); 924 925 for (; i < last_basic_block; i++) 926 SET_BASIC_BLOCK (i, NULL); 927} 928 929 930/* Shove NEW_BLOCK in at OLD_INDEX. Called from if-cvt to hack a 931 block. There is no excuse for people to do this kind of thing. */ 932 933void 934df_bb_replace (struct df *df, int old_index, basic_block new_block) 935{ 936 int p; 937 938 for (p = 0; p < df->num_problems_defined; p++) 939 { 940 struct dataflow *dflow = df->problems_in_order[p]; 941 if (dflow->block_info) 942 { 943 void *temp; 944 945 df_grow_bb_info (dflow); 946 947 /* The old switcheroo. */ 948 949 temp = df_get_bb_info (dflow, old_index); 950 df_set_bb_info (dflow, old_index, 951 df_get_bb_info (dflow, new_block->index)); 952 df_set_bb_info (dflow, new_block->index, temp); 953 } 954 } 955 956 SET_BASIC_BLOCK (old_index, new_block); 957 new_block->index = old_index; 958} 959 960/*---------------------------------------------------------------------------- 961 PUBLIC INTERFACES TO QUERY INFORMATION. 962----------------------------------------------------------------------------*/ 963 964 965/* Return last use of REGNO within BB. */ 966 967struct df_ref * 968df_bb_regno_last_use_find (struct df *df, basic_block bb, unsigned int regno) 969{ 970 rtx insn; 971 struct df_ref *use; 972 unsigned int uid; 973 974 FOR_BB_INSNS_REVERSE (bb, insn) 975 { 976 if (!INSN_P (insn)) 977 continue; 978 979 uid = INSN_UID (insn); 980 for (use = DF_INSN_UID_GET (df, uid)->uses; use; use = use->next_ref) 981 if (DF_REF_REGNO (use) == regno) 982 return use; 983 } 984 return NULL; 985} 986 987 988/* Return first def of REGNO within BB. */ 989 990struct df_ref * 991df_bb_regno_first_def_find (struct df *df, basic_block bb, unsigned int regno) 992{ 993 rtx insn; 994 struct df_ref *def; 995 unsigned int uid; 996 997 FOR_BB_INSNS (bb, insn) 998 { 999 if (!INSN_P (insn)) 1000 continue; 1001 1002 uid = INSN_UID (insn); 1003 for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref) 1004 if (DF_REF_REGNO (def) == regno) 1005 return def; 1006 } 1007 return NULL; 1008} 1009 1010 1011/* Return last def of REGNO within BB. */ 1012 1013struct df_ref * 1014df_bb_regno_last_def_find (struct df *df, basic_block bb, unsigned int regno) 1015{ 1016 rtx insn; 1017 struct df_ref *def; 1018 unsigned int uid; 1019 1020 FOR_BB_INSNS_REVERSE (bb, insn) 1021 { 1022 if (!INSN_P (insn)) 1023 continue; 1024 1025 uid = INSN_UID (insn); 1026 for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref) 1027 if (DF_REF_REGNO (def) == regno) 1028 return def; 1029 } 1030 1031 return NULL; 1032} 1033 1034/* Return true if INSN defines REGNO. */ 1035 1036bool 1037df_insn_regno_def_p (struct df *df, rtx insn, unsigned int regno) 1038{ 1039 unsigned int uid; 1040 struct df_ref *def; 1041 1042 uid = INSN_UID (insn); 1043 for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref) 1044 if (DF_REF_REGNO (def) == regno) 1045 return true; 1046 1047 return false; 1048} 1049 1050 1051/* Finds the reference corresponding to the definition of REG in INSN. 1052 DF is the dataflow object. */ 1053 1054struct df_ref * 1055df_find_def (struct df *df, rtx insn, rtx reg) 1056{ 1057 unsigned int uid; 1058 struct df_ref *def; 1059 1060 if (GET_CODE (reg) == SUBREG) 1061 reg = SUBREG_REG (reg); 1062 gcc_assert (REG_P (reg)); 1063 1064 uid = INSN_UID (insn); 1065 for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref) 1066 if (rtx_equal_p (DF_REF_REAL_REG (def), reg)) 1067 return def; 1068 1069 return NULL; 1070} 1071 1072 1073/* Return true if REG is defined in INSN, zero otherwise. */ 1074 1075bool 1076df_reg_defined (struct df *df, rtx insn, rtx reg) 1077{ 1078 return df_find_def (df, insn, reg) != NULL; 1079} 1080 1081 1082/* Finds the reference corresponding to the use of REG in INSN. 1083 DF is the dataflow object. */ 1084 1085struct df_ref * 1086df_find_use (struct df *df, rtx insn, rtx reg) 1087{ 1088 unsigned int uid; 1089 struct df_ref *use; 1090 1091 if (GET_CODE (reg) == SUBREG) 1092 reg = SUBREG_REG (reg); 1093 gcc_assert (REG_P (reg)); 1094 1095 uid = INSN_UID (insn); 1096 for (use = DF_INSN_UID_GET (df, uid)->uses; use; use = use->next_ref) 1097 if (rtx_equal_p (DF_REF_REAL_REG (use), reg)) 1098 return use; 1099 1100 return NULL; 1101} 1102 1103 1104/* Return true if REG is referenced in INSN, zero otherwise. */ 1105 1106bool 1107df_reg_used (struct df *df, rtx insn, rtx reg) 1108{ 1109 return df_find_use (df, insn, reg) != NULL; 1110} 1111 1112 1113/*---------------------------------------------------------------------------- 1114 Debugging and printing functions. 1115----------------------------------------------------------------------------*/ 1116 1117/* Dump dataflow info. */ 1118void 1119df_dump (struct df *df, FILE *file) 1120{ 1121 int i; 1122 1123 if (!df || !file) 1124 return; 1125 1126 fprintf (file, "\n\n%s\n", current_function_name ()); 1127 fprintf (file, "\nDataflow summary:\n"); 1128 fprintf (file, "def_info->bitmap_size = %d, use_info->bitmap_size = %d\n", 1129 df->def_info.bitmap_size, df->use_info.bitmap_size); 1130 1131 for (i = 0; i < df->num_problems_defined; i++) 1132 df->problems_in_order[i]->problem->dump_fun (df->problems_in_order[i], file); 1133 1134 fprintf (file, "\n"); 1135} 1136 1137 1138void 1139df_refs_chain_dump (struct df_ref *ref, bool follow_chain, FILE *file) 1140{ 1141 fprintf (file, "{ "); 1142 while (ref) 1143 { 1144 fprintf (file, "%c%d(%d) ", 1145 DF_REF_REG_DEF_P (ref) ? 'd' : 'u', 1146 DF_REF_ID (ref), 1147 DF_REF_REGNO (ref)); 1148 if (follow_chain) 1149 df_chain_dump (DF_REF_CHAIN (ref), file); 1150 ref = ref->next_ref; 1151 } 1152 fprintf (file, "}"); 1153} 1154 1155 1156/* Dump either a ref-def or reg-use chain. */ 1157 1158void 1159df_regs_chain_dump (struct df *df ATTRIBUTE_UNUSED, struct df_ref *ref, FILE *file) 1160{ 1161 fprintf (file, "{ "); 1162 while (ref) 1163 { 1164 fprintf (file, "%c%d(%d) ", 1165 DF_REF_REG_DEF_P (ref) ? 'd' : 'u', 1166 DF_REF_ID (ref), 1167 DF_REF_REGNO (ref)); 1168 ref = ref->next_reg; 1169 } 1170 fprintf (file, "}"); 1171} 1172 1173 1174static void 1175df_mws_dump (struct df_mw_hardreg *mws, FILE *file) 1176{ 1177 while (mws) 1178 { 1179 struct df_link *regs = mws->regs; 1180 fprintf (file, "%c%d(", 1181 (mws->type == DF_REF_REG_DEF) ? 'd' : 'u', 1182 DF_REF_REGNO (regs->ref)); 1183 while (regs) 1184 { 1185 fprintf (file, "%d ", DF_REF_REGNO (regs->ref)); 1186 regs = regs->next; 1187 } 1188 1189 fprintf (file, ") "); 1190 mws = mws->next; 1191 } 1192} 1193 1194 1195static void 1196df_insn_uid_debug (struct df *df, unsigned int uid, 1197 bool follow_chain, FILE *file) 1198{ 1199 int bbi; 1200 1201 if (DF_INSN_UID_DEFS (df, uid)) 1202 bbi = DF_REF_BBNO (DF_INSN_UID_DEFS (df, uid)); 1203 else if (DF_INSN_UID_USES(df, uid)) 1204 bbi = DF_REF_BBNO (DF_INSN_UID_USES (df, uid)); 1205 else 1206 bbi = -1; 1207 1208 fprintf (file, "insn %d bb %d luid %d", 1209 uid, bbi, DF_INSN_UID_LUID (df, uid)); 1210 1211 if (DF_INSN_UID_DEFS (df, uid)) 1212 { 1213 fprintf (file, " defs "); 1214 df_refs_chain_dump (DF_INSN_UID_DEFS (df, uid), follow_chain, file); 1215 } 1216 1217 if (DF_INSN_UID_USES (df, uid)) 1218 { 1219 fprintf (file, " uses "); 1220 df_refs_chain_dump (DF_INSN_UID_USES (df, uid), follow_chain, file); 1221 } 1222 1223 if (DF_INSN_UID_MWS (df, uid)) 1224 { 1225 fprintf (file, " mws "); 1226 df_mws_dump (DF_INSN_UID_MWS (df, uid), file); 1227 } 1228 fprintf (file, "\n"); 1229} 1230 1231 1232void 1233df_insn_debug (struct df *df, rtx insn, bool follow_chain, FILE *file) 1234{ 1235 df_insn_uid_debug (df, INSN_UID (insn), follow_chain, file); 1236} 1237 1238void 1239df_insn_debug_regno (struct df *df, rtx insn, FILE *file) 1240{ 1241 unsigned int uid; 1242 int bbi; 1243 1244 uid = INSN_UID (insn); 1245 if (DF_INSN_UID_DEFS (df, uid)) 1246 bbi = DF_REF_BBNO (DF_INSN_UID_DEFS (df, uid)); 1247 else if (DF_INSN_UID_USES(df, uid)) 1248 bbi = DF_REF_BBNO (DF_INSN_UID_USES (df, uid)); 1249 else 1250 bbi = -1; 1251 1252 fprintf (file, "insn %d bb %d luid %d defs ", 1253 uid, bbi, DF_INSN_LUID (df, insn)); 1254 df_regs_chain_dump (df, DF_INSN_UID_DEFS (df, uid), file); 1255 1256 fprintf (file, " uses "); 1257 df_regs_chain_dump (df, DF_INSN_UID_USES (df, uid), file); 1258 fprintf (file, "\n"); 1259} 1260 1261void 1262df_regno_debug (struct df *df, unsigned int regno, FILE *file) 1263{ 1264 fprintf (file, "reg %d defs ", regno); 1265 df_regs_chain_dump (df, DF_REG_DEF_GET (df, regno)->reg_chain, file); 1266 fprintf (file, " uses "); 1267 df_regs_chain_dump (df, DF_REG_USE_GET (df, regno)->reg_chain, file); 1268 fprintf (file, "\n"); 1269} 1270 1271 1272void 1273df_ref_debug (struct df_ref *ref, FILE *file) 1274{ 1275 fprintf (file, "%c%d ", 1276 DF_REF_REG_DEF_P (ref) ? 'd' : 'u', 1277 DF_REF_ID (ref)); 1278 fprintf (file, "reg %d bb %d insn %d flag %x chain ", 1279 DF_REF_REGNO (ref), 1280 DF_REF_BBNO (ref), 1281 DF_REF_INSN (ref) ? INSN_UID (DF_REF_INSN (ref)) : -1, 1282 DF_REF_FLAGS (ref)); 1283 df_chain_dump (DF_REF_CHAIN (ref), file); 1284 fprintf (file, "\n"); 1285} 1286 1287/* Functions for debugging from GDB. */ 1288 1289void 1290debug_df_insn (rtx insn) 1291{ 1292 df_insn_debug (ddf, insn, true, stderr); 1293 debug_rtx (insn); 1294} 1295 1296 1297void 1298debug_df_reg (rtx reg) 1299{ 1300 df_regno_debug (ddf, REGNO (reg), stderr); 1301} 1302 1303 1304void 1305debug_df_regno (unsigned int regno) 1306{ 1307 df_regno_debug (ddf, regno, stderr); 1308} 1309 1310 1311void 1312debug_df_ref (struct df_ref *ref) 1313{ 1314 df_ref_debug (ref, stderr); 1315} 1316 1317 1318void 1319debug_df_defno (unsigned int defno) 1320{ 1321 df_ref_debug (DF_DEFS_GET (ddf, defno), stderr); 1322} 1323 1324 1325void 1326debug_df_useno (unsigned int defno) 1327{ 1328 df_ref_debug (DF_USES_GET (ddf, defno), stderr); 1329} 1330 1331 1332void 1333debug_df_chain (struct df_link *link) 1334{ 1335 df_chain_dump (link, stderr); 1336 fputc ('\n', stderr); 1337} 1338