1169689Skan/* Standard problems 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#include "config.h" 27169689Skan#include "system.h" 28169689Skan#include "coretypes.h" 29169689Skan#include "tm.h" 30169689Skan#include "rtl.h" 31169689Skan#include "tm_p.h" 32169689Skan#include "insn-config.h" 33169689Skan#include "recog.h" 34169689Skan#include "function.h" 35169689Skan#include "regs.h" 36169689Skan#include "output.h" 37169689Skan#include "alloc-pool.h" 38169689Skan#include "flags.h" 39169689Skan#include "hard-reg-set.h" 40169689Skan#include "basic-block.h" 41169689Skan#include "sbitmap.h" 42169689Skan#include "bitmap.h" 43169689Skan#include "timevar.h" 44169689Skan#include "df.h" 45169689Skan#include "vecprim.h" 46169689Skan#include "except.h" 47169689Skan 48169689Skan#if 0 49169689Skan#define REG_DEAD_DEBUGGING 50169689Skan#endif 51169689Skan 52169689Skan#define DF_SPARSE_THRESHOLD 32 53169689Skan 54169689Skanstatic bitmap seen_in_block = NULL; 55169689Skanstatic bitmap seen_in_insn = NULL; 56169689Skanstatic void df_ri_dump (struct dataflow *, FILE *); 57169689Skan 58169689Skan 59169689Skan/*---------------------------------------------------------------------------- 60169689Skan Public functions access functions for the dataflow problems. 61169689Skan----------------------------------------------------------------------------*/ 62169689Skan 63169689Skan/* Create a du or ud chain from SRC to DST and link it into SRC. */ 64169689Skan 65169689Skanstruct df_link * 66169689Skandf_chain_create (struct dataflow *dflow, struct df_ref *src, struct df_ref *dst) 67169689Skan{ 68169689Skan struct df_link *head = DF_REF_CHAIN (src); 69169689Skan struct df_link *link = pool_alloc (dflow->block_pool);; 70169689Skan 71169689Skan DF_REF_CHAIN (src) = link; 72169689Skan link->next = head; 73169689Skan link->ref = dst; 74169689Skan return link; 75169689Skan} 76169689Skan 77169689Skan 78169689Skan/* Delete a du or ud chain for REF. If LINK is NULL, delete all 79169689Skan chains for ref and check to see if the reverse chains can also be 80169689Skan deleted. If LINK is not NULL it must be a link off of ref. In 81169689Skan this case, the other end is not deleted. */ 82169689Skan 83169689Skanvoid 84169689Skandf_chain_unlink (struct dataflow *dflow, struct df_ref *ref, struct df_link *link) 85169689Skan{ 86169689Skan struct df_link *chain = DF_REF_CHAIN (ref); 87169689Skan if (link) 88169689Skan { 89169689Skan /* Link was the first element in the chain. */ 90169689Skan if (chain == link) 91169689Skan DF_REF_CHAIN (ref) = link->next; 92169689Skan else 93169689Skan { 94169689Skan /* Link is an internal element in the chain. */ 95169689Skan struct df_link *prev = chain; 96169689Skan while (chain) 97169689Skan { 98169689Skan if (chain == link) 99169689Skan { 100169689Skan prev->next = chain->next; 101169689Skan break; 102169689Skan } 103169689Skan prev = chain; 104169689Skan chain = chain->next; 105169689Skan } 106169689Skan } 107169689Skan pool_free (dflow->block_pool, link); 108169689Skan } 109169689Skan else 110169689Skan { 111169689Skan /* If chain is NULL here, it was because of a recursive call 112169689Skan when the other flavor of chains was not built. Just run thru 113169689Skan the entire chain calling the other side and then deleting the 114169689Skan link. */ 115169689Skan while (chain) 116169689Skan { 117169689Skan struct df_link *next = chain->next; 118169689Skan /* Delete the other side if it exists. */ 119169689Skan df_chain_unlink (dflow, chain->ref, chain); 120169689Skan chain = next; 121169689Skan } 122169689Skan } 123169689Skan} 124169689Skan 125169689Skan 126169689Skan/* Copy the du or ud chain starting at FROM_REF and attach it to 127169689Skan TO_REF. */ 128169689Skan 129169689Skanvoid 130169689Skandf_chain_copy (struct dataflow *dflow, 131169689Skan struct df_ref *to_ref, 132169689Skan struct df_link *from_ref) 133169689Skan{ 134169689Skan while (from_ref) 135169689Skan { 136169689Skan df_chain_create (dflow, to_ref, from_ref->ref); 137169689Skan from_ref = from_ref->next; 138169689Skan } 139169689Skan} 140169689Skan 141169689Skan 142169689Skan/* Get the live in set for BB no matter what problem happens to be 143169689Skan defined. */ 144169689Skan 145169689Skanbitmap 146169689Skandf_get_live_in (struct df *df, basic_block bb) 147169689Skan{ 148169689Skan gcc_assert (df->problems_by_index[DF_LR]); 149169689Skan 150169689Skan if (df->problems_by_index[DF_UREC]) 151169689Skan return DF_RA_LIVE_IN (df, bb); 152169689Skan else if (df->problems_by_index[DF_UR]) 153169689Skan return DF_LIVE_IN (df, bb); 154169689Skan else 155169689Skan return DF_UPWARD_LIVE_IN (df, bb); 156169689Skan} 157169689Skan 158169689Skan 159169689Skan/* Get the live out set for BB no matter what problem happens to be 160169689Skan defined. */ 161169689Skan 162169689Skanbitmap 163169689Skandf_get_live_out (struct df *df, basic_block bb) 164169689Skan{ 165169689Skan gcc_assert (df->problems_by_index[DF_LR]); 166169689Skan 167169689Skan if (df->problems_by_index[DF_UREC]) 168169689Skan return DF_RA_LIVE_OUT (df, bb); 169169689Skan else if (df->problems_by_index[DF_UR]) 170169689Skan return DF_LIVE_OUT (df, bb); 171169689Skan else 172169689Skan return DF_UPWARD_LIVE_OUT (df, bb); 173169689Skan} 174169689Skan 175169689Skan 176169689Skan/*---------------------------------------------------------------------------- 177169689Skan Utility functions. 178169689Skan----------------------------------------------------------------------------*/ 179169689Skan 180169689Skan/* Generic versions to get the void* version of the block info. Only 181169689Skan used inside the problem instance vectors. */ 182169689Skan 183169689Skan/* Grow the bb_info array. */ 184169689Skan 185169689Skanvoid 186169689Skandf_grow_bb_info (struct dataflow *dflow) 187169689Skan{ 188169689Skan unsigned int new_size = last_basic_block + 1; 189169689Skan if (dflow->block_info_size < new_size) 190169689Skan { 191169689Skan new_size += new_size / 4; 192169689Skan dflow->block_info = xrealloc (dflow->block_info, 193169689Skan new_size *sizeof (void*)); 194169689Skan memset (dflow->block_info + dflow->block_info_size, 0, 195169689Skan (new_size - dflow->block_info_size) *sizeof (void *)); 196169689Skan dflow->block_info_size = new_size; 197169689Skan } 198169689Skan} 199169689Skan 200169689Skan/* Dump a def-use or use-def chain for REF to FILE. */ 201169689Skan 202169689Skanvoid 203169689Skandf_chain_dump (struct df_link *link, FILE *file) 204169689Skan{ 205169689Skan fprintf (file, "{ "); 206169689Skan for (; link; link = link->next) 207169689Skan { 208169689Skan fprintf (file, "%c%d(bb %d insn %d) ", 209169689Skan DF_REF_REG_DEF_P (link->ref) ? 'd' : 'u', 210169689Skan DF_REF_ID (link->ref), 211169689Skan DF_REF_BBNO (link->ref), 212169689Skan DF_REF_INSN (link->ref) ? DF_REF_INSN_UID (link->ref) : -1); 213169689Skan } 214169689Skan fprintf (file, "}"); 215169689Skan} 216169689Skan 217169689Skan 218169689Skan/* Print some basic block info as part of df_dump. */ 219169689Skan 220169689Skanvoid 221169689Skandf_print_bb_index (basic_block bb, FILE *file) 222169689Skan{ 223169689Skan edge e; 224169689Skan edge_iterator ei; 225169689Skan 226169689Skan fprintf (file, "( "); 227169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 228169689Skan { 229169689Skan basic_block pred = e->src; 230169689Skan fprintf (file, "%d ", pred->index); 231169689Skan } 232169689Skan fprintf (file, ")->[%d]->( ", bb->index); 233169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 234169689Skan { 235169689Skan basic_block succ = e->dest; 236169689Skan fprintf (file, "%d ", succ->index); 237169689Skan } 238169689Skan fprintf (file, ")\n"); 239169689Skan} 240169689Skan 241169689Skan 242169689Skan/* Return a bitmap for REGNO from the cache MAPS. The bitmap is to 243169689Skan contain COUNT bits starting at START. These bitmaps are not to be 244169689Skan changed since there is a cache of them. */ 245169689Skan 246169689Skanstatic inline bitmap 247169689Skandf_ref_bitmap (bitmap *maps, unsigned int regno, int start, int count) 248169689Skan{ 249169689Skan bitmap ids = maps[regno]; 250169689Skan if (!ids) 251169689Skan { 252169689Skan unsigned int i; 253169689Skan unsigned int end = start + count;; 254169689Skan ids = BITMAP_ALLOC (NULL); 255169689Skan maps[regno] = ids; 256169689Skan for (i = start; i < end; i++) 257169689Skan bitmap_set_bit (ids, i); 258169689Skan } 259169689Skan return ids; 260169689Skan} 261169689Skan 262169689Skan 263169689Skan/* Make sure that the seen_in_insn and seen_in_block sbitmaps are set 264169689Skan up correctly. */ 265169689Skan 266169689Skanstatic void 267169689Skandf_set_seen (void) 268169689Skan{ 269169689Skan seen_in_block = BITMAP_ALLOC (NULL); 270169689Skan seen_in_insn = BITMAP_ALLOC (NULL); 271169689Skan} 272169689Skan 273169689Skan 274169689Skanstatic void 275169689Skandf_unset_seen (void) 276169689Skan{ 277169689Skan BITMAP_FREE (seen_in_block); 278169689Skan BITMAP_FREE (seen_in_insn); 279169689Skan} 280169689Skan 281169689Skan 282169689Skan 283169689Skan/*---------------------------------------------------------------------------- 284169689Skan REACHING USES 285169689Skan 286169689Skan Find the locations in the function where each use site for a pseudo 287169689Skan can reach backwards. In and out bitvectors are built for each basic 288169689Skan block. The id field in the ref is used to index into these sets. 289169689Skan See df.h for details. 290169689Skan 291169689Skan----------------------------------------------------------------------------*/ 292169689Skan 293169689Skan/* This problem plays a large number of games for the sake of 294169689Skan efficiency. 295169689Skan 296169689Skan 1) The order of the bits in the bitvectors. After the scanning 297169689Skan phase, all of the uses are sorted. All of the uses for the reg 0 298169689Skan are first, followed by all uses for reg 1 and so on. 299169689Skan 300169689Skan 2) There are two kill sets, one if the number of uses is less or 301169689Skan equal to DF_SPARSE_THRESHOLD and another if it is greater. 302169689Skan 303169689Skan <= : There is a bitmap for each register, uses_sites[N], that is 304169689Skan built on demand. This bitvector contains a 1 for each use or reg 305169689Skan N. 306169689Skan 307169689Skan > : One level of indirection is used to keep from generating long 308169689Skan strings of 1 bits in the kill sets. Bitvectors that are indexed 309169689Skan by the regnum are used to represent that there is a killing def 310169689Skan for the register. The confluence and transfer functions use 311169689Skan these along with the bitmap_clear_range call to remove ranges of 312169689Skan bits without actually generating a knockout vector. 313169689Skan 314169689Skan The kill and sparse_kill and the dense_invalidated_by_call and 315169689Skan sparse_invalidated_by call both play this game. */ 316169689Skan 317169689Skan/* Private data used to compute the solution for this problem. These 318169689Skan data structures are not accessible outside of this module. */ 319169689Skanstruct df_ru_problem_data 320169689Skan{ 321169689Skan 322169689Skan bitmap *use_sites; /* Bitmap of uses for each pseudo. */ 323169689Skan unsigned int use_sites_size; /* Size of use_sites. */ 324169689Skan /* The set of defs to regs invalidated by call. */ 325169689Skan bitmap sparse_invalidated_by_call; 326169689Skan /* The set of defs to regs invalidated by call for ru. */ 327169689Skan bitmap dense_invalidated_by_call; 328169689Skan}; 329169689Skan 330169689Skan/* Get basic block info. */ 331169689Skan 332169689Skanstruct df_ru_bb_info * 333169689Skandf_ru_get_bb_info (struct dataflow *dflow, unsigned int index) 334169689Skan{ 335169689Skan return (struct df_ru_bb_info *) dflow->block_info[index]; 336169689Skan} 337169689Skan 338169689Skan 339169689Skan/* Set basic block info. */ 340169689Skan 341169689Skanstatic void 342169689Skandf_ru_set_bb_info (struct dataflow *dflow, unsigned int index, 343169689Skan struct df_ru_bb_info *bb_info) 344169689Skan{ 345169689Skan dflow->block_info[index] = bb_info; 346169689Skan} 347169689Skan 348169689Skan 349169689Skan/* Free basic block info. */ 350169689Skan 351169689Skanstatic void 352169689Skandf_ru_free_bb_info (struct dataflow *dflow, 353169689Skan basic_block bb ATTRIBUTE_UNUSED, 354169689Skan void *vbb_info) 355169689Skan{ 356169689Skan struct df_ru_bb_info *bb_info = (struct df_ru_bb_info *) vbb_info; 357169689Skan if (bb_info) 358169689Skan { 359169689Skan BITMAP_FREE (bb_info->kill); 360169689Skan BITMAP_FREE (bb_info->sparse_kill); 361169689Skan BITMAP_FREE (bb_info->gen); 362169689Skan BITMAP_FREE (bb_info->in); 363169689Skan BITMAP_FREE (bb_info->out); 364169689Skan pool_free (dflow->block_pool, bb_info); 365169689Skan } 366169689Skan} 367169689Skan 368169689Skan 369169689Skan/* Allocate or reset bitmaps for DFLOW blocks. The solution bits are 370169689Skan not touched unless the block is new. */ 371169689Skan 372169689Skanstatic void 373169689Skandf_ru_alloc (struct dataflow *dflow, 374169689Skan bitmap blocks_to_rescan ATTRIBUTE_UNUSED, 375169689Skan bitmap all_blocks) 376169689Skan{ 377169689Skan unsigned int bb_index; 378169689Skan bitmap_iterator bi; 379169689Skan unsigned int reg_size = max_reg_num (); 380169689Skan 381169689Skan if (!dflow->block_pool) 382169689Skan dflow->block_pool = create_alloc_pool ("df_ru_block pool", 383169689Skan sizeof (struct df_ru_bb_info), 50); 384169689Skan 385169689Skan if (dflow->problem_data) 386169689Skan { 387169689Skan unsigned int i; 388169689Skan struct df_ru_problem_data *problem_data 389169689Skan = (struct df_ru_problem_data *) dflow->problem_data; 390169689Skan 391169689Skan for (i = 0; i < problem_data->use_sites_size; i++) 392169689Skan { 393169689Skan bitmap bm = problem_data->use_sites[i]; 394169689Skan if (bm) 395169689Skan { 396169689Skan BITMAP_FREE (bm); 397169689Skan problem_data->use_sites[i] = NULL; 398169689Skan } 399169689Skan } 400169689Skan 401169689Skan if (problem_data->use_sites_size < reg_size) 402169689Skan { 403169689Skan problem_data->use_sites 404169689Skan = xrealloc (problem_data->use_sites, reg_size * sizeof (bitmap)); 405169689Skan memset (problem_data->use_sites + problem_data->use_sites_size, 0, 406169689Skan (reg_size - problem_data->use_sites_size) * sizeof (bitmap)); 407169689Skan problem_data->use_sites_size = reg_size; 408169689Skan } 409169689Skan 410169689Skan bitmap_clear (problem_data->sparse_invalidated_by_call); 411169689Skan bitmap_clear (problem_data->dense_invalidated_by_call); 412169689Skan } 413169689Skan else 414169689Skan { 415169689Skan struct df_ru_problem_data *problem_data = XNEW (struct df_ru_problem_data); 416169689Skan dflow->problem_data = problem_data; 417169689Skan 418169689Skan problem_data->use_sites = XCNEWVEC (bitmap, reg_size); 419169689Skan problem_data->use_sites_size = reg_size; 420169689Skan problem_data->sparse_invalidated_by_call = BITMAP_ALLOC (NULL); 421169689Skan problem_data->dense_invalidated_by_call = BITMAP_ALLOC (NULL); 422169689Skan } 423169689Skan 424169689Skan df_grow_bb_info (dflow); 425169689Skan 426169689Skan /* Because of the clustering of all def sites for the same pseudo, 427169689Skan we have to process all of the blocks before doing the 428169689Skan analysis. */ 429169689Skan 430169689Skan EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) 431169689Skan { 432169689Skan struct df_ru_bb_info *bb_info = df_ru_get_bb_info (dflow, bb_index); 433169689Skan if (bb_info) 434169689Skan { 435169689Skan bitmap_clear (bb_info->kill); 436169689Skan bitmap_clear (bb_info->sparse_kill); 437169689Skan bitmap_clear (bb_info->gen); 438169689Skan } 439169689Skan else 440169689Skan { 441169689Skan bb_info = (struct df_ru_bb_info *) pool_alloc (dflow->block_pool); 442169689Skan df_ru_set_bb_info (dflow, bb_index, bb_info); 443169689Skan bb_info->kill = BITMAP_ALLOC (NULL); 444169689Skan bb_info->sparse_kill = BITMAP_ALLOC (NULL); 445169689Skan bb_info->gen = BITMAP_ALLOC (NULL); 446169689Skan bb_info->in = BITMAP_ALLOC (NULL); 447169689Skan bb_info->out = BITMAP_ALLOC (NULL); 448169689Skan } 449169689Skan } 450169689Skan} 451169689Skan 452169689Skan 453169689Skan/* Process a list of DEFs for df_ru_bb_local_compute. */ 454169689Skan 455169689Skanstatic void 456169689Skandf_ru_bb_local_compute_process_def (struct dataflow *dflow, 457169689Skan struct df_ru_bb_info *bb_info, 458169689Skan struct df_ref *def, 459169689Skan enum df_ref_flags top_flag) 460169689Skan{ 461169689Skan struct df *df = dflow->df; 462169689Skan while (def) 463169689Skan { 464169689Skan if ((top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP)) 465169689Skan /* If the def is to only part of the reg, it is as if it did 466169689Skan not happen, since some of the bits may get thru. */ 467169689Skan && (!(DF_REF_FLAGS (def) & DF_REF_PARTIAL))) 468169689Skan { 469169689Skan unsigned int regno = DF_REF_REGNO (def); 470169689Skan unsigned int begin = DF_REG_USE_GET (df, regno)->begin; 471169689Skan unsigned int n_uses = DF_REG_USE_GET (df, regno)->n_refs; 472169689Skan if (!bitmap_bit_p (seen_in_block, regno)) 473169689Skan { 474169689Skan /* The first def for regno in the insn, causes the kill 475169689Skan info to be generated. Do not modify the gen set 476169689Skan because the only values in it are the uses from here 477169689Skan to the top of the block and this def does not effect 478169689Skan them. */ 479169689Skan if (!bitmap_bit_p (seen_in_insn, regno)) 480169689Skan { 481169689Skan if (n_uses > DF_SPARSE_THRESHOLD) 482169689Skan bitmap_set_bit (bb_info->sparse_kill, regno); 483169689Skan else 484169689Skan { 485169689Skan struct df_ru_problem_data * problem_data 486169689Skan = (struct df_ru_problem_data *)dflow->problem_data; 487169689Skan bitmap uses 488169689Skan = df_ref_bitmap (problem_data->use_sites, regno, 489169689Skan begin, n_uses); 490169689Skan bitmap_ior_into (bb_info->kill, uses); 491169689Skan } 492169689Skan } 493169689Skan bitmap_set_bit (seen_in_insn, regno); 494169689Skan } 495169689Skan } 496169689Skan def = def->next_ref; 497169689Skan } 498169689Skan} 499169689Skan 500169689Skan 501169689Skan/* Process a list of USEs for df_ru_bb_local_compute. */ 502169689Skan 503169689Skanstatic void 504169689Skandf_ru_bb_local_compute_process_use (struct df_ru_bb_info *bb_info, 505169689Skan struct df_ref *use, 506169689Skan enum df_ref_flags top_flag) 507169689Skan{ 508169689Skan while (use) 509169689Skan { 510169689Skan if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP)) 511169689Skan { 512169689Skan /* Add use to set of gens in this BB unless we have seen a 513169689Skan def in a previous instruction. */ 514169689Skan unsigned int regno = DF_REF_REGNO (use); 515169689Skan if (!bitmap_bit_p (seen_in_block, regno)) 516169689Skan bitmap_set_bit (bb_info->gen, DF_REF_ID (use)); 517169689Skan } 518169689Skan use = use->next_ref; 519169689Skan } 520169689Skan} 521169689Skan 522169689Skan/* Compute local reaching use (upward exposed use) info for basic 523169689Skan block BB. USE_INFO->REGS[R] caches the set of uses for register R. */ 524169689Skanstatic void 525169689Skandf_ru_bb_local_compute (struct dataflow *dflow, unsigned int bb_index) 526169689Skan{ 527169689Skan struct df *df = dflow->df; 528169689Skan basic_block bb = BASIC_BLOCK (bb_index); 529169689Skan struct df_ru_bb_info *bb_info = df_ru_get_bb_info (dflow, bb_index); 530169689Skan rtx insn; 531169689Skan 532169689Skan /* Set when a def for regno is seen. */ 533169689Skan bitmap_clear (seen_in_block); 534169689Skan bitmap_clear (seen_in_insn); 535169689Skan 536169689Skan#ifdef EH_USES 537169689Skan /* Variables defined in the prolog that are used by the exception 538169689Skan handler. */ 539169689Skan df_ru_bb_local_compute_process_use (bb_info, 540169689Skan df_get_artificial_uses (df, bb_index), 541169689Skan DF_REF_AT_TOP); 542169689Skan#endif 543169689Skan df_ru_bb_local_compute_process_def (dflow, bb_info, 544169689Skan df_get_artificial_defs (df, bb_index), 545169689Skan DF_REF_AT_TOP); 546169689Skan 547169689Skan FOR_BB_INSNS (bb, insn) 548169689Skan { 549169689Skan unsigned int uid = INSN_UID (insn); 550169689Skan if (!INSN_P (insn)) 551169689Skan continue; 552169689Skan 553169689Skan df_ru_bb_local_compute_process_use (bb_info, 554169689Skan DF_INSN_UID_USES (df, uid), 0); 555169689Skan 556169689Skan df_ru_bb_local_compute_process_def (dflow, bb_info, 557169689Skan DF_INSN_UID_DEFS (df, uid), 0); 558169689Skan 559169689Skan bitmap_ior_into (seen_in_block, seen_in_insn); 560169689Skan bitmap_clear (seen_in_insn); 561169689Skan } 562169689Skan 563169689Skan /* Process the hardware registers that are always live. */ 564169689Skan df_ru_bb_local_compute_process_use (bb_info, 565169689Skan df_get_artificial_uses (df, bb_index), 0); 566169689Skan 567169689Skan df_ru_bb_local_compute_process_def (dflow, bb_info, 568169689Skan df_get_artificial_defs (df, bb_index), 0); 569169689Skan} 570169689Skan 571169689Skan 572169689Skan/* Compute local reaching use (upward exposed use) info for each basic 573169689Skan block within BLOCKS. */ 574169689Skanstatic void 575169689Skandf_ru_local_compute (struct dataflow *dflow, 576169689Skan bitmap all_blocks, 577169689Skan bitmap rescan_blocks ATTRIBUTE_UNUSED) 578169689Skan{ 579169689Skan struct df *df = dflow->df; 580169689Skan unsigned int bb_index; 581169689Skan bitmap_iterator bi; 582169689Skan unsigned int regno; 583169689Skan struct df_ru_problem_data *problem_data 584169689Skan = (struct df_ru_problem_data *) dflow->problem_data; 585169689Skan bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call; 586169689Skan bitmap dense_invalidated = problem_data->dense_invalidated_by_call; 587169689Skan 588169689Skan df_set_seen (); 589169689Skan 590169689Skan if (!df->use_info.refs_organized) 591169689Skan df_reorganize_refs (&df->use_info); 592169689Skan 593169689Skan EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) 594169689Skan { 595169689Skan df_ru_bb_local_compute (dflow, bb_index); 596169689Skan } 597169689Skan 598169689Skan /* Set up the knockout bit vectors to be applied across EH_EDGES. */ 599169689Skan EXECUTE_IF_SET_IN_BITMAP (df_invalidated_by_call, 0, regno, bi) 600169689Skan { 601169689Skan struct df_reg_info *reg_info = DF_REG_USE_GET (df, regno); 602169689Skan if (reg_info->n_refs > DF_SPARSE_THRESHOLD) 603169689Skan bitmap_set_bit (sparse_invalidated, regno); 604169689Skan else 605169689Skan { 606169689Skan bitmap defs = df_ref_bitmap (problem_data->use_sites, regno, 607169689Skan reg_info->begin, reg_info->n_refs); 608169689Skan bitmap_ior_into (dense_invalidated, defs); 609169689Skan } 610169689Skan } 611169689Skan 612169689Skan df_unset_seen (); 613169689Skan} 614169689Skan 615169689Skan 616169689Skan/* Initialize the solution bit vectors for problem. */ 617169689Skan 618169689Skanstatic void 619169689Skandf_ru_init_solution (struct dataflow *dflow, bitmap all_blocks) 620169689Skan{ 621169689Skan unsigned int bb_index; 622169689Skan bitmap_iterator bi; 623169689Skan 624169689Skan EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) 625169689Skan { 626169689Skan struct df_ru_bb_info *bb_info = df_ru_get_bb_info (dflow, bb_index); 627169689Skan bitmap_copy (bb_info->in, bb_info->gen); 628169689Skan bitmap_clear (bb_info->out); 629169689Skan } 630169689Skan} 631169689Skan 632169689Skan 633169689Skan/* Out of target gets or of in of source. */ 634169689Skan 635169689Skanstatic void 636169689Skandf_ru_confluence_n (struct dataflow *dflow, edge e) 637169689Skan{ 638169689Skan bitmap op1 = df_ru_get_bb_info (dflow, e->src->index)->out; 639169689Skan bitmap op2 = df_ru_get_bb_info (dflow, e->dest->index)->in; 640169689Skan 641169689Skan if (e->flags & EDGE_EH) 642169689Skan { 643169689Skan struct df_ru_problem_data *problem_data 644169689Skan = (struct df_ru_problem_data *) dflow->problem_data; 645169689Skan bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call; 646169689Skan bitmap dense_invalidated = problem_data->dense_invalidated_by_call; 647169689Skan struct df *df = dflow->df; 648169689Skan bitmap_iterator bi; 649169689Skan unsigned int regno; 650169689Skan bitmap tmp = BITMAP_ALLOC (NULL); 651169689Skan 652169689Skan bitmap_copy (tmp, op2); 653169689Skan bitmap_and_compl_into (tmp, dense_invalidated); 654169689Skan 655169689Skan EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi) 656169689Skan { 657169689Skan bitmap_clear_range (tmp, 658169689Skan DF_REG_USE_GET (df, regno)->begin, 659169689Skan DF_REG_USE_GET (df, regno)->n_refs); 660169689Skan } 661169689Skan bitmap_ior_into (op1, tmp); 662169689Skan BITMAP_FREE (tmp); 663169689Skan } 664169689Skan else 665169689Skan bitmap_ior_into (op1, op2); 666169689Skan} 667169689Skan 668169689Skan 669169689Skan/* Transfer function. */ 670169689Skan 671169689Skanstatic bool 672169689Skandf_ru_transfer_function (struct dataflow *dflow, int bb_index) 673169689Skan{ 674169689Skan struct df_ru_bb_info *bb_info = df_ru_get_bb_info (dflow, bb_index); 675169689Skan unsigned int regno; 676169689Skan bitmap_iterator bi; 677169689Skan bitmap in = bb_info->in; 678169689Skan bitmap out = bb_info->out; 679169689Skan bitmap gen = bb_info->gen; 680169689Skan bitmap kill = bb_info->kill; 681169689Skan bitmap sparse_kill = bb_info->sparse_kill; 682169689Skan 683169689Skan if (bitmap_empty_p (sparse_kill)) 684169689Skan return bitmap_ior_and_compl (in, gen, out, kill); 685169689Skan else 686169689Skan { 687169689Skan struct df *df = dflow->df; 688169689Skan bool changed = false; 689169689Skan bitmap tmp = BITMAP_ALLOC (NULL); 690169689Skan bitmap_copy (tmp, out); 691169689Skan EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi) 692169689Skan { 693169689Skan bitmap_clear_range (tmp, 694169689Skan DF_REG_USE_GET (df, regno)->begin, 695169689Skan DF_REG_USE_GET (df, regno)->n_refs); 696169689Skan } 697169689Skan bitmap_and_compl_into (tmp, kill); 698169689Skan bitmap_ior_into (tmp, gen); 699169689Skan changed = !bitmap_equal_p (tmp, in); 700169689Skan if (changed) 701169689Skan { 702169689Skan BITMAP_FREE (in); 703169689Skan bb_info->in = tmp; 704169689Skan } 705169689Skan else 706169689Skan BITMAP_FREE (tmp); 707169689Skan return changed; 708169689Skan } 709169689Skan} 710169689Skan 711169689Skan 712169689Skan/* Free all storage associated with the problem. */ 713169689Skan 714169689Skanstatic void 715169689Skandf_ru_free (struct dataflow *dflow) 716169689Skan{ 717169689Skan unsigned int i; 718169689Skan struct df_ru_problem_data *problem_data 719169689Skan = (struct df_ru_problem_data *) dflow->problem_data; 720169689Skan 721169689Skan if (problem_data) 722169689Skan { 723169689Skan for (i = 0; i < dflow->block_info_size; i++) 724169689Skan { 725169689Skan struct df_ru_bb_info *bb_info = df_ru_get_bb_info (dflow, i); 726169689Skan if (bb_info) 727169689Skan { 728169689Skan BITMAP_FREE (bb_info->kill); 729169689Skan BITMAP_FREE (bb_info->sparse_kill); 730169689Skan BITMAP_FREE (bb_info->gen); 731169689Skan BITMAP_FREE (bb_info->in); 732169689Skan BITMAP_FREE (bb_info->out); 733169689Skan } 734169689Skan } 735169689Skan 736169689Skan free_alloc_pool (dflow->block_pool); 737169689Skan 738169689Skan for (i = 0; i < problem_data->use_sites_size; i++) 739169689Skan { 740169689Skan bitmap bm = problem_data->use_sites[i]; 741169689Skan if (bm) 742169689Skan BITMAP_FREE (bm); 743169689Skan } 744169689Skan 745169689Skan free (problem_data->use_sites); 746169689Skan BITMAP_FREE (problem_data->sparse_invalidated_by_call); 747169689Skan BITMAP_FREE (problem_data->dense_invalidated_by_call); 748169689Skan 749169689Skan dflow->block_info_size = 0; 750169689Skan free (dflow->block_info); 751169689Skan free (dflow->problem_data); 752169689Skan } 753169689Skan free (dflow); 754169689Skan} 755169689Skan 756169689Skan 757169689Skan/* Debugging info. */ 758169689Skan 759169689Skanstatic void 760169689Skandf_ru_dump (struct dataflow *dflow, FILE *file) 761169689Skan{ 762169689Skan basic_block bb; 763169689Skan struct df *df = dflow->df; 764169689Skan struct df_ru_problem_data *problem_data 765169689Skan = (struct df_ru_problem_data *) dflow->problem_data; 766169689Skan unsigned int m = max_reg_num (); 767169689Skan unsigned int regno; 768169689Skan 769169689Skan if (!dflow->block_info) 770169689Skan return; 771169689Skan 772169689Skan fprintf (file, "Reaching uses:\n"); 773169689Skan 774169689Skan fprintf (file, " sparse invalidated \t"); 775169689Skan dump_bitmap (file, problem_data->sparse_invalidated_by_call); 776169689Skan fprintf (file, " dense invalidated \t"); 777169689Skan dump_bitmap (file, problem_data->dense_invalidated_by_call); 778169689Skan 779169689Skan for (regno = 0; regno < m; regno++) 780169689Skan if (DF_REG_USE_GET (df, regno)->n_refs) 781169689Skan fprintf (file, "%d[%d,%d] ", regno, 782169689Skan DF_REG_USE_GET (df, regno)->begin, 783169689Skan DF_REG_USE_GET (df, regno)->n_refs); 784169689Skan fprintf (file, "\n"); 785169689Skan 786169689Skan FOR_ALL_BB (bb) 787169689Skan { 788169689Skan struct df_ru_bb_info *bb_info = df_ru_get_bb_info (dflow, bb->index); 789169689Skan df_print_bb_index (bb, file); 790169689Skan 791169689Skan if (!bb_info->in) 792169689Skan continue; 793169689Skan 794169689Skan fprintf (file, " in \t(%d)\n", (int) bitmap_count_bits (bb_info->in)); 795169689Skan dump_bitmap (file, bb_info->in); 796169689Skan fprintf (file, " gen \t(%d)\n", (int) bitmap_count_bits (bb_info->gen)); 797169689Skan dump_bitmap (file, bb_info->gen); 798169689Skan fprintf (file, " kill\t(%d)\n", (int) bitmap_count_bits (bb_info->kill)); 799169689Skan dump_bitmap (file, bb_info->kill); 800169689Skan fprintf (file, " out \t(%d)\n", (int) bitmap_count_bits (bb_info->out)); 801169689Skan dump_bitmap (file, bb_info->out); 802169689Skan } 803169689Skan} 804169689Skan 805169689Skan/* All of the information associated with every instance of the problem. */ 806169689Skan 807169689Skanstatic struct df_problem problem_RU = 808169689Skan{ 809169689Skan DF_RU, /* Problem id. */ 810169689Skan DF_BACKWARD, /* Direction. */ 811169689Skan df_ru_alloc, /* Allocate the problem specific data. */ 812169689Skan NULL, /* Reset global information. */ 813169689Skan df_ru_free_bb_info, /* Free basic block info. */ 814169689Skan df_ru_local_compute, /* Local compute function. */ 815169689Skan df_ru_init_solution, /* Init the solution specific data. */ 816169689Skan df_iterative_dataflow, /* Iterative solver. */ 817169689Skan NULL, /* Confluence operator 0. */ 818169689Skan df_ru_confluence_n, /* Confluence operator n. */ 819169689Skan df_ru_transfer_function, /* Transfer function. */ 820169689Skan NULL, /* Finalize function. */ 821169689Skan df_ru_free, /* Free all of the problem information. */ 822169689Skan df_ru_dump, /* Debugging. */ 823169689Skan NULL, /* Dependent problem. */ 824169689Skan 0 /* Changeable flags. */ 825169689Skan}; 826169689Skan 827169689Skan 828169689Skan 829169689Skan/* Create a new DATAFLOW instance and add it to an existing instance 830169689Skan of DF. The returned structure is what is used to get at the 831169689Skan solution. */ 832169689Skan 833169689Skanstruct dataflow * 834169689Skandf_ru_add_problem (struct df *df, int flags) 835169689Skan{ 836169689Skan return df_add_problem (df, &problem_RU, flags); 837169689Skan} 838169689Skan 839169689Skan 840169689Skan/*---------------------------------------------------------------------------- 841169689Skan REACHING DEFINITIONS 842169689Skan 843169689Skan Find the locations in the function where each definition site for a 844169689Skan pseudo reaches. In and out bitvectors are built for each basic 845169689Skan block. The id field in the ref is used to index into these sets. 846169689Skan See df.h for details. 847169689Skan ----------------------------------------------------------------------------*/ 848169689Skan 849169689Skan/* See the comment at the top of the Reaching Uses problem for how the 850169689Skan uses are represented in the kill sets. The same games are played 851169689Skan here for the defs. */ 852169689Skan 853169689Skan/* Private data used to compute the solution for this problem. These 854169689Skan data structures are not accessible outside of this module. */ 855169689Skanstruct df_rd_problem_data 856169689Skan{ 857169689Skan /* If the number of defs for regnum N is less than 858169689Skan DF_SPARSE_THRESHOLD, uses_sites[N] contains a mask of the all of 859169689Skan the defs of reg N indexed by the id in the ref structure. If 860169689Skan there are more than DF_SPARSE_THRESHOLD defs for regnum N a 861169689Skan different mechanism is used to mask the def. */ 862169689Skan bitmap *def_sites; /* Bitmap of defs for each pseudo. */ 863169689Skan unsigned int def_sites_size; /* Size of def_sites. */ 864169689Skan /* The set of defs to regs invalidated by call. */ 865169689Skan bitmap sparse_invalidated_by_call; 866169689Skan /* The set of defs to regs invalidate by call for rd. */ 867169689Skan bitmap dense_invalidated_by_call; 868169689Skan}; 869169689Skan 870169689Skan/* Get basic block info. */ 871169689Skan 872169689Skanstruct df_rd_bb_info * 873169689Skandf_rd_get_bb_info (struct dataflow *dflow, unsigned int index) 874169689Skan{ 875169689Skan return (struct df_rd_bb_info *) dflow->block_info[index]; 876169689Skan} 877169689Skan 878169689Skan 879169689Skan/* Set basic block info. */ 880169689Skan 881169689Skanstatic void 882169689Skandf_rd_set_bb_info (struct dataflow *dflow, unsigned int index, 883169689Skan struct df_rd_bb_info *bb_info) 884169689Skan{ 885169689Skan dflow->block_info[index] = bb_info; 886169689Skan} 887169689Skan 888169689Skan 889169689Skan/* Free basic block info. */ 890169689Skan 891169689Skanstatic void 892169689Skandf_rd_free_bb_info (struct dataflow *dflow, 893169689Skan basic_block bb ATTRIBUTE_UNUSED, 894169689Skan void *vbb_info) 895169689Skan{ 896169689Skan struct df_rd_bb_info *bb_info = (struct df_rd_bb_info *) vbb_info; 897169689Skan if (bb_info) 898169689Skan { 899169689Skan BITMAP_FREE (bb_info->kill); 900169689Skan BITMAP_FREE (bb_info->sparse_kill); 901169689Skan BITMAP_FREE (bb_info->gen); 902169689Skan BITMAP_FREE (bb_info->in); 903169689Skan BITMAP_FREE (bb_info->out); 904169689Skan pool_free (dflow->block_pool, bb_info); 905169689Skan } 906169689Skan} 907169689Skan 908169689Skan 909169689Skan/* Allocate or reset bitmaps for DFLOW blocks. The solution bits are 910169689Skan not touched unless the block is new. */ 911169689Skan 912169689Skanstatic void 913169689Skandf_rd_alloc (struct dataflow *dflow, 914169689Skan bitmap blocks_to_rescan ATTRIBUTE_UNUSED, 915169689Skan bitmap all_blocks) 916169689Skan{ 917169689Skan unsigned int bb_index; 918169689Skan bitmap_iterator bi; 919169689Skan unsigned int reg_size = max_reg_num (); 920169689Skan 921169689Skan if (!dflow->block_pool) 922169689Skan dflow->block_pool = create_alloc_pool ("df_rd_block pool", 923169689Skan sizeof (struct df_rd_bb_info), 50); 924169689Skan 925169689Skan if (dflow->problem_data) 926169689Skan { 927169689Skan unsigned int i; 928169689Skan struct df_rd_problem_data *problem_data 929169689Skan = (struct df_rd_problem_data *) dflow->problem_data; 930169689Skan 931169689Skan for (i = 0; i < problem_data->def_sites_size; i++) 932169689Skan { 933169689Skan bitmap bm = problem_data->def_sites[i]; 934169689Skan if (bm) 935169689Skan { 936169689Skan BITMAP_FREE (bm); 937169689Skan problem_data->def_sites[i] = NULL; 938169689Skan } 939169689Skan } 940169689Skan 941169689Skan if (problem_data->def_sites_size < reg_size) 942169689Skan { 943169689Skan problem_data->def_sites 944169689Skan = xrealloc (problem_data->def_sites, reg_size *sizeof (bitmap)); 945169689Skan memset (problem_data->def_sites + problem_data->def_sites_size, 0, 946169689Skan (reg_size - problem_data->def_sites_size) *sizeof (bitmap)); 947169689Skan problem_data->def_sites_size = reg_size; 948169689Skan } 949169689Skan 950169689Skan bitmap_clear (problem_data->sparse_invalidated_by_call); 951169689Skan bitmap_clear (problem_data->dense_invalidated_by_call); 952169689Skan } 953169689Skan else 954169689Skan { 955169689Skan struct df_rd_problem_data *problem_data = XNEW (struct df_rd_problem_data); 956169689Skan dflow->problem_data = problem_data; 957169689Skan 958169689Skan problem_data->def_sites = XCNEWVEC (bitmap, reg_size); 959169689Skan problem_data->def_sites_size = reg_size; 960169689Skan problem_data->sparse_invalidated_by_call = BITMAP_ALLOC (NULL); 961169689Skan problem_data->dense_invalidated_by_call = BITMAP_ALLOC (NULL); 962169689Skan } 963169689Skan 964169689Skan df_grow_bb_info (dflow); 965169689Skan 966169689Skan /* Because of the clustering of all use sites for the same pseudo, 967169689Skan we have to process all of the blocks before doing the 968169689Skan analysis. */ 969169689Skan 970169689Skan EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) 971169689Skan { 972169689Skan struct df_rd_bb_info *bb_info = df_rd_get_bb_info (dflow, bb_index); 973169689Skan if (bb_info) 974169689Skan { 975169689Skan bitmap_clear (bb_info->kill); 976169689Skan bitmap_clear (bb_info->sparse_kill); 977169689Skan bitmap_clear (bb_info->gen); 978169689Skan } 979169689Skan else 980169689Skan { 981169689Skan bb_info = (struct df_rd_bb_info *) pool_alloc (dflow->block_pool); 982169689Skan df_rd_set_bb_info (dflow, bb_index, bb_info); 983169689Skan bb_info->kill = BITMAP_ALLOC (NULL); 984169689Skan bb_info->sparse_kill = BITMAP_ALLOC (NULL); 985169689Skan bb_info->gen = BITMAP_ALLOC (NULL); 986169689Skan bb_info->in = BITMAP_ALLOC (NULL); 987169689Skan bb_info->out = BITMAP_ALLOC (NULL); 988169689Skan } 989169689Skan } 990169689Skan} 991169689Skan 992169689Skan 993169689Skan/* Process a list of DEFs for df_rd_bb_local_compute. */ 994169689Skan 995169689Skanstatic void 996169689Skandf_rd_bb_local_compute_process_def (struct dataflow *dflow, 997169689Skan struct df_rd_bb_info *bb_info, 998169689Skan struct df_ref *def, 999169689Skan enum df_ref_flags top_flag) 1000169689Skan{ 1001169689Skan struct df *df = dflow->df; 1002169689Skan while (def) 1003169689Skan { 1004169689Skan if (top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP)) 1005169689Skan { 1006169689Skan unsigned int regno = DF_REF_REGNO (def); 1007169689Skan unsigned int begin = DF_REG_DEF_GET (df, regno)->begin; 1008169689Skan unsigned int n_defs = DF_REG_DEF_GET (df, regno)->n_refs; 1009169689Skan 1010169689Skan /* Only the last def(s) for a regno in the block has any 1011169689Skan effect. */ 1012169689Skan if (!bitmap_bit_p (seen_in_block, regno)) 1013169689Skan { 1014169689Skan /* The first def for regno in insn gets to knock out the 1015169689Skan defs from other instructions. */ 1016169689Skan if ((!bitmap_bit_p (seen_in_insn, regno)) 1017169689Skan /* If the def is to only part of the reg, it does 1018169689Skan not kill the other defs that reach here. */ 1019169689Skan && (!((DF_REF_FLAGS (def) & DF_REF_PARTIAL) 1020169689Skan || (DF_REF_FLAGS (def) & DF_REF_MAY_CLOBBER)))) 1021169689Skan { 1022169689Skan if (n_defs > DF_SPARSE_THRESHOLD) 1023169689Skan { 1024169689Skan bitmap_set_bit (bb_info->sparse_kill, regno); 1025169689Skan bitmap_clear_range(bb_info->gen, begin, n_defs); 1026169689Skan } 1027169689Skan else 1028169689Skan { 1029169689Skan struct df_rd_problem_data * problem_data 1030169689Skan = (struct df_rd_problem_data *)dflow->problem_data; 1031169689Skan bitmap defs = df_ref_bitmap (problem_data->def_sites, 1032169689Skan regno, begin, n_defs); 1033169689Skan bitmap_ior_into (bb_info->kill, defs); 1034169689Skan bitmap_and_compl_into (bb_info->gen, defs); 1035169689Skan } 1036169689Skan } 1037169689Skan 1038169689Skan bitmap_set_bit (seen_in_insn, regno); 1039169689Skan /* All defs for regno in the instruction may be put into 1040169689Skan the gen set. */ 1041169689Skan if (!(DF_REF_FLAGS (def) 1042169689Skan & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))) 1043169689Skan bitmap_set_bit (bb_info->gen, DF_REF_ID (def)); 1044169689Skan } 1045169689Skan } 1046169689Skan def = def->next_ref; 1047169689Skan } 1048169689Skan} 1049169689Skan 1050169689Skan/* Compute local reaching def info for basic block BB. */ 1051169689Skan 1052169689Skanstatic void 1053169689Skandf_rd_bb_local_compute (struct dataflow *dflow, unsigned int bb_index) 1054169689Skan{ 1055169689Skan struct df *df = dflow->df; 1056169689Skan basic_block bb = BASIC_BLOCK (bb_index); 1057169689Skan struct df_rd_bb_info *bb_info = df_rd_get_bb_info (dflow, bb_index); 1058169689Skan rtx insn; 1059169689Skan 1060169689Skan bitmap_clear (seen_in_block); 1061169689Skan bitmap_clear (seen_in_insn); 1062169689Skan 1063169689Skan df_rd_bb_local_compute_process_def (dflow, bb_info, 1064169689Skan df_get_artificial_defs (df, bb_index), 0); 1065169689Skan 1066169689Skan FOR_BB_INSNS_REVERSE (bb, insn) 1067169689Skan { 1068169689Skan unsigned int uid = INSN_UID (insn); 1069169689Skan 1070169689Skan if (!INSN_P (insn)) 1071169689Skan continue; 1072169689Skan 1073169689Skan df_rd_bb_local_compute_process_def (dflow, bb_info, 1074169689Skan DF_INSN_UID_DEFS (df, uid), 0); 1075169689Skan 1076169689Skan /* This complex dance with the two bitmaps is required because 1077169689Skan instructions can assign twice to the same pseudo. This 1078169689Skan generally happens with calls that will have one def for the 1079169689Skan result and another def for the clobber. If only one vector 1080169689Skan is used and the clobber goes first, the result will be 1081169689Skan lost. */ 1082169689Skan bitmap_ior_into (seen_in_block, seen_in_insn); 1083169689Skan bitmap_clear (seen_in_insn); 1084169689Skan } 1085169689Skan 1086169689Skan /* Process the artificial defs at the top of the block last since we 1087169689Skan are going backwards through the block and these are logically at 1088169689Skan the start. */ 1089169689Skan df_rd_bb_local_compute_process_def (dflow, bb_info, 1090169689Skan df_get_artificial_defs (df, bb_index), 1091169689Skan DF_REF_AT_TOP); 1092169689Skan} 1093169689Skan 1094169689Skan 1095169689Skan/* Compute local reaching def info for each basic block within BLOCKS. */ 1096169689Skan 1097169689Skanstatic void 1098169689Skandf_rd_local_compute (struct dataflow *dflow, 1099169689Skan bitmap all_blocks, 1100169689Skan bitmap rescan_blocks ATTRIBUTE_UNUSED) 1101169689Skan{ 1102169689Skan struct df *df = dflow->df; 1103169689Skan unsigned int bb_index; 1104169689Skan bitmap_iterator bi; 1105169689Skan unsigned int regno; 1106169689Skan struct df_rd_problem_data *problem_data 1107169689Skan = (struct df_rd_problem_data *) dflow->problem_data; 1108169689Skan bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call; 1109169689Skan bitmap dense_invalidated = problem_data->dense_invalidated_by_call; 1110169689Skan 1111169689Skan df_set_seen (); 1112169689Skan 1113169689Skan if (!df->def_info.refs_organized) 1114169689Skan df_reorganize_refs (&df->def_info); 1115169689Skan 1116169689Skan EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) 1117169689Skan { 1118169689Skan df_rd_bb_local_compute (dflow, bb_index); 1119169689Skan } 1120169689Skan 1121169689Skan /* Set up the knockout bit vectors to be applied across EH_EDGES. */ 1122169689Skan EXECUTE_IF_SET_IN_BITMAP (df_invalidated_by_call, 0, regno, bi) 1123169689Skan { 1124169689Skan struct df_reg_info *reg_info = DF_REG_DEF_GET (df, regno); 1125169689Skan if (reg_info->n_refs > DF_SPARSE_THRESHOLD) 1126169689Skan { 1127169689Skan bitmap_set_bit (sparse_invalidated, regno); 1128169689Skan } 1129169689Skan else 1130169689Skan { 1131169689Skan bitmap defs = df_ref_bitmap (problem_data->def_sites, regno, 1132169689Skan reg_info->begin, reg_info->n_refs); 1133169689Skan bitmap_ior_into (dense_invalidated, defs); 1134169689Skan } 1135169689Skan } 1136169689Skan df_unset_seen (); 1137169689Skan} 1138169689Skan 1139169689Skan 1140169689Skan/* Initialize the solution bit vectors for problem. */ 1141169689Skan 1142169689Skanstatic void 1143169689Skandf_rd_init_solution (struct dataflow *dflow, bitmap all_blocks) 1144169689Skan{ 1145169689Skan unsigned int bb_index; 1146169689Skan bitmap_iterator bi; 1147169689Skan 1148169689Skan EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) 1149169689Skan { 1150169689Skan struct df_rd_bb_info *bb_info = df_rd_get_bb_info (dflow, bb_index); 1151169689Skan 1152169689Skan bitmap_copy (bb_info->out, bb_info->gen); 1153169689Skan bitmap_clear (bb_info->in); 1154169689Skan } 1155169689Skan} 1156169689Skan 1157169689Skan/* In of target gets or of out of source. */ 1158169689Skan 1159169689Skanstatic void 1160169689Skandf_rd_confluence_n (struct dataflow *dflow, edge e) 1161169689Skan{ 1162169689Skan bitmap op1 = df_rd_get_bb_info (dflow, e->dest->index)->in; 1163169689Skan bitmap op2 = df_rd_get_bb_info (dflow, e->src->index)->out; 1164169689Skan 1165169689Skan if (e->flags & EDGE_EH) 1166169689Skan { 1167169689Skan struct df_rd_problem_data *problem_data 1168169689Skan = (struct df_rd_problem_data *) dflow->problem_data; 1169169689Skan bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call; 1170169689Skan bitmap dense_invalidated = problem_data->dense_invalidated_by_call; 1171169689Skan struct df *df = dflow->df; 1172169689Skan bitmap_iterator bi; 1173169689Skan unsigned int regno; 1174169689Skan bitmap tmp = BITMAP_ALLOC (NULL); 1175169689Skan 1176169689Skan bitmap_copy (tmp, op2); 1177169689Skan bitmap_and_compl_into (tmp, dense_invalidated); 1178169689Skan 1179169689Skan EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi) 1180169689Skan { 1181169689Skan bitmap_clear_range (tmp, 1182169689Skan DF_REG_DEF_GET (df, regno)->begin, 1183169689Skan DF_REG_DEF_GET (df, regno)->n_refs); 1184169689Skan } 1185169689Skan bitmap_ior_into (op1, tmp); 1186169689Skan BITMAP_FREE (tmp); 1187169689Skan } 1188169689Skan else 1189169689Skan bitmap_ior_into (op1, op2); 1190169689Skan} 1191169689Skan 1192169689Skan 1193169689Skan/* Transfer function. */ 1194169689Skan 1195169689Skanstatic bool 1196169689Skandf_rd_transfer_function (struct dataflow *dflow, int bb_index) 1197169689Skan{ 1198169689Skan struct df_rd_bb_info *bb_info = df_rd_get_bb_info (dflow, bb_index); 1199169689Skan unsigned int regno; 1200169689Skan bitmap_iterator bi; 1201169689Skan bitmap in = bb_info->in; 1202169689Skan bitmap out = bb_info->out; 1203169689Skan bitmap gen = bb_info->gen; 1204169689Skan bitmap kill = bb_info->kill; 1205169689Skan bitmap sparse_kill = bb_info->sparse_kill; 1206169689Skan 1207169689Skan if (bitmap_empty_p (sparse_kill)) 1208169689Skan return bitmap_ior_and_compl (out, gen, in, kill); 1209169689Skan else 1210169689Skan { 1211169689Skan struct df *df = dflow->df; 1212169689Skan bool changed = false; 1213169689Skan bitmap tmp = BITMAP_ALLOC (NULL); 1214169689Skan bitmap_copy (tmp, in); 1215169689Skan EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi) 1216169689Skan { 1217169689Skan bitmap_clear_range (tmp, 1218169689Skan DF_REG_DEF_GET (df, regno)->begin, 1219169689Skan DF_REG_DEF_GET (df, regno)->n_refs); 1220169689Skan } 1221169689Skan bitmap_and_compl_into (tmp, kill); 1222169689Skan bitmap_ior_into (tmp, gen); 1223169689Skan changed = !bitmap_equal_p (tmp, out); 1224169689Skan if (changed) 1225169689Skan { 1226169689Skan BITMAP_FREE (out); 1227169689Skan bb_info->out = tmp; 1228169689Skan } 1229169689Skan else 1230169689Skan BITMAP_FREE (tmp); 1231169689Skan return changed; 1232169689Skan } 1233169689Skan} 1234169689Skan 1235169689Skan 1236169689Skan/* Free all storage associated with the problem. */ 1237169689Skan 1238169689Skanstatic void 1239169689Skandf_rd_free (struct dataflow *dflow) 1240169689Skan{ 1241169689Skan unsigned int i; 1242169689Skan struct df_rd_problem_data *problem_data 1243169689Skan = (struct df_rd_problem_data *) dflow->problem_data; 1244169689Skan 1245169689Skan if (problem_data) 1246169689Skan { 1247169689Skan for (i = 0; i < dflow->block_info_size; i++) 1248169689Skan { 1249169689Skan struct df_rd_bb_info *bb_info = df_rd_get_bb_info (dflow, i); 1250169689Skan if (bb_info) 1251169689Skan { 1252169689Skan BITMAP_FREE (bb_info->kill); 1253169689Skan BITMAP_FREE (bb_info->sparse_kill); 1254169689Skan BITMAP_FREE (bb_info->gen); 1255169689Skan BITMAP_FREE (bb_info->in); 1256169689Skan BITMAP_FREE (bb_info->out); 1257169689Skan } 1258169689Skan } 1259169689Skan 1260169689Skan free_alloc_pool (dflow->block_pool); 1261169689Skan 1262169689Skan for (i = 0; i < problem_data->def_sites_size; i++) 1263169689Skan { 1264169689Skan bitmap bm = problem_data->def_sites[i]; 1265169689Skan if (bm) 1266169689Skan BITMAP_FREE (bm); 1267169689Skan } 1268169689Skan 1269169689Skan free (problem_data->def_sites); 1270169689Skan BITMAP_FREE (problem_data->sparse_invalidated_by_call); 1271169689Skan BITMAP_FREE (problem_data->dense_invalidated_by_call); 1272169689Skan 1273169689Skan dflow->block_info_size = 0; 1274169689Skan free (dflow->block_info); 1275169689Skan free (dflow->problem_data); 1276169689Skan } 1277169689Skan free (dflow); 1278169689Skan} 1279169689Skan 1280169689Skan 1281169689Skan/* Debugging info. */ 1282169689Skan 1283169689Skanstatic void 1284169689Skandf_rd_dump (struct dataflow *dflow, FILE *file) 1285169689Skan{ 1286169689Skan struct df *df = dflow->df; 1287169689Skan basic_block bb; 1288169689Skan struct df_rd_problem_data *problem_data 1289169689Skan = (struct df_rd_problem_data *) dflow->problem_data; 1290169689Skan unsigned int m = max_reg_num (); 1291169689Skan unsigned int regno; 1292169689Skan 1293169689Skan if (!dflow->block_info) 1294169689Skan return; 1295169689Skan 1296169689Skan fprintf (file, "Reaching defs:\n\n"); 1297169689Skan 1298169689Skan fprintf (file, " sparse invalidated \t"); 1299169689Skan dump_bitmap (file, problem_data->sparse_invalidated_by_call); 1300169689Skan fprintf (file, " dense invalidated \t"); 1301169689Skan dump_bitmap (file, problem_data->dense_invalidated_by_call); 1302169689Skan 1303169689Skan for (regno = 0; regno < m; regno++) 1304169689Skan if (DF_REG_DEF_GET (df, regno)->n_refs) 1305169689Skan fprintf (file, "%d[%d,%d] ", regno, 1306169689Skan DF_REG_DEF_GET (df, regno)->begin, 1307169689Skan DF_REG_DEF_GET (df, regno)->n_refs); 1308169689Skan fprintf (file, "\n"); 1309169689Skan 1310169689Skan FOR_ALL_BB (bb) 1311169689Skan { 1312169689Skan struct df_rd_bb_info *bb_info = df_rd_get_bb_info (dflow, bb->index); 1313169689Skan df_print_bb_index (bb, file); 1314169689Skan 1315169689Skan if (!bb_info->in) 1316169689Skan continue; 1317169689Skan 1318169689Skan fprintf (file, " in \t(%d)\n", (int) bitmap_count_bits (bb_info->in)); 1319169689Skan dump_bitmap (file, bb_info->in); 1320169689Skan fprintf (file, " gen \t(%d)\n", (int) bitmap_count_bits (bb_info->gen)); 1321169689Skan dump_bitmap (file, bb_info->gen); 1322169689Skan fprintf (file, " kill\t(%d)\n", (int) bitmap_count_bits (bb_info->kill)); 1323169689Skan dump_bitmap (file, bb_info->kill); 1324169689Skan fprintf (file, " out \t(%d)\n", (int) bitmap_count_bits (bb_info->out)); 1325169689Skan dump_bitmap (file, bb_info->out); 1326169689Skan } 1327169689Skan} 1328169689Skan 1329169689Skan/* All of the information associated with every instance of the problem. */ 1330169689Skan 1331169689Skanstatic struct df_problem problem_RD = 1332169689Skan{ 1333169689Skan DF_RD, /* Problem id. */ 1334169689Skan DF_FORWARD, /* Direction. */ 1335169689Skan df_rd_alloc, /* Allocate the problem specific data. */ 1336169689Skan NULL, /* Reset global information. */ 1337169689Skan df_rd_free_bb_info, /* Free basic block info. */ 1338169689Skan df_rd_local_compute, /* Local compute function. */ 1339169689Skan df_rd_init_solution, /* Init the solution specific data. */ 1340169689Skan df_iterative_dataflow, /* Iterative solver. */ 1341169689Skan NULL, /* Confluence operator 0. */ 1342169689Skan df_rd_confluence_n, /* Confluence operator n. */ 1343169689Skan df_rd_transfer_function, /* Transfer function. */ 1344169689Skan NULL, /* Finalize function. */ 1345169689Skan df_rd_free, /* Free all of the problem information. */ 1346169689Skan df_rd_dump, /* Debugging. */ 1347169689Skan NULL, /* Dependent problem. */ 1348169689Skan 0 /* Changeable flags. */ 1349169689Skan}; 1350169689Skan 1351169689Skan 1352169689Skan 1353169689Skan/* Create a new DATAFLOW instance and add it to an existing instance 1354169689Skan of DF. The returned structure is what is used to get at the 1355169689Skan solution. */ 1356169689Skan 1357169689Skanstruct dataflow * 1358169689Skandf_rd_add_problem (struct df *df, int flags) 1359169689Skan{ 1360169689Skan return df_add_problem (df, &problem_RD, flags); 1361169689Skan} 1362169689Skan 1363169689Skan 1364169689Skan 1365169689Skan/*---------------------------------------------------------------------------- 1366169689Skan LIVE REGISTERS 1367169689Skan 1368169689Skan Find the locations in the function where any use of a pseudo can 1369169689Skan reach in the backwards direction. In and out bitvectors are built 1370169689Skan for each basic block. The regnum is used to index into these sets. 1371169689Skan See df.h for details. 1372169689Skan ----------------------------------------------------------------------------*/ 1373169689Skan 1374169689Skan/* Get basic block info. */ 1375169689Skan 1376169689Skanstruct df_lr_bb_info * 1377169689Skandf_lr_get_bb_info (struct dataflow *dflow, unsigned int index) 1378169689Skan{ 1379169689Skan return (struct df_lr_bb_info *) dflow->block_info[index]; 1380169689Skan} 1381169689Skan 1382169689Skan 1383169689Skan/* Set basic block info. */ 1384169689Skan 1385169689Skanstatic void 1386169689Skandf_lr_set_bb_info (struct dataflow *dflow, unsigned int index, 1387169689Skan struct df_lr_bb_info *bb_info) 1388169689Skan{ 1389169689Skan dflow->block_info[index] = bb_info; 1390169689Skan} 1391169689Skan 1392169689Skan 1393169689Skan/* Free basic block info. */ 1394169689Skan 1395169689Skanstatic void 1396169689Skandf_lr_free_bb_info (struct dataflow *dflow, 1397169689Skan basic_block bb ATTRIBUTE_UNUSED, 1398169689Skan void *vbb_info) 1399169689Skan{ 1400169689Skan struct df_lr_bb_info *bb_info = (struct df_lr_bb_info *) vbb_info; 1401169689Skan if (bb_info) 1402169689Skan { 1403169689Skan BITMAP_FREE (bb_info->use); 1404169689Skan BITMAP_FREE (bb_info->def); 1405169689Skan BITMAP_FREE (bb_info->in); 1406169689Skan BITMAP_FREE (bb_info->out); 1407169689Skan pool_free (dflow->block_pool, bb_info); 1408169689Skan } 1409169689Skan} 1410169689Skan 1411169689Skan 1412169689Skan/* Allocate or reset bitmaps for DFLOW blocks. The solution bits are 1413169689Skan not touched unless the block is new. */ 1414169689Skan 1415169689Skanstatic void 1416169689Skandf_lr_alloc (struct dataflow *dflow, bitmap blocks_to_rescan, 1417169689Skan bitmap all_blocks ATTRIBUTE_UNUSED) 1418169689Skan{ 1419169689Skan unsigned int bb_index; 1420169689Skan bitmap_iterator bi; 1421169689Skan 1422169689Skan if (!dflow->block_pool) 1423169689Skan dflow->block_pool = create_alloc_pool ("df_lr_block pool", 1424169689Skan sizeof (struct df_lr_bb_info), 50); 1425169689Skan 1426169689Skan df_grow_bb_info (dflow); 1427169689Skan 1428169689Skan EXECUTE_IF_SET_IN_BITMAP (blocks_to_rescan, 0, bb_index, bi) 1429169689Skan { 1430169689Skan struct df_lr_bb_info *bb_info = df_lr_get_bb_info (dflow, bb_index); 1431169689Skan if (bb_info) 1432169689Skan { 1433169689Skan bitmap_clear (bb_info->def); 1434169689Skan bitmap_clear (bb_info->use); 1435169689Skan } 1436169689Skan else 1437169689Skan { 1438169689Skan bb_info = (struct df_lr_bb_info *) pool_alloc (dflow->block_pool); 1439169689Skan df_lr_set_bb_info (dflow, bb_index, bb_info); 1440169689Skan bb_info->use = BITMAP_ALLOC (NULL); 1441169689Skan bb_info->def = BITMAP_ALLOC (NULL); 1442169689Skan bb_info->in = BITMAP_ALLOC (NULL); 1443169689Skan bb_info->out = BITMAP_ALLOC (NULL); 1444169689Skan } 1445169689Skan } 1446169689Skan} 1447169689Skan 1448169689Skan 1449169689Skan/* Compute local live register info for basic block BB. */ 1450169689Skan 1451169689Skanstatic void 1452169689Skandf_lr_bb_local_compute (struct dataflow *dflow, 1453169689Skan struct df *df, unsigned int bb_index) 1454169689Skan{ 1455169689Skan basic_block bb = BASIC_BLOCK (bb_index); 1456169689Skan struct df_lr_bb_info *bb_info = df_lr_get_bb_info (dflow, bb_index); 1457169689Skan rtx insn; 1458169689Skan struct df_ref *def; 1459169689Skan struct df_ref *use; 1460169689Skan 1461169689Skan /* Process the registers set in an exception handler. */ 1462169689Skan for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref) 1463169689Skan if (((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0) 1464169689Skan && (!(DF_REF_FLAGS (def) & DF_REF_PARTIAL))) 1465169689Skan { 1466169689Skan unsigned int dregno = DF_REF_REGNO (def); 1467169689Skan bitmap_set_bit (bb_info->def, dregno); 1468169689Skan bitmap_clear_bit (bb_info->use, dregno); 1469169689Skan } 1470169689Skan 1471169689Skan /* Process the hardware registers that are always live. */ 1472169689Skan for (use = df_get_artificial_uses (df, bb_index); use; use = use->next_ref) 1473169689Skan /* Add use to set of uses in this BB. */ 1474169689Skan if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0) 1475169689Skan bitmap_set_bit (bb_info->use, DF_REF_REGNO (use)); 1476169689Skan 1477169689Skan FOR_BB_INSNS_REVERSE (bb, insn) 1478169689Skan { 1479169689Skan unsigned int uid = INSN_UID (insn); 1480169689Skan 1481169689Skan if (!INSN_P (insn)) 1482169689Skan continue; 1483169689Skan 1484169689Skan if (CALL_P (insn)) 1485169689Skan { 1486169689Skan for (def = DF_INSN_UID_DEFS (df, uid); def; def = def->next_ref) 1487169689Skan { 1488169689Skan unsigned int dregno = DF_REF_REGNO (def); 1489169689Skan 1490169689Skan if (dregno >= FIRST_PSEUDO_REGISTER 1491169689Skan || !(SIBLING_CALL_P (insn) 1492169689Skan && bitmap_bit_p (df->exit_block_uses, dregno) 1493169689Skan && !refers_to_regno_p (dregno, dregno+1, 1494169689Skan current_function_return_rtx, 1495169689Skan (rtx *)0))) 1496169689Skan { 1497169689Skan /* If the def is to only part of the reg, it does 1498169689Skan not kill the other defs that reach here. */ 1499169689Skan if (!(DF_REF_FLAGS (def) & DF_REF_PARTIAL)) 1500169689Skan { 1501169689Skan bitmap_set_bit (bb_info->def, dregno); 1502169689Skan bitmap_clear_bit (bb_info->use, dregno); 1503169689Skan } 1504169689Skan } 1505169689Skan } 1506169689Skan } 1507169689Skan else 1508169689Skan { 1509169689Skan for (def = DF_INSN_UID_DEFS (df, uid); def; def = def->next_ref) 1510169689Skan { 1511169689Skan unsigned int dregno = DF_REF_REGNO (def); 1512169689Skan 1513169689Skan if (DF_INSN_CONTAINS_ASM (df, insn) 1514169689Skan && dregno < FIRST_PSEUDO_REGISTER) 1515169689Skan { 1516169689Skan unsigned int i; 1517169689Skan unsigned int end = dregno 1518169689Skan + hard_regno_nregs[dregno][GET_MODE (DF_REF_REG (def))] - 1; 1519169689Skan for (i = dregno; i <= end; ++i) 1520169689Skan regs_asm_clobbered[i] = 1; 1521169689Skan } 1522169689Skan /* If the def is to only part of the reg, it does 1523169689Skan not kill the other defs that reach here. */ 1524169689Skan if (!(DF_REF_FLAGS (def) & DF_REF_PARTIAL)) 1525169689Skan { 1526169689Skan bitmap_set_bit (bb_info->def, dregno); 1527169689Skan bitmap_clear_bit (bb_info->use, dregno); 1528169689Skan } 1529169689Skan } 1530169689Skan } 1531169689Skan 1532169689Skan for (use = DF_INSN_UID_USES (df, uid); use; use = use->next_ref) 1533169689Skan /* Add use to set of uses in this BB. */ 1534169689Skan bitmap_set_bit (bb_info->use, DF_REF_REGNO (use)); 1535169689Skan } 1536169689Skan 1537169689Skan /* Process the registers set in an exception handler. */ 1538169689Skan for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref) 1539169689Skan if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) 1540169689Skan && (!(DF_REF_FLAGS (def) & DF_REF_PARTIAL))) 1541169689Skan { 1542169689Skan unsigned int dregno = DF_REF_REGNO (def); 1543169689Skan bitmap_set_bit (bb_info->def, dregno); 1544169689Skan bitmap_clear_bit (bb_info->use, dregno); 1545169689Skan } 1546169689Skan 1547169689Skan#ifdef EH_USES 1548169689Skan /* Process the uses that are live into an exception handler. */ 1549169689Skan for (use = df_get_artificial_uses (df, bb_index); use; use = use->next_ref) 1550169689Skan /* Add use to set of uses in this BB. */ 1551169689Skan if (DF_REF_FLAGS (use) & DF_REF_AT_TOP) 1552169689Skan bitmap_set_bit (bb_info->use, DF_REF_REGNO (use)); 1553169689Skan#endif 1554169689Skan} 1555169689Skan 1556169689Skan 1557169689Skan/* Compute local live register info for each basic block within BLOCKS. */ 1558169689Skan 1559169689Skanstatic void 1560169689Skandf_lr_local_compute (struct dataflow *dflow, 1561169689Skan bitmap all_blocks, 1562169689Skan bitmap rescan_blocks) 1563169689Skan{ 1564169689Skan struct df *df = dflow->df; 1565169689Skan unsigned int bb_index; 1566169689Skan bitmap_iterator bi; 1567169689Skan 1568169689Skan /* Assume that the stack pointer is unchanging if alloca hasn't 1569169689Skan been used. */ 1570169689Skan if (bitmap_equal_p (all_blocks, rescan_blocks)) 1571169689Skan memset (regs_asm_clobbered, 0, sizeof (regs_asm_clobbered)); 1572169689Skan 1573169689Skan bitmap_clear (df->hardware_regs_used); 1574169689Skan 1575169689Skan /* The all-important stack pointer must always be live. */ 1576169689Skan bitmap_set_bit (df->hardware_regs_used, STACK_POINTER_REGNUM); 1577169689Skan 1578169689Skan /* Before reload, there are a few registers that must be forced 1579169689Skan live everywhere -- which might not already be the case for 1580169689Skan blocks within infinite loops. */ 1581169689Skan if (!reload_completed) 1582169689Skan { 1583169689Skan /* Any reference to any pseudo before reload is a potential 1584169689Skan reference of the frame pointer. */ 1585169689Skan bitmap_set_bit (df->hardware_regs_used, FRAME_POINTER_REGNUM); 1586169689Skan 1587169689Skan#if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM 1588169689Skan /* Pseudos with argument area equivalences may require 1589169689Skan reloading via the argument pointer. */ 1590169689Skan if (fixed_regs[ARG_POINTER_REGNUM]) 1591169689Skan bitmap_set_bit (df->hardware_regs_used, ARG_POINTER_REGNUM); 1592169689Skan#endif 1593169689Skan 1594169689Skan /* Any constant, or pseudo with constant equivalences, may 1595169689Skan require reloading from memory using the pic register. */ 1596169689Skan if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM 1597169689Skan && fixed_regs[PIC_OFFSET_TABLE_REGNUM]) 1598169689Skan bitmap_set_bit (df->hardware_regs_used, PIC_OFFSET_TABLE_REGNUM); 1599169689Skan } 1600169689Skan 1601169689Skan if (bitmap_bit_p (rescan_blocks, EXIT_BLOCK)) 1602169689Skan { 1603169689Skan /* The exit block is special for this problem and its bits are 1604169689Skan computed from thin air. */ 1605169689Skan struct df_lr_bb_info *bb_info = df_lr_get_bb_info (dflow, EXIT_BLOCK); 1606169689Skan bitmap_copy (bb_info->use, df->exit_block_uses); 1607169689Skan } 1608169689Skan 1609169689Skan EXECUTE_IF_SET_IN_BITMAP (rescan_blocks, 0, bb_index, bi) 1610169689Skan { 1611169689Skan if (bb_index == EXIT_BLOCK) 1612169689Skan continue; 1613169689Skan df_lr_bb_local_compute (dflow, df, bb_index); 1614169689Skan } 1615169689Skan} 1616169689Skan 1617169689Skan 1618169689Skan/* Initialize the solution vectors. */ 1619169689Skan 1620169689Skanstatic void 1621169689Skandf_lr_init (struct dataflow *dflow, bitmap all_blocks) 1622169689Skan{ 1623169689Skan unsigned int bb_index; 1624169689Skan bitmap_iterator bi; 1625169689Skan 1626169689Skan EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) 1627169689Skan { 1628169689Skan struct df_lr_bb_info *bb_info = df_lr_get_bb_info (dflow, bb_index); 1629169689Skan bitmap_copy (bb_info->in, bb_info->use); 1630169689Skan bitmap_clear (bb_info->out); 1631169689Skan } 1632169689Skan} 1633169689Skan 1634169689Skan 1635169689Skan/* Confluence function that processes infinite loops. This might be a 1636169689Skan noreturn function that throws. And even if it isn't, getting the 1637169689Skan unwind info right helps debugging. */ 1638169689Skanstatic void 1639169689Skandf_lr_confluence_0 (struct dataflow *dflow, basic_block bb) 1640169689Skan{ 1641169689Skan struct df *df = dflow->df; 1642169689Skan 1643169689Skan bitmap op1 = df_lr_get_bb_info (dflow, bb->index)->out; 1644169689Skan if (bb != EXIT_BLOCK_PTR) 1645169689Skan bitmap_copy (op1, df->hardware_regs_used); 1646169689Skan} 1647169689Skan 1648169689Skan 1649169689Skan/* Confluence function that ignores fake edges. */ 1650169689Skan 1651169689Skanstatic void 1652169689Skandf_lr_confluence_n (struct dataflow *dflow, edge e) 1653169689Skan{ 1654169689Skan bitmap op1 = df_lr_get_bb_info (dflow, e->src->index)->out; 1655169689Skan bitmap op2 = df_lr_get_bb_info (dflow, e->dest->index)->in; 1656169689Skan 1657169689Skan /* Call-clobbered registers die across exception and call edges. */ 1658169689Skan /* ??? Abnormal call edges ignored for the moment, as this gets 1659169689Skan confused by sibling call edges, which crashes reg-stack. */ 1660169689Skan if (e->flags & EDGE_EH) 1661169689Skan bitmap_ior_and_compl_into (op1, op2, df_invalidated_by_call); 1662169689Skan else 1663169689Skan bitmap_ior_into (op1, op2); 1664169689Skan 1665169689Skan bitmap_ior_into (op1, dflow->df->hardware_regs_used); 1666169689Skan} 1667169689Skan 1668169689Skan 1669169689Skan/* Transfer function. */ 1670169689Skan 1671169689Skanstatic bool 1672169689Skandf_lr_transfer_function (struct dataflow *dflow, int bb_index) 1673169689Skan{ 1674169689Skan struct df_lr_bb_info *bb_info = df_lr_get_bb_info (dflow, bb_index); 1675169689Skan bitmap in = bb_info->in; 1676169689Skan bitmap out = bb_info->out; 1677169689Skan bitmap use = bb_info->use; 1678169689Skan bitmap def = bb_info->def; 1679169689Skan 1680169689Skan return bitmap_ior_and_compl (in, use, out, def); 1681169689Skan} 1682169689Skan 1683169689Skan 1684169689Skan/* Free all storage associated with the problem. */ 1685169689Skan 1686169689Skanstatic void 1687169689Skandf_lr_free (struct dataflow *dflow) 1688169689Skan{ 1689169689Skan if (dflow->block_info) 1690169689Skan { 1691169689Skan unsigned int i; 1692169689Skan for (i = 0; i < dflow->block_info_size; i++) 1693169689Skan { 1694169689Skan struct df_lr_bb_info *bb_info = df_lr_get_bb_info (dflow, i); 1695169689Skan if (bb_info) 1696169689Skan { 1697169689Skan BITMAP_FREE (bb_info->use); 1698169689Skan BITMAP_FREE (bb_info->def); 1699169689Skan BITMAP_FREE (bb_info->in); 1700169689Skan BITMAP_FREE (bb_info->out); 1701169689Skan } 1702169689Skan } 1703169689Skan free_alloc_pool (dflow->block_pool); 1704169689Skan 1705169689Skan dflow->block_info_size = 0; 1706169689Skan free (dflow->block_info); 1707169689Skan } 1708169689Skan 1709169689Skan free (dflow->problem_data); 1710169689Skan free (dflow); 1711169689Skan} 1712169689Skan 1713169689Skan 1714169689Skan/* Debugging info. */ 1715169689Skan 1716169689Skanstatic void 1717169689Skandf_lr_dump (struct dataflow *dflow, FILE *file) 1718169689Skan{ 1719169689Skan basic_block bb; 1720169689Skan 1721169689Skan if (!dflow->block_info) 1722169689Skan return; 1723169689Skan 1724169689Skan fprintf (file, "Live Registers:\n"); 1725169689Skan FOR_ALL_BB (bb) 1726169689Skan { 1727169689Skan struct df_lr_bb_info *bb_info = df_lr_get_bb_info (dflow, bb->index); 1728169689Skan df_print_bb_index (bb, file); 1729169689Skan 1730169689Skan if (!bb_info->in) 1731169689Skan continue; 1732169689Skan 1733169689Skan fprintf (file, " in \t"); 1734169689Skan dump_bitmap (file, bb_info->in); 1735169689Skan fprintf (file, " use \t"); 1736169689Skan dump_bitmap (file, bb_info->use); 1737169689Skan fprintf (file, " def \t"); 1738169689Skan dump_bitmap (file, bb_info->def); 1739169689Skan fprintf (file, " out \t"); 1740169689Skan dump_bitmap (file, bb_info->out); 1741169689Skan } 1742169689Skan} 1743169689Skan 1744169689Skan/* All of the information associated with every instance of the problem. */ 1745169689Skan 1746169689Skanstatic struct df_problem problem_LR = 1747169689Skan{ 1748169689Skan DF_LR, /* Problem id. */ 1749169689Skan DF_BACKWARD, /* Direction. */ 1750169689Skan df_lr_alloc, /* Allocate the problem specific data. */ 1751169689Skan NULL, /* Reset global information. */ 1752169689Skan df_lr_free_bb_info, /* Free basic block info. */ 1753169689Skan df_lr_local_compute, /* Local compute function. */ 1754169689Skan df_lr_init, /* Init the solution specific data. */ 1755169689Skan df_iterative_dataflow, /* Iterative solver. */ 1756169689Skan df_lr_confluence_0, /* Confluence operator 0. */ 1757169689Skan df_lr_confluence_n, /* Confluence operator n. */ 1758169689Skan df_lr_transfer_function, /* Transfer function. */ 1759169689Skan NULL, /* Finalize function. */ 1760169689Skan df_lr_free, /* Free all of the problem information. */ 1761169689Skan df_lr_dump, /* Debugging. */ 1762169689Skan NULL, /* Dependent problem. */ 1763169689Skan 0 1764169689Skan}; 1765169689Skan 1766169689Skan 1767169689Skan/* Create a new DATAFLOW instance and add it to an existing instance 1768169689Skan of DF. The returned structure is what is used to get at the 1769169689Skan solution. */ 1770169689Skan 1771169689Skanstruct dataflow * 1772169689Skandf_lr_add_problem (struct df *df, int flags) 1773169689Skan{ 1774169689Skan return df_add_problem (df, &problem_LR, flags); 1775169689Skan} 1776169689Skan 1777169689Skan 1778169689Skan 1779169689Skan/*---------------------------------------------------------------------------- 1780169689Skan UNINITIALIZED REGISTERS 1781169689Skan 1782169689Skan Find the set of uses for registers that are reachable from the entry 1783169689Skan block without passing thru a definition. In and out bitvectors are built 1784169689Skan for each basic block. The regnum is used to index into these sets. 1785169689Skan See df.h for details. 1786169689Skan----------------------------------------------------------------------------*/ 1787169689Skan 1788169689Skan/* Get basic block info. */ 1789169689Skan 1790169689Skanstruct df_ur_bb_info * 1791169689Skandf_ur_get_bb_info (struct dataflow *dflow, unsigned int index) 1792169689Skan{ 1793169689Skan return (struct df_ur_bb_info *) dflow->block_info[index]; 1794169689Skan} 1795169689Skan 1796169689Skan 1797169689Skan/* Set basic block info. */ 1798169689Skan 1799169689Skanstatic void 1800169689Skandf_ur_set_bb_info (struct dataflow *dflow, unsigned int index, 1801169689Skan struct df_ur_bb_info *bb_info) 1802169689Skan{ 1803169689Skan dflow->block_info[index] = bb_info; 1804169689Skan} 1805169689Skan 1806169689Skan 1807169689Skan/* Free basic block info. */ 1808169689Skan 1809169689Skanstatic void 1810169689Skandf_ur_free_bb_info (struct dataflow *dflow, 1811169689Skan basic_block bb ATTRIBUTE_UNUSED, 1812169689Skan void *vbb_info) 1813169689Skan{ 1814169689Skan struct df_ur_bb_info *bb_info = (struct df_ur_bb_info *) vbb_info; 1815169689Skan if (bb_info) 1816169689Skan { 1817169689Skan BITMAP_FREE (bb_info->gen); 1818169689Skan BITMAP_FREE (bb_info->kill); 1819169689Skan BITMAP_FREE (bb_info->in); 1820169689Skan BITMAP_FREE (bb_info->out); 1821169689Skan pool_free (dflow->block_pool, bb_info); 1822169689Skan } 1823169689Skan} 1824169689Skan 1825169689Skan 1826169689Skan/* Allocate or reset bitmaps for DFLOW blocks. The solution bits are 1827169689Skan not touched unless the block is new. */ 1828169689Skan 1829169689Skanstatic void 1830169689Skandf_ur_alloc (struct dataflow *dflow, bitmap blocks_to_rescan, 1831169689Skan bitmap all_blocks ATTRIBUTE_UNUSED) 1832169689Skan{ 1833169689Skan unsigned int bb_index; 1834169689Skan bitmap_iterator bi; 1835169689Skan 1836169689Skan if (!dflow->block_pool) 1837169689Skan dflow->block_pool = create_alloc_pool ("df_ur_block pool", 1838169689Skan sizeof (struct df_ur_bb_info), 100); 1839169689Skan 1840169689Skan df_grow_bb_info (dflow); 1841169689Skan 1842169689Skan EXECUTE_IF_SET_IN_BITMAP (blocks_to_rescan, 0, bb_index, bi) 1843169689Skan { 1844169689Skan struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, bb_index); 1845169689Skan if (bb_info) 1846169689Skan { 1847169689Skan bitmap_clear (bb_info->kill); 1848169689Skan bitmap_clear (bb_info->gen); 1849169689Skan } 1850169689Skan else 1851169689Skan { 1852169689Skan bb_info = (struct df_ur_bb_info *) pool_alloc (dflow->block_pool); 1853169689Skan df_ur_set_bb_info (dflow, bb_index, bb_info); 1854169689Skan bb_info->kill = BITMAP_ALLOC (NULL); 1855169689Skan bb_info->gen = BITMAP_ALLOC (NULL); 1856169689Skan bb_info->in = BITMAP_ALLOC (NULL); 1857169689Skan bb_info->out = BITMAP_ALLOC (NULL); 1858169689Skan } 1859169689Skan } 1860169689Skan} 1861169689Skan 1862169689Skan 1863169689Skan/* Compute local uninitialized register info for basic block BB. */ 1864169689Skan 1865169689Skanstatic void 1866169689Skandf_ur_bb_local_compute (struct dataflow *dflow, unsigned int bb_index) 1867169689Skan{ 1868169689Skan struct df *df = dflow->df; 1869169689Skan basic_block bb = BASIC_BLOCK (bb_index); 1870169689Skan struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, bb_index); 1871169689Skan rtx insn; 1872169689Skan struct df_ref *def; 1873169689Skan 1874169689Skan bitmap_clear (seen_in_block); 1875169689Skan bitmap_clear (seen_in_insn); 1876169689Skan 1877169689Skan for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref) 1878169689Skan if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0) 1879169689Skan { 1880169689Skan unsigned int regno = DF_REF_REGNO (def); 1881169689Skan if (!bitmap_bit_p (seen_in_block, regno)) 1882169689Skan { 1883169689Skan bitmap_set_bit (seen_in_block, regno); 1884169689Skan bitmap_set_bit (bb_info->gen, regno); 1885169689Skan } 1886169689Skan } 1887169689Skan 1888169689Skan FOR_BB_INSNS_REVERSE (bb, insn) 1889169689Skan { 1890169689Skan unsigned int uid = INSN_UID (insn); 1891169689Skan if (!INSN_P (insn)) 1892169689Skan continue; 1893169689Skan 1894169689Skan for (def = DF_INSN_UID_DEFS (df, uid); def; def = def->next_ref) 1895169689Skan { 1896169689Skan unsigned int regno = DF_REF_REGNO (def); 1897169689Skan /* Only the last def counts. */ 1898169689Skan if (!bitmap_bit_p (seen_in_block, regno)) 1899169689Skan { 1900169689Skan bitmap_set_bit (seen_in_insn, regno); 1901169689Skan 1902169689Skan if (DF_REF_FLAGS (def) 1903169689Skan & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)) 1904169689Skan { 1905169689Skan /* Only must clobbers for the entire reg destroy the 1906169689Skan value. */ 1907169689Skan if ((DF_REF_FLAGS (def) & DF_REF_MUST_CLOBBER) 1908169689Skan && (!DF_REF_FLAGS (def) & DF_REF_PARTIAL)) 1909169689Skan bitmap_set_bit (bb_info->kill, regno); 1910169689Skan } 1911169689Skan else 1912169689Skan bitmap_set_bit (bb_info->gen, regno); 1913169689Skan } 1914169689Skan } 1915169689Skan bitmap_ior_into (seen_in_block, seen_in_insn); 1916169689Skan bitmap_clear (seen_in_insn); 1917169689Skan } 1918169689Skan 1919169689Skan for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref) 1920169689Skan if (DF_REF_FLAGS (def) & DF_REF_AT_TOP) 1921169689Skan { 1922169689Skan unsigned int regno = DF_REF_REGNO (def); 1923169689Skan if (!bitmap_bit_p (seen_in_block, regno)) 1924169689Skan { 1925169689Skan bitmap_set_bit (seen_in_block, regno); 1926169689Skan bitmap_set_bit (bb_info->gen, regno); 1927169689Skan } 1928169689Skan } 1929169689Skan} 1930169689Skan 1931169689Skan 1932169689Skan/* Compute local uninitialized register info. */ 1933169689Skan 1934169689Skanstatic void 1935169689Skandf_ur_local_compute (struct dataflow *dflow, 1936169689Skan bitmap all_blocks ATTRIBUTE_UNUSED, 1937169689Skan bitmap rescan_blocks) 1938169689Skan{ 1939169689Skan unsigned int bb_index; 1940169689Skan bitmap_iterator bi; 1941169689Skan 1942169689Skan df_set_seen (); 1943169689Skan 1944169689Skan EXECUTE_IF_SET_IN_BITMAP (rescan_blocks, 0, bb_index, bi) 1945169689Skan { 1946169689Skan df_ur_bb_local_compute (dflow, bb_index); 1947169689Skan } 1948169689Skan 1949169689Skan df_unset_seen (); 1950169689Skan} 1951169689Skan 1952169689Skan 1953169689Skan/* Initialize the solution vectors. */ 1954169689Skan 1955169689Skanstatic void 1956169689Skandf_ur_init (struct dataflow *dflow, bitmap all_blocks) 1957169689Skan{ 1958169689Skan unsigned int bb_index; 1959169689Skan bitmap_iterator bi; 1960169689Skan 1961169689Skan EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) 1962169689Skan { 1963169689Skan struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, bb_index); 1964169689Skan 1965169689Skan bitmap_copy (bb_info->out, bb_info->gen); 1966169689Skan bitmap_clear (bb_info->in); 1967169689Skan } 1968169689Skan} 1969169689Skan 1970169689Skan 1971169689Skan/* Or in the stack regs, hard regs and early clobber regs into the the 1972169689Skan ur_in sets of all of the blocks. */ 1973169689Skan 1974169689Skanstatic void 1975169689Skandf_ur_local_finalize (struct dataflow *dflow, bitmap all_blocks) 1976169689Skan{ 1977169689Skan struct df *df = dflow->df; 1978169689Skan struct dataflow *lr_dflow = df->problems_by_index[DF_LR]; 1979169689Skan bitmap tmp = BITMAP_ALLOC (NULL); 1980169689Skan bitmap_iterator bi; 1981169689Skan unsigned int bb_index; 1982169689Skan 1983169689Skan EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) 1984169689Skan { 1985169689Skan struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, bb_index); 1986169689Skan struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (lr_dflow, bb_index); 1987169689Skan 1988169689Skan /* No register may reach a location where it is not used. Thus 1989169689Skan we trim the rr result to the places where it is used. */ 1990169689Skan bitmap_and_into (bb_info->in, bb_lr_info->in); 1991169689Skan bitmap_and_into (bb_info->out, bb_lr_info->out); 1992169689Skan 1993169689Skan#if 1 1994169689Skan /* Hard registers may still stick in the ur_out set, but not 1995169689Skan be in the ur_in set, if their only mention was in a call 1996169689Skan in this block. This is because a call kills in the lr 1997169689Skan problem but does not kill in the ur problem. To clean 1998169689Skan this up, we execute the transfer function on the lr_in 1999169689Skan set and then use that to knock bits out of ur_out. */ 2000169689Skan bitmap_ior_and_compl (tmp, bb_info->gen, bb_lr_info->in, 2001169689Skan bb_info->kill); 2002169689Skan bitmap_and_into (bb_info->out, tmp); 2003169689Skan#endif 2004169689Skan } 2005169689Skan 2006169689Skan BITMAP_FREE (tmp); 2007169689Skan} 2008169689Skan 2009169689Skan 2010169689Skan/* Confluence function that ignores fake edges. */ 2011169689Skan 2012169689Skanstatic void 2013169689Skandf_ur_confluence_n (struct dataflow *dflow, edge e) 2014169689Skan{ 2015169689Skan bitmap op1 = df_ur_get_bb_info (dflow, e->dest->index)->in; 2016169689Skan bitmap op2 = df_ur_get_bb_info (dflow, e->src->index)->out; 2017169689Skan 2018169689Skan if (e->flags & EDGE_FAKE) 2019169689Skan return; 2020169689Skan 2021169689Skan bitmap_ior_into (op1, op2); 2022169689Skan} 2023169689Skan 2024169689Skan 2025169689Skan/* Transfer function. */ 2026169689Skan 2027169689Skanstatic bool 2028169689Skandf_ur_transfer_function (struct dataflow *dflow, int bb_index) 2029169689Skan{ 2030169689Skan struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, bb_index); 2031169689Skan bitmap in = bb_info->in; 2032169689Skan bitmap out = bb_info->out; 2033169689Skan bitmap gen = bb_info->gen; 2034169689Skan bitmap kill = bb_info->kill; 2035169689Skan 2036169689Skan return bitmap_ior_and_compl (out, gen, in, kill); 2037169689Skan} 2038169689Skan 2039169689Skan 2040169689Skan/* Free all storage associated with the problem. */ 2041169689Skan 2042169689Skanstatic void 2043169689Skandf_ur_free (struct dataflow *dflow) 2044169689Skan{ 2045169689Skan if (dflow->block_info) 2046169689Skan { 2047169689Skan unsigned int i; 2048169689Skan 2049169689Skan for (i = 0; i < dflow->block_info_size; i++) 2050169689Skan { 2051169689Skan struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, i); 2052169689Skan if (bb_info) 2053169689Skan { 2054169689Skan BITMAP_FREE (bb_info->gen); 2055169689Skan BITMAP_FREE (bb_info->kill); 2056169689Skan BITMAP_FREE (bb_info->in); 2057169689Skan BITMAP_FREE (bb_info->out); 2058169689Skan } 2059169689Skan } 2060169689Skan 2061169689Skan free_alloc_pool (dflow->block_pool); 2062169689Skan dflow->block_info_size = 0; 2063169689Skan free (dflow->block_info); 2064169689Skan } 2065169689Skan free (dflow); 2066169689Skan} 2067169689Skan 2068169689Skan 2069169689Skan/* Debugging info. */ 2070169689Skan 2071169689Skanstatic void 2072169689Skandf_ur_dump (struct dataflow *dflow, FILE *file) 2073169689Skan{ 2074169689Skan basic_block bb; 2075169689Skan 2076169689Skan if (!dflow->block_info) 2077169689Skan return; 2078169689Skan 2079169689Skan fprintf (file, "Undefined regs:\n"); 2080169689Skan 2081169689Skan FOR_ALL_BB (bb) 2082169689Skan { 2083169689Skan struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, bb->index); 2084169689Skan df_print_bb_index (bb, file); 2085169689Skan 2086169689Skan if (!bb_info->in) 2087169689Skan continue; 2088169689Skan 2089169689Skan fprintf (file, " in \t"); 2090169689Skan dump_bitmap (file, bb_info->in); 2091169689Skan fprintf (file, " gen \t"); 2092169689Skan dump_bitmap (file, bb_info->gen); 2093169689Skan fprintf (file, " kill\t"); 2094169689Skan dump_bitmap (file, bb_info->kill); 2095169689Skan fprintf (file, " out \t"); 2096169689Skan dump_bitmap (file, bb_info->out); 2097169689Skan } 2098169689Skan} 2099169689Skan 2100169689Skan/* All of the information associated with every instance of the problem. */ 2101169689Skan 2102169689Skanstatic struct df_problem problem_UR = 2103169689Skan{ 2104169689Skan DF_UR, /* Problem id. */ 2105169689Skan DF_FORWARD, /* Direction. */ 2106169689Skan df_ur_alloc, /* Allocate the problem specific data. */ 2107169689Skan NULL, /* Reset global information. */ 2108169689Skan df_ur_free_bb_info, /* Free basic block info. */ 2109169689Skan df_ur_local_compute, /* Local compute function. */ 2110169689Skan df_ur_init, /* Init the solution specific data. */ 2111169689Skan df_iterative_dataflow, /* Iterative solver. */ 2112169689Skan NULL, /* Confluence operator 0. */ 2113169689Skan df_ur_confluence_n, /* Confluence operator n. */ 2114169689Skan df_ur_transfer_function, /* Transfer function. */ 2115169689Skan df_ur_local_finalize, /* Finalize function. */ 2116169689Skan df_ur_free, /* Free all of the problem information. */ 2117169689Skan df_ur_dump, /* Debugging. */ 2118169689Skan df_lr_add_problem, /* Dependent problem. */ 2119169689Skan 0 /* Changeable flags. */ 2120169689Skan}; 2121169689Skan 2122169689Skan 2123169689Skan/* Create a new DATAFLOW instance and add it to an existing instance 2124169689Skan of DF. The returned structure is what is used to get at the 2125169689Skan solution. */ 2126169689Skan 2127169689Skanstruct dataflow * 2128169689Skandf_ur_add_problem (struct df *df, int flags) 2129169689Skan{ 2130169689Skan return df_add_problem (df, &problem_UR, flags); 2131169689Skan} 2132169689Skan 2133169689Skan 2134169689Skan 2135169689Skan/*---------------------------------------------------------------------------- 2136169689Skan UNINITIALIZED REGISTERS WITH EARLYCLOBBER 2137169689Skan 2138169689Skan Find the set of uses for registers that are reachable from the entry 2139169689Skan block without passing thru a definition. In and out bitvectors are built 2140169689Skan for each basic block. The regnum is used to index into these sets. 2141169689Skan See df.h for details. 2142169689Skan 2143169689Skan This is a variant of the UR problem above that has a lot of special 2144169689Skan features just for the register allocation phase. This problem 2145169689Skan should go a away if someone would fix the interference graph. 2146169689Skan 2147169689Skan ----------------------------------------------------------------------------*/ 2148169689Skan 2149169689Skan/* Private data used to compute the solution for this problem. These 2150169689Skan data structures are not accessible outside of this module. */ 2151169689Skanstruct df_urec_problem_data 2152169689Skan{ 2153169689Skan bool earlyclobbers_found; /* True if any instruction contains an 2154169689Skan earlyclobber. */ 2155169689Skan#ifdef STACK_REGS 2156169689Skan bitmap stack_regs; /* Registers that may be allocated to a STACK_REGS. */ 2157169689Skan#endif 2158169689Skan}; 2159169689Skan 2160169689Skan 2161169689Skan/* Get basic block info. */ 2162169689Skan 2163169689Skanstruct df_urec_bb_info * 2164169689Skandf_urec_get_bb_info (struct dataflow *dflow, unsigned int index) 2165169689Skan{ 2166169689Skan return (struct df_urec_bb_info *) dflow->block_info[index]; 2167169689Skan} 2168169689Skan 2169169689Skan 2170169689Skan/* Set basic block info. */ 2171169689Skan 2172169689Skanstatic void 2173169689Skandf_urec_set_bb_info (struct dataflow *dflow, unsigned int index, 2174169689Skan struct df_urec_bb_info *bb_info) 2175169689Skan{ 2176169689Skan dflow->block_info[index] = bb_info; 2177169689Skan} 2178169689Skan 2179169689Skan 2180169689Skan/* Free basic block info. */ 2181169689Skan 2182169689Skanstatic void 2183169689Skandf_urec_free_bb_info (struct dataflow *dflow, 2184169689Skan basic_block bb ATTRIBUTE_UNUSED, 2185169689Skan void *vbb_info) 2186169689Skan{ 2187169689Skan struct df_urec_bb_info *bb_info = (struct df_urec_bb_info *) vbb_info; 2188169689Skan if (bb_info) 2189169689Skan { 2190169689Skan BITMAP_FREE (bb_info->gen); 2191169689Skan BITMAP_FREE (bb_info->kill); 2192169689Skan BITMAP_FREE (bb_info->in); 2193169689Skan BITMAP_FREE (bb_info->out); 2194169689Skan BITMAP_FREE (bb_info->earlyclobber); 2195169689Skan pool_free (dflow->block_pool, bb_info); 2196169689Skan } 2197169689Skan} 2198169689Skan 2199169689Skan 2200169689Skan/* Allocate or reset bitmaps for DFLOW blocks. The solution bits are 2201169689Skan not touched unless the block is new. */ 2202169689Skan 2203169689Skanstatic void 2204169689Skandf_urec_alloc (struct dataflow *dflow, bitmap blocks_to_rescan, 2205169689Skan bitmap all_blocks ATTRIBUTE_UNUSED) 2206169689Skan 2207169689Skan{ 2208169689Skan unsigned int bb_index; 2209169689Skan bitmap_iterator bi; 2210169689Skan struct df_urec_problem_data *problem_data 2211169689Skan = (struct df_urec_problem_data *) dflow->problem_data; 2212169689Skan 2213169689Skan if (!dflow->block_pool) 2214169689Skan dflow->block_pool = create_alloc_pool ("df_urec_block pool", 2215169689Skan sizeof (struct df_urec_bb_info), 50); 2216169689Skan 2217169689Skan if (!dflow->problem_data) 2218169689Skan { 2219169689Skan problem_data = XNEW (struct df_urec_problem_data); 2220169689Skan dflow->problem_data = problem_data; 2221169689Skan } 2222169689Skan problem_data->earlyclobbers_found = false; 2223169689Skan 2224169689Skan df_grow_bb_info (dflow); 2225169689Skan 2226169689Skan EXECUTE_IF_SET_IN_BITMAP (blocks_to_rescan, 0, bb_index, bi) 2227169689Skan { 2228169689Skan struct df_urec_bb_info *bb_info = df_urec_get_bb_info (dflow, bb_index); 2229169689Skan if (bb_info) 2230169689Skan { 2231169689Skan bitmap_clear (bb_info->kill); 2232169689Skan bitmap_clear (bb_info->gen); 2233169689Skan bitmap_clear (bb_info->earlyclobber); 2234169689Skan } 2235169689Skan else 2236169689Skan { 2237169689Skan bb_info = (struct df_urec_bb_info *) pool_alloc (dflow->block_pool); 2238169689Skan df_urec_set_bb_info (dflow, bb_index, bb_info); 2239169689Skan bb_info->kill = BITMAP_ALLOC (NULL); 2240169689Skan bb_info->gen = BITMAP_ALLOC (NULL); 2241169689Skan bb_info->in = BITMAP_ALLOC (NULL); 2242169689Skan bb_info->out = BITMAP_ALLOC (NULL); 2243169689Skan bb_info->earlyclobber = BITMAP_ALLOC (NULL); 2244169689Skan } 2245169689Skan } 2246169689Skan} 2247169689Skan 2248169689Skan 2249169689Skan/* The function modifies local info for register REG being changed in 2250169689Skan SETTER. DATA is used to pass the current basic block info. */ 2251169689Skan 2252169689Skanstatic void 2253169689Skandf_urec_mark_reg_change (rtx reg, rtx setter, void *data) 2254169689Skan{ 2255169689Skan int regno; 2256169689Skan int endregno; 2257169689Skan int i; 2258169689Skan struct df_urec_bb_info *bb_info = (struct df_urec_bb_info*) data; 2259169689Skan 2260169689Skan if (GET_CODE (reg) == SUBREG) 2261169689Skan reg = SUBREG_REG (reg); 2262169689Skan 2263169689Skan if (!REG_P (reg)) 2264169689Skan return; 2265169689Skan 2266169689Skan 2267169689Skan endregno = regno = REGNO (reg); 2268169689Skan if (regno < FIRST_PSEUDO_REGISTER) 2269169689Skan { 2270169689Skan endregno +=hard_regno_nregs[regno][GET_MODE (reg)]; 2271169689Skan 2272169689Skan for (i = regno; i < endregno; i++) 2273169689Skan { 2274169689Skan bitmap_set_bit (bb_info->kill, i); 2275169689Skan 2276169689Skan if (GET_CODE (setter) != CLOBBER) 2277169689Skan bitmap_set_bit (bb_info->gen, i); 2278169689Skan else 2279169689Skan bitmap_clear_bit (bb_info->gen, i); 2280169689Skan } 2281169689Skan } 2282169689Skan else 2283169689Skan { 2284169689Skan bitmap_set_bit (bb_info->kill, regno); 2285169689Skan 2286169689Skan if (GET_CODE (setter) != CLOBBER) 2287169689Skan bitmap_set_bit (bb_info->gen, regno); 2288169689Skan else 2289169689Skan bitmap_clear_bit (bb_info->gen, regno); 2290169689Skan } 2291169689Skan} 2292169689Skan/* Classes of registers which could be early clobbered in the current 2293169689Skan insn. */ 2294169689Skan 2295169689Skanstatic VEC(int,heap) *earlyclobber_regclass; 2296169689Skan 2297169689Skan/* This function finds and stores register classes that could be early 2298169689Skan clobbered in INSN. If any earlyclobber classes are found, the function 2299169689Skan returns TRUE, in all other cases it returns FALSE. */ 2300169689Skan 2301169689Skanstatic bool 2302169689Skandf_urec_check_earlyclobber (rtx insn) 2303169689Skan{ 2304169689Skan int opno; 2305169689Skan bool found = false; 2306169689Skan 2307169689Skan extract_insn (insn); 2308169689Skan 2309169689Skan VEC_truncate (int, earlyclobber_regclass, 0); 2310169689Skan for (opno = 0; opno < recog_data.n_operands; opno++) 2311169689Skan { 2312169689Skan char c; 2313169689Skan bool amp_p; 2314169689Skan int i; 2315169689Skan enum reg_class class; 2316169689Skan const char *p = recog_data.constraints[opno]; 2317169689Skan 2318169689Skan class = NO_REGS; 2319169689Skan amp_p = false; 2320169689Skan for (;;) 2321169689Skan { 2322169689Skan c = *p; 2323169689Skan switch (c) 2324169689Skan { 2325169689Skan case '=': case '+': case '?': 2326169689Skan case '#': case '!': 2327169689Skan case '*': case '%': 2328169689Skan case 'm': case '<': case '>': case 'V': case 'o': 2329169689Skan case 'E': case 'F': case 'G': case 'H': 2330169689Skan case 's': case 'i': case 'n': 2331169689Skan case 'I': case 'J': case 'K': case 'L': 2332169689Skan case 'M': case 'N': case 'O': case 'P': 2333169689Skan case 'X': 2334169689Skan case '0': case '1': case '2': case '3': case '4': 2335169689Skan case '5': case '6': case '7': case '8': case '9': 2336169689Skan /* These don't say anything we care about. */ 2337169689Skan break; 2338169689Skan 2339169689Skan case '&': 2340169689Skan amp_p = true; 2341169689Skan break; 2342169689Skan case '\0': 2343169689Skan case ',': 2344169689Skan if (amp_p && class != NO_REGS) 2345169689Skan { 2346169689Skan int rc; 2347169689Skan 2348169689Skan found = true; 2349169689Skan for (i = 0; 2350169689Skan VEC_iterate (int, earlyclobber_regclass, i, rc); 2351169689Skan i++) 2352169689Skan { 2353169689Skan if (rc == (int) class) 2354169689Skan goto found_rc; 2355169689Skan } 2356169689Skan 2357169689Skan /* We use VEC_quick_push here because 2358169689Skan earlyclobber_regclass holds no more than 2359169689Skan N_REG_CLASSES elements. */ 2360169689Skan VEC_quick_push (int, earlyclobber_regclass, (int) class); 2361169689Skan found_rc: 2362169689Skan ; 2363169689Skan } 2364169689Skan 2365169689Skan amp_p = false; 2366169689Skan class = NO_REGS; 2367169689Skan break; 2368169689Skan 2369169689Skan case 'r': 2370169689Skan class = GENERAL_REGS; 2371169689Skan break; 2372169689Skan 2373169689Skan default: 2374169689Skan class = REG_CLASS_FROM_CONSTRAINT (c, p); 2375169689Skan break; 2376169689Skan } 2377169689Skan if (c == '\0') 2378169689Skan break; 2379169689Skan p += CONSTRAINT_LEN (c, p); 2380169689Skan } 2381169689Skan } 2382169689Skan 2383169689Skan return found; 2384169689Skan} 2385169689Skan 2386169689Skan/* The function checks that pseudo-register *X has a class 2387169689Skan intersecting with the class of pseudo-register could be early 2388169689Skan clobbered in the same insn. 2389169689Skan 2390169689Skan This function is a no-op if earlyclobber_regclass is empty. 2391169689Skan 2392169689Skan Reload can assign the same hard register to uninitialized 2393169689Skan pseudo-register and early clobbered pseudo-register in an insn if 2394169689Skan the pseudo-register is used first time in given BB and not lived at 2395169689Skan the BB start. To prevent this we don't change life information for 2396169689Skan such pseudo-registers. */ 2397169689Skan 2398169689Skanstatic int 2399169689Skandf_urec_mark_reg_use_for_earlyclobber (rtx *x, void *data) 2400169689Skan{ 2401169689Skan enum reg_class pref_class, alt_class; 2402169689Skan int i, regno; 2403169689Skan struct df_urec_bb_info *bb_info = (struct df_urec_bb_info*) data; 2404169689Skan 2405169689Skan if (REG_P (*x) && REGNO (*x) >= FIRST_PSEUDO_REGISTER) 2406169689Skan { 2407169689Skan int rc; 2408169689Skan 2409169689Skan regno = REGNO (*x); 2410169689Skan if (bitmap_bit_p (bb_info->kill, regno) 2411169689Skan || bitmap_bit_p (bb_info->gen, regno)) 2412169689Skan return 0; 2413169689Skan pref_class = reg_preferred_class (regno); 2414169689Skan alt_class = reg_alternate_class (regno); 2415169689Skan for (i = 0; VEC_iterate (int, earlyclobber_regclass, i, rc); i++) 2416169689Skan { 2417169689Skan if (reg_classes_intersect_p (rc, pref_class) 2418169689Skan || (rc != NO_REGS 2419169689Skan && reg_classes_intersect_p (rc, alt_class))) 2420169689Skan { 2421169689Skan bitmap_set_bit (bb_info->earlyclobber, regno); 2422169689Skan break; 2423169689Skan } 2424169689Skan } 2425169689Skan } 2426169689Skan return 0; 2427169689Skan} 2428169689Skan 2429169689Skan/* The function processes all pseudo-registers in *X with the aid of 2430169689Skan previous function. */ 2431169689Skan 2432169689Skanstatic void 2433169689Skandf_urec_mark_reg_use_for_earlyclobber_1 (rtx *x, void *data) 2434169689Skan{ 2435169689Skan for_each_rtx (x, df_urec_mark_reg_use_for_earlyclobber, data); 2436169689Skan} 2437169689Skan 2438169689Skan 2439169689Skan/* Compute local uninitialized register info for basic block BB. */ 2440169689Skan 2441169689Skanstatic void 2442169689Skandf_urec_bb_local_compute (struct dataflow *dflow, unsigned int bb_index) 2443169689Skan{ 2444169689Skan struct df *df = dflow->df; 2445169689Skan basic_block bb = BASIC_BLOCK (bb_index); 2446169689Skan struct df_urec_bb_info *bb_info = df_urec_get_bb_info (dflow, bb_index); 2447169689Skan rtx insn; 2448169689Skan struct df_ref *def; 2449169689Skan 2450169689Skan for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref) 2451169689Skan if (DF_REF_FLAGS (def) & DF_REF_AT_TOP) 2452169689Skan { 2453169689Skan unsigned int regno = DF_REF_REGNO (def); 2454169689Skan bitmap_set_bit (bb_info->gen, regno); 2455169689Skan } 2456169689Skan 2457169689Skan FOR_BB_INSNS (bb, insn) 2458169689Skan { 2459169689Skan if (INSN_P (insn)) 2460169689Skan { 2461169689Skan note_stores (PATTERN (insn), df_urec_mark_reg_change, bb_info); 2462169689Skan if (df_urec_check_earlyclobber (insn)) 2463169689Skan { 2464169689Skan struct df_urec_problem_data *problem_data 2465169689Skan = (struct df_urec_problem_data *) dflow->problem_data; 2466169689Skan problem_data->earlyclobbers_found = true; 2467169689Skan note_uses (&PATTERN (insn), 2468169689Skan df_urec_mark_reg_use_for_earlyclobber_1, bb_info); 2469169689Skan } 2470169689Skan } 2471169689Skan } 2472169689Skan 2473169689Skan for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref) 2474169689Skan if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0) 2475169689Skan { 2476169689Skan unsigned int regno = DF_REF_REGNO (def); 2477169689Skan bitmap_set_bit (bb_info->gen, regno); 2478169689Skan } 2479169689Skan 2480169689Skan} 2481169689Skan 2482169689Skan 2483169689Skan/* Compute local uninitialized register info. */ 2484169689Skan 2485169689Skanstatic void 2486169689Skandf_urec_local_compute (struct dataflow *dflow, 2487169689Skan bitmap all_blocks ATTRIBUTE_UNUSED, 2488169689Skan bitmap rescan_blocks) 2489169689Skan{ 2490169689Skan unsigned int bb_index; 2491169689Skan bitmap_iterator bi; 2492169689Skan#ifdef STACK_REGS 2493169689Skan int i; 2494169689Skan HARD_REG_SET zero, stack_hard_regs, used; 2495169689Skan struct df_urec_problem_data *problem_data 2496169689Skan = (struct df_urec_problem_data *) dflow->problem_data; 2497169689Skan 2498169689Skan /* Any register that MAY be allocated to a register stack (like the 2499169689Skan 387) is treated poorly. Each such register is marked as being 2500169689Skan live everywhere. This keeps the register allocator and the 2501169689Skan subsequent passes from doing anything useful with these values. 2502169689Skan 2503169689Skan FIXME: This seems like an incredibly poor idea. */ 2504169689Skan 2505169689Skan CLEAR_HARD_REG_SET (zero); 2506169689Skan CLEAR_HARD_REG_SET (stack_hard_regs); 2507169689Skan for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++) 2508169689Skan SET_HARD_REG_BIT (stack_hard_regs, i); 2509169689Skan problem_data->stack_regs = BITMAP_ALLOC (NULL); 2510169689Skan for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) 2511169689Skan { 2512169689Skan COPY_HARD_REG_SET (used, reg_class_contents[reg_preferred_class (i)]); 2513169689Skan IOR_HARD_REG_SET (used, reg_class_contents[reg_alternate_class (i)]); 2514169689Skan AND_HARD_REG_SET (used, stack_hard_regs); 2515169689Skan GO_IF_HARD_REG_EQUAL (used, zero, skip); 2516169689Skan bitmap_set_bit (problem_data->stack_regs, i); 2517169689Skan skip: 2518169689Skan ; 2519169689Skan } 2520169689Skan#endif 2521169689Skan 2522169689Skan /* We know that earlyclobber_regclass holds no more than 2523169689Skan N_REG_CLASSES elements. See df_urec_check_earlyclobber. */ 2524169689Skan earlyclobber_regclass = VEC_alloc (int, heap, N_REG_CLASSES); 2525169689Skan 2526169689Skan EXECUTE_IF_SET_IN_BITMAP (rescan_blocks, 0, bb_index, bi) 2527169689Skan { 2528169689Skan df_urec_bb_local_compute (dflow, bb_index); 2529169689Skan } 2530169689Skan 2531169689Skan VEC_free (int, heap, earlyclobber_regclass); 2532169689Skan} 2533169689Skan 2534169689Skan 2535169689Skan/* Initialize the solution vectors. */ 2536169689Skan 2537169689Skanstatic void 2538169689Skandf_urec_init (struct dataflow *dflow, bitmap all_blocks) 2539169689Skan{ 2540169689Skan unsigned int bb_index; 2541169689Skan bitmap_iterator bi; 2542169689Skan 2543169689Skan EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) 2544169689Skan { 2545169689Skan struct df_urec_bb_info *bb_info = df_urec_get_bb_info (dflow, bb_index); 2546169689Skan 2547169689Skan bitmap_copy (bb_info->out, bb_info->gen); 2548169689Skan bitmap_clear (bb_info->in); 2549169689Skan } 2550169689Skan} 2551169689Skan 2552169689Skan 2553169689Skan/* Or in the stack regs, hard regs and early clobber regs into the the 2554169689Skan ur_in sets of all of the blocks. */ 2555169689Skan 2556169689Skanstatic void 2557169689Skandf_urec_local_finalize (struct dataflow *dflow, bitmap all_blocks) 2558169689Skan{ 2559169689Skan struct df *df = dflow->df; 2560169689Skan struct dataflow *lr_dflow = df->problems_by_index[DF_LR]; 2561169689Skan bitmap tmp = BITMAP_ALLOC (NULL); 2562169689Skan bitmap_iterator bi; 2563169689Skan unsigned int bb_index; 2564169689Skan struct df_urec_problem_data *problem_data 2565169689Skan = (struct df_urec_problem_data *) dflow->problem_data; 2566169689Skan 2567169689Skan EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) 2568169689Skan { 2569169689Skan struct df_urec_bb_info *bb_info = df_urec_get_bb_info (dflow, bb_index); 2570169689Skan struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (lr_dflow, bb_index); 2571169689Skan 2572169689Skan if (bb_index != ENTRY_BLOCK && bb_index != EXIT_BLOCK) 2573169689Skan { 2574169689Skan if (problem_data->earlyclobbers_found) 2575169689Skan bitmap_ior_into (bb_info->in, bb_info->earlyclobber); 2576169689Skan 2577169689Skan#ifdef STACK_REGS 2578169689Skan /* We can not use the same stack register for uninitialized 2579169689Skan pseudo-register and another living pseudo-register 2580169689Skan because if the uninitialized pseudo-register dies, 2581169689Skan subsequent pass reg-stack will be confused (it will 2582169689Skan believe that the other register dies). */ 2583169689Skan bitmap_ior_into (bb_info->in, problem_data->stack_regs); 2584169689Skan bitmap_ior_into (bb_info->out, problem_data->stack_regs); 2585169689Skan#endif 2586169689Skan } 2587169689Skan 2588169689Skan /* No register may reach a location where it is not used. Thus 2589169689Skan we trim the rr result to the places where it is used. */ 2590169689Skan bitmap_and_into (bb_info->in, bb_lr_info->in); 2591169689Skan bitmap_and_into (bb_info->out, bb_lr_info->out); 2592169689Skan 2593169689Skan#if 1 2594169689Skan /* Hard registers may still stick in the ur_out set, but not 2595169689Skan be in the ur_in set, if their only mention was in a call 2596169689Skan in this block. This is because a call kills in the lr 2597169689Skan problem but does not kill in the rr problem. To clean 2598169689Skan this up, we execute the transfer function on the lr_in 2599169689Skan set and then use that to knock bits out of ur_out. */ 2600169689Skan bitmap_ior_and_compl (tmp, bb_info->gen, bb_lr_info->in, 2601169689Skan bb_info->kill); 2602169689Skan bitmap_and_into (bb_info->out, tmp); 2603169689Skan#endif 2604169689Skan } 2605169689Skan 2606169689Skan#ifdef STACK_REGS 2607169689Skan BITMAP_FREE (problem_data->stack_regs); 2608169689Skan#endif 2609169689Skan BITMAP_FREE (tmp); 2610169689Skan} 2611169689Skan 2612169689Skan 2613169689Skan/* Confluence function that ignores fake edges. */ 2614169689Skan 2615169689Skanstatic void 2616169689Skandf_urec_confluence_n (struct dataflow *dflow, edge e) 2617169689Skan{ 2618169689Skan bitmap op1 = df_urec_get_bb_info (dflow, e->dest->index)->in; 2619169689Skan bitmap op2 = df_urec_get_bb_info (dflow, e->src->index)->out; 2620169689Skan 2621169689Skan if (e->flags & EDGE_FAKE) 2622169689Skan return; 2623169689Skan 2624169689Skan bitmap_ior_into (op1, op2); 2625169689Skan} 2626169689Skan 2627169689Skan 2628169689Skan/* Transfer function. */ 2629169689Skan 2630169689Skanstatic bool 2631169689Skandf_urec_transfer_function (struct dataflow *dflow, int bb_index) 2632169689Skan{ 2633169689Skan struct df_urec_bb_info *bb_info = df_urec_get_bb_info (dflow, bb_index); 2634169689Skan bitmap in = bb_info->in; 2635169689Skan bitmap out = bb_info->out; 2636169689Skan bitmap gen = bb_info->gen; 2637169689Skan bitmap kill = bb_info->kill; 2638169689Skan 2639169689Skan return bitmap_ior_and_compl (out, gen, in, kill); 2640169689Skan} 2641169689Skan 2642169689Skan 2643169689Skan/* Free all storage associated with the problem. */ 2644169689Skan 2645169689Skanstatic void 2646169689Skandf_urec_free (struct dataflow *dflow) 2647169689Skan{ 2648169689Skan if (dflow->block_info) 2649169689Skan { 2650169689Skan unsigned int i; 2651169689Skan 2652169689Skan for (i = 0; i < dflow->block_info_size; i++) 2653169689Skan { 2654169689Skan struct df_urec_bb_info *bb_info = df_urec_get_bb_info (dflow, i); 2655169689Skan if (bb_info) 2656169689Skan { 2657169689Skan BITMAP_FREE (bb_info->gen); 2658169689Skan BITMAP_FREE (bb_info->kill); 2659169689Skan BITMAP_FREE (bb_info->in); 2660169689Skan BITMAP_FREE (bb_info->out); 2661169689Skan BITMAP_FREE (bb_info->earlyclobber); 2662169689Skan } 2663169689Skan } 2664169689Skan 2665169689Skan free_alloc_pool (dflow->block_pool); 2666169689Skan 2667169689Skan dflow->block_info_size = 0; 2668169689Skan free (dflow->block_info); 2669169689Skan free (dflow->problem_data); 2670169689Skan } 2671169689Skan free (dflow); 2672169689Skan} 2673169689Skan 2674169689Skan 2675169689Skan/* Debugging info. */ 2676169689Skan 2677169689Skanstatic void 2678169689Skandf_urec_dump (struct dataflow *dflow, FILE *file) 2679169689Skan{ 2680169689Skan basic_block bb; 2681169689Skan 2682169689Skan if (!dflow->block_info) 2683169689Skan return; 2684169689Skan 2685169689Skan fprintf (file, "Undefined regs:\n"); 2686169689Skan 2687169689Skan FOR_ALL_BB (bb) 2688169689Skan { 2689169689Skan struct df_urec_bb_info *bb_info = df_urec_get_bb_info (dflow, bb->index); 2690169689Skan df_print_bb_index (bb, file); 2691169689Skan 2692169689Skan if (!bb_info->in) 2693169689Skan continue; 2694169689Skan 2695169689Skan fprintf (file, " in \t"); 2696169689Skan dump_bitmap (file, bb_info->in); 2697169689Skan fprintf (file, " gen \t"); 2698169689Skan dump_bitmap (file, bb_info->gen); 2699169689Skan fprintf (file, " kill\t"); 2700169689Skan dump_bitmap (file, bb_info->kill); 2701169689Skan fprintf (file, " ec\t"); 2702169689Skan dump_bitmap (file, bb_info->earlyclobber); 2703169689Skan fprintf (file, " out \t"); 2704169689Skan dump_bitmap (file, bb_info->out); 2705169689Skan } 2706169689Skan} 2707169689Skan 2708169689Skan/* All of the information associated with every instance of the problem. */ 2709169689Skan 2710169689Skanstatic struct df_problem problem_UREC = 2711169689Skan{ 2712169689Skan DF_UREC, /* Problem id. */ 2713169689Skan DF_FORWARD, /* Direction. */ 2714169689Skan df_urec_alloc, /* Allocate the problem specific data. */ 2715169689Skan NULL, /* Reset global information. */ 2716169689Skan df_urec_free_bb_info, /* Free basic block info. */ 2717169689Skan df_urec_local_compute, /* Local compute function. */ 2718169689Skan df_urec_init, /* Init the solution specific data. */ 2719169689Skan df_iterative_dataflow, /* Iterative solver. */ 2720169689Skan NULL, /* Confluence operator 0. */ 2721169689Skan df_urec_confluence_n, /* Confluence operator n. */ 2722169689Skan df_urec_transfer_function, /* Transfer function. */ 2723169689Skan df_urec_local_finalize, /* Finalize function. */ 2724169689Skan df_urec_free, /* Free all of the problem information. */ 2725169689Skan df_urec_dump, /* Debugging. */ 2726169689Skan df_lr_add_problem, /* Dependent problem. */ 2727169689Skan 0 /* Changeable flags. */ 2728169689Skan}; 2729169689Skan 2730169689Skan 2731169689Skan/* Create a new DATAFLOW instance and add it to an existing instance 2732169689Skan of DF. The returned structure is what is used to get at the 2733169689Skan solution. */ 2734169689Skan 2735169689Skanstruct dataflow * 2736169689Skandf_urec_add_problem (struct df *df, int flags) 2737169689Skan{ 2738169689Skan return df_add_problem (df, &problem_UREC, flags); 2739169689Skan} 2740169689Skan 2741169689Skan 2742169689Skan 2743169689Skan/*---------------------------------------------------------------------------- 2744169689Skan CREATE DEF_USE (DU) and / or USE_DEF (UD) CHAINS 2745169689Skan 2746169689Skan Link either the defs to the uses and / or the uses to the defs. 2747169689Skan 2748169689Skan These problems are set up like the other dataflow problems so that 2749169689Skan they nicely fit into the framework. They are much simpler and only 2750169689Skan involve a single traversal of instructions and an examination of 2751169689Skan the reaching defs information (the dependent problem). 2752169689Skan----------------------------------------------------------------------------*/ 2753169689Skan 2754169689Skan/* Create def-use or use-def chains. */ 2755169689Skan 2756169689Skanstatic void 2757169689Skandf_chain_alloc (struct dataflow *dflow, 2758169689Skan bitmap blocks_to_rescan ATTRIBUTE_UNUSED, 2759169689Skan bitmap all_blocks ATTRIBUTE_UNUSED) 2760169689Skan 2761169689Skan{ 2762169689Skan struct df *df = dflow->df; 2763169689Skan unsigned int i; 2764169689Skan 2765169689Skan /* Wholesale destruction of the old chains. */ 2766169689Skan if (dflow->block_pool) 2767169689Skan free_alloc_pool (dflow->block_pool); 2768169689Skan 2769169689Skan dflow->block_pool = create_alloc_pool ("df_chain_chain_block pool", 2770169689Skan sizeof (struct df_link), 100); 2771169689Skan 2772169689Skan if (dflow->flags & DF_DU_CHAIN) 2773169689Skan { 2774169689Skan if (!df->def_info.refs_organized) 2775169689Skan df_reorganize_refs (&df->def_info); 2776169689Skan 2777169689Skan /* Clear out the pointers from the refs. */ 2778169689Skan for (i = 0; i < DF_DEFS_SIZE (df); i++) 2779169689Skan { 2780169689Skan struct df_ref *ref = df->def_info.refs[i]; 2781169689Skan DF_REF_CHAIN (ref) = NULL; 2782169689Skan } 2783169689Skan } 2784169689Skan 2785169689Skan if (dflow->flags & DF_UD_CHAIN) 2786169689Skan { 2787169689Skan if (!df->use_info.refs_organized) 2788169689Skan df_reorganize_refs (&df->use_info); 2789169689Skan for (i = 0; i < DF_USES_SIZE (df); i++) 2790169689Skan { 2791169689Skan struct df_ref *ref = df->use_info.refs[i]; 2792169689Skan DF_REF_CHAIN (ref) = NULL; 2793169689Skan } 2794169689Skan } 2795169689Skan} 2796169689Skan 2797169689Skan 2798169689Skan/* Reset all def_use and use_def chains in INSN. */ 2799169689Skan 2800169689Skanstatic void 2801169689Skandf_chain_insn_reset (struct dataflow *dflow, rtx insn) 2802169689Skan{ 2803169689Skan struct df *df = dflow->df; 2804169689Skan unsigned int uid = INSN_UID (insn); 2805169689Skan struct df_insn_info *insn_info = NULL; 2806169689Skan struct df_ref *ref; 2807169689Skan 2808169689Skan if (uid < df->insns_size) 2809169689Skan insn_info = DF_INSN_UID_GET (df, uid); 2810169689Skan 2811169689Skan if (insn_info) 2812169689Skan { 2813169689Skan if (dflow->flags & DF_DU_CHAIN) 2814169689Skan { 2815169689Skan ref = insn_info->defs; 2816169689Skan while (ref) 2817169689Skan { 2818169689Skan ref->chain = NULL; 2819169689Skan ref = ref->next_ref; 2820169689Skan } 2821169689Skan } 2822169689Skan 2823169689Skan if (dflow->flags & DF_UD_CHAIN) 2824169689Skan { 2825169689Skan ref = insn_info->uses; 2826169689Skan while (ref) 2827169689Skan { 2828169689Skan ref->chain = NULL; 2829169689Skan ref = ref->next_ref; 2830169689Skan } 2831169689Skan } 2832169689Skan } 2833169689Skan} 2834169689Skan 2835169689Skan 2836169689Skan/* Reset all def_use and use_def chains in basic block. */ 2837169689Skan 2838169689Skanstatic void 2839169689Skandf_chain_bb_reset (struct dataflow *dflow, unsigned int bb_index) 2840169689Skan{ 2841169689Skan struct df *df = dflow->df; 2842169689Skan rtx insn; 2843169689Skan basic_block bb = BASIC_BLOCK (bb_index); 2844169689Skan 2845169689Skan /* Some one deleted the basic block out from under us. */ 2846169689Skan if (!bb) 2847169689Skan return; 2848169689Skan 2849169689Skan FOR_BB_INSNS (bb, insn) 2850169689Skan { 2851169689Skan if (INSN_P (insn)) 2852169689Skan { 2853169689Skan /* Record defs within INSN. */ 2854169689Skan df_chain_insn_reset (dflow, insn); 2855169689Skan } 2856169689Skan } 2857169689Skan 2858169689Skan /* Get rid of any chains in artificial uses or defs. */ 2859169689Skan if (dflow->flags & DF_DU_CHAIN) 2860169689Skan { 2861169689Skan struct df_ref *def; 2862169689Skan def = df_get_artificial_defs (df, bb_index); 2863169689Skan while (def) 2864169689Skan { 2865169689Skan def->chain = NULL; 2866169689Skan def = def->next_ref; 2867169689Skan } 2868169689Skan } 2869169689Skan 2870169689Skan if (dflow->flags & DF_UD_CHAIN) 2871169689Skan { 2872169689Skan struct df_ref *use; 2873169689Skan use = df_get_artificial_uses (df, bb_index); 2874169689Skan while (use) 2875169689Skan { 2876169689Skan use->chain = NULL; 2877169689Skan use = use->next_ref; 2878169689Skan } 2879169689Skan } 2880169689Skan} 2881169689Skan 2882169689Skan 2883169689Skan/* Reset all of the chains when the set of basic blocks changes. */ 2884169689Skan 2885169689Skan 2886169689Skanstatic void 2887169689Skandf_chain_reset (struct dataflow *dflow, bitmap blocks_to_clear) 2888169689Skan{ 2889169689Skan bitmap_iterator bi; 2890169689Skan unsigned int bb_index; 2891169689Skan 2892169689Skan EXECUTE_IF_SET_IN_BITMAP (blocks_to_clear, 0, bb_index, bi) 2893169689Skan { 2894169689Skan df_chain_bb_reset (dflow, bb_index); 2895169689Skan } 2896169689Skan 2897169689Skan free_alloc_pool (dflow->block_pool); 2898169689Skan dflow->block_pool = NULL; 2899169689Skan} 2900169689Skan 2901169689Skan 2902169689Skan/* Create the chains for a list of USEs. */ 2903169689Skan 2904169689Skanstatic void 2905169689Skandf_chain_create_bb_process_use (struct dataflow *dflow, 2906169689Skan bitmap local_rd, 2907169689Skan struct df_ref *use, 2908169689Skan enum df_ref_flags top_flag) 2909169689Skan{ 2910169689Skan struct df *df = dflow->df; 2911169689Skan bitmap_iterator bi; 2912169689Skan unsigned int def_index; 2913169689Skan 2914169689Skan while (use) 2915169689Skan { 2916169689Skan /* Do not want to go through this for an uninitialized var. */ 2917169689Skan unsigned int uregno = DF_REF_REGNO (use); 2918169689Skan int count = DF_REG_DEF_GET (df, uregno)->n_refs; 2919169689Skan if (count) 2920169689Skan { 2921169689Skan if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP)) 2922169689Skan { 2923169689Skan unsigned int first_index = DF_REG_DEF_GET (df, uregno)->begin; 2924169689Skan unsigned int last_index = first_index + count - 1; 2925169689Skan 2926169689Skan EXECUTE_IF_SET_IN_BITMAP (local_rd, first_index, def_index, bi) 2927169689Skan { 2928169689Skan struct df_ref *def; 2929169689Skan if (def_index > last_index) 2930169689Skan break; 2931169689Skan 2932169689Skan def = DF_DEFS_GET (df, def_index); 2933169689Skan if (dflow->flags & DF_DU_CHAIN) 2934169689Skan df_chain_create (dflow, def, use); 2935169689Skan if (dflow->flags & DF_UD_CHAIN) 2936169689Skan df_chain_create (dflow, use, def); 2937169689Skan } 2938169689Skan } 2939169689Skan } 2940169689Skan use = use->next_ref; 2941169689Skan } 2942169689Skan} 2943169689Skan 2944169689Skan/* Reset the storage pool that the def-use or use-def chains have been 2945169689Skan allocated in. We do not need to re adjust the pointers in the refs, 2946169689Skan these have already been clean out.*/ 2947169689Skan 2948169689Skan/* Create chains from reaching defs bitmaps for basic block BB. */ 2949169689Skanstatic void 2950169689Skandf_chain_create_bb (struct dataflow *dflow, 2951169689Skan struct dataflow *rd_dflow, 2952169689Skan unsigned int bb_index) 2953169689Skan{ 2954169689Skan basic_block bb = BASIC_BLOCK (bb_index); 2955169689Skan struct df_rd_bb_info *bb_info = df_rd_get_bb_info (rd_dflow, bb_index); 2956169689Skan rtx insn; 2957169689Skan bitmap cpy = BITMAP_ALLOC (NULL); 2958169689Skan struct df *df = dflow->df; 2959169689Skan struct df_ref *def; 2960169689Skan 2961169689Skan bitmap_copy (cpy, bb_info->in); 2962169689Skan 2963169689Skan /* Since we are going forwards, process the artificial uses first 2964169689Skan then the artificial defs second. */ 2965169689Skan 2966169689Skan#ifdef EH_USES 2967169689Skan /* Create the chains for the artificial uses from the EH_USES at the 2968169689Skan beginning of the block. */ 2969169689Skan df_chain_create_bb_process_use (dflow, cpy, 2970169689Skan df_get_artificial_uses (df, bb->index), 2971169689Skan DF_REF_AT_TOP); 2972169689Skan#endif 2973169689Skan 2974169689Skan for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref) 2975169689Skan if (DF_REF_FLAGS (def) & DF_REF_AT_TOP) 2976169689Skan { 2977169689Skan unsigned int dregno = DF_REF_REGNO (def); 2978169689Skan if (!(DF_REF_FLAGS (def) & DF_REF_PARTIAL)) 2979169689Skan bitmap_clear_range (cpy, 2980169689Skan DF_REG_DEF_GET (df, dregno)->begin, 2981169689Skan DF_REG_DEF_GET (df, dregno)->n_refs); 2982169689Skan bitmap_set_bit (cpy, DF_REF_ID (def)); 2983169689Skan } 2984169689Skan 2985169689Skan /* Process the regular instructions next. */ 2986169689Skan FOR_BB_INSNS (bb, insn) 2987169689Skan { 2988169689Skan struct df_ref *def; 2989169689Skan unsigned int uid = INSN_UID (insn); 2990169689Skan 2991169689Skan if (!INSN_P (insn)) 2992169689Skan continue; 2993169689Skan 2994169689Skan /* Now scan the uses and link them up with the defs that remain 2995169689Skan in the cpy vector. */ 2996169689Skan 2997169689Skan df_chain_create_bb_process_use (dflow, cpy, 2998169689Skan DF_INSN_UID_USES (df, uid), 0); 2999169689Skan 3000169689Skan /* Since we are going forwards, process the defs second. This 3001169689Skan pass only changes the bits in cpy. */ 3002169689Skan for (def = DF_INSN_UID_DEFS (df, uid); def; def = def->next_ref) 3003169689Skan { 3004169689Skan unsigned int dregno = DF_REF_REGNO (def); 3005169689Skan if (!(DF_REF_FLAGS (def) & DF_REF_PARTIAL)) 3006169689Skan bitmap_clear_range (cpy, 3007169689Skan DF_REG_DEF_GET (df, dregno)->begin, 3008169689Skan DF_REG_DEF_GET (df, dregno)->n_refs); 3009169689Skan if (!(DF_REF_FLAGS (def) 3010169689Skan & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))) 3011169689Skan bitmap_set_bit (cpy, DF_REF_ID (def)); 3012169689Skan } 3013169689Skan } 3014169689Skan 3015169689Skan /* Create the chains for the artificial uses of the hard registers 3016169689Skan at the end of the block. */ 3017169689Skan df_chain_create_bb_process_use (dflow, cpy, 3018169689Skan df_get_artificial_uses (df, bb->index), 0); 3019169689Skan} 3020169689Skan 3021169689Skan/* Create def-use chains from reaching use bitmaps for basic blocks 3022169689Skan in BLOCKS. */ 3023169689Skan 3024169689Skanstatic void 3025169689Skandf_chain_finalize (struct dataflow *dflow, bitmap all_blocks) 3026169689Skan{ 3027169689Skan unsigned int bb_index; 3028169689Skan bitmap_iterator bi; 3029169689Skan struct df *df = dflow->df; 3030169689Skan struct dataflow *rd_dflow = df->problems_by_index [DF_RD]; 3031169689Skan 3032169689Skan EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) 3033169689Skan { 3034169689Skan df_chain_create_bb (dflow, rd_dflow, bb_index); 3035169689Skan } 3036169689Skan} 3037169689Skan 3038169689Skan 3039169689Skan/* Free all storage associated with the problem. */ 3040169689Skan 3041169689Skanstatic void 3042169689Skandf_chain_free (struct dataflow *dflow) 3043169689Skan{ 3044169689Skan free_alloc_pool (dflow->block_pool); 3045169689Skan free (dflow); 3046169689Skan} 3047169689Skan 3048169689Skan 3049169689Skan/* Debugging info. */ 3050169689Skan 3051169689Skanstatic void 3052169689Skandf_chains_dump (struct dataflow *dflow, FILE *file) 3053169689Skan{ 3054169689Skan struct df *df = dflow->df; 3055169689Skan unsigned int j; 3056169689Skan 3057169689Skan if (dflow->flags & DF_DU_CHAIN) 3058169689Skan { 3059169689Skan fprintf (file, "Def-use chains:\n"); 3060169689Skan for (j = 0; j < df->def_info.bitmap_size; j++) 3061169689Skan { 3062169689Skan struct df_ref *def = DF_DEFS_GET (df, j); 3063169689Skan if (def) 3064169689Skan { 3065169689Skan fprintf (file, "d%d bb %d luid %d insn %d reg %d ", 3066169689Skan j, DF_REF_BBNO (def), 3067169689Skan DF_REF_INSN (def) ? 3068169689Skan DF_INSN_LUID (df, DF_REF_INSN (def)): 3069169689Skan -1, 3070169689Skan DF_REF_INSN (def) ? DF_REF_INSN_UID (def) : -1, 3071169689Skan DF_REF_REGNO (def)); 3072169689Skan if (def->flags & DF_REF_READ_WRITE) 3073169689Skan fprintf (file, "read/write "); 3074169689Skan df_chain_dump (DF_REF_CHAIN (def), file); 3075169689Skan fprintf (file, "\n"); 3076169689Skan } 3077169689Skan } 3078169689Skan } 3079169689Skan 3080169689Skan if (dflow->flags & DF_UD_CHAIN) 3081169689Skan { 3082169689Skan fprintf (file, "Use-def chains:\n"); 3083169689Skan for (j = 0; j < df->use_info.bitmap_size; j++) 3084169689Skan { 3085169689Skan struct df_ref *use = DF_USES_GET (df, j); 3086169689Skan if (use) 3087169689Skan { 3088169689Skan fprintf (file, "u%d bb %d luid %d insn %d reg %d ", 3089169689Skan j, DF_REF_BBNO (use), 3090169689Skan DF_REF_INSN (use) ? 3091169689Skan DF_INSN_LUID (df, DF_REF_INSN (use)) 3092169689Skan : -1, 3093169689Skan DF_REF_INSN (DF_USES_GET (df, j)) ? 3094169689Skan DF_REF_INSN_UID (DF_USES_GET (df,j)) 3095169689Skan : -1, 3096169689Skan DF_REF_REGNO (use)); 3097169689Skan if (use->flags & DF_REF_READ_WRITE) 3098169689Skan fprintf (file, "read/write "); 3099169689Skan if (use->flags & DF_REF_STRIPPED) 3100169689Skan fprintf (file, "stripped "); 3101169689Skan if (use->flags & DF_REF_IN_NOTE) 3102169689Skan fprintf (file, "note "); 3103169689Skan df_chain_dump (DF_REF_CHAIN (use), file); 3104169689Skan fprintf (file, "\n"); 3105169689Skan } 3106169689Skan } 3107169689Skan } 3108169689Skan} 3109169689Skan 3110169689Skan 3111169689Skanstatic struct df_problem problem_CHAIN = 3112169689Skan{ 3113169689Skan DF_CHAIN, /* Problem id. */ 3114169689Skan DF_NONE, /* Direction. */ 3115169689Skan df_chain_alloc, /* Allocate the problem specific data. */ 3116169689Skan df_chain_reset, /* Reset global information. */ 3117169689Skan NULL, /* Free basic block info. */ 3118169689Skan NULL, /* Local compute function. */ 3119169689Skan NULL, /* Init the solution specific data. */ 3120169689Skan NULL, /* Iterative solver. */ 3121169689Skan NULL, /* Confluence operator 0. */ 3122169689Skan NULL, /* Confluence operator n. */ 3123169689Skan NULL, /* Transfer function. */ 3124169689Skan df_chain_finalize, /* Finalize function. */ 3125169689Skan df_chain_free, /* Free all of the problem information. */ 3126169689Skan df_chains_dump, /* Debugging. */ 3127169689Skan df_rd_add_problem, /* Dependent problem. */ 3128169689Skan 0 /* Changeable flags. */ 3129169689Skan}; 3130169689Skan 3131169689Skan 3132169689Skan/* Create a new DATAFLOW instance and add it to an existing instance 3133169689Skan of DF. The returned structure is what is used to get at the 3134169689Skan solution. */ 3135169689Skan 3136169689Skanstruct dataflow * 3137169689Skandf_chain_add_problem (struct df *df, int flags) 3138169689Skan{ 3139169689Skan return df_add_problem (df, &problem_CHAIN, flags); 3140169689Skan} 3141169689Skan 3142169689Skan 3143169689Skan/*---------------------------------------------------------------------------- 3144169689Skan REGISTER INFORMATION 3145169689Skan 3146169689Skan This pass properly computes REG_DEAD and REG_UNUSED notes. 3147169689Skan 3148169689Skan If the DF_RI_LIFE flag is set the following vectors containing 3149169689Skan information about register usage are properly set: REG_N_REFS, 3150169689Skan REG_N_DEATHS, REG_N_SETS, REG_LIVE_LENGTH, REG_N_CALLS_CROSSED, 3151169689Skan REG_N_THROWING_CALLS_CROSSED and REG_BASIC_BLOCK. 3152169689Skan 3153169689Skan ----------------------------------------------------------------------------*/ 3154169689Skan 3155169689Skan#ifdef REG_DEAD_DEBUGGING 3156169689Skanstatic void 3157169689Skanprint_note (char *prefix, rtx insn, rtx note) 3158169689Skan{ 3159169689Skan fprintf (stderr, "%s %d ", prefix, INSN_UID (insn)); 3160169689Skan print_rtl (stderr, note); 3161169689Skan fprintf (stderr, "\n"); 3162169689Skan} 3163169689Skan#endif 3164169689Skan 3165169689Skan/* Allocate the lifetime information. */ 3166169689Skan 3167169689Skanstatic void 3168169689Skandf_ri_alloc (struct dataflow *dflow, 3169169689Skan bitmap blocks_to_rescan ATTRIBUTE_UNUSED, 3170169689Skan bitmap all_blocks ATTRIBUTE_UNUSED) 3171169689Skan{ 3172169689Skan int i; 3173169689Skan struct df *df = dflow->df; 3174169689Skan 3175169689Skan if (dflow->flags & DF_RI_LIFE) 3176169689Skan { 3177169689Skan max_regno = max_reg_num (); 3178169689Skan allocate_reg_info (max_regno, FALSE, FALSE); 3179169689Skan 3180169689Skan /* Reset all the data we'll collect. */ 3181169689Skan for (i = 0; i < max_regno; i++) 3182169689Skan { 3183169689Skan REG_N_SETS (i) = DF_REG_DEF_COUNT (df, i); 3184169689Skan REG_N_REFS (i) = DF_REG_USE_COUNT (df, i) + REG_N_SETS (i); 3185169689Skan REG_N_DEATHS (i) = 0; 3186169689Skan REG_N_CALLS_CROSSED (i) = 0; 3187169689Skan REG_N_THROWING_CALLS_CROSSED (i) = 0; 3188169689Skan REG_LIVE_LENGTH (i) = 0; 3189169689Skan REG_FREQ (i) = 0; 3190169689Skan REG_BASIC_BLOCK (i) = REG_BLOCK_UNKNOWN; 3191169689Skan } 3192169689Skan } 3193169689Skan} 3194169689Skan 3195169689Skan 3196169689Skan/* After reg-stack, the x86 floating point stack regs are difficult to 3197169689Skan analyze because of all of the pushes, pops and rotations. Thus, we 3198169689Skan just leave the notes alone. */ 3199169689Skan 3200169689Skanstatic inline bool 3201169689Skandf_ignore_stack_reg (int regno ATTRIBUTE_UNUSED) 3202169689Skan{ 3203169689Skan#ifdef STACK_REGS 3204169689Skan return (regstack_completed 3205169689Skan && IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG)); 3206169689Skan#else 3207169689Skan return false; 3208169689Skan#endif 3209169689Skan} 3210169689Skan 3211169689Skan 3212169689Skan/* Remove all of the REG_DEAD or REG_UNUSED notes from INSN. */ 3213169689Skan 3214169689Skanstatic void 3215169689Skandf_kill_notes (rtx insn, int flags) 3216169689Skan{ 3217169689Skan rtx *pprev = ®_NOTES (insn); 3218169689Skan rtx link = *pprev; 3219169689Skan 3220169689Skan while (link) 3221169689Skan { 3222169689Skan switch (REG_NOTE_KIND (link)) 3223169689Skan { 3224169689Skan case REG_DEAD: 3225169689Skan if (flags & DF_RI_LIFE) 3226169689Skan if (df_ignore_stack_reg (REGNO (XEXP (link, 0)))) 3227169689Skan REG_N_DEATHS (REGNO (XEXP (link, 0)))++; 3228169689Skan 3229169689Skan /* Fallthru */ 3230169689Skan case REG_UNUSED: 3231169689Skan if (!df_ignore_stack_reg (REGNO (XEXP (link, 0)))) 3232169689Skan { 3233169689Skan rtx next = XEXP (link, 1); 3234169689Skan#ifdef REG_DEAD_DEBUGGING 3235169689Skan print_note ("deleting: ", insn, link); 3236169689Skan#endif 3237169689Skan free_EXPR_LIST_node (link); 3238169689Skan *pprev = link = next; 3239169689Skan } 3240169689Skan break; 3241169689Skan 3242169689Skan default: 3243169689Skan pprev = &XEXP (link, 1); 3244169689Skan link = *pprev; 3245169689Skan break; 3246169689Skan } 3247169689Skan } 3248169689Skan} 3249169689Skan 3250169689Skan 3251169689Skan/* Set the REG_UNUSED notes for the multiword hardreg defs in INSN 3252169689Skan based on the bits in LIVE. Do not generate notes for registers in 3253169689Skan artificial uses. DO_NOT_GEN is updated so that REG_DEAD notes are 3254169689Skan not generated if the reg is both read and written by the 3255169689Skan instruction. 3256169689Skan*/ 3257169689Skan 3258169689Skanstatic void 3259169689Skandf_set_unused_notes_for_mw (rtx insn, struct df_mw_hardreg *mws, 3260169689Skan bitmap live, bitmap do_not_gen, 3261169689Skan bitmap artificial_uses, int flags) 3262169689Skan{ 3263169689Skan bool all_dead = true; 3264169689Skan struct df_link *regs = mws->regs; 3265169689Skan unsigned int regno = DF_REF_REGNO (regs->ref); 3266169689Skan 3267169689Skan#ifdef REG_DEAD_DEBUGGING 3268169689Skan fprintf (stderr, "mw unused looking at %d\n", DF_REF_REGNO (regs->ref)); 3269169689Skan df_ref_debug (regs->ref, stderr); 3270169689Skan#endif 3271169689Skan while (regs) 3272169689Skan { 3273169689Skan unsigned int regno = DF_REF_REGNO (regs->ref); 3274169689Skan if ((bitmap_bit_p (live, regno)) 3275169689Skan || bitmap_bit_p (artificial_uses, regno)) 3276169689Skan { 3277169689Skan all_dead = false; 3278169689Skan break; 3279169689Skan } 3280169689Skan regs = regs->next; 3281169689Skan } 3282169689Skan 3283169689Skan if (all_dead) 3284169689Skan { 3285169689Skan struct df_link *regs = mws->regs; 3286169689Skan rtx note = alloc_EXPR_LIST (REG_UNUSED, *DF_REF_LOC (regs->ref), 3287169689Skan REG_NOTES (insn)); 3288169689Skan REG_NOTES (insn) = note; 3289169689Skan#ifdef REG_DEAD_DEBUGGING 3290169689Skan print_note ("adding 1: ", insn, note); 3291169689Skan#endif 3292169689Skan bitmap_set_bit (do_not_gen, regno); 3293169689Skan /* Only do this if the value is totally dead. */ 3294169689Skan if (flags & DF_RI_LIFE) 3295169689Skan { 3296169689Skan REG_N_DEATHS (regno) ++; 3297169689Skan REG_LIVE_LENGTH (regno)++; 3298169689Skan } 3299169689Skan } 3300169689Skan else 3301169689Skan { 3302169689Skan struct df_link *regs = mws->regs; 3303169689Skan while (regs) 3304169689Skan { 3305169689Skan struct df_ref *ref = regs->ref; 3306169689Skan 3307169689Skan regno = DF_REF_REGNO (ref); 3308169689Skan if ((!bitmap_bit_p (live, regno)) 3309169689Skan && (!bitmap_bit_p (artificial_uses, regno))) 3310169689Skan { 3311169689Skan rtx note = alloc_EXPR_LIST (REG_UNUSED, regno_reg_rtx[regno], 3312169689Skan REG_NOTES (insn)); 3313169689Skan REG_NOTES (insn) = note; 3314169689Skan#ifdef REG_DEAD_DEBUGGING 3315169689Skan print_note ("adding 2: ", insn, note); 3316169689Skan#endif 3317169689Skan } 3318169689Skan bitmap_set_bit (do_not_gen, regno); 3319169689Skan regs = regs->next; 3320169689Skan } 3321169689Skan } 3322169689Skan} 3323169689Skan 3324169689Skan 3325169689Skan/* Set the REG_DEAD notes for the multiword hardreg use in INSN based 3326169689Skan on the bits in LIVE. DO_NOT_GEN is used to keep REG_DEAD notes 3327169689Skan from being set if the instruction both reads and writes the 3328169689Skan register. */ 3329169689Skan 3330169689Skanstatic void 3331169689Skandf_set_dead_notes_for_mw (rtx insn, struct df_mw_hardreg *mws, 3332169689Skan bitmap live, bitmap do_not_gen, 3333169689Skan bitmap artificial_uses, int flags) 3334169689Skan{ 3335169689Skan bool all_dead = true; 3336169689Skan struct df_link *regs = mws->regs; 3337169689Skan unsigned int regno = DF_REF_REGNO (regs->ref); 3338169689Skan 3339169689Skan#ifdef REG_DEAD_DEBUGGING 3340169689Skan fprintf (stderr, "mw looking at %d\n", DF_REF_REGNO (regs->ref)); 3341169689Skan df_ref_debug (regs->ref, stderr); 3342169689Skan#endif 3343169689Skan while (regs) 3344169689Skan { 3345169689Skan unsigned int regno = DF_REF_REGNO (regs->ref); 3346169689Skan if ((bitmap_bit_p (live, regno)) 3347169689Skan || bitmap_bit_p (artificial_uses, regno)) 3348169689Skan { 3349169689Skan all_dead = false; 3350169689Skan break; 3351169689Skan } 3352169689Skan regs = regs->next; 3353169689Skan } 3354169689Skan 3355169689Skan if (all_dead) 3356169689Skan { 3357169689Skan if (!bitmap_bit_p (do_not_gen, regno)) 3358169689Skan { 3359169689Skan /* Add a dead note for the entire multi word register. */ 3360169689Skan struct df_link *regs = mws->regs; 3361169689Skan rtx note = alloc_EXPR_LIST (REG_DEAD, *DF_REF_LOC (regs->ref), 3362169689Skan REG_NOTES (insn)); 3363169689Skan REG_NOTES (insn) = note; 3364169689Skan#ifdef REG_DEAD_DEBUGGING 3365169689Skan print_note ("adding 1: ", insn, note); 3366169689Skan#endif 3367169689Skan 3368169689Skan if (flags & DF_RI_LIFE) 3369169689Skan { 3370169689Skan struct df_link *regs = mws->regs; 3371169689Skan while (regs) 3372169689Skan { 3373169689Skan struct df_ref *ref = regs->ref; 3374169689Skan regno = DF_REF_REGNO (ref); 3375169689Skan REG_N_DEATHS (regno)++; 3376169689Skan regs = regs->next; 3377169689Skan } 3378169689Skan } 3379169689Skan } 3380169689Skan } 3381169689Skan else 3382169689Skan { 3383169689Skan struct df_link *regs = mws->regs; 3384169689Skan while (regs) 3385169689Skan { 3386169689Skan struct df_ref *ref = regs->ref; 3387169689Skan 3388169689Skan regno = DF_REF_REGNO (ref); 3389169689Skan if ((!bitmap_bit_p (live, regno)) 3390169689Skan && (!bitmap_bit_p (artificial_uses, regno)) 3391169689Skan && (!bitmap_bit_p (do_not_gen, regno))) 3392169689Skan { 3393169689Skan rtx note = alloc_EXPR_LIST (REG_DEAD, regno_reg_rtx[regno], 3394169689Skan REG_NOTES (insn)); 3395169689Skan REG_NOTES (insn) = note; 3396169689Skan if (flags & DF_RI_LIFE) 3397169689Skan REG_N_DEATHS (regno)++; 3398169689Skan#ifdef REG_DEAD_DEBUGGING 3399169689Skan print_note ("adding 2: ", insn, note); 3400169689Skan#endif 3401169689Skan } 3402169689Skan 3403169689Skan regs = regs->next; 3404169689Skan } 3405169689Skan } 3406169689Skan} 3407169689Skan 3408169689Skan 3409169689Skan/* Create a REG_UNUSED note if necessary for DEF in INSN updating LIVE 3410169689Skan and DO_NOT_GEN. Do not generate notes for registers in artificial 3411169689Skan uses. */ 3412169689Skan 3413169689Skanstatic void 3414169689Skandf_create_unused_note (basic_block bb, rtx insn, struct df_ref *def, 3415169689Skan bitmap live, bitmap do_not_gen, bitmap artificial_uses, 3416169689Skan bitmap local_live, bitmap local_processed, 3417169689Skan int flags, int luid) 3418169689Skan{ 3419169689Skan unsigned int dregno = DF_REF_REGNO (def); 3420169689Skan 3421169689Skan#ifdef REG_DEAD_DEBUGGING 3422169689Skan fprintf (stderr, " regular looking at def "); 3423169689Skan df_ref_debug (def, stderr); 3424169689Skan#endif 3425169689Skan 3426169689Skan if (bitmap_bit_p (live, dregno)) 3427169689Skan { 3428169689Skan if (flags & DF_RI_LIFE) 3429169689Skan { 3430169689Skan /* If we have seen this regno, then it has already been 3431169689Skan processed correctly with the per insn increment. If we 3432169689Skan have not seen it we need to add the length from here to 3433169689Skan the end of the block to the live length. */ 3434169689Skan if (bitmap_bit_p (local_processed, dregno)) 3435169689Skan { 3436169689Skan if (!(DF_REF_FLAGS (def) & DF_REF_PARTIAL)) 3437169689Skan bitmap_clear_bit (local_live, dregno); 3438169689Skan } 3439169689Skan else 3440169689Skan { 3441169689Skan bitmap_set_bit (local_processed, dregno); 3442169689Skan REG_LIVE_LENGTH (dregno) += luid; 3443169689Skan } 3444169689Skan } 3445169689Skan } 3446169689Skan else if ((!(DF_REF_FLAGS (def) & DF_REF_MW_HARDREG)) 3447169689Skan && (!bitmap_bit_p (artificial_uses, dregno)) 3448169689Skan && (!df_ignore_stack_reg (dregno))) 3449169689Skan { 3450169689Skan rtx reg = GET_CODE (*DF_REF_LOC (def)) == SUBREG ? 3451169689Skan SUBREG_REG (*DF_REF_LOC (def)) : *DF_REF_LOC (def); 3452169689Skan rtx note = alloc_EXPR_LIST (REG_UNUSED, reg, REG_NOTES (insn)); 3453169689Skan REG_NOTES (insn) = note; 3454169689Skan#ifdef REG_DEAD_DEBUGGING 3455169689Skan print_note ("adding 3: ", insn, note); 3456169689Skan#endif 3457169689Skan if (flags & DF_RI_LIFE) 3458169689Skan { 3459169689Skan REG_N_DEATHS (dregno) ++; 3460169689Skan REG_LIVE_LENGTH (dregno)++; 3461169689Skan } 3462169689Skan } 3463169689Skan 3464169689Skan if ((flags & DF_RI_LIFE) && (dregno >= FIRST_PSEUDO_REGISTER)) 3465169689Skan { 3466169689Skan REG_FREQ (dregno) += REG_FREQ_FROM_BB (bb); 3467169689Skan if (REG_BASIC_BLOCK (dregno) == REG_BLOCK_UNKNOWN) 3468169689Skan REG_BASIC_BLOCK (dregno) = bb->index; 3469169689Skan else if (REG_BASIC_BLOCK (dregno) != bb->index) 3470169689Skan REG_BASIC_BLOCK (dregno) = REG_BLOCK_GLOBAL; 3471169689Skan } 3472169689Skan 3473169689Skan if (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER + DF_REF_MAY_CLOBBER))) 3474169689Skan bitmap_set_bit (do_not_gen, dregno); 3475169689Skan 3476169689Skan /* Kill this register if it is not a subreg store. */ 3477169689Skan if (!(DF_REF_FLAGS (def) & DF_REF_PARTIAL)) 3478169689Skan bitmap_clear_bit (live, dregno); 3479169689Skan} 3480169689Skan 3481169689Skan 3482169689Skan/* Recompute the REG_DEAD and REG_UNUSED notes and compute register 3483169689Skan info: lifetime, bb, and number of defs and uses for basic block 3484169689Skan BB. The three bitvectors are scratch regs used here. */ 3485169689Skan 3486169689Skanstatic void 3487169689Skandf_ri_bb_compute (struct dataflow *dflow, unsigned int bb_index, 3488169689Skan bitmap live, bitmap do_not_gen, bitmap artificial_uses, 3489169689Skan bitmap local_live, bitmap local_processed, bitmap setjumps_crossed) 3490169689Skan{ 3491169689Skan struct df *df = dflow->df; 3492169689Skan basic_block bb = BASIC_BLOCK (bb_index); 3493169689Skan rtx insn; 3494169689Skan struct df_ref *def; 3495169689Skan struct df_ref *use; 3496169689Skan int luid = 0; 3497169689Skan 3498169689Skan bitmap_copy (live, df_get_live_out (df, bb)); 3499169689Skan bitmap_clear (artificial_uses); 3500169689Skan 3501169689Skan if (dflow->flags & DF_RI_LIFE) 3502169689Skan { 3503169689Skan /* Process the regs live at the end of the block. Mark them as 3504169689Skan not local to any one basic block. */ 3505169689Skan bitmap_iterator bi; 3506169689Skan unsigned int regno; 3507169689Skan EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi) 3508169689Skan REG_BASIC_BLOCK (regno) = REG_BLOCK_GLOBAL; 3509169689Skan } 3510169689Skan 3511169689Skan /* Process the artificial defs and uses at the bottom of the block 3512169689Skan to begin processing. */ 3513169689Skan for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref) 3514169689Skan if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0) 3515169689Skan bitmap_clear_bit (live, DF_REF_REGNO (def)); 3516169689Skan 3517169689Skan for (use = df_get_artificial_uses (df, bb_index); use; use = use->next_ref) 3518169689Skan if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0) 3519169689Skan { 3520169689Skan unsigned int regno = DF_REF_REGNO (use); 3521169689Skan bitmap_set_bit (live, regno); 3522169689Skan 3523169689Skan /* Notes are not generated for any of the artificial registers 3524169689Skan at the bottom of the block. */ 3525169689Skan bitmap_set_bit (artificial_uses, regno); 3526169689Skan } 3527169689Skan 3528169689Skan FOR_BB_INSNS_REVERSE (bb, insn) 3529169689Skan { 3530169689Skan unsigned int uid = INSN_UID (insn); 3531169689Skan unsigned int regno; 3532169689Skan bitmap_iterator bi; 3533169689Skan struct df_mw_hardreg *mws; 3534169689Skan 3535169689Skan if (!INSN_P (insn)) 3536169689Skan continue; 3537169689Skan 3538169689Skan if (dflow->flags & DF_RI_LIFE) 3539169689Skan { 3540169689Skan /* Increment the live_length for all of the registers that 3541169689Skan are are referenced in this block and live at this 3542169689Skan particular point. */ 3543169689Skan bitmap_iterator bi; 3544169689Skan unsigned int regno; 3545169689Skan EXECUTE_IF_SET_IN_BITMAP (local_live, 0, regno, bi) 3546169689Skan { 3547169689Skan REG_LIVE_LENGTH (regno)++; 3548169689Skan } 3549169689Skan luid++; 3550169689Skan } 3551169689Skan 3552169689Skan bitmap_clear (do_not_gen); 3553169689Skan df_kill_notes (insn, dflow->flags); 3554169689Skan 3555169689Skan /* Process the defs. */ 3556169689Skan if (CALL_P (insn)) 3557169689Skan { 3558169689Skan if (dflow->flags & DF_RI_LIFE) 3559169689Skan { 3560169689Skan bool can_throw = can_throw_internal (insn); 3561169689Skan bool set_jump = (find_reg_note (insn, REG_SETJMP, NULL) != NULL); 3562169689Skan EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi) 3563169689Skan { 3564169689Skan REG_N_CALLS_CROSSED (regno)++; 3565169689Skan if (can_throw) 3566169689Skan REG_N_THROWING_CALLS_CROSSED (regno)++; 3567169689Skan 3568169689Skan /* We have a problem with any pseudoreg that lives 3569169689Skan across the setjmp. ANSI says that if a user 3570169689Skan variable does not change in value between the 3571169689Skan setjmp and the longjmp, then the longjmp 3572169689Skan preserves it. This includes longjmp from a place 3573169689Skan where the pseudo appears dead. (In principle, 3574169689Skan the value still exists if it is in scope.) If 3575169689Skan the pseudo goes in a hard reg, some other value 3576169689Skan may occupy that hard reg where this pseudo is 3577169689Skan dead, thus clobbering the pseudo. Conclusion: 3578169689Skan such a pseudo must not go in a hard reg. */ 3579169689Skan if (set_jump && regno >= FIRST_PSEUDO_REGISTER) 3580169689Skan bitmap_set_bit (setjumps_crossed, regno); 3581169689Skan } 3582169689Skan } 3583169689Skan 3584169689Skan /* We only care about real sets for calls. Clobbers only 3585169689Skan may clobber and cannot be depended on. */ 3586169689Skan for (mws = DF_INSN_UID_MWS (df, uid); mws; mws = mws->next) 3587169689Skan { 3588169689Skan if ((mws->type == DF_REF_REG_DEF) 3589169689Skan && !df_ignore_stack_reg (REGNO (mws->mw_reg))) 3590169689Skan df_set_unused_notes_for_mw (insn, mws, live, do_not_gen, 3591169689Skan artificial_uses, dflow->flags); 3592169689Skan } 3593169689Skan 3594169689Skan /* All of the defs except the return value are some sort of 3595169689Skan clobber. This code is for the return. */ 3596169689Skan for (def = DF_INSN_UID_DEFS (df, uid); def; def = def->next_ref) 3597169689Skan if (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))) 3598169689Skan df_create_unused_note (bb, insn, def, live, do_not_gen, 3599169689Skan artificial_uses, local_live, 3600169689Skan local_processed, dflow->flags, luid); 3601169689Skan 3602169689Skan } 3603169689Skan else 3604169689Skan { 3605169689Skan /* Regular insn. */ 3606169689Skan for (mws = DF_INSN_UID_MWS (df, uid); mws; mws = mws->next) 3607169689Skan { 3608169689Skan if (mws->type == DF_REF_REG_DEF) 3609169689Skan df_set_unused_notes_for_mw (insn, mws, live, do_not_gen, 3610169689Skan artificial_uses, dflow->flags); 3611169689Skan } 3612169689Skan 3613169689Skan for (def = DF_INSN_UID_DEFS (df, uid); def; def = def->next_ref) 3614169689Skan df_create_unused_note (bb, insn, def, live, do_not_gen, 3615169689Skan artificial_uses, local_live, 3616169689Skan local_processed, dflow->flags, luid); 3617169689Skan } 3618169689Skan 3619169689Skan /* Process the uses. */ 3620169689Skan for (mws = DF_INSN_UID_MWS (df, uid); mws; mws = mws->next) 3621169689Skan { 3622169689Skan if ((mws->type != DF_REF_REG_DEF) 3623169689Skan && !df_ignore_stack_reg (REGNO (mws->mw_reg))) 3624169689Skan df_set_dead_notes_for_mw (insn, mws, live, do_not_gen, 3625169689Skan artificial_uses, dflow->flags); 3626169689Skan } 3627169689Skan 3628169689Skan for (use = DF_INSN_UID_USES (df, uid); use; use = use->next_ref) 3629169689Skan { 3630169689Skan unsigned int uregno = DF_REF_REGNO (use); 3631169689Skan 3632169689Skan if ((dflow->flags & DF_RI_LIFE) && (uregno >= FIRST_PSEUDO_REGISTER)) 3633169689Skan { 3634169689Skan REG_FREQ (uregno) += REG_FREQ_FROM_BB (bb); 3635169689Skan if (REG_BASIC_BLOCK (uregno) == REG_BLOCK_UNKNOWN) 3636169689Skan REG_BASIC_BLOCK (uregno) = bb->index; 3637169689Skan else if (REG_BASIC_BLOCK (uregno) != bb->index) 3638169689Skan REG_BASIC_BLOCK (uregno) = REG_BLOCK_GLOBAL; 3639169689Skan } 3640169689Skan 3641169689Skan#ifdef REG_DEAD_DEBUGGING 3642169689Skan fprintf (stderr, " regular looking at use "); 3643169689Skan df_ref_debug (use, stderr); 3644169689Skan#endif 3645169689Skan if (!bitmap_bit_p (live, uregno)) 3646169689Skan { 3647169689Skan if ( (!(DF_REF_FLAGS (use) & DF_REF_MW_HARDREG)) 3648169689Skan && (!bitmap_bit_p (do_not_gen, uregno)) 3649169689Skan && (!bitmap_bit_p (artificial_uses, uregno)) 3650169689Skan && (!(DF_REF_FLAGS (use) & DF_REF_READ_WRITE)) 3651169689Skan && (!df_ignore_stack_reg (uregno))) 3652169689Skan { 3653169689Skan rtx reg = GET_CODE (*DF_REF_LOC (use)) == SUBREG ? 3654169689Skan SUBREG_REG (*DF_REF_LOC (use)) : *DF_REF_LOC (use); 3655169689Skan rtx note = alloc_EXPR_LIST (REG_DEAD, reg, REG_NOTES (insn)); 3656169689Skan REG_NOTES (insn) = note; 3657169689Skan if (dflow->flags & DF_RI_LIFE) 3658169689Skan REG_N_DEATHS (uregno)++; 3659169689Skan 3660169689Skan#ifdef REG_DEAD_DEBUGGING 3661169689Skan print_note ("adding 4: ", insn, note); 3662169689Skan#endif 3663169689Skan } 3664169689Skan /* This register is now live. */ 3665169689Skan bitmap_set_bit (live, uregno); 3666169689Skan 3667169689Skan if (dflow->flags & DF_RI_LIFE) 3668169689Skan { 3669169689Skan /* If we have seen this regno, then it has already 3670169689Skan been processed correctly with the per insn 3671169689Skan increment. If we have not seen it we set the bit 3672169689Skan so that begins to get processed locally. Note 3673169689Skan that we don't even get here if the variable was 3674169689Skan live at the end of the block since just a ref 3675169689Skan inside the block does not effect the 3676169689Skan calculations. */ 3677169689Skan REG_LIVE_LENGTH (uregno) ++; 3678169689Skan bitmap_set_bit (local_live, uregno); 3679169689Skan bitmap_set_bit (local_processed, uregno); 3680169689Skan } 3681169689Skan } 3682169689Skan } 3683169689Skan } 3684169689Skan 3685169689Skan if (dflow->flags & DF_RI_LIFE) 3686169689Skan { 3687169689Skan /* Add the length of the block to all of the registers that were 3688169689Skan not referenced, but still live in this block. */ 3689169689Skan bitmap_iterator bi; 3690169689Skan unsigned int regno; 3691169689Skan bitmap_and_compl_into (live, local_processed); 3692169689Skan EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi) 3693169689Skan { 3694169689Skan REG_LIVE_LENGTH (regno) += luid; 3695169689Skan } 3696169689Skan bitmap_clear (local_processed); 3697169689Skan bitmap_clear (local_live); 3698169689Skan } 3699169689Skan} 3700169689Skan 3701169689Skan 3702169689Skan/* Compute register info: lifetime, bb, and number of defs and uses. */ 3703169689Skanstatic void 3704169689Skandf_ri_compute (struct dataflow *dflow, bitmap all_blocks ATTRIBUTE_UNUSED, 3705169689Skan bitmap blocks_to_scan) 3706169689Skan{ 3707169689Skan unsigned int bb_index; 3708169689Skan bitmap_iterator bi; 3709169689Skan bitmap live = BITMAP_ALLOC (NULL); 3710169689Skan bitmap do_not_gen = BITMAP_ALLOC (NULL); 3711169689Skan bitmap artificial_uses = BITMAP_ALLOC (NULL); 3712169689Skan bitmap local_live = NULL; 3713169689Skan bitmap local_processed = NULL; 3714169689Skan bitmap setjumps_crossed = NULL; 3715169689Skan 3716169689Skan if (dflow->flags & DF_RI_LIFE) 3717169689Skan { 3718169689Skan local_live = BITMAP_ALLOC (NULL); 3719169689Skan local_processed = BITMAP_ALLOC (NULL); 3720169689Skan setjumps_crossed = BITMAP_ALLOC (NULL); 3721169689Skan } 3722169689Skan 3723169689Skan 3724169689Skan#ifdef REG_DEAD_DEBUGGING 3725169689Skan df_lr_dump (dflow->df->problems_by_index [DF_LR], stderr); 3726169689Skan print_rtl_with_bb (stderr, get_insns()); 3727169689Skan#endif 3728169689Skan 3729169689Skan EXECUTE_IF_SET_IN_BITMAP (blocks_to_scan, 0, bb_index, bi) 3730169689Skan { 3731169689Skan df_ri_bb_compute (dflow, bb_index, live, do_not_gen, artificial_uses, 3732169689Skan local_live, local_processed, setjumps_crossed); 3733169689Skan } 3734169689Skan 3735169689Skan BITMAP_FREE (live); 3736169689Skan BITMAP_FREE (do_not_gen); 3737169689Skan BITMAP_FREE (artificial_uses); 3738169689Skan if (dflow->flags & DF_RI_LIFE) 3739169689Skan { 3740169689Skan bitmap_iterator bi; 3741169689Skan unsigned int regno; 3742169689Skan /* See the setjump comment in df_ri_bb_compute. */ 3743169689Skan EXECUTE_IF_SET_IN_BITMAP (setjumps_crossed, 0, regno, bi) 3744169689Skan { 3745169689Skan REG_BASIC_BLOCK (regno) = REG_BLOCK_UNKNOWN; 3746169689Skan REG_LIVE_LENGTH (regno) = -1; 3747169689Skan } 3748169689Skan 3749169689Skan BITMAP_FREE (local_live); 3750169689Skan BITMAP_FREE (local_processed); 3751169689Skan BITMAP_FREE (setjumps_crossed); 3752169689Skan } 3753169689Skan} 3754169689Skan 3755169689Skan 3756169689Skan/* Free all storage associated with the problem. */ 3757169689Skan 3758169689Skanstatic void 3759169689Skandf_ri_free (struct dataflow *dflow) 3760169689Skan{ 3761169689Skan free (dflow->problem_data); 3762169689Skan free (dflow); 3763169689Skan} 3764169689Skan 3765169689Skan 3766169689Skan/* Debugging info. */ 3767169689Skan 3768169689Skanstatic void 3769169689Skandf_ri_dump (struct dataflow *dflow, FILE *file) 3770169689Skan{ 3771169689Skan print_rtl_with_bb (file, get_insns ()); 3772169689Skan 3773169689Skan if (dflow->flags & DF_RI_LIFE) 3774169689Skan { 3775169689Skan fprintf (file, "Register info:\n"); 3776169689Skan dump_flow_info (file, -1); 3777169689Skan } 3778169689Skan} 3779169689Skan 3780169689Skan/* All of the information associated every instance of the problem. */ 3781169689Skan 3782169689Skanstatic struct df_problem problem_RI = 3783169689Skan{ 3784169689Skan DF_RI, /* Problem id. */ 3785169689Skan DF_NONE, /* Direction. */ 3786169689Skan df_ri_alloc, /* Allocate the problem specific data. */ 3787169689Skan NULL, /* Reset global information. */ 3788169689Skan NULL, /* Free basic block info. */ 3789169689Skan df_ri_compute, /* Local compute function. */ 3790169689Skan NULL, /* Init the solution specific data. */ 3791169689Skan NULL, /* Iterative solver. */ 3792169689Skan NULL, /* Confluence operator 0. */ 3793169689Skan NULL, /* Confluence operator n. */ 3794169689Skan NULL, /* Transfer function. */ 3795169689Skan NULL, /* Finalize function. */ 3796169689Skan df_ri_free, /* Free all of the problem information. */ 3797169689Skan df_ri_dump, /* Debugging. */ 3798169689Skan 3799169689Skan /* Technically this is only dependent on the live registers problem 3800169689Skan but it will produce information if built one of uninitialized 3801169689Skan register problems (UR, UREC) is also run. */ 3802169689Skan df_lr_add_problem, /* Dependent problem. */ 3803169689Skan 0 /* Changeable flags. */ 3804169689Skan}; 3805169689Skan 3806169689Skan 3807169689Skan/* Create a new DATAFLOW instance and add it to an existing instance 3808169689Skan of DF. The returned structure is what is used to get at the 3809169689Skan solution. */ 3810169689Skan 3811169689Skanstruct dataflow * 3812169689Skandf_ri_add_problem (struct df *df, int flags) 3813169689Skan{ 3814169689Skan return df_add_problem (df, &problem_RI, flags); 3815169689Skan} 3816