1169689Skan/* RTL factoring (sequence abstraction). 2169689Skan Copyright (C) 2004, 2005, 2006 Free Software Foundation, Inc. 3169689Skan 4169689SkanThis file is part of GCC. 5169689Skan 6169689SkanGCC is free software; you can redistribute it and/or modify it under 7169689Skanthe terms of the GNU General Public License as published by the Free 8169689SkanSoftware Foundation; either version 2, or (at your option) any later 9169689Skanversion. 10169689Skan 11169689SkanGCC is distributed in the hope that it will be useful, but WITHOUT ANY 12169689SkanWARRANTY; without even the implied warranty of MERCHANTABILITY or 13169689SkanFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14169689Skanfor more details. 15169689Skan 16169689SkanYou should have received a copy of the GNU General Public License 17169689Skanalong with GCC; see the file COPYING. If not, write to the Free 18169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 19169689Skan02110-1301, USA. */ 20169689Skan 21169689Skan#include "config.h" 22169689Skan#include "system.h" 23169689Skan#include "coretypes.h" 24169689Skan#include "tm.h" 25169689Skan#include "rtl.h" 26169689Skan#include "obstack.h" 27169689Skan#include "basic-block.h" 28169689Skan#include "resource.h" 29169689Skan#include "flags.h" 30169689Skan#include "ggc.h" 31169689Skan#include "regs.h" 32169689Skan#include "params.h" 33169689Skan#include "expr.h" 34169689Skan#include "tm_p.h" 35169689Skan#include "tree-pass.h" 36169689Skan#include "tree-flow.h" 37169689Skan#include "timevar.h" 38169689Skan#include "output.h" 39169689Skan#include "addresses.h" 40169689Skan 41169689Skan/* Sequence abstraction: 42169689Skan 43169689Skan It is a size optimization method. The main idea of this technique is to 44169689Skan find identical sequences of code, which can be turned into procedures and 45169689Skan then replace all occurrences with calls to the newly created subroutine. 46169689Skan It is kind of an opposite of function inlining. 47169689Skan 48169689Skan There are four major parts of this file: 49169689Skan 50169689Skan sequence fingerprint 51169689Skan In order to avoid the comparison of every insn with every other, hash 52169689Skan value will be designed for every insn by COMPUTE_HASH. 53169689Skan These hash values are used for grouping the sequence candidates. So 54169689Skan we only need to compare every insn with every other in same hash group. 55169689Skan 56169689Skan FILL_HASH_BUCKET creates all hash values and stores into HASH_BUCKETS. 57169689Skan The result is used by COLLECT_PATTERN_SEQS. 58169689Skan 59169689Skan code matching 60169689Skan In code matching the algorithm compares every two possible sequence 61169689Skan candidates which last insns are in the same hash group. If these 62169689Skan sequences are identical they will be stored and do further searches for 63169689Skan finding more sequences which are identical with the first one. 64169689Skan 65169689Skan COLLECT_PATTERN_SEQS does the code matching and stores the results into 66169689Skan PATTERN_SEQS. 67169689Skan 68169689Skan gain computation 69169689Skan This part computes the gain of abstraction which could be archived when 70169689Skan turning the pattern sequence into a pseudo-function and its matching 71169689Skan sequences into pseudo-calls. After it the most effective sequences will 72169689Skan be marked for abstraction. 73169689Skan 74169689Skan RECOMPUTE_GAIN does the gain computation. The sequences with the maximum 75169689Skan gain is on the top of PATTERN_SEQS. 76169689Skan 77169689Skan abstract code 78169689Skan This part turns the pattern sequence into a pseudo-function and its 79169689Skan matching sequences into pseudo-calls. 80169689Skan 81169689Skan ABSTRACT_BEST_SEQ does the code merging. 82169689Skan 83169689Skan 84169689Skan C code example: 85169689Skan 86169689Skan // Original source // After sequence abstraction 87169689Skan { { 88169689Skan void *jump_label; 89169689Skan ... ... 90169689Skan jump_label = &&exit_0; 91169689Skan entry_0: 92169689Skan I0; I0; 93169689Skan I1; I1; 94169689Skan I2; I2; 95169689Skan I3; I3; 96169689Skan goto *jump_label; 97169689Skan exit_0: 98169689Skan ... ... 99169689Skan jump_label = &&exit_1; 100169689Skan goto entry_0; 101169689Skan I0; 102169689Skan I1; 103169689Skan I2; 104169689Skan I3; 105169689Skan exit_1: 106169689Skan ... ... 107169689Skan jump_label = &&exit_2; 108169689Skan goto entry_0; 109169689Skan I0; 110169689Skan I1; 111169689Skan I2; 112169689Skan I3; 113169689Skan exit_2: 114169689Skan ... ... 115169689Skan jump_label = &&exit_3; 116169689Skan goto entry_0; 117169689Skan I0; 118169689Skan I1; 119169689Skan I2; 120169689Skan I3; 121169689Skan exit_3: 122169689Skan ... ... 123169689Skan } } 124169689Skan 125169689Skan 126169689Skan TODO: 127169689Skan - Use REG_ALLOC_ORDER when choosing link register. 128169689Skan - Handle JUMP_INSNs. Also handle volatile function calls (handle them 129169689Skan similar to unconditional jumps.) 130169689Skan - Test command line option -fpic. 131169689Skan*/ 132169689Skan 133169689Skan/* Predicate yielding nonzero iff X is an abstractable insn. Non-jump insns are 134169689Skan abstractable. */ 135169689Skan#define ABSTRACTABLE_INSN_P(X) (INSN_P (X) && !JUMP_P (X)) 136169689Skan 137169689Skan/* First parameter of the htab_create function call. */ 138169689Skan#define HASH_INIT 1023 139169689Skan 140169689Skan/* Multiplier for cost of sequence call to avoid abstracting short 141169689Skan sequences. */ 142169689Skan#ifndef SEQ_CALL_COST_MULTIPLIER 143169689Skan#define SEQ_CALL_COST_MULTIPLIER 2 144169689Skan#endif 145169689Skan 146169689Skan/* Recomputes the cost of MSEQ pattern/matching sequence. */ 147169689Skan#define RECOMPUTE_COST(SEQ) \ 148169689Skan{ \ 149169689Skan int l; \ 150169689Skan rtx x = SEQ->insn; \ 151169689Skan SEQ->cost = 0; \ 152169689Skan for (l = 0; l < SEQ->abstracted_length; l++) \ 153169689Skan { \ 154169689Skan SEQ->cost += compute_rtx_cost (x); \ 155169689Skan x = prev_insn_in_block (x); \ 156169689Skan } \ 157169689Skan} 158169689Skan 159169689Skan/* A sequence matching a pattern sequence. */ 160169689Skantypedef struct matching_seq_def 161169689Skan{ 162169689Skan /* The last insn in the matching sequence. */ 163169689Skan rtx insn; 164169689Skan 165169689Skan /* Index of INSN instruction. */ 166169689Skan unsigned long idx; 167169689Skan 168169689Skan /* The number of insns matching in this sequence and the pattern sequence. 169169689Skan */ 170169689Skan int matching_length; 171169689Skan 172169689Skan /* The number of insns selected to abstract from this sequence. Less than 173169689Skan or equal to MATCHING_LENGTH. */ 174169689Skan int abstracted_length; 175169689Skan 176169689Skan /* The cost of the sequence. */ 177169689Skan int cost; 178169689Skan 179169689Skan /* The next sequence in the chain matching the same pattern. */ 180169689Skan struct matching_seq_def *next_matching_seq; 181169689Skan} *matching_seq; 182169689Skan 183169689Skan 184169689Skan/* A pattern instruction sequence. */ 185169689Skantypedef struct pattern_seq_def 186169689Skan{ 187169689Skan /* The last insn in the pattern sequence. */ 188169689Skan rtx insn; 189169689Skan 190169689Skan /* Index of INSN instruction. */ 191169689Skan unsigned long idx; 192169689Skan 193169689Skan /* The gain of transforming the pattern sequence into a pseudo-function and 194169689Skan the matching sequences into pseudo-calls. */ 195169689Skan int gain; 196169689Skan 197169689Skan /* The maximum of the ABSTRACTED_LENGTH of the matching sequences. */ 198169689Skan int abstracted_length; 199169689Skan 200169689Skan /* The cost of the sequence. */ 201169689Skan int cost; 202169689Skan 203169689Skan /* The register used to hold the return address during the pseudo-call. */ 204169689Skan rtx link_reg; 205169689Skan 206169689Skan /* The sequences matching this pattern. */ 207169689Skan matching_seq matching_seqs; 208169689Skan 209169689Skan /* The next pattern sequence in the chain. */ 210169689Skan struct pattern_seq_def *next_pattern_seq; 211169689Skan} *pattern_seq; 212169689Skan 213169689Skan 214169689Skan/* A block of a pattern sequence. */ 215169689Skantypedef struct seq_block_def 216169689Skan{ 217169689Skan /* The number of insns in the block. */ 218169689Skan int length; 219169689Skan 220169689Skan /* The code_label of the block. */ 221169689Skan rtx label; 222169689Skan 223169689Skan /* The sequences entering the pattern sequence at LABEL. */ 224169689Skan matching_seq matching_seqs; 225169689Skan 226169689Skan /* The next block in the chain. The blocks are sorted by LENGTH in 227169689Skan ascending order. */ 228169689Skan struct seq_block_def *next_seq_block; 229169689Skan} *seq_block; 230169689Skan 231169689Skan/* Contains same sequence candidates for further searching. */ 232169689Skantypedef struct hash_bucket_def 233169689Skan{ 234169689Skan /* The hash value of the group. */ 235169689Skan unsigned int hash; 236169689Skan 237169689Skan /* List of sequence candidates. */ 238169689Skan htab_t seq_candidates; 239169689Skan} *p_hash_bucket; 240169689Skan 241169689Skan/* Contains the last insn of the sequence, and its index value. */ 242169689Skantypedef struct hash_elem_def 243169689Skan{ 244169689Skan /* Unique index; ordered by FILL_HASH_BUCKET. */ 245169689Skan unsigned long idx; 246169689Skan 247169689Skan /* The last insn in the sequence. */ 248169689Skan rtx insn; 249169689Skan 250169689Skan /* The cached length of the insn. */ 251169689Skan int length; 252169689Skan} *p_hash_elem; 253169689Skan 254169689Skan/* The list of same sequence candidates. */ 255169689Skanstatic htab_t hash_buckets; 256169689Skan 257169689Skan/* The pattern sequences collected from the current functions. */ 258169689Skanstatic pattern_seq pattern_seqs; 259169689Skan 260169689Skan/* The blocks of the current pattern sequence. */ 261169689Skanstatic seq_block seq_blocks; 262169689Skan 263169689Skan/* Cost of calling sequence. */ 264169689Skanstatic int seq_call_cost; 265169689Skan 266169689Skan/* Cost of jump. */ 267169689Skanstatic int seq_jump_cost; 268169689Skan 269169689Skan/* Cost of returning. */ 270169689Skanstatic int seq_return_cost; 271169689Skan 272169689Skan/* Returns the first insn preceding INSN for which INSN_P is true and belongs to 273169689Skan the same basic block. Returns NULL_RTX if no such insn can be found. */ 274169689Skan 275169689Skanstatic rtx 276169689Skanprev_insn_in_block (rtx insn) 277169689Skan{ 278169689Skan basic_block bb = BLOCK_FOR_INSN (insn); 279169689Skan 280169689Skan if (!bb) 281169689Skan return NULL_RTX; 282169689Skan 283169689Skan while (insn != BB_HEAD (bb)) 284169689Skan { 285169689Skan insn = PREV_INSN (insn); 286169689Skan if (INSN_P (insn)) 287169689Skan return insn; 288169689Skan } 289169689Skan return NULL_RTX; 290169689Skan} 291169689Skan 292169689Skan/* Returns the hash value of INSN. */ 293169689Skan 294169689Skanstatic unsigned int 295169689Skancompute_hash (rtx insn) 296169689Skan{ 297169689Skan unsigned int hash = 0; 298169689Skan rtx prev; 299169689Skan 300169689Skan hash = INSN_CODE (insn) * 100; 301169689Skan 302169689Skan prev = prev_insn_in_block (insn); 303169689Skan if (prev) 304169689Skan hash += INSN_CODE (prev); 305169689Skan 306169689Skan return hash; 307169689Skan} 308169689Skan 309169689Skan/* Compute the cost of INSN rtx for abstraction. */ 310169689Skan 311169689Skanstatic int 312169689Skancompute_rtx_cost (rtx insn) 313169689Skan{ 314169689Skan struct hash_bucket_def tmp_bucket; 315169689Skan p_hash_bucket bucket; 316169689Skan struct hash_elem_def tmp_elem; 317169689Skan p_hash_elem elem = NULL; 318169689Skan int cost = -1; 319169689Skan 320169689Skan /* Compute hash value for INSN. */ 321169689Skan tmp_bucket.hash = compute_hash (insn); 322169689Skan 323169689Skan /* Select the hash group. */ 324169689Skan bucket = htab_find (hash_buckets, &tmp_bucket); 325169689Skan 326169689Skan if (bucket) 327169689Skan { 328169689Skan tmp_elem.insn = insn; 329169689Skan 330169689Skan /* Select the insn. */ 331169689Skan elem = htab_find (bucket->seq_candidates, &tmp_elem); 332169689Skan 333169689Skan /* If INSN is parsed the cost will be the cached length. */ 334169689Skan if (elem) 335169689Skan cost = elem->length; 336169689Skan } 337169689Skan 338169689Skan /* If we can't parse the INSN cost will be the instruction length. */ 339169689Skan if (cost == -1) 340169689Skan { 341169689Skan cost = get_attr_length (insn); 342169689Skan 343169689Skan /* Cache the length. */ 344169689Skan if (elem) 345169689Skan elem->length = cost; 346169689Skan } 347169689Skan 348169689Skan /* If we can't get an accurate estimate for a complex instruction, 349169689Skan assume that it has the same cost as a single fast instruction. */ 350169689Skan return cost != 0 ? cost : COSTS_N_INSNS (1); 351169689Skan} 352169689Skan 353169689Skan/* Determines the number of common insns in the sequences ending in INSN1 and 354169689Skan INSN2. Returns with LEN number of common insns and COST cost of sequence. 355169689Skan*/ 356169689Skan 357169689Skanstatic void 358169689Skanmatching_length (rtx insn1, rtx insn2, int* len, int* cost) 359169689Skan{ 360169689Skan rtx x1; 361169689Skan rtx x2; 362169689Skan 363169689Skan x1 = insn1; 364169689Skan x2 = insn2; 365169689Skan *len = 0; 366169689Skan *cost = 0; 367169689Skan while (x1 && x2 && (x1 != insn2) && (x2 != insn1) 368169689Skan && rtx_equal_p (PATTERN (x1), PATTERN (x2))) 369169689Skan { 370169689Skan (*len)++; 371169689Skan (*cost) += compute_rtx_cost (x1); 372169689Skan x1 = prev_insn_in_block (x1); 373169689Skan x2 = prev_insn_in_block (x2); 374169689Skan } 375169689Skan} 376169689Skan 377169689Skan/* Adds E0 as a pattern sequence to PATTERN_SEQS with E1 as a matching 378169689Skan sequence. */ 379169689Skan 380169689Skanstatic void 381169689Skanmatch_seqs (p_hash_elem e0, p_hash_elem e1) 382169689Skan{ 383169689Skan int len; 384169689Skan int cost; 385169689Skan matching_seq mseq, p_prev, p_next; 386169689Skan 387169689Skan /* Determines the cost of the sequence and return without doing anything 388169689Skan if it is too small to produce any gain. */ 389169689Skan matching_length (e0->insn, e1->insn, &len, &cost); 390169689Skan if (cost <= seq_call_cost) 391169689Skan return; 392169689Skan 393169689Skan /* Prepend a new PATTERN_SEQ to PATTERN_SEQS if the last pattern sequence 394169689Skan does not end in E0->INSN. This assumes that once the E0->INSN changes 395169689Skan the old value will never appear again. */ 396169689Skan if (!pattern_seqs || pattern_seqs->insn != e0->insn) 397169689Skan { 398169689Skan pattern_seq pseq = 399169689Skan (pattern_seq) xmalloc (sizeof (struct pattern_seq_def)); 400169689Skan pseq->insn = e0->insn; 401169689Skan pseq->idx = e0->idx; 402169689Skan pseq->gain = 0; /* Set to zero to force recomputing. */ 403169689Skan pseq->abstracted_length = 0; 404169689Skan pseq->cost = 0; 405169689Skan pseq->link_reg = NULL_RTX; 406169689Skan pseq->matching_seqs = NULL; 407169689Skan pseq->next_pattern_seq = pattern_seqs; 408169689Skan pattern_seqs = pseq; 409169689Skan } 410169689Skan 411169689Skan /* Find the position of E1 in the matching sequences list. */ 412169689Skan p_prev = NULL; 413169689Skan p_next = pattern_seqs->matching_seqs; 414169689Skan while (p_next && p_next->idx < e1->idx) 415169689Skan { 416169689Skan p_prev = p_next; 417169689Skan p_next = p_next->next_matching_seq; 418169689Skan } 419169689Skan 420169689Skan /* Add a new E1 matching sequence to the pattern sequence. We know that 421169689Skan it ends in E0->INSN. */ 422169689Skan mseq = (matching_seq) xmalloc (sizeof (struct matching_seq_def)); 423169689Skan mseq->insn = e1->insn; 424169689Skan mseq->idx = e1->idx; 425169689Skan mseq->matching_length = len; 426169689Skan mseq->abstracted_length = 0; 427169689Skan mseq->cost = cost; 428169689Skan 429169689Skan if (p_prev == NULL) 430169689Skan pattern_seqs->matching_seqs = mseq; 431169689Skan else 432169689Skan p_prev->next_matching_seq = mseq; 433169689Skan mseq->next_matching_seq = p_next; 434169689Skan} 435169689Skan 436169689Skan/* Collects all pattern sequences and their matching sequences and puts them 437169689Skan into PATTERN_SEQS. */ 438169689Skan 439169689Skanstatic void 440169689Skancollect_pattern_seqs (void) 441169689Skan{ 442169689Skan htab_iterator hti0, hti1, hti2; 443169689Skan p_hash_bucket hash_bucket; 444169689Skan p_hash_elem e0, e1; 445169689Skan#ifdef STACK_REGS 446169689Skan basic_block bb; 447169689Skan bitmap_head stack_reg_live; 448169689Skan 449169689Skan /* Extra initialization step to ensure that no stack registers (if present) 450169689Skan are live across abnormal edges. Set a flag in STACK_REG_LIVE for an insn 451169689Skan if a stack register is live after the insn. */ 452169689Skan bitmap_initialize (&stack_reg_live, NULL); 453169689Skan 454169689Skan FOR_EACH_BB (bb) 455169689Skan { 456169689Skan regset_head live; 457169689Skan struct propagate_block_info *pbi; 458169689Skan rtx insn; 459169689Skan 460169689Skan /* Initialize liveness propagation. */ 461169689Skan INIT_REG_SET (&live); 462169689Skan COPY_REG_SET (&live, bb->il.rtl->global_live_at_end); 463169689Skan pbi = init_propagate_block_info (bb, &live, NULL, NULL, 0); 464169689Skan 465169689Skan /* Propagate liveness info and mark insns where a stack reg is live. */ 466169689Skan insn = BB_END (bb); 467169689Skan while (1) 468169689Skan { 469169689Skan int reg; 470169689Skan for (reg = FIRST_STACK_REG; reg <= LAST_STACK_REG; reg++) 471169689Skan { 472169689Skan if (REGNO_REG_SET_P (&live, reg)) 473169689Skan { 474169689Skan bitmap_set_bit (&stack_reg_live, INSN_UID (insn)); 475169689Skan break; 476169689Skan } 477169689Skan } 478169689Skan 479169689Skan if (insn == BB_HEAD (bb)) 480169689Skan break; 481169689Skan insn = propagate_one_insn (pbi, insn); 482169689Skan } 483169689Skan 484169689Skan /* Free unused data. */ 485169689Skan CLEAR_REG_SET (&live); 486169689Skan free_propagate_block_info (pbi); 487169689Skan } 488169689Skan#endif 489169689Skan 490169689Skan /* Initialize PATTERN_SEQS to empty. */ 491169689Skan pattern_seqs = 0; 492169689Skan 493169689Skan /* Try to match every abstractable insn with every other insn in the same 494169689Skan HASH_BUCKET. */ 495169689Skan 496169689Skan FOR_EACH_HTAB_ELEMENT (hash_buckets, hash_bucket, p_hash_bucket, hti0) 497169689Skan if (htab_elements (hash_bucket->seq_candidates) > 1) 498169689Skan FOR_EACH_HTAB_ELEMENT (hash_bucket->seq_candidates, e0, p_hash_elem, hti1) 499169689Skan FOR_EACH_HTAB_ELEMENT (hash_bucket->seq_candidates, e1, p_hash_elem, 500169689Skan hti2) 501169689Skan if (e0 != e1 502169689Skan#ifdef STACK_REGS 503169689Skan && !bitmap_bit_p (&stack_reg_live, INSN_UID (e0->insn)) 504169689Skan && !bitmap_bit_p (&stack_reg_live, INSN_UID (e1->insn)) 505169689Skan#endif 506169689Skan ) 507169689Skan match_seqs (e0, e1); 508169689Skan#ifdef STACK_REGS 509169689Skan /* Free unused data. */ 510169689Skan bitmap_clear (&stack_reg_live); 511169689Skan#endif 512169689Skan} 513169689Skan 514169689Skan/* Transforms a regset to a HARD_REG_SET. Every hard register in REGS is added 515169689Skan to hregs. Additionally, the hard counterpart of every renumbered pseudo 516169689Skan register is also added. */ 517169689Skan 518169689Skanstatic void 519169689Skanrenumbered_reg_set_to_hard_reg_set (HARD_REG_SET * hregs, regset regs) 520169689Skan{ 521169689Skan int r; 522169689Skan 523169689Skan REG_SET_TO_HARD_REG_SET (*hregs, regs); 524169689Skan for (r = FIRST_PSEUDO_REGISTER; r < max_regno; r++) 525169689Skan if (REGNO_REG_SET_P (regs, r) && reg_renumber[r] >= 0) 526169689Skan SET_HARD_REG_BIT (*hregs, reg_renumber[r]); 527169689Skan} 528169689Skan 529169689Skan/* Clears the bits in REGS for all registers, which are live in the sequence 530169689Skan give by its last INSN and its LENGTH. */ 531169689Skan 532169689Skanstatic void 533169689Skanclear_regs_live_in_seq (HARD_REG_SET * regs, rtx insn, int length) 534169689Skan{ 535169689Skan basic_block bb; 536169689Skan regset_head live; 537169689Skan HARD_REG_SET hlive; 538169689Skan struct propagate_block_info *pbi; 539169689Skan rtx x; 540169689Skan int i; 541169689Skan 542169689Skan /* Initialize liveness propagation. */ 543169689Skan bb = BLOCK_FOR_INSN (insn); 544169689Skan INIT_REG_SET (&live); 545169689Skan COPY_REG_SET (&live, bb->il.rtl->global_live_at_end); 546169689Skan pbi = init_propagate_block_info (bb, &live, NULL, NULL, 0); 547169689Skan 548169689Skan /* Propagate until INSN if found. */ 549169689Skan for (x = BB_END (bb); x != insn;) 550169689Skan x = propagate_one_insn (pbi, x); 551169689Skan 552169689Skan /* Clear registers live after INSN. */ 553169689Skan renumbered_reg_set_to_hard_reg_set (&hlive, &live); 554169689Skan AND_COMPL_HARD_REG_SET (*regs, hlive); 555169689Skan 556169689Skan /* Clear registers live in and before the sequence. */ 557169689Skan for (i = 0; i < length;) 558169689Skan { 559169689Skan rtx prev = propagate_one_insn (pbi, x); 560169689Skan 561169689Skan if (INSN_P (x)) 562169689Skan { 563169689Skan renumbered_reg_set_to_hard_reg_set (&hlive, &live); 564169689Skan AND_COMPL_HARD_REG_SET (*regs, hlive); 565169689Skan i++; 566169689Skan } 567169689Skan 568169689Skan x = prev; 569169689Skan } 570169689Skan 571169689Skan /* Free unused data. */ 572169689Skan free_propagate_block_info (pbi); 573169689Skan CLEAR_REG_SET (&live); 574169689Skan} 575169689Skan 576169689Skan/* Computes the gain of turning PSEQ into a pseudo-function and its matching 577169689Skan sequences into pseudo-calls. Also computes and caches the number of insns to 578169689Skan abstract from the matching sequences. */ 579169689Skan 580169689Skanstatic void 581169689Skanrecompute_gain_for_pattern_seq (pattern_seq pseq) 582169689Skan{ 583169689Skan matching_seq mseq; 584169689Skan rtx x; 585169689Skan int i; 586169689Skan int hascall; 587169689Skan HARD_REG_SET linkregs; 588169689Skan 589169689Skan /* Initialize data. */ 590169689Skan SET_HARD_REG_SET (linkregs); 591169689Skan pseq->link_reg = NULL_RTX; 592169689Skan pseq->abstracted_length = 0; 593169689Skan 594169689Skan pseq->gain = -(seq_call_cost - seq_jump_cost + seq_return_cost); 595169689Skan 596169689Skan /* Determine ABSTRACTED_LENGTH and COST for matching sequences of PSEQ. 597169689Skan ABSTRACTED_LENGTH may be less than MATCHING_LENGTH if sequences in the 598169689Skan same block overlap. */ 599169689Skan 600169689Skan for (mseq = pseq->matching_seqs; mseq; mseq = mseq->next_matching_seq) 601169689Skan { 602169689Skan /* Determine ABSTRACTED_LENGTH. */ 603169689Skan if (mseq->next_matching_seq) 604169689Skan mseq->abstracted_length = (int)(mseq->next_matching_seq->idx - 605169689Skan mseq->idx); 606169689Skan else 607169689Skan mseq->abstracted_length = mseq->matching_length; 608169689Skan 609169689Skan if (mseq->abstracted_length > mseq->matching_length) 610169689Skan mseq->abstracted_length = mseq->matching_length; 611169689Skan 612169689Skan /* Compute the cost of sequence. */ 613169689Skan RECOMPUTE_COST (mseq); 614169689Skan 615169689Skan /* If COST is big enough registers live in this matching sequence 616169689Skan should not be used as a link register. Also set ABSTRACTED_LENGTH 617169689Skan of PSEQ. */ 618169689Skan if (mseq->cost > seq_call_cost) 619169689Skan { 620169689Skan clear_regs_live_in_seq (&linkregs, mseq->insn, 621169689Skan mseq->abstracted_length); 622169689Skan if (mseq->abstracted_length > pseq->abstracted_length) 623169689Skan pseq->abstracted_length = mseq->abstracted_length; 624169689Skan } 625169689Skan } 626169689Skan 627169689Skan /* Modify ABSTRACTED_LENGTH of PSEQ if pattern sequence overlaps with one 628169689Skan of the matching sequences. */ 629169689Skan for (mseq = pseq->matching_seqs; mseq; mseq = mseq->next_matching_seq) 630169689Skan { 631169689Skan x = pseq->insn; 632169689Skan for (i = 0; (i < pseq->abstracted_length) && (x != mseq->insn); i++) 633169689Skan x = prev_insn_in_block (x); 634169689Skan pseq->abstracted_length = i; 635169689Skan } 636169689Skan 637169689Skan /* Compute the cost of pattern sequence. */ 638169689Skan RECOMPUTE_COST (pseq); 639169689Skan 640169689Skan /* No gain if COST is too small. */ 641169689Skan if (pseq->cost <= seq_call_cost) 642169689Skan { 643169689Skan pseq->gain = -1; 644169689Skan return; 645169689Skan } 646169689Skan 647169689Skan /* Ensure that no matching sequence is longer than the pattern sequence. */ 648169689Skan for (mseq = pseq->matching_seqs; mseq; mseq = mseq->next_matching_seq) 649169689Skan { 650169689Skan if (mseq->abstracted_length > pseq->abstracted_length) 651169689Skan { 652169689Skan mseq->abstracted_length = pseq->abstracted_length; 653169689Skan RECOMPUTE_COST (mseq); 654169689Skan } 655169689Skan /* Once the length is stabilizing the gain can be calculated. */ 656169689Skan if (mseq->cost > seq_call_cost) 657169689Skan pseq->gain += mseq->cost - seq_call_cost; 658169689Skan } 659169689Skan 660169689Skan /* No need to do further work if there is no gain. */ 661169689Skan if (pseq->gain <= 0) 662169689Skan return; 663169689Skan 664169689Skan /* Should not use registers live in the pattern sequence as link register. 665169689Skan */ 666169689Skan clear_regs_live_in_seq (&linkregs, pseq->insn, pseq->abstracted_length); 667169689Skan 668169689Skan /* Determine whether pattern sequence contains a call_insn. */ 669169689Skan hascall = 0; 670169689Skan x = pseq->insn; 671169689Skan for (i = 0; i < pseq->abstracted_length; i++) 672169689Skan { 673169689Skan if (CALL_P (x)) 674169689Skan { 675169689Skan hascall = 1; 676169689Skan break; 677169689Skan } 678169689Skan x = prev_insn_in_block (x); 679169689Skan } 680169689Skan 681169689Skan /* Should not use a register as a link register if - it is a fixed 682169689Skan register, or - the sequence contains a call insn and the register is a 683169689Skan call used register, or - the register needs to be saved if used in a 684169689Skan function but was not used before (since saving it can invalidate already 685169689Skan computed frame pointer offsets), or - the register cannot be used as a 686169689Skan base register. */ 687169689Skan 688169689Skan for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 689169689Skan if (fixed_regs[i] 690169689Skan#ifdef REGNO_OK_FOR_INDIRECT_JUMP_P 691169689Skan || (!REGNO_OK_FOR_INDIRECT_JUMP_P (i, Pmode)) 692169689Skan#else 693169689Skan || (!ok_for_base_p_1 (i, Pmode, MEM, SCRATCH)) 694169689Skan || (!reg_class_subset_p (REGNO_REG_CLASS (i), 695169689Skan base_reg_class (VOIDmode, MEM, SCRATCH))) 696169689Skan#endif 697169689Skan || (hascall && call_used_regs[i]) 698169689Skan || (!call_used_regs[i] && !regs_ever_live[i])) 699169689Skan CLEAR_HARD_REG_BIT (linkregs, i); 700169689Skan 701169689Skan /* Find an appropriate register to be used as the link register. */ 702169689Skan for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 703169689Skan if (TEST_HARD_REG_BIT (linkregs, i)) 704169689Skan { 705169689Skan pseq->link_reg = gen_rtx_REG (Pmode, i); 706169689Skan break; 707169689Skan } 708169689Skan 709169689Skan /* Abstraction is not possible if no link register is available, so set 710169689Skan gain to 0. */ 711169689Skan if (!pseq->link_reg) 712169689Skan pseq->gain = 0; 713169689Skan} 714169689Skan 715169689Skan/* Deallocates memory occupied by PSEQ and its matching seqs. */ 716169689Skan 717169689Skanstatic void 718169689Skanfree_pattern_seq (pattern_seq pseq) 719169689Skan{ 720169689Skan while (pseq->matching_seqs) 721169689Skan { 722169689Skan matching_seq mseq = pseq->matching_seqs; 723169689Skan pseq->matching_seqs = mseq->next_matching_seq; 724169689Skan free (mseq); 725169689Skan } 726169689Skan free (pseq); 727169689Skan} 728169689Skan 729169689Skan 730169689Skan/* Computes the gain for pattern sequences. Pattern sequences producing no gain 731169689Skan are deleted. The pattern sequence with the biggest gain is moved to the first 732169689Skan place of PATTERN_SEQS. */ 733169689Skan 734169689Skanstatic void 735169689Skanrecompute_gain (void) 736169689Skan{ 737169689Skan pattern_seq *pseq; 738169689Skan int maxgain; 739169689Skan 740169689Skan maxgain = 0; 741169689Skan for (pseq = &pattern_seqs; *pseq;) 742169689Skan { 743169689Skan if ((*pseq)->gain <= 0) 744169689Skan recompute_gain_for_pattern_seq (*pseq); 745169689Skan 746169689Skan if ((*pseq)->gain > 0) 747169689Skan { 748169689Skan if ((*pseq)->gain > maxgain) 749169689Skan { 750169689Skan pattern_seq temp = *pseq; 751169689Skan (*pseq) = temp->next_pattern_seq; 752169689Skan temp->next_pattern_seq = pattern_seqs; 753169689Skan pattern_seqs = temp; 754169689Skan maxgain = pattern_seqs->gain; 755169689Skan } 756169689Skan else 757169689Skan { 758169689Skan pseq = &(*pseq)->next_pattern_seq; 759169689Skan } 760169689Skan } 761169689Skan else 762169689Skan { 763169689Skan pattern_seq temp = *pseq; 764169689Skan *pseq = temp->next_pattern_seq; 765169689Skan free_pattern_seq (temp); 766169689Skan } 767169689Skan } 768169689Skan} 769169689Skan 770169689Skan/* Updated those pattern sequences and matching sequences, which overlap with 771169689Skan the sequence given by INSN and LEN. Deletes sequences shrinking below a 772169689Skan limit. */ 773169689Skan 774169689Skanstatic void 775169689Skanerase_from_pattern_seqs (rtx insn, int len) 776169689Skan{ 777169689Skan pattern_seq *pseq; 778169689Skan matching_seq *mseq; 779169689Skan rtx x; 780169689Skan int plen, mlen; 781169689Skan int pcost, mcost; 782169689Skan 783169689Skan while (len > 0) 784169689Skan { 785169689Skan for (pseq = &pattern_seqs; *pseq;) 786169689Skan { 787169689Skan plen = 0; 788169689Skan pcost = 0; 789169689Skan for (x = (*pseq)->insn; x && (x != insn); 790169689Skan x = prev_insn_in_block (x)) 791169689Skan { 792169689Skan plen++; 793169689Skan pcost += compute_rtx_cost (x); 794169689Skan } 795169689Skan 796169689Skan if (pcost <= seq_call_cost) 797169689Skan { 798169689Skan pattern_seq temp = *pseq; 799169689Skan *pseq = temp->next_pattern_seq; 800169689Skan free_pattern_seq (temp); 801169689Skan } 802169689Skan else 803169689Skan { 804169689Skan for (mseq = &(*pseq)->matching_seqs; *mseq;) 805169689Skan { 806169689Skan mlen = 0; 807169689Skan mcost = 0; 808169689Skan for (x = (*mseq)->insn; 809169689Skan x && (x != insn) && (mlen < plen) 810169689Skan && (mlen < (*mseq)->matching_length); 811169689Skan x = prev_insn_in_block (x)) 812169689Skan { 813169689Skan mlen++; 814169689Skan mcost += compute_rtx_cost (x); 815169689Skan } 816169689Skan 817169689Skan if (mcost <= seq_call_cost) 818169689Skan { 819169689Skan matching_seq temp = *mseq; 820169689Skan *mseq = temp->next_matching_seq; 821169689Skan free (temp); 822169689Skan /* Set to 0 to force gain recomputation. */ 823169689Skan (*pseq)->gain = 0; 824169689Skan } 825169689Skan else 826169689Skan { 827169689Skan if (mlen < (*mseq)->matching_length) 828169689Skan { 829169689Skan (*mseq)->cost = mcost; 830169689Skan (*mseq)->matching_length = mlen; 831169689Skan /* Set to 0 to force gain recomputation. */ 832169689Skan (*pseq)->gain = 0; 833169689Skan } 834169689Skan mseq = &(*mseq)->next_matching_seq; 835169689Skan } 836169689Skan } 837169689Skan 838169689Skan pseq = &(*pseq)->next_pattern_seq; 839169689Skan } 840169689Skan } 841169689Skan 842169689Skan len--; 843169689Skan insn = prev_insn_in_block (insn); 844169689Skan } 845169689Skan} 846169689Skan 847169689Skan/* Updates those pattern sequences and matching sequences, which overlap with 848169689Skan the pattern sequence with the biggest gain and its matching sequences. */ 849169689Skan 850169689Skanstatic void 851169689Skanupdate_pattern_seqs (void) 852169689Skan{ 853169689Skan pattern_seq bestpseq; 854169689Skan matching_seq mseq; 855169689Skan 856169689Skan bestpseq = pattern_seqs; 857169689Skan pattern_seqs = bestpseq->next_pattern_seq; 858169689Skan 859169689Skan for (mseq = bestpseq->matching_seqs; mseq; mseq = mseq->next_matching_seq) 860169689Skan if (mseq->cost > seq_call_cost) 861169689Skan erase_from_pattern_seqs (mseq->insn, mseq->abstracted_length); 862169689Skan erase_from_pattern_seqs (bestpseq->insn, bestpseq->abstracted_length); 863169689Skan 864169689Skan bestpseq->next_pattern_seq = pattern_seqs; 865169689Skan pattern_seqs = bestpseq; 866169689Skan} 867169689Skan 868169689Skan/* Groups together those matching sequences of the best pattern sequence, which 869169689Skan have the same ABSTRACTED_LENGTH and puts these groups in ascending order. 870169689Skan SEQ_BLOCKS contains the result. */ 871169689Skan 872169689Skanstatic void 873169689Skandetermine_seq_blocks (void) 874169689Skan{ 875169689Skan seq_block sb; 876169689Skan matching_seq *mseq; 877169689Skan matching_seq m; 878169689Skan 879169689Skan /* Initialize SEQ_BLOCKS to empty. */ 880169689Skan seq_blocks = 0; 881169689Skan 882169689Skan /* Process all matching sequences. */ 883169689Skan for (mseq = &pattern_seqs->matching_seqs; *mseq;) 884169689Skan { 885169689Skan /* Deal only with matching sequences being long enough. */ 886169689Skan if ((*mseq)->cost <= seq_call_cost) 887169689Skan { 888169689Skan mseq = &(*mseq)->next_matching_seq; 889169689Skan continue; 890169689Skan } 891169689Skan 892169689Skan /* Ensure that SB contains a seq_block with the appropriate length. 893169689Skan Insert a new seq_block if necessary. */ 894169689Skan if (!seq_blocks || ((*mseq)->abstracted_length < seq_blocks->length)) 895169689Skan { 896169689Skan sb = (seq_block) xmalloc (sizeof (struct seq_block_def)); 897169689Skan sb->length = (*mseq)->abstracted_length; 898169689Skan sb->label = NULL_RTX; 899169689Skan sb->matching_seqs = 0; 900169689Skan sb->next_seq_block = seq_blocks; 901169689Skan seq_blocks = sb; 902169689Skan } 903169689Skan else 904169689Skan { 905169689Skan for (sb = seq_blocks; sb; sb = sb->next_seq_block) 906169689Skan { 907169689Skan if ((*mseq)->abstracted_length == sb->length) 908169689Skan break; 909169689Skan if (!sb->next_seq_block 910169689Skan || ((*mseq)->abstracted_length < 911169689Skan sb->next_seq_block->length)) 912169689Skan { 913169689Skan seq_block temp = 914169689Skan (seq_block) xmalloc (sizeof (struct seq_block_def)); 915169689Skan temp->length = (*mseq)->abstracted_length; 916169689Skan temp->label = NULL_RTX; 917169689Skan temp->matching_seqs = 0; 918169689Skan temp->next_seq_block = sb->next_seq_block; 919169689Skan sb->next_seq_block = temp; 920169689Skan } 921169689Skan } 922169689Skan } 923169689Skan 924169689Skan /* Remove the matching sequence from the linked list of the pattern 925169689Skan sequence and link it to SB. */ 926169689Skan m = *mseq; 927169689Skan *mseq = m->next_matching_seq; 928169689Skan m->next_matching_seq = sb->matching_seqs; 929169689Skan sb->matching_seqs = m; 930169689Skan } 931169689Skan} 932169689Skan 933169689Skan/* Builds a symbol_ref for LABEL. */ 934169689Skan 935169689Skanstatic rtx 936169689Skangen_symbol_ref_rtx_for_label (rtx label) 937169689Skan{ 938169689Skan char name[20]; 939169689Skan rtx sym; 940169689Skan 941169689Skan ASM_GENERATE_INTERNAL_LABEL (name, "L", CODE_LABEL_NUMBER (label)); 942169689Skan sym = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (name)); 943169689Skan SYMBOL_REF_FLAGS (sym) = SYMBOL_FLAG_LOCAL; 944169689Skan return sym; 945169689Skan} 946169689Skan 947169689Skan/* Ensures that INSN is the last insn in its block and returns the block label 948169689Skan of the next block. */ 949169689Skan 950169689Skanstatic rtx 951169689Skanblock_label_after (rtx insn) 952169689Skan{ 953169689Skan basic_block bb = BLOCK_FOR_INSN (insn); 954169689Skan if ((insn == BB_END (bb)) && (bb->next_bb != EXIT_BLOCK_PTR)) 955169689Skan return block_label (bb->next_bb); 956169689Skan else 957169689Skan return block_label (split_block (bb, insn)->dest); 958169689Skan} 959169689Skan 960169689Skan/* Ensures that the last insns of the best pattern and its matching sequences 961169689Skan are the last insns in their block. Additionally, extends the live set at the 962169689Skan end of the pattern sequence with the live sets at the end of the matching 963169689Skan sequences. */ 964169689Skan 965169689Skanstatic void 966169689Skansplit_blocks_after_seqs (void) 967169689Skan{ 968169689Skan seq_block sb; 969169689Skan matching_seq mseq; 970169689Skan 971169689Skan block_label_after (pattern_seqs->insn); 972169689Skan for (sb = seq_blocks; sb; sb = sb->next_seq_block) 973169689Skan { 974169689Skan for (mseq = sb->matching_seqs; mseq; mseq = mseq->next_matching_seq) 975169689Skan { 976169689Skan block_label_after (mseq->insn); 977169689Skan IOR_REG_SET (BLOCK_FOR_INSN (pattern_seqs->insn)-> 978169689Skan il.rtl->global_live_at_end, 979169689Skan BLOCK_FOR_INSN (mseq->insn)->il.rtl->global_live_at_end); 980169689Skan } 981169689Skan } 982169689Skan} 983169689Skan 984169689Skan/* Splits the best pattern sequence according to SEQ_BLOCKS. Emits pseudo-call 985169689Skan and -return insns before and after the sequence. */ 986169689Skan 987169689Skanstatic void 988169689Skansplit_pattern_seq (void) 989169689Skan{ 990169689Skan rtx insn; 991169689Skan basic_block bb; 992169689Skan rtx retlabel, retjmp, saveinsn; 993169689Skan int i; 994169689Skan seq_block sb; 995169689Skan 996169689Skan insn = pattern_seqs->insn; 997169689Skan bb = BLOCK_FOR_INSN (insn); 998169689Skan 999169689Skan /* Get the label after the sequence. This will be the return address. The 1000169689Skan label will be referenced using a symbol_ref so protect it from 1001169689Skan deleting. */ 1002169689Skan retlabel = block_label_after (insn); 1003169689Skan LABEL_PRESERVE_P (retlabel) = 1; 1004169689Skan 1005169689Skan /* Emit an indirect jump via the link register after the sequence acting 1006169689Skan as the return insn. Also emit a barrier and update the basic block. */ 1007169689Skan retjmp = emit_jump_insn_after (gen_indirect_jump (pattern_seqs->link_reg), 1008169689Skan BB_END (bb)); 1009169689Skan emit_barrier_after (BB_END (bb)); 1010169689Skan 1011169689Skan /* Replace all outgoing edges with a new one to the block of RETLABEL. */ 1012169689Skan while (EDGE_COUNT (bb->succs) != 0) 1013169689Skan remove_edge (EDGE_SUCC (bb, 0)); 1014169689Skan make_edge (bb, BLOCK_FOR_INSN (retlabel), EDGE_ABNORMAL); 1015169689Skan 1016169689Skan /* Split the sequence according to SEQ_BLOCKS and cache the label of the 1017169689Skan resulting basic blocks. */ 1018169689Skan i = 0; 1019169689Skan for (sb = seq_blocks; sb; sb = sb->next_seq_block) 1020169689Skan { 1021169689Skan for (; i < sb->length; i++) 1022169689Skan insn = prev_insn_in_block (insn); 1023169689Skan 1024169689Skan sb->label = block_label (split_block (bb, insn)->dest); 1025169689Skan } 1026169689Skan 1027169689Skan /* Emit an insn saving the return address to the link register before the 1028169689Skan sequence. */ 1029169689Skan saveinsn = emit_insn_after (gen_move_insn (pattern_seqs->link_reg, 1030169689Skan gen_symbol_ref_rtx_for_label 1031169689Skan (retlabel)), BB_END (bb)); 1032169689Skan /* Update liveness info. */ 1033169689Skan SET_REGNO_REG_SET (bb->il.rtl->global_live_at_end, 1034169689Skan REGNO (pattern_seqs->link_reg)); 1035169689Skan} 1036169689Skan 1037169689Skan/* Deletes the insns of the matching sequences of the best pattern sequence and 1038169689Skan replaces them with pseudo-calls to the pattern sequence. */ 1039169689Skan 1040169689Skanstatic void 1041169689Skanerase_matching_seqs (void) 1042169689Skan{ 1043169689Skan seq_block sb; 1044169689Skan matching_seq mseq; 1045169689Skan rtx insn; 1046169689Skan basic_block bb; 1047169689Skan rtx retlabel, saveinsn, callinsn; 1048169689Skan int i; 1049169689Skan 1050169689Skan for (sb = seq_blocks; sb; sb = sb->next_seq_block) 1051169689Skan { 1052169689Skan for (mseq = sb->matching_seqs; mseq; mseq = mseq->next_matching_seq) 1053169689Skan { 1054169689Skan insn = mseq->insn; 1055169689Skan bb = BLOCK_FOR_INSN (insn); 1056169689Skan 1057169689Skan /* Get the label after the sequence. This will be the return 1058169689Skan address. The label will be referenced using a symbol_ref so 1059169689Skan protect it from deleting. */ 1060169689Skan retlabel = block_label_after (insn); 1061169689Skan LABEL_PRESERVE_P (retlabel) = 1; 1062169689Skan 1063169689Skan /* Delete the insns of the sequence. */ 1064169689Skan for (i = 0; i < sb->length; i++) 1065169689Skan insn = prev_insn_in_block (insn); 1066169689Skan delete_basic_block (split_block (bb, insn)->dest); 1067169689Skan 1068169689Skan /* Emit an insn saving the return address to the link register 1069169689Skan before the deleted sequence. */ 1070169689Skan saveinsn = emit_insn_after (gen_move_insn (pattern_seqs->link_reg, 1071169689Skan gen_symbol_ref_rtx_for_label 1072169689Skan (retlabel)), 1073169689Skan BB_END (bb)); 1074169689Skan BLOCK_FOR_INSN (saveinsn) = bb; 1075169689Skan 1076169689Skan /* Emit a jump to the appropriate part of the pattern sequence 1077169689Skan after the save insn. Also update the basic block. */ 1078169689Skan callinsn = emit_jump_insn_after (gen_jump (sb->label), saveinsn); 1079169689Skan JUMP_LABEL (callinsn) = sb->label; 1080169689Skan LABEL_NUSES (sb->label)++; 1081169689Skan BLOCK_FOR_INSN (callinsn) = bb; 1082169689Skan BB_END (bb) = callinsn; 1083169689Skan 1084169689Skan /* Maintain control flow and liveness information. */ 1085169689Skan SET_REGNO_REG_SET (bb->il.rtl->global_live_at_end, 1086169689Skan REGNO (pattern_seqs->link_reg)); 1087169689Skan emit_barrier_after (BB_END (bb)); 1088169689Skan make_single_succ_edge (bb, BLOCK_FOR_INSN (sb->label), 0); 1089169689Skan IOR_REG_SET (bb->il.rtl->global_live_at_end, 1090169689Skan BLOCK_FOR_INSN (sb->label)->il.rtl->global_live_at_start); 1091169689Skan 1092169689Skan make_edge (BLOCK_FOR_INSN (seq_blocks->label), 1093169689Skan BLOCK_FOR_INSN (retlabel), EDGE_ABNORMAL); 1094169689Skan } 1095169689Skan } 1096169689Skan} 1097169689Skan 1098169689Skan/* Deallocates SEQ_BLOCKS and all the matching sequences. */ 1099169689Skan 1100169689Skanstatic void 1101169689Skanfree_seq_blocks (void) 1102169689Skan{ 1103169689Skan while (seq_blocks) 1104169689Skan { 1105169689Skan seq_block sb = seq_blocks; 1106169689Skan while (sb->matching_seqs) 1107169689Skan { 1108169689Skan matching_seq mseq = sb->matching_seqs; 1109169689Skan sb->matching_seqs = mseq->next_matching_seq; 1110169689Skan free (mseq); 1111169689Skan } 1112169689Skan seq_blocks = sb->next_seq_block; 1113169689Skan free (sb); 1114169689Skan } 1115169689Skan} 1116169689Skan 1117169689Skan/* Transforms the best pattern sequence into a pseudo-function and its matching 1118169689Skan sequences to pseudo-calls. Afterwards the best pattern sequence is removed 1119169689Skan from PATTERN_SEQS. */ 1120169689Skan 1121169689Skanstatic void 1122169689Skanabstract_best_seq (void) 1123169689Skan{ 1124169689Skan pattern_seq bestpseq; 1125169689Skan 1126169689Skan /* Do the abstraction. */ 1127169689Skan determine_seq_blocks (); 1128169689Skan split_blocks_after_seqs (); 1129169689Skan split_pattern_seq (); 1130169689Skan erase_matching_seqs (); 1131169689Skan free_seq_blocks (); 1132169689Skan 1133169689Skan /* Record the usage of the link register. */ 1134169689Skan regs_ever_live[REGNO (pattern_seqs->link_reg)] = 1; 1135169689Skan 1136169689Skan /* Remove the best pattern sequence. */ 1137169689Skan bestpseq = pattern_seqs; 1138169689Skan pattern_seqs = bestpseq->next_pattern_seq; 1139169689Skan free_pattern_seq (bestpseq); 1140169689Skan} 1141169689Skan 1142169689Skan/* Prints info on the pattern sequences to the dump file. */ 1143169689Skan 1144169689Skanstatic void 1145169689Skandump_pattern_seqs (void) 1146169689Skan{ 1147169689Skan pattern_seq pseq; 1148169689Skan matching_seq mseq; 1149169689Skan 1150169689Skan if (!dump_file) 1151169689Skan return; 1152169689Skan 1153169689Skan fprintf (dump_file, ";; Pattern sequences\n"); 1154169689Skan for (pseq = pattern_seqs; pseq; pseq = pseq->next_pattern_seq) 1155169689Skan { 1156169689Skan fprintf (dump_file, "Pattern sequence at insn %d matches sequences at", 1157169689Skan INSN_UID (pseq->insn)); 1158169689Skan for (mseq = pseq->matching_seqs; mseq; mseq = mseq->next_matching_seq) 1159169689Skan { 1160169689Skan fprintf (dump_file, " insn %d (length %d)", INSN_UID (mseq->insn), 1161169689Skan mseq->matching_length); 1162169689Skan if (mseq->next_matching_seq) 1163169689Skan fprintf (dump_file, ","); 1164169689Skan } 1165169689Skan fprintf (dump_file, ".\n"); 1166169689Skan } 1167169689Skan fprintf (dump_file, "\n"); 1168169689Skan} 1169169689Skan 1170169689Skan/* Prints info on the best pattern sequence transformed in the ITER-th 1171169689Skan iteration to the dump file. */ 1172169689Skan 1173169689Skanstatic void 1174169689Skandump_best_pattern_seq (int iter) 1175169689Skan{ 1176169689Skan matching_seq mseq; 1177169689Skan 1178169689Skan if (!dump_file) 1179169689Skan return; 1180169689Skan 1181169689Skan fprintf (dump_file, ";; Iteration %d\n", iter); 1182169689Skan fprintf (dump_file, 1183169689Skan "Best pattern sequence with %d gain is at insn %d (length %d).\n", 1184169689Skan pattern_seqs->gain, INSN_UID (pattern_seqs->insn), 1185169689Skan pattern_seqs->abstracted_length); 1186169689Skan fprintf (dump_file, "Matching sequences are at"); 1187169689Skan for (mseq = pattern_seqs->matching_seqs; mseq; 1188169689Skan mseq = mseq->next_matching_seq) 1189169689Skan { 1190169689Skan fprintf (dump_file, " insn %d (length %d)", INSN_UID (mseq->insn), 1191169689Skan mseq->abstracted_length); 1192169689Skan if (mseq->next_matching_seq) 1193169689Skan fprintf (dump_file, ","); 1194169689Skan } 1195169689Skan fprintf (dump_file, ".\n"); 1196169689Skan fprintf (dump_file, "Using reg %d as link register.\n\n", 1197169689Skan REGNO (pattern_seqs->link_reg)); 1198169689Skan} 1199169689Skan 1200169689Skan/* Htab hash function for hash_bucket_def structure. */ 1201169689Skan 1202169689Skanstatic unsigned int 1203169689Skanhtab_hash_bucket (const void *p) 1204169689Skan{ 1205169689Skan p_hash_bucket bucket = (p_hash_bucket) p; 1206169689Skan return bucket->hash; 1207169689Skan} 1208169689Skan 1209169689Skan/* Htab equal function for hash_bucket_def structure. */ 1210169689Skan 1211169689Skanstatic int 1212169689Skanhtab_eq_bucket (const void *p0, const void *p1) 1213169689Skan{ 1214169689Skan return htab_hash_bucket (p0) == htab_hash_bucket (p1); 1215169689Skan} 1216169689Skan 1217169689Skan/* Htab delete function for hash_bucket_def structure. */ 1218169689Skan 1219169689Skanstatic void 1220169689Skanhtab_del_bucket (void *p) 1221169689Skan{ 1222169689Skan p_hash_bucket bucket = (p_hash_bucket) p; 1223169689Skan 1224169689Skan if (bucket->seq_candidates) 1225169689Skan htab_delete (bucket->seq_candidates); 1226169689Skan 1227169689Skan free (bucket); 1228169689Skan} 1229169689Skan 1230169689Skan/* Htab hash function for hash_bucket_def structure. */ 1231169689Skan 1232169689Skanstatic unsigned int 1233169689Skanhtab_hash_elem (const void *p) 1234169689Skan{ 1235169689Skan p_hash_elem elem = (p_hash_elem) p; 1236169689Skan return htab_hash_pointer (elem->insn); 1237169689Skan} 1238169689Skan 1239169689Skan/* Htab equal function for hash_bucket_def structure. */ 1240169689Skan 1241169689Skanstatic int 1242169689Skanhtab_eq_elem (const void *p0, const void *p1) 1243169689Skan{ 1244169689Skan return htab_hash_elem (p0) == htab_hash_elem (p1); 1245169689Skan} 1246169689Skan 1247169689Skan/* Htab delete function for hash_bucket_def structure. */ 1248169689Skan 1249169689Skanstatic void 1250169689Skanhtab_del_elem (void *p) 1251169689Skan{ 1252169689Skan p_hash_elem elem = (p_hash_elem) p; 1253169689Skan free (elem); 1254169689Skan} 1255169689Skan 1256169689Skan/* Creates a hash value for each sequence candidate and saves them 1257169689Skan in HASH_BUCKET. */ 1258169689Skan 1259169689Skanstatic void 1260169689Skanfill_hash_bucket (void) 1261169689Skan{ 1262169689Skan basic_block bb; 1263169689Skan rtx insn; 1264169689Skan void **slot; 1265169689Skan p_hash_bucket bucket; 1266169689Skan struct hash_bucket_def tmp_bucket; 1267169689Skan p_hash_elem elem; 1268169689Skan unsigned long insn_idx; 1269169689Skan 1270169689Skan insn_idx = 0; 1271169689Skan FOR_EACH_BB (bb) 1272169689Skan { 1273169689Skan FOR_BB_INSNS_REVERSE (bb, insn) 1274169689Skan { 1275169689Skan if (!ABSTRACTABLE_INSN_P (insn)) 1276169689Skan continue; 1277169689Skan 1278169689Skan /* Compute hash value for INSN. */ 1279169689Skan tmp_bucket.hash = compute_hash (insn); 1280169689Skan 1281169689Skan /* Select the hash group. */ 1282169689Skan bucket = htab_find (hash_buckets, &tmp_bucket); 1283169689Skan 1284169689Skan if (!bucket) 1285169689Skan { 1286169689Skan /* Create a new hash group. */ 1287169689Skan bucket = (p_hash_bucket) xcalloc (1, 1288169689Skan sizeof (struct hash_bucket_def)); 1289169689Skan bucket->hash = tmp_bucket.hash; 1290169689Skan bucket->seq_candidates = NULL; 1291169689Skan 1292169689Skan slot = htab_find_slot (hash_buckets, &tmp_bucket, INSERT); 1293169689Skan *slot = bucket; 1294169689Skan } 1295169689Skan 1296169689Skan /* Create new list for storing sequence candidates. */ 1297169689Skan if (!bucket->seq_candidates) 1298169689Skan bucket->seq_candidates = htab_create (HASH_INIT, 1299169689Skan htab_hash_elem, 1300169689Skan htab_eq_elem, 1301169689Skan htab_del_elem); 1302169689Skan 1303169689Skan elem = (p_hash_elem) xcalloc (1, sizeof (struct hash_elem_def)); 1304169689Skan elem->insn = insn; 1305169689Skan elem->idx = insn_idx; 1306169689Skan elem->length = get_attr_length (insn); 1307169689Skan 1308169689Skan /* Insert INSN into BUCKET hash bucket. */ 1309169689Skan slot = htab_find_slot (bucket->seq_candidates, elem, INSERT); 1310169689Skan *slot = elem; 1311169689Skan 1312169689Skan insn_idx++; 1313169689Skan } 1314169689Skan } 1315169689Skan} 1316169689Skan 1317169689Skan/* Computes the cost of calling sequence and the cost of return. */ 1318169689Skan 1319169689Skanstatic void 1320169689Skancompute_init_costs (void) 1321169689Skan{ 1322169689Skan rtx rtx_jump, rtx_store, rtx_return, reg, label; 1323169689Skan basic_block bb; 1324169689Skan 1325169689Skan FOR_EACH_BB (bb) 1326169689Skan if (BB_HEAD (bb)) 1327169689Skan break; 1328169689Skan 1329169689Skan label = block_label (bb); 1330169689Skan reg = gen_rtx_REG (Pmode, 0); 1331169689Skan 1332169689Skan /* Pattern for indirect jump. */ 1333169689Skan rtx_jump = gen_indirect_jump (reg); 1334169689Skan 1335169689Skan /* Pattern for storing address. */ 1336169689Skan rtx_store = gen_rtx_SET (VOIDmode, reg, gen_symbol_ref_rtx_for_label (label)); 1337169689Skan 1338169689Skan /* Pattern for return insn. */ 1339169689Skan rtx_return = gen_jump (label); 1340169689Skan 1341169689Skan /* The cost of jump. */ 1342169689Skan seq_jump_cost = compute_rtx_cost (make_jump_insn_raw (rtx_jump)); 1343169689Skan 1344169689Skan /* The cost of calling sequence. */ 1345169689Skan seq_call_cost = seq_jump_cost + compute_rtx_cost (make_insn_raw (rtx_store)); 1346169689Skan 1347169689Skan /* The cost of return. */ 1348169689Skan seq_return_cost = compute_rtx_cost (make_jump_insn_raw (rtx_return)); 1349169689Skan 1350169689Skan /* Simple heuristic for minimal sequence cost. */ 1351169689Skan seq_call_cost = (int)(seq_call_cost * (double)SEQ_CALL_COST_MULTIPLIER); 1352169689Skan} 1353169689Skan 1354169689Skan/* Finds equivalent insn sequences in the current function and retains only one 1355169689Skan instance of them which is turned into a pseudo-function. The additional 1356169689Skan copies are erased and replaced by pseudo-calls to the retained sequence. */ 1357169689Skan 1358169689Skanstatic void 1359169689Skanrtl_seqabstr (void) 1360169689Skan{ 1361169689Skan int iter; 1362169689Skan 1363169689Skan /* Create a hash list for COLLECT_PATTERN_SEQS. */ 1364169689Skan hash_buckets = htab_create (HASH_INIT, htab_hash_bucket , htab_eq_bucket , 1365169689Skan htab_del_bucket); 1366169689Skan fill_hash_bucket (); 1367169689Skan 1368169689Skan /* Compute the common cost of abstraction. */ 1369169689Skan compute_init_costs (); 1370169689Skan 1371169689Skan /* Build an initial set of pattern sequences from the current function. */ 1372169689Skan collect_pattern_seqs (); 1373169689Skan dump_pattern_seqs (); 1374169689Skan 1375169689Skan /* Iterate until there are no sequences to abstract. */ 1376169689Skan for (iter = 1;; iter++) 1377169689Skan { 1378169689Skan /* Recompute gain for sequences if necessary and select sequence with 1379169689Skan biggest gain. */ 1380169689Skan recompute_gain (); 1381169689Skan if (!pattern_seqs) 1382169689Skan break; 1383169689Skan dump_best_pattern_seq (iter); 1384169689Skan /* Update the cached info of the other sequences and force gain 1385169689Skan recomputation where needed. */ 1386169689Skan update_pattern_seqs (); 1387169689Skan /* Turn best sequences into pseudo-functions and -calls. */ 1388169689Skan abstract_best_seq (); 1389169689Skan } 1390169689Skan 1391169689Skan /* Cleanup hash tables. */ 1392169689Skan htab_delete (hash_buckets); 1393169689Skan 1394169689Skan if (iter > 1) 1395169689Skan { 1396169689Skan /* Update notes. */ 1397169689Skan count_or_remove_death_notes (NULL, 1); 1398169689Skan 1399169689Skan life_analysis (PROP_DEATH_NOTES | PROP_SCAN_DEAD_CODE 1400169689Skan | PROP_KILL_DEAD_CODE); 1401169689Skan 1402169689Skan /* Extra cleanup. */ 1403169689Skan cleanup_cfg (CLEANUP_EXPENSIVE | 1404169689Skan CLEANUP_UPDATE_LIFE | 1405169689Skan (flag_crossjumping ? CLEANUP_CROSSJUMP : 0)); 1406169689Skan } 1407169689Skan} 1408169689Skan 1409169689Skan/* The gate function for TREE_OPT_PASS. */ 1410169689Skan 1411169689Skanstatic bool 1412169689Skangate_rtl_seqabstr (void) 1413169689Skan{ 1414169689Skan return flag_rtl_seqabstr; 1415169689Skan} 1416169689Skan 1417169689Skan/* The entry point of the sequence abstraction algorithm. */ 1418169689Skan 1419169689Skanstatic unsigned int 1420169689Skanrest_of_rtl_seqabstr (void) 1421169689Skan{ 1422169689Skan life_analysis (PROP_DEATH_NOTES | PROP_SCAN_DEAD_CODE | PROP_KILL_DEAD_CODE); 1423169689Skan 1424169689Skan cleanup_cfg (CLEANUP_EXPENSIVE | 1425169689Skan CLEANUP_UPDATE_LIFE | 1426169689Skan (flag_crossjumping ? CLEANUP_CROSSJUMP : 0)); 1427169689Skan 1428169689Skan /* Abstract out common insn sequences. */ 1429169689Skan rtl_seqabstr (); 1430169689Skan return 0; 1431169689Skan} 1432169689Skan 1433169689Skanstruct tree_opt_pass pass_rtl_seqabstr = { 1434169689Skan "seqabstr", /* name */ 1435169689Skan gate_rtl_seqabstr, /* gate */ 1436169689Skan rest_of_rtl_seqabstr, /* execute */ 1437169689Skan NULL, /* sub */ 1438169689Skan NULL, /* next */ 1439169689Skan 0, /* static_pass_number */ 1440169689Skan TV_SEQABSTR, /* tv_id */ 1441169689Skan 0, /* properties_required */ 1442169689Skan 0, /* properties_provided */ 1443169689Skan 0, /* properties_destroyed */ 1444169689Skan 0, /* todo_flags_start */ 1445169689Skan TODO_dump_func | 1446169689Skan TODO_ggc_collect, /* todo_flags_finish */ 1447169689Skan 'Q' /* letter */ 1448169689Skan}; 1449