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