--- /dev/null
+/* RTL factoring (sequence abstraction).
+ Copyright (C) 2004, 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "rtl.h"
+#include "obstack.h"
+#include "basic-block.h"
+#include "resource.h"
+#include "flags.h"
+#include "ggc.h"
+#include "regs.h"
+#include "params.h"
+#include "expr.h"
+#include "tm_p.h"
+#include "tree-pass.h"
+#include "tree-flow.h"
+#include "timevar.h"
+#include "output.h"
+#include "df.h"
+#include "addresses.h"
+
+/* Sequence abstraction:
+
+ It is a size optimization method. The main idea of this technique is to
+ find identical sequences of code, which can be turned into procedures and
+ then replace all occurrences with calls to the newly created subroutine.
+ It is kind of an opposite of function inlining.
+
+ There are four major parts of this file:
+
+ sequence fingerprint
+ In order to avoid the comparison of every insn with every other, hash
+ value will be designed for every insn by COMPUTE_HASH.
+ These hash values are used for grouping the sequence candidates. So
+ we only need to compare every insn with every other in same hash group.
+
+ FILL_HASH_BUCKET creates all hash values and stores into HASH_BUCKETS.
+ The result is used by COLLECT_PATTERN_SEQS.
+
+ code matching
+ In code matching the algorithm compares every two possible sequence
+ candidates which last insns are in the same hash group. If these
+ sequences are identical they will be stored and do further searches for
+ finding more sequences which are identical with the first one.
+
+ COLLECT_PATTERN_SEQS does the code matching and stores the results into
+ PATTERN_SEQS.
+
+ gain computation
+ This part computes the gain of abstraction which could be archived when
+ turning the pattern sequence into a pseudo-function and its matching
+ sequences into pseudo-calls. After it the most effective sequences will
+ be marked for abstraction.
+
+ RECOMPUTE_GAIN does the gain computation. The sequences with the maximum
+ gain is on the top of PATTERN_SEQS.
+
+ abstract code
+ This part turns the pattern sequence into a pseudo-function and its
+ matching sequences into pseudo-calls.
+
+ ABSTRACT_BEST_SEQ does the code merging.
+
+
+ C code example:
+
+ // Original source // After sequence abstraction
+ { {
+ void *jump_label;
+ ... ...
+ jump_label = &&exit_0;
+ entry_0:
+ I0; I0;
+ I1; I1;
+ I2; I2;
+ I3; I3;
+ goto *jump_label;
+ exit_0:
+ ... ...
+ jump_label = &&exit_1;
+ goto entry_0;
+ I0;
+ I1;
+ I2;
+ I3;
+ exit_1:
+ ... ...
+ jump_label = &&exit_2;
+ goto entry_0;
+ I0;
+ I1;
+ I2;
+ I3;
+ exit_2:
+ ... ...
+ jump_label = &&exit_3;
+ goto entry_0;
+ I0;
+ I1;
+ I2;
+ I3;
+ exit_3:
+ ... ...
+ } }
+
+
+ TODO:
+ - Use REG_ALLOC_ORDER when choosing link register.
+ - Handle JUMP_INSNs. Also handle volatile function calls (handle them
+ similar to unconditional jumps.)
+ - Test command line option -fpic.
+*/
+
+/* Predicate yielding nonzero iff X is an abstractable insn. Non-jump insns are
+ abstractable. */
+#define ABSTRACTABLE_INSN_P(X) (INSN_P (X) && !JUMP_P (X))
+
+/* First parameter of the htab_create function call. */
+#define HASH_INIT 1023
+
+/* Multiplier for cost of sequence call to avoid abstracting short
+ sequences. */
+#ifndef SEQ_CALL_COST_MULTIPLIER
+#define SEQ_CALL_COST_MULTIPLIER 2
+#endif
+
+/* Recomputes the cost of MSEQ pattern/matching sequence. */
+#define RECOMPUTE_COST(SEQ) \
+{ \
+ int l; \
+ rtx x = SEQ->insn; \
+ SEQ->cost = 0; \
+ for (l = 0; l < SEQ->abstracted_length; l++) \
+ { \
+ SEQ->cost += compute_rtx_cost (x); \
+ x = prev_insn_in_block (x); \
+ } \
+}
+
+/* A sequence matching a pattern sequence. */
+typedef struct matching_seq_def
+{
+ /* The last insn in the matching sequence. */
+ rtx insn;
+
+ /* Index of INSN instruction. */
+ unsigned long idx;
+
+ /* The number of insns matching in this sequence and the pattern sequence.
+ */
+ int matching_length;
+
+ /* The number of insns selected to abstract from this sequence. Less than
+ or equal to MATCHING_LENGTH. */
+ int abstracted_length;
+
+ /* The cost of the sequence. */
+ int cost;
+
+ /* The next sequence in the chain matching the same pattern. */
+ struct matching_seq_def *next_matching_seq;
+} *matching_seq;
+
+
+/* A pattern instruction sequence. */
+typedef struct pattern_seq_def
+{
+ /* The last insn in the pattern sequence. */
+ rtx insn;
+
+ /* Index of INSN instruction. */
+ unsigned long idx;
+
+ /* The gain of transforming the pattern sequence into a pseudo-function and
+ the matching sequences into pseudo-calls. */
+ int gain;
+
+ /* The maximum of the ABSTRACTED_LENGTH of the matching sequences. */
+ int abstracted_length;
+
+ /* The cost of the sequence. */
+ int cost;
+
+ /* The register used to hold the return address during the pseudo-call. */
+ rtx link_reg;
+
+ /* The sequences matching this pattern. */
+ matching_seq matching_seqs;
+
+ /* The next pattern sequence in the chain. */
+ struct pattern_seq_def *next_pattern_seq;
+} *pattern_seq;
+
+
+/* A block of a pattern sequence. */
+typedef struct seq_block_def
+{
+ /* The number of insns in the block. */
+ int length;
+
+ /* The code_label of the block. */
+ rtx label;
+
+ /* The sequences entering the pattern sequence at LABEL. */
+ matching_seq matching_seqs;
+
+ /* The next block in the chain. The blocks are sorted by LENGTH in
+ ascending order. */
+ struct seq_block_def *next_seq_block;
+} *seq_block;
+
+/* Contains same sequence candidates for further searching. */
+typedef struct hash_bucket_def
+{
+ /* The hash value of the group. */
+ unsigned int hash;
+
+ /* List of sequence candidates. */
+ htab_t seq_candidates;
+} *p_hash_bucket;
+typedef const struct hash_bucket_def *const_p_hash_bucket;
+
+/* Contains the last insn of the sequence, and its index value. */
+typedef struct hash_elem_def
+{
+ /* Unique index; ordered by FILL_HASH_BUCKET. */
+ unsigned long idx;
+
+ /* The last insn in the sequence. */
+ rtx insn;
+
+ /* The cached length of the insn. */
+ int length;
+} *p_hash_elem;
+typedef const struct hash_elem_def *const_p_hash_elem;
+
+/* The list of same sequence candidates. */
+static htab_t hash_buckets;
+
+/* The pattern sequences collected from the current functions. */
+static pattern_seq pattern_seqs;
+
+/* The blocks of the current pattern sequence. */
+static seq_block seq_blocks;
+
+/* Cost of calling sequence. */
+static int seq_call_cost;
+
+/* Cost of jump. */
+static int seq_jump_cost;
+
+/* Cost of returning. */
+static int seq_return_cost;
+
+/* Returns the first insn preceding INSN for which INSN_P is true and belongs to
+ the same basic block. Returns NULL_RTX if no such insn can be found. */
+
+static rtx
+prev_insn_in_block (rtx insn)
+{
+ basic_block bb = BLOCK_FOR_INSN (insn);
+
+ if (!bb)
+ return NULL_RTX;
+
+ while (insn != BB_HEAD (bb))
+ {
+ insn = PREV_INSN (insn);
+ if (INSN_P (insn))
+ return insn;
+ }
+ return NULL_RTX;
+}
+
+/* Returns the hash value of INSN. */
+
+static unsigned int
+compute_hash (rtx insn)
+{
+ unsigned int hash = 0;
+ rtx prev;
+
+ hash = INSN_CODE (insn) * 100;
+
+ prev = prev_insn_in_block (insn);
+ if (prev)
+ hash += INSN_CODE (prev);
+
+ return hash;
+}
+
+/* Compute the cost of INSN rtx for abstraction. */
+
+static int
+compute_rtx_cost (rtx insn)
+{
+ struct hash_bucket_def tmp_bucket;
+ p_hash_bucket bucket;
+ struct hash_elem_def tmp_elem;
+ p_hash_elem elem = NULL;
+ int cost = -1;
+
+ /* Compute hash value for INSN. */
+ tmp_bucket.hash = compute_hash (insn);
+
+ /* Select the hash group. */
+ bucket = (p_hash_bucket) htab_find (hash_buckets, &tmp_bucket);
+
+ if (bucket)
+ {
+ tmp_elem.insn = insn;
+
+ /* Select the insn. */
+ elem = (p_hash_elem) htab_find (bucket->seq_candidates, &tmp_elem);
+
+ /* If INSN is parsed the cost will be the cached length. */
+ if (elem)
+ cost = elem->length;
+ }
+
+ /* If we can't parse the INSN cost will be the instruction length. */
+ if (cost == -1)
+ {
+ cost = get_attr_length (insn);
+
+ /* Cache the length. */
+ if (elem)
+ elem->length = cost;
+ }
+
+ /* If we can't get an accurate estimate for a complex instruction,
+ assume that it has the same cost as a single fast instruction. */
+ return cost != 0 ? cost : COSTS_N_INSNS (1);
+}
+
+/* Determines the number of common insns in the sequences ending in INSN1 and
+ INSN2. Returns with LEN number of common insns and COST cost of sequence.
+*/
+
+static void
+matching_length (rtx insn1, rtx insn2, int* len, int* cost)
+{
+ rtx x1;
+ rtx x2;
+
+ x1 = insn1;
+ x2 = insn2;
+ *len = 0;
+ *cost = 0;
+ while (x1 && x2 && (x1 != insn2) && (x2 != insn1)
+ && rtx_equal_p (PATTERN (x1), PATTERN (x2)))
+ {
+ (*len)++;
+ (*cost) += compute_rtx_cost (x1);
+ x1 = prev_insn_in_block (x1);
+ x2 = prev_insn_in_block (x2);
+ }
+}
+
+/* Adds E0 as a pattern sequence to PATTERN_SEQS with E1 as a matching
+ sequence. */
+
+static void
+match_seqs (p_hash_elem e0, p_hash_elem e1)
+{
+ int len;
+ int cost;
+ matching_seq mseq, p_prev, p_next;
+
+ /* Determines the cost of the sequence and return without doing anything
+ if it is too small to produce any gain. */
+ matching_length (e0->insn, e1->insn, &len, &cost);
+ if (cost <= seq_call_cost)
+ return;
+
+ /* Prepend a new PATTERN_SEQ to PATTERN_SEQS if the last pattern sequence
+ does not end in E0->INSN. This assumes that once the E0->INSN changes
+ the old value will never appear again. */
+ if (!pattern_seqs || pattern_seqs->insn != e0->insn)
+ {
+ pattern_seq pseq =
+ (pattern_seq) xmalloc (sizeof (struct pattern_seq_def));
+ pseq->insn = e0->insn;
+ pseq->idx = e0->idx;
+ pseq->gain = 0; /* Set to zero to force recomputing. */
+ pseq->abstracted_length = 0;
+ pseq->cost = 0;
+ pseq->link_reg = NULL_RTX;
+ pseq->matching_seqs = NULL;
+ pseq->next_pattern_seq = pattern_seqs;
+ pattern_seqs = pseq;
+ }
+
+ /* Find the position of E1 in the matching sequences list. */
+ p_prev = NULL;
+ p_next = pattern_seqs->matching_seqs;
+ while (p_next && p_next->idx < e1->idx)
+ {
+ p_prev = p_next;
+ p_next = p_next->next_matching_seq;
+ }
+
+ /* Add a new E1 matching sequence to the pattern sequence. We know that
+ it ends in E0->INSN. */
+ mseq = (matching_seq) xmalloc (sizeof (struct matching_seq_def));
+ mseq->insn = e1->insn;
+ mseq->idx = e1->idx;
+ mseq->matching_length = len;
+ mseq->abstracted_length = 0;
+ mseq->cost = cost;
+
+ if (p_prev == NULL)
+ pattern_seqs->matching_seqs = mseq;
+ else
+ p_prev->next_matching_seq = mseq;
+ mseq->next_matching_seq = p_next;
+}
+
+/* Collects all pattern sequences and their matching sequences and puts them
+ into PATTERN_SEQS. */
+
+static void
+collect_pattern_seqs (void)
+{
+ htab_iterator hti0, hti1, hti2;
+ p_hash_bucket hash_bucket;
+ p_hash_elem e0, e1;
+#if defined STACK_REGS || defined HAVE_cc0
+ basic_block bb;
+ bitmap_head dont_collect;
+
+ /* Extra initialization step to ensure that no stack registers (if present)
+ or cc0 code (if present) are live across abnormal edges.
+ Set a flag in DONT_COLLECT for an insn if a stack register is live
+ after the insn or the insn is cc0 setter or user. */
+ bitmap_initialize (&dont_collect, NULL);
+
+#ifdef STACK_REGS
+ FOR_EACH_BB (bb)
+ {
+ regset_head live;
+ rtx insn;
+ rtx prev;
+
+ /* Initialize liveness propagation. */
+ INIT_REG_SET (&live);
+ bitmap_copy (&live, DF_LR_OUT (bb));
+ df_simulate_initialize_backwards (bb, &live);
+
+ /* Propagate liveness info and mark insns where a stack reg is live. */
+ insn = BB_END (bb);
+ for (insn = BB_END (bb); ; insn = prev)
+ {
+ prev = PREV_INSN (insn);
+ if (INSN_P (insn))
+ {
+ int reg;
+ for (reg = FIRST_STACK_REG; reg <= LAST_STACK_REG; reg++)
+ {
+ if (REGNO_REG_SET_P (&live, reg))
+ {
+ bitmap_set_bit (&dont_collect, INSN_UID (insn));
+ break;
+ }
+ }
+
+ }
+ if (insn == BB_HEAD (bb))
+ break;
+ df_simulate_one_insn_backwards (bb, insn, &live);
+ insn = prev;
+ }
+
+ /* Free unused data. */
+ CLEAR_REG_SET (&live);
+ }
+#endif
+
+#ifdef HAVE_cc0
+ /* Mark CC0 setters and users as ineligible for collection into sequences.
+ This is an over-conservative fix, since it is OK to include
+ a cc0_setter, but only if we also include the corresponding cc0_user,
+ and vice versa. */
+ FOR_EACH_BB (bb)
+ {
+ rtx insn;
+ rtx next_tail;
+
+ next_tail = NEXT_INSN (BB_END (bb));
+
+ for (insn = BB_HEAD (bb); insn != next_tail; insn = NEXT_INSN (insn))
+ {
+ if (INSN_P (insn) && reg_mentioned_p (cc0_rtx, PATTERN (insn)))
+ bitmap_set_bit (&dont_collect, INSN_UID (insn));
+ }
+ }
+#endif
+
+#endif /* defined STACK_REGS || defined HAVE_cc0 */
+
+ /* Initialize PATTERN_SEQS to empty. */
+ pattern_seqs = 0;
+
+ /* Try to match every abstractable insn with every other insn in the same
+ HASH_BUCKET. */
+
+ FOR_EACH_HTAB_ELEMENT (hash_buckets, hash_bucket, p_hash_bucket, hti0)
+ if (htab_elements (hash_bucket->seq_candidates) > 1)
+ FOR_EACH_HTAB_ELEMENT (hash_bucket->seq_candidates, e0, p_hash_elem, hti1)
+ FOR_EACH_HTAB_ELEMENT (hash_bucket->seq_candidates, e1, p_hash_elem,
+ hti2)
+ if (e0 != e1
+#if defined STACK_REGS || defined HAVE_cc0
+ && !bitmap_bit_p (&dont_collect, INSN_UID (e0->insn))
+ && !bitmap_bit_p (&dont_collect, INSN_UID (e1->insn))
+#endif
+ )
+ match_seqs (e0, e1);
+#if defined STACK_REGS || defined HAVE_cc0
+ /* Free unused data. */
+ bitmap_clear (&dont_collect);
+#endif
+}
+
+/* Transforms a regset to a HARD_REG_SET. Every hard register in REGS is added
+ to hregs. Additionally, the hard counterpart of every renumbered pseudo
+ register is also added. */
+
+static void
+renumbered_reg_set_to_hard_reg_set (HARD_REG_SET * hregs, regset regs)
+{
+ int r;
+
+ REG_SET_TO_HARD_REG_SET (*hregs, regs);
+ for (r = FIRST_PSEUDO_REGISTER; r < max_regno; r++)
+ if (REGNO_REG_SET_P (regs, r) && reg_renumber[r] >= 0)
+ SET_HARD_REG_BIT (*hregs, reg_renumber[r]);
+}
+
+/* Clears the bits in REGS for all registers, which are live in the sequence
+ give by its last INSN and its LENGTH. */
+
+static void
+clear_regs_live_in_seq (HARD_REG_SET * regs, rtx insn, int length)
+{
+ basic_block bb;
+ regset_head live;
+ HARD_REG_SET hlive;
+ rtx x;
+ int i;
+
+ /* Initialize liveness propagation. */
+ bb = BLOCK_FOR_INSN (insn);
+ INIT_REG_SET (&live);
+ bitmap_copy (&live, DF_LR_OUT (bb));
+ df_simulate_initialize_backwards (bb, &live);
+
+ /* Propagate until INSN if found. */
+ for (x = BB_END (bb); x != insn; x = PREV_INSN (x))
+ df_simulate_one_insn_backwards (bb, x, &live);
+
+ /* Clear registers live after INSN. */
+ renumbered_reg_set_to_hard_reg_set (&hlive, &live);
+ AND_COMPL_HARD_REG_SET (*regs, hlive);
+
+ /* Clear registers live in and before the sequence. */
+ for (i = 0; i < length;)
+ {
+ rtx prev = PREV_INSN (x);
+ df_simulate_one_insn_backwards (bb, x, &live);
+
+ if (INSN_P (x))
+ {
+ renumbered_reg_set_to_hard_reg_set (&hlive, &live);
+ AND_COMPL_HARD_REG_SET (*regs, hlive);
+ i++;
+ }
+
+ x = prev;
+ }
+
+ /* Free unused data. */
+ CLEAR_REG_SET (&live);
+}
+
+/* Computes the gain of turning PSEQ into a pseudo-function and its matching
+ sequences into pseudo-calls. Also computes and caches the number of insns to
+ abstract from the matching sequences. */
+
+static void
+recompute_gain_for_pattern_seq (pattern_seq pseq)
+{
+ matching_seq mseq;
+ rtx x;
+ int i;
+ int hascall;
+ HARD_REG_SET linkregs;
+
+ /* Initialize data. */
+ SET_HARD_REG_SET (linkregs);
+ pseq->link_reg = NULL_RTX;
+ pseq->abstracted_length = 0;
+
+ pseq->gain = -(seq_call_cost - seq_jump_cost + seq_return_cost);
+
+ /* Determine ABSTRACTED_LENGTH and COST for matching sequences of PSEQ.
+ ABSTRACTED_LENGTH may be less than MATCHING_LENGTH if sequences in the
+ same block overlap. */
+
+ for (mseq = pseq->matching_seqs; mseq; mseq = mseq->next_matching_seq)
+ {
+ /* Determine ABSTRACTED_LENGTH. */
+ if (mseq->next_matching_seq)
+ mseq->abstracted_length = (int)(mseq->next_matching_seq->idx -
+ mseq->idx);
+ else
+ mseq->abstracted_length = mseq->matching_length;
+
+ if (mseq->abstracted_length > mseq->matching_length)
+ mseq->abstracted_length = mseq->matching_length;
+
+ /* Compute the cost of sequence. */
+ RECOMPUTE_COST (mseq);
+
+ /* If COST is big enough registers live in this matching sequence
+ should not be used as a link register. Also set ABSTRACTED_LENGTH
+ of PSEQ. */
+ if (mseq->cost > seq_call_cost)
+ {
+ clear_regs_live_in_seq (&linkregs, mseq->insn,
+ mseq->abstracted_length);
+ if (mseq->abstracted_length > pseq->abstracted_length)
+ pseq->abstracted_length = mseq->abstracted_length;
+ }
+ }
+
+ /* Modify ABSTRACTED_LENGTH of PSEQ if pattern sequence overlaps with one
+ of the matching sequences. */
+ for (mseq = pseq->matching_seqs; mseq; mseq = mseq->next_matching_seq)
+ {
+ x = pseq->insn;
+ for (i = 0; (i < pseq->abstracted_length) && (x != mseq->insn); i++)
+ x = prev_insn_in_block (x);
+ pseq->abstracted_length = i;
+ }
+
+ /* Compute the cost of pattern sequence. */
+ RECOMPUTE_COST (pseq);
+
+ /* No gain if COST is too small. */
+ if (pseq->cost <= seq_call_cost)
+ {
+ pseq->gain = -1;
+ return;
+ }
+
+ /* Ensure that no matching sequence is longer than the pattern sequence. */
+ for (mseq = pseq->matching_seqs; mseq; mseq = mseq->next_matching_seq)
+ {
+ if (mseq->abstracted_length > pseq->abstracted_length)
+ {
+ mseq->abstracted_length = pseq->abstracted_length;
+ RECOMPUTE_COST (mseq);
+ }
+ /* Once the length is stabilizing the gain can be calculated. */
+ if (mseq->cost > seq_call_cost)
+ pseq->gain += mseq->cost - seq_call_cost;
+ }
+
+ /* No need to do further work if there is no gain. */
+ if (pseq->gain <= 0)
+ return;
+
+ /* Should not use registers live in the pattern sequence as link register.
+ */
+ clear_regs_live_in_seq (&linkregs, pseq->insn, pseq->abstracted_length);
+
+ /* Determine whether pattern sequence contains a call_insn. */
+ hascall = 0;
+ x = pseq->insn;
+ for (i = 0; i < pseq->abstracted_length; i++)
+ {
+ if (CALL_P (x))
+ {
+ hascall = 1;
+ break;
+ }
+ x = prev_insn_in_block (x);
+ }
+
+ /* Should not use a register as a link register if - it is a fixed
+ register, or - the sequence contains a call insn and the register is a
+ call used register, or - the register needs to be saved if used in a
+ function but was not used before (since saving it can invalidate already
+ computed frame pointer offsets), or - the register cannot be used as a
+ base register. */
+
+ for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+ if (fixed_regs[i]
+#ifdef REGNO_OK_FOR_INDIRECT_JUMP_P
+ || (!REGNO_OK_FOR_INDIRECT_JUMP_P (i, Pmode))
+#else
+ || (!ok_for_base_p_1 (i, Pmode, MEM, SCRATCH))
+ || (!reg_class_subset_p (REGNO_REG_CLASS (i),
+ base_reg_class (VOIDmode, MEM, SCRATCH)))
+#endif
+ || (hascall && call_used_regs[i])
+ || (!call_used_regs[i] && !df_regs_ever_live_p (i)))
+ CLEAR_HARD_REG_BIT (linkregs, i);
+
+ /* Find an appropriate register to be used as the link register. */
+ for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+ if (TEST_HARD_REG_BIT (linkregs, i))
+ {
+ pseq->link_reg = gen_rtx_REG (Pmode, i);
+ break;
+ }
+
+ /* Abstraction is not possible if no link register is available, so set
+ gain to 0. */
+ if (!pseq->link_reg)
+ pseq->gain = 0;
+}
+
+/* Deallocates memory occupied by PSEQ and its matching seqs. */
+
+static void
+free_pattern_seq (pattern_seq pseq)
+{
+ while (pseq->matching_seqs)
+ {
+ matching_seq mseq = pseq->matching_seqs;
+ pseq->matching_seqs = mseq->next_matching_seq;
+ free (mseq);
+ }
+ free (pseq);
+}
+
+
+/* Computes the gain for pattern sequences. Pattern sequences producing no gain
+ are deleted. The pattern sequence with the biggest gain is moved to the first
+ place of PATTERN_SEQS. */
+
+static void
+recompute_gain (void)
+{
+ pattern_seq *pseq;
+ int maxgain;
+
+ maxgain = 0;
+ for (pseq = &pattern_seqs; *pseq;)
+ {
+ if ((*pseq)->gain <= 0)
+ recompute_gain_for_pattern_seq (*pseq);
+
+ if ((*pseq)->gain > 0)
+ {
+ if ((*pseq)->gain > maxgain)
+ {
+ pattern_seq temp = *pseq;
+ (*pseq) = temp->next_pattern_seq;
+ temp->next_pattern_seq = pattern_seqs;
+ pattern_seqs = temp;
+ maxgain = pattern_seqs->gain;
+ }
+ else
+ {
+ pseq = &(*pseq)->next_pattern_seq;
+ }
+ }
+ else
+ {
+ pattern_seq temp = *pseq;
+ *pseq = temp->next_pattern_seq;
+ free_pattern_seq (temp);
+ }
+ }
+}
+
+/* Updated those pattern sequences and matching sequences, which overlap with
+ the sequence given by INSN and LEN. Deletes sequences shrinking below a
+ limit. */
+
+static void
+erase_from_pattern_seqs (rtx insn, int len)
+{
+ pattern_seq *pseq;
+ matching_seq *mseq;
+ rtx x;
+ int plen, mlen;
+ int pcost, mcost;
+
+ while (len > 0)
+ {
+ for (pseq = &pattern_seqs; *pseq;)
+ {
+ plen = 0;
+ pcost = 0;
+ for (x = (*pseq)->insn; x && (x != insn);
+ x = prev_insn_in_block (x))
+ {
+ plen++;
+ pcost += compute_rtx_cost (x);
+ }
+
+ if (pcost <= seq_call_cost)
+ {
+ pattern_seq temp = *pseq;
+ *pseq = temp->next_pattern_seq;
+ free_pattern_seq (temp);
+ }
+ else
+ {
+ for (mseq = &(*pseq)->matching_seqs; *mseq;)
+ {
+ mlen = 0;
+ mcost = 0;
+ for (x = (*mseq)->insn;
+ x && (x != insn) && (mlen < plen)
+ && (mlen < (*mseq)->matching_length);
+ x = prev_insn_in_block (x))
+ {
+ mlen++;
+ mcost += compute_rtx_cost (x);
+ }
+
+ if (mcost <= seq_call_cost)
+ {
+ matching_seq temp = *mseq;
+ *mseq = temp->next_matching_seq;
+ free (temp);
+ /* Set to 0 to force gain recomputation. */
+ (*pseq)->gain = 0;
+ }
+ else
+ {
+ if (mlen < (*mseq)->matching_length)
+ {
+ (*mseq)->cost = mcost;
+ (*mseq)->matching_length = mlen;
+ /* Set to 0 to force gain recomputation. */
+ (*pseq)->gain = 0;
+ }
+ mseq = &(*mseq)->next_matching_seq;
+ }
+ }
+
+ pseq = &(*pseq)->next_pattern_seq;
+ }
+ }
+
+ len--;
+ insn = prev_insn_in_block (insn);
+ }
+}
+
+/* Updates those pattern sequences and matching sequences, which overlap with
+ the pattern sequence with the biggest gain and its matching sequences. */
+
+static void
+update_pattern_seqs (void)
+{
+ pattern_seq bestpseq;
+ matching_seq mseq;
+
+ bestpseq = pattern_seqs;
+ pattern_seqs = bestpseq->next_pattern_seq;
+
+ for (mseq = bestpseq->matching_seqs; mseq; mseq = mseq->next_matching_seq)
+ if (mseq->cost > seq_call_cost)
+ erase_from_pattern_seqs (mseq->insn, mseq->abstracted_length);
+ erase_from_pattern_seqs (bestpseq->insn, bestpseq->abstracted_length);
+
+ bestpseq->next_pattern_seq = pattern_seqs;
+ pattern_seqs = bestpseq;
+}
+
+/* Groups together those matching sequences of the best pattern sequence, which
+ have the same ABSTRACTED_LENGTH and puts these groups in ascending order.
+ SEQ_BLOCKS contains the result. */
+
+static void
+determine_seq_blocks (void)
+{
+ seq_block sb;
+ matching_seq *mseq;
+ matching_seq m;
+
+ /* Initialize SEQ_BLOCKS to empty. */
+ seq_blocks = 0;
+
+ /* Process all matching sequences. */
+ for (mseq = &pattern_seqs->matching_seqs; *mseq;)
+ {
+ /* Deal only with matching sequences being long enough. */
+ if ((*mseq)->cost <= seq_call_cost)
+ {
+ mseq = &(*mseq)->next_matching_seq;
+ continue;
+ }
+
+ /* Ensure that SB contains a seq_block with the appropriate length.
+ Insert a new seq_block if necessary. */
+ if (!seq_blocks || ((*mseq)->abstracted_length < seq_blocks->length))
+ {
+ sb = (seq_block) xmalloc (sizeof (struct seq_block_def));
+ sb->length = (*mseq)->abstracted_length;
+ sb->label = NULL_RTX;
+ sb->matching_seqs = 0;
+ sb->next_seq_block = seq_blocks;
+ seq_blocks = sb;
+ }
+ else
+ {
+ for (sb = seq_blocks; sb; sb = sb->next_seq_block)
+ {
+ if ((*mseq)->abstracted_length == sb->length)
+ break;
+ if (!sb->next_seq_block
+ || ((*mseq)->abstracted_length <
+ sb->next_seq_block->length))
+ {
+ seq_block temp =
+ (seq_block) xmalloc (sizeof (struct seq_block_def));
+ temp->length = (*mseq)->abstracted_length;
+ temp->label = NULL_RTX;
+ temp->matching_seqs = 0;
+ temp->next_seq_block = sb->next_seq_block;
+ sb->next_seq_block = temp;
+ }
+ }
+ }
+
+ /* Remove the matching sequence from the linked list of the pattern
+ sequence and link it to SB. */
+ m = *mseq;
+ *mseq = m->next_matching_seq;
+ m->next_matching_seq = sb->matching_seqs;
+ sb->matching_seqs = m;
+ }
+}
+
+/* Builds a symbol_ref for LABEL. */
+
+static rtx
+gen_symbol_ref_rtx_for_label (const_rtx label)
+{
+ char name[20];
+ rtx sym;
+
+ ASM_GENERATE_INTERNAL_LABEL (name, "L", CODE_LABEL_NUMBER (label));
+ sym = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (name));
+ SYMBOL_REF_FLAGS (sym) = SYMBOL_FLAG_LOCAL;
+ return sym;
+}
+
+/* Splits basic block at the requested insn and rebuilds dataflow. */
+
+static basic_block
+split_block_and_df_analyze (basic_block bb, rtx insn)
+{
+ basic_block next;
+ next = split_block (bb, insn)->dest;
+ df_analyze ();
+ return next;
+}
+
+/* Ensures that INSN is the last insn in its block and returns the block label
+ of the next block. */
+
+static rtx
+block_label_after (rtx insn)
+{
+ basic_block bb = BLOCK_FOR_INSN (insn);
+ if ((insn == BB_END (bb)) && (bb->next_bb != EXIT_BLOCK_PTR))
+ return block_label (bb->next_bb);
+ else
+ return block_label (split_block_and_df_analyze (bb, insn));
+}
+
+/* Ensures that the last insns of the best pattern and its matching sequences
+ are the last insns in their block. Additionally, extends the live set at the
+ end of the pattern sequence with the live sets at the end of the matching
+ sequences. */
+
+static void
+split_blocks_after_seqs (void)
+{
+ seq_block sb;
+ matching_seq mseq;
+
+ block_label_after (pattern_seqs->insn);
+ for (sb = seq_blocks; sb; sb = sb->next_seq_block)
+ {
+ for (mseq = sb->matching_seqs; mseq; mseq = mseq->next_matching_seq)
+ {
+ block_label_after (mseq->insn);
+ IOR_REG_SET (df_get_live_out (BLOCK_FOR_INSN (pattern_seqs->insn)),
+ df_get_live_out (BLOCK_FOR_INSN (mseq->insn)));
+ }
+ }
+}
+
+/* Splits the best pattern sequence according to SEQ_BLOCKS. Emits pseudo-call
+ and -return insns before and after the sequence. */
+
+static void
+split_pattern_seq (void)
+{
+ rtx insn;
+ basic_block bb;
+ rtx retlabel, retjmp, saveinsn;
+ int i;
+ seq_block sb;
+
+ insn = pattern_seqs->insn;
+ bb = BLOCK_FOR_INSN (insn);
+
+ /* Get the label after the sequence. This will be the return address. The
+ label will be referenced using a symbol_ref so protect it from
+ deleting. */
+ retlabel = block_label_after (insn);
+ LABEL_PRESERVE_P (retlabel) = 1;
+
+ /* Emit an indirect jump via the link register after the sequence acting
+ as the return insn. Also emit a barrier and update the basic block. */
+ if (!find_reg_note (BB_END (bb), REG_NORETURN, NULL))
+ retjmp = emit_jump_insn_after (gen_indirect_jump (pattern_seqs->link_reg),
+ BB_END (bb));
+ emit_barrier_after (BB_END (bb));
+
+ /* Replace all outgoing edges with a new one to the block of RETLABEL. */
+ while (EDGE_COUNT (bb->succs) != 0)
+ remove_edge (EDGE_SUCC (bb, 0));
+ make_edge (bb, BLOCK_FOR_INSN (retlabel), EDGE_ABNORMAL);
+
+ /* Split the sequence according to SEQ_BLOCKS and cache the label of the
+ resulting basic blocks. */
+ i = 0;
+ for (sb = seq_blocks; sb; sb = sb->next_seq_block)
+ {
+ for (; i < sb->length; i++)
+ insn = prev_insn_in_block (insn);
+
+ sb->label = block_label (split_block_and_df_analyze (bb, insn));
+ }
+
+ /* Emit an insn saving the return address to the link register before the
+ sequence. */
+ saveinsn = emit_insn_after (gen_move_insn (pattern_seqs->link_reg,
+ gen_symbol_ref_rtx_for_label
+ (retlabel)), BB_END (bb));
+ /* Update liveness info. */
+ SET_REGNO_REG_SET (df_get_live_out (bb),
+ REGNO (pattern_seqs->link_reg));
+}
+
+/* Deletes the insns of the matching sequences of the best pattern sequence and
+ replaces them with pseudo-calls to the pattern sequence. */
+
+static void
+erase_matching_seqs (void)
+{
+ seq_block sb;
+ matching_seq mseq;
+ rtx insn;
+ basic_block bb;
+ rtx retlabel, saveinsn, callinsn;
+ int i;
+
+ for (sb = seq_blocks; sb; sb = sb->next_seq_block)
+ {
+ for (mseq = sb->matching_seqs; mseq; mseq = mseq->next_matching_seq)
+ {
+ insn = mseq->insn;
+ bb = BLOCK_FOR_INSN (insn);
+
+ /* Get the label after the sequence. This will be the return
+ address. The label will be referenced using a symbol_ref so
+ protect it from deleting. */
+ retlabel = block_label_after (insn);
+ LABEL_PRESERVE_P (retlabel) = 1;
+
+ /* Delete the insns of the sequence. */
+ for (i = 0; i < sb->length; i++)
+ insn = prev_insn_in_block (insn);
+ delete_basic_block (split_block_and_df_analyze (bb, insn));
+
+ /* Emit an insn saving the return address to the link register
+ before the deleted sequence. */
+ saveinsn = emit_insn_after (gen_move_insn (pattern_seqs->link_reg,
+ gen_symbol_ref_rtx_for_label
+ (retlabel)),
+ BB_END (bb));
+ BLOCK_FOR_INSN (saveinsn) = bb;
+
+ /* Emit a jump to the appropriate part of the pattern sequence
+ after the save insn. Also update the basic block. */
+ callinsn = emit_jump_insn_after (gen_jump (sb->label), saveinsn);
+ JUMP_LABEL (callinsn) = sb->label;
+ LABEL_NUSES (sb->label)++;
+ BLOCK_FOR_INSN (callinsn) = bb;
+ BB_END (bb) = callinsn;
+
+ /* Maintain control flow and liveness information. */
+ SET_REGNO_REG_SET (df_get_live_out (bb),
+ REGNO (pattern_seqs->link_reg));
+ emit_barrier_after (BB_END (bb));
+ make_single_succ_edge (bb, BLOCK_FOR_INSN (sb->label), 0);
+ IOR_REG_SET (df_get_live_out (bb),
+ df_get_live_in (BLOCK_FOR_INSN (sb->label)));
+
+ make_edge (BLOCK_FOR_INSN (seq_blocks->label),
+ BLOCK_FOR_INSN (retlabel), EDGE_ABNORMAL);
+ }
+ }
+}
+
+/* Deallocates SEQ_BLOCKS and all the matching sequences. */
+
+static void
+free_seq_blocks (void)
+{
+ while (seq_blocks)
+ {
+ seq_block sb = seq_blocks;
+ while (sb->matching_seqs)
+ {
+ matching_seq mseq = sb->matching_seqs;
+ sb->matching_seqs = mseq->next_matching_seq;
+ free (mseq);
+ }
+ seq_blocks = sb->next_seq_block;
+ free (sb);
+ }
+}
+
+/* Transforms the best pattern sequence into a pseudo-function and its matching
+ sequences to pseudo-calls. Afterwards the best pattern sequence is removed
+ from PATTERN_SEQS. */
+
+static void
+abstract_best_seq (void)
+{
+ pattern_seq bestpseq;
+
+ /* Do the abstraction. */
+ determine_seq_blocks ();
+ split_blocks_after_seqs ();
+ split_pattern_seq ();
+ erase_matching_seqs ();
+ free_seq_blocks ();
+
+ /* Record the usage of the link register. */
+ df_set_regs_ever_live (REGNO (pattern_seqs->link_reg), true);
+
+ /* Remove the best pattern sequence. */
+ bestpseq = pattern_seqs;
+ pattern_seqs = bestpseq->next_pattern_seq;
+ free_pattern_seq (bestpseq);
+}
+
+/* Prints info on the pattern sequences to the dump file. */
+
+static void
+dump_pattern_seqs (void)
+{
+ pattern_seq pseq;
+ matching_seq mseq;
+
+ if (!dump_file)
+ return;
+
+ fprintf (dump_file, ";; Pattern sequences\n");
+ for (pseq = pattern_seqs; pseq; pseq = pseq->next_pattern_seq)
+ {
+ fprintf (dump_file, "Pattern sequence at insn %d matches sequences at",
+ INSN_UID (pseq->insn));
+ for (mseq = pseq->matching_seqs; mseq; mseq = mseq->next_matching_seq)
+ {
+ fprintf (dump_file, " insn %d (length %d)", INSN_UID (mseq->insn),
+ mseq->matching_length);
+ if (mseq->next_matching_seq)
+ fprintf (dump_file, ",");
+ }
+ fprintf (dump_file, ".\n");
+ }
+ fprintf (dump_file, "\n");
+}
+
+/* Prints info on the best pattern sequence transformed in the ITER-th
+ iteration to the dump file. */
+
+static void
+dump_best_pattern_seq (int iter)
+{
+ matching_seq mseq;
+
+ if (!dump_file)
+ return;
+
+ fprintf (dump_file, ";; Iteration %d\n", iter);
+ fprintf (dump_file,
+ "Best pattern sequence with %d gain is at insn %d (length %d).\n",
+ pattern_seqs->gain, INSN_UID (pattern_seqs->insn),
+ pattern_seqs->abstracted_length);
+ fprintf (dump_file, "Matching sequences are at");
+ for (mseq = pattern_seqs->matching_seqs; mseq;
+ mseq = mseq->next_matching_seq)
+ {
+ fprintf (dump_file, " insn %d (length %d)", INSN_UID (mseq->insn),
+ mseq->abstracted_length);
+ if (mseq->next_matching_seq)
+ fprintf (dump_file, ",");
+ }
+ fprintf (dump_file, ".\n");
+ fprintf (dump_file, "Using reg %d as link register.\n\n",
+ REGNO (pattern_seqs->link_reg));
+}
+
+/* Htab hash function for hash_bucket_def structure. */
+
+static unsigned int
+htab_hash_bucket (const void *p)
+{
+ const_p_hash_bucket bucket = (const_p_hash_bucket) p;
+ return bucket->hash;
+}
+
+/* Htab equal function for hash_bucket_def structure. */
+
+static int
+htab_eq_bucket (const void *p0, const void *p1)
+{
+ return htab_hash_bucket (p0) == htab_hash_bucket (p1);
+}
+
+/* Htab delete function for hash_bucket_def structure. */
+
+static void
+htab_del_bucket (void *p)
+{
+ p_hash_bucket bucket = (p_hash_bucket) p;
+
+ if (bucket->seq_candidates)
+ htab_delete (bucket->seq_candidates);
+
+ free (bucket);
+}
+
+/* Htab hash function for hash_bucket_def structure. */
+
+static unsigned int
+htab_hash_elem (const void *p)
+{
+ const_p_hash_elem elem = (const_p_hash_elem) p;
+ return htab_hash_pointer (elem->insn);
+}
+
+/* Htab equal function for hash_bucket_def structure. */
+
+static int
+htab_eq_elem (const void *p0, const void *p1)
+{
+ return htab_hash_elem (p0) == htab_hash_elem (p1);
+}
+
+/* Htab delete function for hash_bucket_def structure. */
+
+static void
+htab_del_elem (void *p)
+{
+ p_hash_elem elem = (p_hash_elem) p;
+ free (elem);
+}
+
+/* Creates a hash value for each sequence candidate and saves them
+ in HASH_BUCKET. */
+
+static void
+fill_hash_bucket (void)
+{
+ basic_block bb;
+ rtx insn;
+ void **slot;
+ p_hash_bucket bucket;
+ struct hash_bucket_def tmp_bucket;
+ p_hash_elem elem;
+ unsigned long insn_idx;
+
+ insn_idx = 0;
+ FOR_EACH_BB (bb)
+ {
+ FOR_BB_INSNS_REVERSE (bb, insn)
+ {
+ if (!ABSTRACTABLE_INSN_P (insn))
+ continue;
+
+ /* Compute hash value for INSN. */
+ tmp_bucket.hash = compute_hash (insn);
+
+ /* Select the hash group. */
+ bucket = (p_hash_bucket) htab_find (hash_buckets, &tmp_bucket);
+
+ if (!bucket)
+ {
+ /* Create a new hash group. */
+ bucket = (p_hash_bucket) xcalloc (1,
+ sizeof (struct hash_bucket_def));
+ bucket->hash = tmp_bucket.hash;
+ bucket->seq_candidates = NULL;
+
+ slot = htab_find_slot (hash_buckets, &tmp_bucket, INSERT);
+ *slot = bucket;
+ }
+
+ /* Create new list for storing sequence candidates. */
+ if (!bucket->seq_candidates)
+ bucket->seq_candidates = htab_create (HASH_INIT,
+ htab_hash_elem,
+ htab_eq_elem,
+ htab_del_elem);
+
+ elem = (p_hash_elem) xcalloc (1, sizeof (struct hash_elem_def));
+ elem->insn = insn;
+ elem->idx = insn_idx;
+ elem->length = get_attr_length (insn);
+
+ /* Insert INSN into BUCKET hash bucket. */
+ slot = htab_find_slot (bucket->seq_candidates, elem, INSERT);
+ *slot = elem;
+
+ insn_idx++;
+ }
+ }
+}
+
+/* Computes the cost of calling sequence and the cost of return. */
+
+static void
+compute_init_costs (void)
+{
+ rtx rtx_jump, rtx_store, rtx_return, reg, label;
+ basic_block bb;
+
+ FOR_EACH_BB (bb)
+ if (BB_HEAD (bb))
+ break;
+
+ label = block_label (bb);
+ reg = gen_rtx_REG (Pmode, 0);
+
+ /* Pattern for indirect jump. */
+ rtx_jump = gen_indirect_jump (reg);
+
+ /* Pattern for storing address. */
+ rtx_store = gen_rtx_SET (VOIDmode, reg, gen_symbol_ref_rtx_for_label (label));
+
+ /* Pattern for return insn. */
+ rtx_return = gen_jump (label);
+
+ /* The cost of jump. */
+ seq_jump_cost = compute_rtx_cost (make_jump_insn_raw (rtx_jump));
+
+ /* The cost of calling sequence. */
+ seq_call_cost = seq_jump_cost + compute_rtx_cost (make_insn_raw (rtx_store));
+
+ /* The cost of return. */
+ seq_return_cost = compute_rtx_cost (make_jump_insn_raw (rtx_return));
+
+ /* Simple heuristic for minimal sequence cost. */
+ seq_call_cost = (int)(seq_call_cost * (double)SEQ_CALL_COST_MULTIPLIER);
+}
+
+/* Finds equivalent insn sequences in the current function and retains only one
+ instance of them which is turned into a pseudo-function. The additional
+ copies are erased and replaced by pseudo-calls to the retained sequence. */
+
+static void
+rtl_seqabstr (void)
+{
+ int iter;
+ df_set_flags (DF_LR_RUN_DCE);
+ df_analyze ();
+
+ /* Create a hash list for COLLECT_PATTERN_SEQS. */
+ hash_buckets = htab_create (HASH_INIT, htab_hash_bucket , htab_eq_bucket ,
+ htab_del_bucket);
+ fill_hash_bucket ();
+
+ /* Compute the common cost of abstraction. */
+ compute_init_costs ();
+
+ /* Build an initial set of pattern sequences from the current function. */
+ collect_pattern_seqs ();
+ dump_pattern_seqs ();
+
+ /* Iterate until there are no sequences to abstract. */
+ for (iter = 1;; iter++)
+ {
+ /* Recompute gain for sequences if necessary and select sequence with
+ biggest gain. */
+ recompute_gain ();
+ if (!pattern_seqs)
+ break;
+ dump_best_pattern_seq (iter);
+ /* Update the cached info of the other sequences and force gain
+ recomputation where needed. */
+ update_pattern_seqs ();
+ /* Turn best sequences into pseudo-functions and -calls. */
+ abstract_best_seq ();
+ }
+
+ /* Cleanup hash tables. */
+ htab_delete (hash_buckets);
+}
+
+/* The gate function for TREE_OPT_PASS. */
+
+static bool
+gate_rtl_seqabstr (void)
+{
+ return flag_rtl_seqabstr;
+}
+
+/* The entry point of the sequence abstraction algorithm. */
+
+static unsigned int
+rest_of_rtl_seqabstr (void)
+{
+ /* Abstract out common insn sequences. */
+ rtl_seqabstr ();
+ return 0;
+}
+
+struct rtl_opt_pass pass_rtl_seqabstr =
+{
+ {
+ RTL_PASS,
+ "seqabstr", /* name */
+ gate_rtl_seqabstr, /* gate */
+ rest_of_rtl_seqabstr, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_SEQABSTR, /* tv_id */
+ 0, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_df_finish | TODO_verify_rtl_sharing |
+ TODO_dump_func |
+ TODO_ggc_collect /* todo_flags_finish */
+ }
+};
projects / msp430-gcc.git / blobdiff