This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: Does anyone have Vlad's CSE speedup patches from many years ago
- From: Bernd Schmidt <bernds_cb1 at t-online dot de>
- To: "Vladimir N. Makarov" <vmakarov at redhat dot com>
- Cc: Steven Bosscher <stevenb dot gcc at gmail dot com>, gcc at gcc dot gnu dot org, law at redhat dot com, wilson at specifixinc dot com, ian at airs dot com
- Date: Mon, 29 May 2006 16:30:51 +0200
- Subject: Re: Does anyone have Vlad's CSE speedup patches from many years ago
- References: <200605282323.18841.steven@gcc.gnu.org> <447A173D.3050308@redhat.com>
Vladimir N. Makarov wrote:
Steven Bosscher wrote:
I found out long ago that even longer ago Vlad had patches to keep the
state for basic blocks and re-using it. The latest message mentioning
this work is http://gcc.gnu.org/ml/gcc-patches/2001-02/msg01166.html,
and apparently Vlad's patches never made it out of the Cygnus network.
So...
Does anyone of you pack-rats still have these patches? Maybe there is
code in them that I can re-use, or at least learn from because right
now, even in my cleaned-up-and-cut-down version of cse.c (down to 5000
lines) I still can't make a whole lot of sense of all the tables that
are used in that pass.
I am sorry to say but I think it was lost. The patch was created in
1998 or 1999 and posted on internal website with benchmark results.
During IT reorganization after Redhat bought Cygnus, the page was lost.
Don't discount the pack-rats. I saved that patch in an
interesting-patches file, and I still have it.
I'm appending a copy of the mail you sent, with references to a certain
commercial testsuite snipped out. Not sure how useful the patch is; I'm
sure a few things have changed in the last 7 years.
Bernd
From: Vladimir Makarov <vmakarov@cygnus.com>
Hello everybody.
I've made the patch which is considerably speedup CSE [snip].
What the patch does:
1. Instead of David Miller's reg_hash table, now array
cse_reg_info_table and bb_tick to (in)validate elements of the array
are used. The validated array elements actually correspond to
elements in reg_hash. But the access to the validated elements in
such implementation is the fastest (although actually it gives only
very small speedup) and simpler. This is the simplest change.
2. CSE now can save and restore its state which permits considerably
speedup CSE. CSE when flag_cse_follow_jumps and flag_cse_skip_blocks
are true (this is default for -O2 because it produces considerably
better code) processes function parts which consist of several
extended blocks. As example, let us look at weird plumhall tests
which consists of thousands of code parts of the following view:
BB1: some non-control code
if () <-- branch 1
some noncontrol code
BB2: some non-control code
if () <-- branch 2
some noncontrol code
....
BB10: some non-control code
if () <-- branch 10
some noncontrol code
CSE look ahead at most 10 branches and processes code starting with
BB1 11 times:
iteration
1 BB1 .... BB10 all branches are considered TAKEN (in cse terminology
branch has status AROUND)
2 BB1 ... BB10 all branches are considered TAKEN but branch in BB10
is not taken (this permits to make CSE inside if-stmt.
branch with status AROUND results in invalidation of
some CSE equivalences affected by stmnts inside
if-stmnt)
3 BB1 ... BB9 all branches are considered TAKEN but branch in BB9
is not taken
4 BB1 ... BB8 all branches are considered TAKEN but branch in BB8
is not taken
10 BB1 .. BB2
11 BB1 the first branch is considered as NOT_TAKEN
Saving and restoring CSE state permits fast start on 2-11 iteration
from the last branch.
To save and restore CSE state, logs of several tables changes are
kept. It works when new option -fcse-reuse-info is given (default now
for -O2).
3. Now there is no constraint in 10 branches for CSE. End of
processed code is now only natural bounds (loops or jumps into the
code from outside the code). This permits further speedup of CSE. In
our example, after the first 11 iterations, cse start the same with
the basic block 2:
iteration
1 BB2 .... BB11
2 BB2 ... BB11
3 BB2 ... BB10
4 BB2 ... BB9
10 BB2 .. BB3
11 BB2
Now we do not process blocks which was processed previously without
lost of quality generated code. In our example, BB11 has the same
context (and more) during new processing starting with BB1 as it had
during processing starting with BB2 early. Moreover, in some case
(when there are cse paths containing more 10 branches) it may
generates better code. On other hand, very long path may result in
increased register pressure and spilling especially for targets with
small number of registers (x86).
This feature is controlled by new option -fcse-limit-path (which is not
default for -O2).
Actually, on many programs cse processes many slightly different
paths. So this approach should be productive.
4. The last change is for better code generation. I've added
processing if-then-else statements which can be on the path of CSE. Now
this is only not nested if-then-else statements. Processing nested
if-then-else statement can be added. But may be it is better rewrite
all cse and make it dominator-based.
This feature is controlled by new option -fcse-skip-if-else (which is
not default for -O2).
5. The following tables compare the current egcs (with the last David
Miller's cse patch) and the same code with my patch. I've use the
fastest available for me x86 and sparc.
[snip]
cc1- | text section size cc1 without cse.o built by gcc with/without the patch
cse.o| compilation time of cc1
-------------------------------------------------------------------------------
| old cse | new cse | new cse | new cse | new cse
| -O2 | -O2 |-O2 & skip ifs| -O2 & limit | -O2 & skip-ifs
| | | | | & limit path
-------------------------------------------------------------------------------
x86 | | | | |
| 2056129bytes| 2056721bytes| 2056577 bytes| 2057025bytes | 2056881 bytes
| 393.15s | 353.77s | 352.44s | 360.55s | 363.13s
| | | | |
| | | | |
sparc| | | | |
| 2064806bytes| 2066074bytes| 2065374bytes | 2066778bytes | 2066074bytes
| 10m43.780s | 9m59.610s | 10m1.970s | 10m13.820s | 10m21.930s
| | | | |
6. Cse now is very useful component which makes some optimizations
not made by gcse (taking rtx cost into account). So there is sense to
improve generated code quality. Now the slightly worse code quality
is result of increased register pressure when the path is unlimited.
Also I suspect that another reason of that is in multiple processing of
the block may result in slightly better code. So I see the following
ways to improve cse in future:
1. Reuse CSE state only if on previous path there were no a
subexpression elimination.
2. Limit path depending on number of target general registers.
3. Implementation of skipping nested if-then-else statements.
Richard, please review the patch. If it is ok, I would like to commit
it into egcs.
Thanks in advance.
Vlad
Thu Jan 20 12:06:49 2000 Vladimir Makarov <vmakarov@toad.to.cygnus.com>
* flags.h (flag_cse_reuse_info, flag_cse_limit_path,
flag_cse_skip_if_else): New flags.
* toplev.c (flag_cse_reuse_info, flag_cse_limit_path,
flag_cse_skip_if_else): Dito.
(f_options): Element for the new flags.
(main): Initiate flags when optimize >= 2.
* invoke.texi (-fcse-reuse-info, -fno-cse-limit-path,
-fno-cse-skip-if-else): New flags.
* rtl.h (cse_basic_block_data, cse_end_of_basic_block): Remove the
external declarations.
* cse.c (qty_table_elem): New members qty and save_key.
(saved_qty_table, saved_qty_table_size): New global variables.
(CHECK_SAVING_QTY): New macro.
(reg_eqv_elem): New members regno and save_key.
(CHECK_SAVING_REG_EQV): New macro.
(saved_reg_eqv_table, saved_reg_eqv_table_size): New global
variables.
(cse_reg_info): New members save_key and bb_tick.
(cse_reg_info_free_list): Remove global variables.
(cse_reg_info_table): New global variable.
(cse_reg_info_used_list, cse_reg_info_used_list_end): Remove
global variables.
(REGHASH_SHIFT, REGHASH_SIZE, REGHASH_MASK, REGHASH_FN): Remove
macros.
(reg_hash, cached_regno, cached_cse_reg_info): Remove global
variables.
(saved_cse_reg_info_table, saved_cse_reg_info_table_size,
bb_tick): New global variables.
(table_elt): New members save_key, new_key, chain, and orig.
(GET_CSE_REG_INFO): Modify.
(CHECK_SAVING_TABLE_ELT, GET_LVAL_CSE_REG_INFO, LVAL_REG_TICK,
LVAL_REG_IN_TABLE, LVAL_REG_QTY, INIT_PATHLENGTH): New macros.
(PATHLENGTH): Remove macro.
(branch_path_entry): New structure.
(branch_path_t): New type.
(cse_basic_block_data): Use the type. New member pathlength.
(state): New structure.
(stack, stack_free, stack_length): New global variables.
(save_cse_reg_info, pop_cse_reg_info, reject_cse_reg_info_log,
free_stack, init_stack, finish_stack, push_state, pop_state,
save_qty_table_elem, pop_qty_table, reject_qty_table_log,
save_reg_eqv_table_elem, pop_reg_eqv_table,
reject_reg_eqv_table_log, save_table_elt, restore_table,
reject_table_log, free_element, get_element, init_path,
finish_path, check_pathlength): New functions and prototypes.
(get_cse_reg_info): Use array instead of hash table.
(new_basic_block): Reject stack of states.
(make_new_qty, make_regs_eqv, delete_reg_equiv, mention_regs,
insert_regs, remove_from_table, insert, invalidate,
rehash_using_reg, invalidate_for_call, record_jump_cond, cse_insn,
addr_affects_sp_p): Use macros for possible saving cse state.
(print_table): New function.
(insert): Use get_element.
(invalidate_skipped_block): Return end of the block (CODE_LABEL).
(cse_end_of_basic_block): New parameter start. Function returns
start insn. Add code for DIAMOND_AROUND. Restoring CSE state.
(cse_main): Allocate and free the most of CSE arrays. Add
output of debugging information.
(cse_basic_block): New parameters cont_p, file, next_branch. Save
cse state. Add output of debugging information.
Index: flags.h
===================================================================
RCS file: /cvs/gcc/egcs/gcc/flags.h,v
retrieving revision 1.39
diff -c -p -r1.39 flags.h
*** flags.h 2000/01/19 09:42:10 1.39
--- flags.h 2000/01/21 22:34:02
*************** extern int flag_cse_follow_jumps;
*** 255,262 ****
--- 255,279 ----
extern int flag_cse_skip_blocks;
+ /* Nonzero for -fcse-reuse-info:
+ try to use cse information for processing extended block similiar
+ to the previous one. */
+
+ extern int flag_cse_reuse_info;
+
+ /* Nonzero for -fcse-limit-path:
+ limit branch path length which cse follows. */
+
+ extern int flag_cse_limit_path;
+
+ /* Nonzero for -fcse-skip-if-else:
+ have cse follow a branch around a simple if-the-else statement. */
+
+ extern int flag_cse_skip_if_else;
+
/* Nonzero for -fexpensive-optimizations:
perform miscellaneous relatively-expensive optimizations. */
+
extern int flag_expensive_optimizations;
/* Nonzero for -fwritable-strings:
Index: toplev.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/toplev.c,v
retrieving revision 1.282
diff -c -p -r1.282 toplev.c
*** toplev.c 2000/01/19 09:42:11 1.282
--- toplev.c 2000/01/21 22:34:07
*************** int flag_cse_follow_jumps;
*** 427,434 ****
--- 427,451 ----
/* Nonzero for -fcse-skip-blocks:
have cse follow a branch around a block. */
+
int flag_cse_skip_blocks;
+ /* Nonzero for -fcse-reuse-info:
+ try to use cse information for processing extended block similiar
+ to the previous one. */
+
+ int flag_cse_reuse_info;
+
+ /* Nonzero for -fcse-limit-path:
+ limit branch path length which cse follows. */
+
+ int flag_cse_limit_path = 1;
+
+ /* Nonzero for -fcse-skip-if-else:
+ have cse follow a branch around a simple if-the-else statement. */
+
+ int flag_cse_skip_if_else;
+
/* Nonzero for -fexpensive-optimizations:
perform miscellaneous relatively-expensive optimizations. */
int flag_expensive_optimizations;
*************** lang_independent_options f_options[] =
*** 850,855 ****
--- 867,878 ----
"When running CSE, follow jumps to their targets" },
{"cse-skip-blocks", &flag_cse_skip_blocks, 1,
"When running CSE, follow conditional jumps" },
+ {"cse-reuse-info", &flag_cse_reuse_info, 1,
+ "When running CSE, reuse information for processing analogous path" },
+ {"cse-limit-path", &flag_cse_limit_path, 1,
+ "When running CSE, limit length of processed path of branches" },
+ {"cse-skip-if-else", &flag_cse_skip_if_else, 1,
+ "When running CSE, skip simple if-then-else statements" },
{"expensive-optimizations", &flag_expensive_optimizations, 1,
"Perform a number of minor, expensive optimisations" },
{"thread-jumps", &flag_thread_jumps, 1,
*************** main (argc, argv)
*** 4561,4566 ****
--- 4584,4592 ----
{
flag_cse_follow_jumps = 1;
flag_cse_skip_blocks = 1;
+ flag_cse_reuse_info = 1;
+ flag_cse_limit_path = 0;
+ flag_cse_skip_if_else = 0;
flag_gcse = 1;
flag_expensive_optimizations = 1;
flag_strength_reduce = 1;
Index: invoke.texi
===================================================================
RCS file: /cvs/gcc/egcs/gcc/invoke.texi,v
retrieving revision 1.166
diff -c -p -r1.166 invoke.texi
*** invoke.texi 2000/01/07 00:42:12 1.166
--- invoke.texi 2000/01/21 22:34:18
*************** in the following sections.
*** 157,163 ****
@smallexample
-falign-functions=@var{n} -falign-labels=@var{n} -falign-loops=@var{n}
-falign-jumps=@var{n} -fbranch-probabilities
! -fcaller-saves -fcse-follow-jumps -fcse-skip-blocks
-fdelayed-branch -fdelete-null-pointer-checks -fexpensive-optimizations
-ffast-math -ffloat-store -fforce-addr -fforce-mem -fno-math-errno
-fdata-sections -ffunction-sections -fgcse
--- 157,164 ----
@smallexample
-falign-functions=@var{n} -falign-labels=@var{n} -falign-loops=@var{n}
-falign-jumps=@var{n} -fbranch-probabilities
! -fcaller-saves -fcse-follow-jumps -fcse-skip-blocks -fcse-reuse-info
! -fno-cse-limit-path -fno-cse-skip-if-else
-fdelayed-branch -fdelete-null-pointer-checks -fexpensive-optimizations
-ffast-math -ffloat-store -fforce-addr -fforce-mem -fno-math-errno
-fdata-sections -ffunction-sections -fgcse
*************** follow jumps which conditionally skip ov
*** 2553,2558 ****
--- 2554,2577 ----
encounters a simple @code{if} statement with no else clause,
@samp{-fcse-skip-blocks} causes CSE to follow the jump around the
body of the @code{if}.
+
+ @item -fcse-reuse-info
+ This causes CSE to reuse information obtained on processing analogous
+ path of jumps and in some cases this results in considerable speeding
+ up CSE.
+
+ @item -fno-cse-limit-path
+ @samp{-fcse-limit-path} causes CSE to limit number of jumps which
+ conditionally skip over blocks, skip through jump instructions, or
+ skip over simple if-then-else statements. Otherwise, the bound is
+ natural (e.g. loop).
+
+ @item -fno-cse-skip-if-else
+ @samp{-fcse-skip-if-else} is similar to @samp{-fcse-skip-blocks}, but
+ causes CSE to follow jumps which is part of simple if-then-else
+ statement. When CSE encounters a simple @code{if} statement with else
+ clause, @samp{-fcse-skip-if-else} causes CSE to follow around the body
+ of the all @code{if} statement.
@item -frerun-cse-after-loop
Re-run common subexpression elimination after loop optimizations has been
Index: rtl.h
===================================================================
RCS file: /cvs/gcc/egcs/gcc/rtl.h,v
retrieving revision 1.162
diff -c -p -r1.162 rtl.h
*** rtl.h 2000/01/19 09:42:11 1.162
--- rtl.h 2000/01/21 22:34:20
*************** extern void pop_obstacks PARAMS ((void)
*** 1383,1397 ****
extern void push_obstacks PARAMS ((struct obstack *,
struct obstack *));
/* In cse.c */
- struct cse_basic_block_data;
extern int rtx_cost PARAMS ((rtx, enum rtx_code));
extern void delete_trivially_dead_insns PARAMS ((rtx, int));
#ifdef BUFSIZ
extern int cse_main PARAMS ((rtx, int, int, FILE *));
#endif
- extern void cse_end_of_basic_block PARAMS ((rtx,
- struct cse_basic_block_data *,
- int, int, int));
/* In jump.c */
extern int comparison_dominates_p PARAMS ((enum rtx_code, enum rtx_code));
--- 1383,1393 ----
Index: cse.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/cse.c,v
retrieving revision 1.127
diff -c -p -r1.127 cse.c
*** cse.c 2000/01/18 00:30:16 1.127
--- cse.c 2000/01/21 22:34:29
*************** Boston, MA 02111-1307, USA. */
*** 38,56 ****
#include "output.h"
#include "ggc.h"
! /* The basic idea of common subexpression elimination is to go
! through the code, keeping a record of expressions that would
! have the same value at the current scan point, and replacing
! expressions encountered with the cheapest equivalent expression.
It is too complicated to keep track of the different possibilities
! when control paths merge in this code; so, at each label, we forget all
! that is known and start fresh. This can be described as processing each
! extended basic block separately. We have a separate pass to perform
! global CSE.
! Note CSE can turn a conditional or computed jump into a nop or
! an unconditional jump. When this occurs we arrange to run the jump
optimizer after CSE to delete the unreachable code.
We use two data structures to record the equivalent expressions:
--- 38,56 ----
#include "output.h"
#include "ggc.h"
! /* The basic idea of common subexpression elimination is to go through
! the code, keeping a record of expressions that would have the same
! value at the current scan point, and replacing expressions
! encountered with the cheapest equivalent expression.
It is too complicated to keep track of the different possibilities
! when control paths merge in this code; so, at each label, we forget
! all that is known and start fresh. This can be described as
! processing each extended basic block separately. We have a
! separate pass to perform global CSE.
! Note CSE can turn a conditional or computed jump into a nop or an
! unconditional jump. When this occurs we arrange to run the jump
optimizer after CSE to delete the unreachable code.
We use two data structures to record the equivalent expressions:
*************** Boston, MA 02111-1307, USA. */
*** 59,181 ****
The use of the special data structure for registers is desirable
because it is faster. It is possible because registers references
! contain a fairly small number, the register number, taken from
! a contiguously allocated series, and two register references are
! identical if they have the same number. General expressions
! do not have any such thing, so the only way to retrieve the
! information recorded on an expression other than a register
! is to keep it in a hash table.
Registers and "quantity numbers":
At the start of each basic block, all of the (hardware and pseudo)
! registers used in the function are given distinct quantity
! numbers to indicate their contents. During scan, when the code
! copies one register into another, we copy the quantity number.
! When a register is loaded in any other way, we allocate a new
! quantity number to describe the value generated by this operation.
! `reg_qty' records what quantity a register is currently thought
! of as containing.
All real quantity numbers are greater than or equal to `max_reg'.
! If register N has not been assigned a quantity, reg_qty[N] will equal N.
! Quantity numbers below `max_reg' do not exist and none of the `qty_table'
! entries should be referenced with an index below `max_reg'.
We also maintain a bidirectional chain of registers for each
! quantity number. The `qty_table` members `first_reg' and `last_reg',
! and `reg_eqv_table' members `next' and `prev' hold these chains.
!
! The first register in a chain is the one whose lifespan is least local.
! Among equals, it is the one that was seen first.
! We replace any equivalent register with that one.
!
! If two registers have the same quantity number, it must be true that
! REG expressions with qty_table `mode' must be in the hash table for both
! registers and must be in the same class.
!
! The converse is not true. Since hard registers may be referenced in
! any mode, two REG expressions might be equivalent in the hash table
! but not have the same quantity number if the quantity number of one
! of the registers is not the same mode as those expressions.
Constants and quantity numbers
! When a quantity has a known constant value, that value is stored
! in the appropriate qty_table `const_rtx'. This is in addition to
putting the constant in the hash table as is usual for non-regs.
! Whether a reg or a constant is preferred is determined by the configuration
! macro CONST_COSTS and will often depend on the constant value. In any
! event, expressions containing constants can be simplified, by fold_rtx.
!
! When a quantity has a known nearly constant value (such as an address
! of a stack slot), that value is stored in the appropriate qty_table
! `const_rtx'.
Integer constants don't have a machine mode. However, cse
! determines the intended machine mode from the destination
! of the instruction that moves the constant. The machine mode
! is recorded in the hash table along with the actual RTL
! constant expression so that different modes are kept separate.
Other expressions:
! To record known equivalences among expressions in general
! we use a hash table called `table'. It has a fixed number of buckets
! that contain chains of `struct table_elt' elements for expressions.
These chains connect the elements whose expressions have the same
hash codes.
Other chains through the same elements connect the elements which
currently have equivalent values.
! Register references in an expression are canonicalized before hashing
! the expression. This is done using `reg_qty' and qty_table `first_reg'.
! The hash code of a register reference is computed using the quantity
! number, not the register number.
!
! When the value of an expression changes, it is necessary to remove from the
! hash table not just that expression but all expressions whose values
! could be different as a result.
1. If the value changing is in memory, except in special cases
ANYTHING referring to memory could be changed. That is because
! nobody knows where a pointer does not point.
! The function `invalidate_memory' removes what is necessary.
! The special cases are when the address is constant or is
! a constant plus a fixed register such as the frame pointer
! or a static chain pointer. When such addresses are stored in,
! we can tell exactly which other such addresses must be invalidated
! due to overlap. `invalidate' does this.
! All expressions that refer to non-constant
! memory addresses are also invalidated. `invalidate_memory' does this.
2. If the value changing is a register, all expressions
! containing references to that register, and only those,
! must be removed.
! Because searching the entire hash table for expressions that contain
! a register is very slow, we try to figure out when it isn't necessary.
! Precisely, this is necessary only when expressions have been
! entered in the hash table using this register, and then the value has
! changed, and then another expression wants to be added to refer to
! the register's new value. This sequence of circumstances is rare
! within any one basic block.
!
! The vectors `reg_tick' and `reg_in_table' are used to detect this case.
! reg_tick[i] is incremented whenever a value is stored in register i.
! reg_in_table[i] holds -1 if no references to register i have been
! entered in the table; otherwise, it contains the value reg_tick[i] had
when the references were entered. If we want to enter a reference
! and reg_in_table[i] != reg_tick[i], we must scan and remove old references.
! Until we want to enter a new entry, the mere fact that the two vectors
! don't match makes the entries be ignored if anyone tries to match them.
Registers themselves are entered in the hash table as well as in
! the equivalent-register chains. However, the vectors `reg_tick'
and `reg_in_table' do not apply to expressions which are simple
register references. These expressions are removed from the table
immediately when they become invalid, and this can be done even if
--- 59,189 ----
The use of the special data structure for registers is desirable
because it is faster. It is possible because registers references
! contain a fairly small number, the register number, taken from a
! contiguously allocated series, and two register references are
! identical if they have the same number. General expressions do not
! have any such thing, so the only way to retrieve the information
! recorded on an expression other than a register is to keep it in a
! hash table.
Registers and "quantity numbers":
At the start of each basic block, all of the (hardware and pseudo)
! registers used in the function are given distinct quantity numbers
! to indicate their contents. During scan, when the code copies one
! register into another, we copy the quantity number. When a
! register is loaded in any other way, we allocate a new quantity
! number to describe the value generated by this operation.
! `reg_qty' records what quantity a register is currently thought of
! as containing.
All real quantity numbers are greater than or equal to `max_reg'.
! If register N has not been assigned a quantity,
! cse_reg_info_table[N].qty will equal N.
! Quantity numbers below `max_reg' do not exist and none of the
! `qty_table' entries should be referenced with an index below
! `max_reg'.
We also maintain a bidirectional chain of registers for each
! quantity number. The `qty_table` members `first_reg' and
! `last_reg', and `reg_eqv_table' members `next' and `prev' hold
! these chains.
!
! The first register in a chain is the one whose lifespan is least
! local. Among equals, it is the one that was seen first. We
! replace any equivalent register with that one.
!
! If two registers have the same quantity number, it must be true
! that REG expressions with qty_table `mode' must be in the hash
! table for both registers and must be in the same class.
!
! The converse is not true. Since hard registers may be referenced
! in any mode, two REG expressions might be equivalent in the hash
! table but not have the same quantity number if the quantity number
! of one of the registers is not the same mode as those expressions.
Constants and quantity numbers
! When a quantity has a known constant value, that value is stored in
! the appropriate qty_table `const_rtx'. This is in addition to
putting the constant in the hash table as is usual for non-regs.
! Whether a reg or a constant is preferred is determined by the
! configuration macro CONST_COSTS and will often depend on the
! constant value. In any event, expressions containing constants can
! be simplified, by fold_rtx.
!
! When a quantity has a known nearly constant value (such as an
! address of a stack slot), that value is stored in the appropriate
! qty_table `const_rtx'.
Integer constants don't have a machine mode. However, cse
! determines the intended machine mode from the destination of the
! instruction that moves the constant. The machine mode is recorded
! in the hash table along with the actual RTL constant expression so
! that different modes are kept separate.
Other expressions:
! To record known equivalences among expressions in general we use a
! hash table called `table'. It has a fixed number of buckets that
! contain chains of `struct table_elt' elements for expressions.
These chains connect the elements whose expressions have the same
hash codes.
Other chains through the same elements connect the elements which
currently have equivalent values.
! Register references in an expression are canonicalized before
! hashing the expression. This is done using `reg_qty' and qty_table
! `first_reg'. The hash code of a register reference is computed
! using the quantity number, not the register number.
!
! When the value of an expression changes, it is necessary to remove
! from the hash table not just that expression but all expressions
! whose values could be different as a result.
1. If the value changing is in memory, except in special cases
ANYTHING referring to memory could be changed. That is because
! nobody knows where a pointer does not point. The function
! `invalidate_memory' removes what is necessary.
! The special cases are when the address is constant or is a
! constant plus a fixed register such as the frame pointer or a
! static chain pointer. When such addresses are stored in, we can
! tell exactly which other such addresses must be invalidated due
! to overlap. `invalidate' does this. All expressions that refer
! to non-constant memory addresses are also invalidated.
! `invalidate_memory' does this.
2. If the value changing is a register, all expressions
! containing references to that register, and only those, must be
! removed.
! Because searching the entire hash table for expressions that
! contain a register is very slow, we try to figure out when it isn't
! necessary. Precisely, this is necessary only when expressions have
! been entered in the hash table using this register, and then the
! value has changed, and then another expression wants to be added to
! refer to the register's new value. This sequence of circumstances
! is rare within any one basic block.
!
! The members `reg_tick' and `reg_in_table' in array
! `cse_reg_info_table' are used to detect this case.
! cse_reg_info_table[i].reg_tick is incremented whenever a value is
! stored in register i. cse_reg_info_table[i].reg_in_table holds -1
! if no references to register i have been entered in the table;
! otherwise, it contains the value cse_reg_info_table[i].reg_tick had
when the references were entered. If we want to enter a reference
! and cse_reg_info_table[i].reg_in_table !=
! cse_reg_info_table[i].reg_tick, we must scan and remove old
! references. Until we want to enter a new entry, the mere fact that
! the two members don't match makes the entries be ignored if anyone
! tries to match them.
Registers themselves are entered in the hash table as well as in
! the equivalent-register chains. However, the members `reg_tick'
and `reg_in_table' do not apply to expressions which are simple
register references. These expressions are removed from the table
immediately when they become invalid, and this can be done even if
*************** Other expressions:
*** 183,199 ****
the register.
A CLOBBER rtx in an instruction invalidates its operand for further
! reuse. A CLOBBER or SET rtx whose operand is a MEM:BLK
! invalidates everything that resides in memory.
Related expressions:
! Constant expressions that differ only by an additive integer
! are called related. When a constant expression is put in
! the table, the related expression with no constant term
! is also entered. These are made to point at each other
! so that it is possible to find out if there exists any
! register equivalent to an expression related to a given expression. */
/* One plus largest register number used in this function. */
--- 191,222 ----
the register.
A CLOBBER rtx in an instruction invalidates its operand for further
! reuse. A CLOBBER or SET rtx whose operand is a MEM:BLK invalidates
! everything that resides in memory.
Related expressions:
! Constant expressions that differ only by an additive integer are
! called related. When a constant expression is put in the table,
! the related expression with no constant term is also entered.
! These are made to point at each other so that it is possible to
! find out if there exists any register equivalent to an expression
! related to a given expression.
!
! Speedup:
!
! Now cse can save and restore its state needed for its correct work
! (see function pop_state, push_state) when flag_cse_reuse_info
! (default for -O2). This permits considerably speedup CSE in some
! cases. In this case, if the current branch path is analogous the
! previous one, information of CSE on the previous one is reused for
! faster cse work.
!
! Cse can limit number of branches on the path when
! flag_cse_limit_path (this is off when -O2). Otherwise, the bound
! of the path is natural (e.g. loop) and in this case the path
! started with the next basic block can be not processed without
! losing code quality. */
/* One plus largest register number used in this function. */
*************** static int next_qty;
*** 216,221 ****
--- 239,250 ----
/* Per-qty information tracking.
+ `qty' is index of the structure in `qty_table'. This member is
+ needed to keep log of changes in `qty_table'.
+
+ `save_key' stores value of `stack_free' when the structure was
+ saved in the change log the last time.
+
`first_reg' and `last_reg' track the head and tail of the
chain of registers which currently contain this quantity.
*************** static int next_qty;
*** 241,246 ****
--- 270,277 ----
struct qty_table_elem
{
+ int qty;
+ int save_key;
rtx const_rtx;
rtx const_insn;
rtx comparison_const;
*************** struct qty_table_elem
*** 253,258 ****
--- 284,303 ----
/* The table of all qtys, indexed by qty number. */
static struct qty_table_elem *qty_table;
+ /* The following array is used to store original values of elements of
+ `qty_table'. So this array is used as log of changes in
+ qty_table. */
+ static struct qty_table_elem *saved_qty_table;
+
+ /* The current allocated length of saved_qty_table in elements. */
+ static int saved_qty_table_size;
+
+ /* The following macro provides access to qty_table elements and
+ additionally saves (if the elements are not saved yet) values of the
+ elements of qty_table. */
+ #define CHECK_SAVING_QTY(ent) \
+ ((ent)->save_key != stack_free ? save_qty_table_elem (ent) : ent)
+
#ifdef HAVE_cc0
/* For machines that have a CC0, we do not record its value in the hash
table since its use is guaranteed to be the insn immediately following
*************** static rtx this_insn;
*** 279,284 ****
--- 324,335 ----
previous) register in the chain of registers sharing the same
value.
+ `regno' is index of the structure in `reg_eqv_table'. This member is
+ needed to keep log of changes in `reg_eqv_table'.
+
+ `save_key' stores value of `stack_free' when the structure was
+ saved in the change log the last time.
+
Or -1 if this register is at the end of the chain.
If reg_qty[N] == N, reg_eqv_table[N].next is undefined. */
*************** static rtx this_insn;
*** 286,310 ****
/* Per-register equivalence chain. */
struct reg_eqv_elem
{
! int next, prev;
};
/* The table of all register equivalence chains. */
static struct reg_eqv_elem *reg_eqv_table;
! struct cse_reg_info
! {
! /* Next in hash chain. */
! struct cse_reg_info *hash_next;
! /* The next cse_reg_info structure in the free or used list. */
! struct cse_reg_info *next;
! /* Search key */
int regno;
! /* The quantity number of the register's current contents. */
! int reg_qty;
/* The number of times the register has been altered in the current
basic block. */
--- 337,373 ----
/* Per-register equivalence chain. */
struct reg_eqv_elem
{
! int regno, save_key, next, prev;
};
+ /* The following macro provides access to reg_eqv_table elements and
+ additionally saves (if the elements are not saved yet) values of the
+ elements of reg_eqv_table. */
+ #define CHECK_SAVING_REG_EQV(regno) \
+ (reg_eqv_table[regno].save_key != stack_free \
+ ? save_reg_eqv_table_elem (regno) : ®_eqv_table[regno])
+
/* The table of all register equivalence chains. */
static struct reg_eqv_elem *reg_eqv_table;
! /* The following array is used to store original values of elements of
! `reg_eqv_table'. So this array is used as log of changes in
! reg_eqv_table. */
! static struct reg_eqv_elem *saved_reg_eqv_table;
! /* The current allocated length of saved_qty_table in elements. */
! static int saved_reg_eqv_table_size;
! struct cse_reg_info
! {
! /* The following member is index of the structure in
! `cse_reg_info_table'. This member is needed to keep log of
! changes in `cse_reg_info_table'. */
int regno;
! /* The following member stores value of `stack_free' when the
! structure was saved in the change log the last time. */
! int save_key;
/* The number of times the register has been altered in the current
basic block. */
*************** struct cse_reg_info
*** 315,342 ****
reg_tick value, such expressions existing in the hash table are
invalid. */
int reg_in_table;
};
! /* A free list of cse_reg_info entries. */
! static struct cse_reg_info *cse_reg_info_free_list;
! /* A used list of cse_reg_info entries. */
! static struct cse_reg_info *cse_reg_info_used_list;
! static struct cse_reg_info *cse_reg_info_used_list_end;
!
! /* A mapping from registers to cse_reg_info data structures. */
! #define REGHASH_SHIFT 7
! #define REGHASH_SIZE (1 << REGHASH_SHIFT)
! #define REGHASH_MASK (REGHASH_SIZE - 1)
! static struct cse_reg_info *reg_hash[REGHASH_SIZE];
!
! #define REGHASH_FN(REGNO) \
! (((REGNO) ^ ((REGNO) >> REGHASH_SHIFT)) & REGHASH_MASK)
!
! /* The last lookup we did into the cse_reg_info_tree. This allows us
! to cache repeated lookups. */
! static int cached_regno;
! static struct cse_reg_info *cached_cse_reg_info;
/* A HARD_REG_SET containing all the hard registers for which there is
currently a REG expression in the hash table. Note the difference
--- 378,410 ----
reg_tick value, such expressions existing in the hash table are
invalid. */
int reg_in_table;
+
+ /* The quantity number of the register's current contents. */
+ int reg_qty;
+
+ /* This member is used to invalidate the register information. Only
+ structures with the field value equal current value of variable
+ bb_tick is considered as validated. */
+ int bb_tick;
};
! /* The following array contains info about processed registers. */
! static struct cse_reg_info *cse_reg_info_table;
! /* The following array is used to store original values of elements of
! `cse_reg_info_table'. So this array is used as log of changes in
! cse_reg_info_table. */
! static struct cse_reg_info *saved_cse_reg_info_table;
!
! /* The current allocated length of saved_cse_reg_info_table in elements. */
! static int saved_cse_reg_info_table_size;
!
! /* The following variable value is increased when processing the next
! basic block (more correctly cse extended basic block) starts.
! Actually, this is not cse extended basic block number because cse
! basic blocks may be processed repeatedly. The value of variable is
! used to (in)validate elements of cse_reg_info_table. */
! static int bb_tick;
/* A HARD_REG_SET containing all the hard registers for which there is
currently a REG expression in the hash table. Note the difference
*************** static int hash_arg_in_memory;
*** 435,445 ****
The `mode' field is usually the same as GET_MODE (`exp'), but
if `exp' is a CONST_INT and has no machine mode then the `mode'
field is the mode it was being used as. Each constant is
! recorded separately for each mode it is used with. */
struct table_elt
{
rtx exp;
struct table_elt *next_same_hash;
struct table_elt *prev_same_hash;
--- 503,532 ----
The `mode' field is usually the same as GET_MODE (`exp'), but
if `exp' is a CONST_INT and has no machine mode then the `mode'
field is the mode it was being used as. Each constant is
! recorded separately for each mode it is used with.
!
! Members `save_key', `new_key', `chain' and `orig' are used for
! supporting change log in the hash table.
!
! `save_key' stores value of `stack_free' when the structure was
! saved in the change log the last time. Such elements are modified
! elements and there are their copies with original structure memeber
! values chained through member `chain'. Start of such chain is
! saved in member `modified_element_chain' of a structure `state'.
! The copies have pointers (memebers `orig') to the corresponding
! elements in the hash table.
!
! `new_key' stores value of `stack_free' when the table element was
! created. The new elements are also chained through member `chain'
! and start of such chain is saved in member `new_element_chain' of
! a structure `state'. */
struct table_elt
{
+ int save_key, new_key;
+ struct table_elt *chain;
+ struct table_elt *orig;
rtx exp;
struct table_elt *next_same_hash;
struct table_elt *prev_same_hash;
*************** struct table_elt
*** 454,459 ****
--- 541,553 ----
char flag;
};
+ /* The following macro provides access to the hash table element and
+ additionally saves (if the elements are not saved yet) values of
+ the hash table elements. */
+ #define CHECK_SAVING_TABLE_ELT(elt) \
+ ((elt)->save_key != stack_free && (elt)->new_key != stack_free \
+ ? save_table_elt (elt) : (elt))
+
/* We don't want a lot of buckets, because we rarely have very many
things stored in the hash table, and a lot of buckets slows
down a lot of loops that happen frequently. */
*************** struct table_elt
*** 503,530 ****
: 2) \
: notreg_cost(X))
! /* Get the info associated with register N. */
#define GET_CSE_REG_INFO(N) \
! (((N) == cached_regno && cached_cse_reg_info) \
! ? cached_cse_reg_info : get_cse_reg_info ((N)))
/* Get the number of times this register has been updated in this
basic block. */
-
#define REG_TICK(N) ((GET_CSE_REG_INFO (N))->reg_tick)
! /* Get the point at which REG was recorded in the table. */
#define REG_IN_TABLE(N) ((GET_CSE_REG_INFO (N))->reg_in_table)
! /* Get the quantity number for REG. */
#define REG_QTY(N) ((GET_CSE_REG_INFO (N))->reg_qty)
! /* Determine if the quantity number for register X represents a valid index
! into the qty_table. */
#define REGNO_QTY_VALID_P(N) (REG_QTY (N) != (N))
#ifdef ADDRESS_COST
--- 597,643 ----
: 2) \
: notreg_cost(X))
! /* Get the info associated with register N. The info is to be used
! only for reading not for modifictaion. */
#define GET_CSE_REG_INFO(N) \
! ((cse_reg_info_table[N].bb_tick == bb_tick) \
! ? &cse_reg_info_table[N] : get_cse_reg_info ((N)))
!
! /* Get the info associated with register N which is to be modified.
! The macro additionaly saves information about original info. Any
! access for modification in cse_reg_info should be made through the
! macro!!! */
!
! #define GET_LVAL_CSE_REG_INFO(N) \
! ((cse_reg_info_table[N].save_key != stack_free \
! ? save_cse_reg_info (N) : 0), \
! (cse_reg_info_table[N].bb_tick == bb_tick) \
! ? &cse_reg_info_table[N] : get_cse_reg_info ((N)))
/* Get the number of times this register has been updated in this
basic block. */
#define REG_TICK(N) ((GET_CSE_REG_INFO (N))->reg_tick)
! /* Get the number of times this register has been updated in this
! basic block for its modification. */
! #define LVAL_REG_TICK(N) ((GET_LVAL_CSE_REG_INFO (N))->reg_tick)
+ /* Get the point at which REG was recorded in the table. */
#define REG_IN_TABLE(N) ((GET_CSE_REG_INFO (N))->reg_in_table)
! /* Get the point at which REG was recorded in the table for its
! modification. */
! #define LVAL_REG_IN_TABLE(N) ((GET_LVAL_CSE_REG_INFO (N))->reg_in_table)
+ /* Get the quantity number for REG. */
#define REG_QTY(N) ((GET_CSE_REG_INFO (N))->reg_qty)
! /* Get the quantity number for REG for its modification. */
! #define LVAL_REG_QTY(N) ((GET_LVAL_CSE_REG_INFO (N))->reg_qty)
+ /* Determine if the quantity number for register X represents a valid
+ index into the qty_table. */
#define REGNO_QTY_VALID_P(N) (REG_QTY (N) != (N))
#ifdef ADDRESS_COST
*************** static struct table_elt *last_jump_equiv
*** 565,576 ****
the insn. */
static int constant_pool_entries_cost;
! /* Define maximum length of a branch path. */
! #define PATHLENGTH 10
! /* This data describes a block that will be processed by cse_basic_block. */
struct cse_basic_block_data
{
--- 678,741 ----
the insn. */
static int constant_pool_entries_cost;
+
+ /* Define initial length of a branch path. */
+
+ #define INIT_PATHLENGTH 10
! /* This structure describes a branch in extended block that will be
! processed by cse_basic_block. */
! struct branch_path_entry
! {
! /* The branch insn. */
! rtx branch;
! /* Whether it should be taken or not. AROUND is the same as taken
! except that it is used when the destination label is not preceded
! by a BARRIER. DIAMDON_AROUND describes control flow
! corresponding to if-then-else statement:
!
! jmpif
!
! / \
! / \
! ... ...
! \ /
! \ /
! \ /
! \ /
! ...
!
! Now DIAMOND_AROUND corresponds only simple (not nested)
! if-then-else statements. It is possibly to implement processing
! also nested if-then[-else] statments. ??? Is it worth. May be it
! is better to rewrite cse and made it dominator based CSE.
!
! For given branch it status can be changed in
! cse_end_of_basic_block in the following ways:
!
! AROUND -> NOT_TAKEN or
! TAKEN -> NOT_TAKEN or
! TAKEN -> DIAMOND_AROUND -> NOT_TAKEN */
! enum taken {TAKEN, NOT_TAKEN, AROUND, DIAMOND_AROUND} status;
! /* The following member is TRUE if the state of CSE before starting
! the branch has been saved. */
! char saved_p;
! /* In the most case, target_insn refers for CODE_LABEL equal to
! JUMP_LABEL (branch). In the case DIAMOND_AROUND, target_insn is
! CODE_LABEL which is the end "diamond" (if-then-else statement).
! Example,
!
! jmpif ELSE <- branch with status DIAMOND_AROUND
! ...
! jmp END
! ELSE: ...
! ...
! END: <- target_insn */
! rtx target_insn;
! };
! typedef struct branch_path_entry *branch_path_t;
struct cse_basic_block_data
{
*************** struct cse_basic_block_data
*** 584,601 ****
rtx last;
/* Size of current branch path, if any. */
int path_size;
! /* Current branch path, indicating which branches will be taken. */
! struct branch_path
! {
! /* The branch insn. */
! rtx branch;
! /* Whether it should be taken or not. AROUND is the same as taken
! except that it is used when the destination label is not preceded
! by a BARRIER. */
! enum taken {TAKEN, NOT_TAKEN, AROUND} status;
! } path[PATHLENGTH];
};
/* Nonzero if X has the form (PLUS frame-pointer integer). We check for
virtual regs here because the simplify_*_operation routines are called
by integrate.c, which is called before virtual register instantiation.
--- 749,797 ----
rtx last;
/* Size of current branch path, if any. */
int path_size;
! /* Current branches path, indicating which branches will be taken. */
! branch_path_t path;
! /* The maximal number of elements which can be placed into path
! currently. */
! int pathlength;
! };
!
! /* The main structure for saving and restoring CSE states before
! starting processing branches. */
!
! struct state
! {
! /* The value of `next_qty' before processing the branch. */
! int next_qty;
! /* The value of `hard_regs_in_table' before processing the branch. */
! HARD_REG_SET hard_regs_in_table;
! /* The value of `table' before processing the branch. ??? Is it the
! size of table sufficiently small to save it all. May be it is
! better to save only changed table elements (usage of a log). */
! struct table_elt *table[HASH_SIZE];
! /* The chain of the hash table elements modified during processing
! insns between two sequential branches. */
! struct table_elt *modified_element_chain;
! /* The chain of the hash table elements created during processing
! insns between two sequential branches. */
! struct table_elt *new_element_chain;
! /* The start and finish indexes of elements of arrays which
! implement the logs of changes in cse_reg_info_table, qty_table,
! and reg_eqv_table during processing insns between two sequential
! branches. */
! int start_reg_info, free_reg_info;
! int start_qty_elem, free_qty_elem;
! int start_reg_eqv, free_reg_eqv;
};
+ /* Saving and restoring CES states are implemented by the following
+ stack. */
+ static struct state *stack;
+ /* Index of the first free state entry on the stack top. */
+ static stack_free;
+ /* The current allocated length of stack in states. */
+ static int stack_length;
+
/* Nonzero if X has the form (PLUS frame-pointer integer). We check for
virtual regs here because the simplify_*_operation routines are called
by integrate.c, which is called before virtual register instantiation.
*************** struct cse_basic_block_data
*** 646,657 ****
--- 842,873 ----
|| GET_CODE (X) == ADDRESSOF)
static int notreg_cost PARAMS ((rtx));
+ static int save_cse_reg_info PARAMS ((int));
+ static void pop_cse_reg_info PARAMS ((void));
+ static void reject_cse_reg_info_log PARAMS ((void));
+ static void free_stack PARAMS ((void));
+ static void init_stack PARAMS ((void));
+ static void finish_stack PARAMS ((void));
+ static void push_state PARAMS ((void));
+ static void pop_state PARAMS ((void));
static void new_basic_block PARAMS ((void));
static void make_new_qty PARAMS ((int, enum machine_mode));
+ static struct qty_table_elem *save_qty_table_elem
+ PARAMS ((struct qty_table_elem *));
+ static void pop_qty_table PARAMS ((void));
+ static void reject_qty_table_log PARAMS ((void));
+ static struct reg_eqv_elem *save_reg_eqv_table_elem PARAMS ((int));
+ static void pop_reg_eqv_table PARAMS ((void));
+ static void reject_reg_eqv_table_log PARAMS ((void));
static void make_regs_eqv PARAMS ((int, int));
static void delete_reg_equiv PARAMS ((int));
static int mention_regs PARAMS ((rtx));
+ static struct table_elt *save_table_elt PARAMS ((struct table_elt *));
+ static void restore_table PARAMS ((void));
+ static void reject_table_log PARAMS ((void));
static int insert_regs PARAMS ((rtx, struct table_elt *, int));
+ static void free_element PARAMS ((struct table_elt *));
+ static struct table_elt *get_element PARAMS ((int));
static void remove_from_table PARAMS ((struct table_elt *, unsigned));
static struct table_elt *lookup PARAMS ((rtx, unsigned, enum machine_mode)),
*lookup_for_remove PARAMS ((rtx, unsigned, enum machine_mode));
*************** static void invalidate_from_clobbers PAR
*** 687,700 ****
static rtx cse_process_notes PARAMS ((rtx, rtx));
static void cse_around_loop PARAMS ((rtx));
static void invalidate_skipped_set PARAMS ((rtx, rtx, void *));
! static void invalidate_skipped_block PARAMS ((rtx));
static void cse_check_loop_start PARAMS ((rtx, rtx, void *));
static void cse_set_around_loop PARAMS ((rtx, rtx, rtx));
! static rtx cse_basic_block PARAMS ((rtx, rtx, struct branch_path *, int));
static void count_reg_usage PARAMS ((rtx, int *, rtx, int));
extern void dump_class PARAMS ((struct table_elt*));
static struct cse_reg_info* get_cse_reg_info PARAMS ((int));
-
static void flush_hash_table PARAMS ((void));
/* Dump the expressions in the equivalence class indicated by CLASSP.
--- 903,921 ----
static rtx cse_process_notes PARAMS ((rtx, rtx));
static void cse_around_loop PARAMS ((rtx));
static void invalidate_skipped_set PARAMS ((rtx, rtx, void *));
! static rtx invalidate_skipped_block PARAMS ((rtx));
static void cse_check_loop_start PARAMS ((rtx, rtx, void *));
static void cse_set_around_loop PARAMS ((rtx, rtx, rtx));
! static void init_path PARAMS ((struct cse_basic_block_data *));
! static void finish_path PARAMS ((struct cse_basic_block_data *));
! static void check_pathlength PARAMS ((struct cse_basic_block_data *, int));
! static rtx cse_end_of_basic_block PARAMS ((rtx,
! struct cse_basic_block_data *,
! int *,int, int, int));
! static rtx cse_basic_block PARAMS ((rtx, rtx, int, struct branch_path_entry *, int, FILE *));
static void count_reg_usage PARAMS ((rtx, int *, rtx, int));
extern void dump_class PARAMS ((struct table_elt*));
static struct cse_reg_info* get_cse_reg_info PARAMS ((int));
static void flush_hash_table PARAMS ((void));
/* Dump the expressions in the equivalence class indicated by CLASSP.
*************** rtx_cost (x, outer_code)
*** 837,935 ****
return total;
}
static struct cse_reg_info *
get_cse_reg_info (regno)
int regno;
{
! struct cse_reg_info **hash_head = ®_hash[REGHASH_FN (regno)];
! struct cse_reg_info *p;
! for (p = *hash_head ; p != NULL; p = p->hash_next)
! if (p->regno == regno)
! break;
! if (p == NULL)
{
! /* Get a new cse_reg_info structure. */
! if (cse_reg_info_free_list)
! {
! p = cse_reg_info_free_list;
! cse_reg_info_free_list = p->next;
! }
! else
! p = (struct cse_reg_info *) xmalloc (sizeof (struct cse_reg_info));
! /* Insert into hash table. */
! p->hash_next = *hash_head;
! *hash_head = p;
! /* Initialize it. */
! p->reg_tick = 1;
! p->reg_in_table = -1;
! p->reg_qty = regno;
! p->regno = regno;
! p->next = cse_reg_info_used_list;
! cse_reg_info_used_list = p;
! if (!cse_reg_info_used_list_end)
! cse_reg_info_used_list_end = p;
}
! /* Cache this lookup; we tend to be looking up information about the
! same register several times in a row. */
! cached_regno = regno;
! cached_cse_reg_info = p;
! return p;
}
! /* Clear the hash table and initialize each register with its own quantity,
! for a new basic block. */
static void
new_basic_block ()
{
register int i;
next_qty = max_reg;
-
- /* Clear out hash table state for this pass. */
! bzero ((char *) reg_hash, sizeof reg_hash);
- if (cse_reg_info_used_list)
- {
- cse_reg_info_used_list_end->next = cse_reg_info_free_list;
- cse_reg_info_free_list = cse_reg_info_used_list;
- cse_reg_info_used_list = cse_reg_info_used_list_end = 0;
- }
- cached_cse_reg_info = 0;
-
CLEAR_HARD_REG_SET (hard_regs_in_table);
/* The per-quantity values used to be initialized here, but it is
much faster to initialize each as it is made in `make_new_qty'. */
for (i = 0; i < HASH_SIZE; i++)
! {
! struct table_elt *first;
!
! first = table[i];
! if (first != NULL)
! {
! struct table_elt *last = first;
!
! table[i] = NULL;
!
! while (last->next_same_hash != NULL)
! last = last->next_same_hash;
!
! /* Now relink this hash entire chain into
! the free element list. */
! last->next_same_hash = free_element_chain;
! free_element_chain = first;
! }
! }
prev_insn = 0;
--- 1058,1253 ----
return total;
}
+
+ /* The following function returns initialized cse_reg_info for
+ REGNO. */
static struct cse_reg_info *
get_cse_reg_info (regno)
int regno;
{
! struct cse_reg_info *cri;
! cri = &cse_reg_info_table [regno];
!
! /* See if we already have this entry. */
! if (cri->save_key == stack_free && cri->bb_tick == bb_tick)
! abort ();
!
! /* Initialize it. */
! cri->regno = regno;
! cri->save_key = 0;
! cri->reg_tick = 0;
! cri->reg_in_table = -1;
! cri->reg_qty = regno;
! cri->bb_tick = bb_tick;
!
! return cri;
! }
! /* The following function saves the current value of cse_reg_info for
! REGNO. */
! static int
! save_cse_reg_info (regno)
! int regno;
! {
! struct cse_reg_info *cri;
!
! cri = &cse_reg_info_table [regno];
!
! if (stack_free == 0 || cri->save_key == stack_free)
! abort ();
! if (saved_cse_reg_info_table == NULL)
{
! saved_cse_reg_info_table
! = xmalloc (max_reg * sizeof (struct cse_reg_info));
! saved_cse_reg_info_table_size = max_reg;
! }
! else if (stack [stack_free - 1].free_reg_info
! >= saved_cse_reg_info_table_size)
! {
! saved_cse_reg_info_table_size *= 2;
! saved_cse_reg_info_table = xrealloc (saved_cse_reg_info_table,
! saved_cse_reg_info_table_size
! * sizeof (struct cse_reg_info));
! }
! saved_cse_reg_info_table [stack [stack_free - 1].free_reg_info++]
! = *cri;
! cri->save_key = stack_free;
! return 0;
! }
! /* The following function restores previous cse_reg_info_table. */
! static void
! pop_cse_reg_info ()
! {
! struct cse_reg_info *cri;
! for (cri = saved_cse_reg_info_table + stack [stack_free - 1].start_reg_info;
! cri < saved_cse_reg_info_table + stack [stack_free - 1].free_reg_info;
! cri++)
! {
! if (cri->regno >= max_reg)
! abort ();
! cse_reg_info_table [cri->regno] = *cri;
}
+ }
! /* The following function rejects log of changes in
! cse_reg_info_table. */
! static void
! reject_cse_reg_info_log ()
! {
! }
!
! /* The following function rejects all saved CSE information. */
! static void
! free_stack ()
! {
! while (stack_free)
! {
! reject_cse_reg_info_log ();
! reject_qty_table_log ();
! reject_reg_eqv_table_log ();
! reject_table_log ();
! stack_free--;
! }
! }
! /* The following function initiates the stack of CSE states. */
! static void
! init_stack ()
! {
! stack_length = INIT_PATHLENGTH;
! stack = xmalloc (stack_length * sizeof (struct state));
! stack_free = 0;
}
! /* The following function finishes work with the stack of CSE states. */
! static void
! finish_stack ()
! {
! free (stack);
! }
+ /* The following function initiates saving CSE on the stack top. */
static void
+ push_state ()
+ {
+ if (stack_length <= stack_free)
+ {
+ stack_length *= 2;
+ stack = xrealloc (stack, stack_length * sizeof (struct state));
+ }
+ COPY_HARD_REG_SET (stack[stack_free].hard_regs_in_table, hard_regs_in_table);
+ stack[stack_free].next_qty = next_qty;
+ memcpy (stack[stack_free].table, table, sizeof (table));
+ stack[stack_free].modified_element_chain
+ = stack[stack_free].new_element_chain = NULL;
+ if (stack_free == 0)
+ {
+ stack[stack_free].start_reg_info = stack[stack_free].free_reg_info = 0;
+ stack[stack_free].start_qty_elem = stack[stack_free].free_qty_elem = 0;
+ stack[stack_free].start_reg_eqv = stack[stack_free].free_reg_eqv = 0;
+ }
+ else
+ {
+ stack[stack_free].start_reg_info
+ = stack[stack_free].free_reg_info
+ = stack[stack_free - 1].free_reg_info;
+ stack[stack_free].start_qty_elem
+ = stack[stack_free].free_qty_elem
+ = stack[stack_free - 1].free_qty_elem;
+ stack[stack_free].start_reg_eqv
+ = stack[stack_free].free_reg_eqv
+ = stack[stack_free - 1].free_reg_eqv;
+ }
+ stack_free++;
+ }
+
+ /* The following function restores CSE state saved on the stack top. */
+ static void
+ pop_state ()
+ {
+ if (stack_free <= 0)
+ abort ();
+ pop_cse_reg_info ();
+ pop_qty_table ();
+ pop_reg_eqv_table ();
+ restore_table ();
+ stack_free--;
+ COPY_HARD_REG_SET (hard_regs_in_table, stack[stack_free].hard_regs_in_table);
+ next_qty = stack[stack_free].next_qty;
+ }
+
+ /* Clear the hash table and initialize each register with its own
+ quantity, for a new basic block. If there is saved CSE states,
+ they are all rejected. */
+ static void
new_basic_block ()
{
register int i;
+ register struct table_elt *this, *next;
next_qty = max_reg;
! bb_tick++;
CLEAR_HARD_REG_SET (hard_regs_in_table);
+ if (stack_free)
+ free_stack ();
+
/* The per-quantity values used to be initialized here, but it is
much faster to initialize each as it is made in `make_new_qty'. */
for (i = 0; i < HASH_SIZE; i++)
! for (this = table[i]; this; this = next)
! {
! next = this->next_same_hash;
! free_element (this);
! }
! bzero ((char *) table, sizeof table);
prev_insn = 0;
*************** new_basic_block ()
*** 939,945 ****
}
/* Say that register REG contains a quantity in mode MODE not in any
! register before and initialize that quantity. */
static void
make_new_qty (reg, mode)
--- 1257,1264 ----
}
/* Say that register REG contains a quantity in mode MODE not in any
! register before and initialize that quantity. The function may save
! qty_table and reg_eqv_table elements for REG. */
static void
make_new_qty (reg, mode)
*************** make_new_qty (reg, mode)
*** 953,960 ****
if (next_qty >= max_qty)
abort ();
! q = REG_QTY (reg) = next_qty++;
ent = &qty_table[q];
ent->first_reg = reg;
ent->last_reg = reg;
ent->mode = mode;
--- 1272,1281 ----
if (next_qty >= max_qty)
abort ();
! q = LVAL_REG_QTY (reg) = next_qty++;
ent = &qty_table[q];
+ ent->qty = q;
+ ent->save_key = 0;
ent->first_reg = reg;
ent->last_reg = reg;
ent->mode = mode;
*************** make_new_qty (reg, mode)
*** 962,974 ****
ent->comparison_code = UNKNOWN;
eqv = ®_eqv_table[reg];
! eqv->next = eqv->prev = -1;
}
! /* Make reg NEW equivalent to reg OLD.
! OLD is not changing; NEW is. */
static void
make_regs_eqv (new, old)
register int new, old;
{
--- 1283,1409 ----
ent->comparison_code = UNKNOWN;
eqv = ®_eqv_table[reg];
! CHECK_SAVING_REG_EQV (reg)->next = -1;
! eqv->prev = -1;
! }
!
! /* The function saves element ENT of qty_table for further
! restoring. */
! static struct qty_table_elem *
! save_qty_table_elem (ent)
! struct qty_table_elem *ent;
! {
! if (stack_free == 0 || ent->save_key == stack_free)
! abort ();
! if (saved_qty_table == NULL)
! {
! saved_qty_table_size = max_qty - max_reg;
! if (max_qty < max_reg)
! abort ();
! saved_qty_table = xmalloc (saved_qty_table_size
! * sizeof (struct qty_table_elem));
! }
! else if (stack[stack_free - 1].free_qty_elem >= saved_qty_table_size)
! {
! saved_qty_table_size *= 2;
! saved_qty_table = xrealloc (saved_qty_table,
! saved_qty_table_size
! * sizeof (struct qty_table_elem));
! }
! saved_qty_table [stack[stack_free - 1].free_qty_elem++] = *ent;
! if (stack [stack_free - 1].free_qty_elem > (max_qty - max_reg))
! abort ();
! ent->save_key = stack_free;
! return ent;
}
! /* The following function restores qty_table saved on the stack
! top. */
! static void
! pop_qty_table ()
! {
! struct qty_table_elem *ent;
!
! if (stack[stack_free - 1].free_qty_elem > (max_qty - max_reg))
! abort ();
! for (ent = saved_qty_table + stack[stack_free - 1].start_qty_elem;
! ent < saved_qty_table + stack[stack_free - 1].free_qty_elem;
! ent++)
! if (ent->qty < stack[stack_free - 1].next_qty)
! {
! if (ent->qty < max_reg)
! abort ();
! qty_table [ent->qty] = *ent;
! }
! }
+ /* The following function rejects log of changes in qty_table. */
static void
+ reject_qty_table_log ()
+ {
+ next_qty = stack[stack_free - 1].next_qty;
+ }
+
+ /* The function saves element of saved_reg_eqv_table for REGNO. */
+ static struct reg_eqv_elem *
+ save_reg_eqv_table_elem (regno)
+ int regno;
+ {
+ struct reg_eqv_elem *eqv = ®_eqv_table [regno];
+
+ if (stack_free == 0 || eqv->save_key == stack_free)
+ abort ();
+ eqv->regno = regno;
+ if (saved_reg_eqv_table == NULL)
+ {
+ saved_reg_eqv_table
+ = xmalloc (max_reg * sizeof(struct reg_eqv_elem));
+ saved_reg_eqv_table_size = max_reg;
+ }
+ else if (stack[stack_free - 1].free_reg_eqv >= saved_reg_eqv_table_size)
+ {
+ saved_reg_eqv_table_size *= 2;
+ saved_reg_eqv_table = xrealloc (saved_reg_eqv_table,
+ saved_reg_eqv_table_size
+ * sizeof(struct reg_eqv_elem));
+ }
+ saved_reg_eqv_table [stack[stack_free - 1].free_reg_eqv++] = *eqv;
+ eqv->save_key = stack_free;
+ return eqv;
+ }
+
+ /* The following function restores reg_eqv_table saved on the stack
+ top. */
+ static void
+ pop_reg_eqv_table ()
+ {
+ struct reg_eqv_elem *eqv;
+
+ for (eqv = saved_reg_eqv_table + stack[stack_free - 1].start_reg_eqv;
+ eqv < saved_reg_eqv_table + stack[stack_free - 1].free_reg_eqv;
+ eqv++)
+ {
+ if (eqv->regno >= max_reg)
+ abort ();
+ reg_eqv_table [eqv->regno] = *eqv;
+ }
+ }
+
+ /* The following function rejects log of changes in reg_eqv_table. */
+ static void
+ reject_reg_eqv_table_log ()
+ {
+ struct reg_eqv_elem *eqv;
+
+ for (eqv = saved_reg_eqv_table + stack[stack_free - 1].start_reg_eqv;
+ eqv < saved_reg_eqv_table + stack[stack_free - 1].free_reg_eqv;
+ eqv++)
+ reg_eqv_table [eqv->regno].save_key = eqv->save_key;
+ }
+
+ /* Make reg NEW equivalent to reg OLD. OLD is not changing; NEW is. */
+
+ static void
make_regs_eqv (new, old)
register int new, old;
{
*************** make_regs_eqv (new, old)
*** 982,988 ****
if (! REGNO_QTY_VALID_P (old))
abort ();
! REG_QTY (new) = q;
firstr = ent->first_reg;
lastr = ent->last_reg;
--- 1417,1423 ----
if (! REGNO_QTY_VALID_P (old))
abort ();
! LVAL_REG_QTY (new) = q;
firstr = ent->first_reg;
lastr = ent->last_reg;
*************** make_regs_eqv (new, old)
*** 1005,1014 ****
&& (uid_cuid[REGNO_LAST_UID (new)]
> uid_cuid[REGNO_LAST_UID (firstr)]))))))
{
! reg_eqv_table[firstr].prev = new;
! reg_eqv_table[new].next = firstr;
reg_eqv_table[new].prev = -1;
! ent->first_reg = new;
}
else
{
--- 1440,1449 ----
&& (uid_cuid[REGNO_LAST_UID (new)]
> uid_cuid[REGNO_LAST_UID (firstr)]))))))
{
! CHECK_SAVING_REG_EQV (firstr)->prev = new;
! CHECK_SAVING_REG_EQV (new)->next = firstr;
reg_eqv_table[new].prev = -1;
! CHECK_SAVING_QTY (ent)->first_reg = new;
}
else
{
*************** make_regs_eqv (new, old)
*** 1020,1032 ****
&& (REGNO_REG_CLASS (lastr) == NO_REGS || ! FIXED_REGNO_P (lastr))
&& new >= FIRST_PSEUDO_REGISTER)
lastr = reg_eqv_table[lastr].prev;
! reg_eqv_table[new].next = reg_eqv_table[lastr].next;
if (reg_eqv_table[lastr].next >= 0)
! reg_eqv_table[reg_eqv_table[lastr].next].prev = new;
else
! qty_table[q].last_reg = new;
! reg_eqv_table[lastr].next = new;
! reg_eqv_table[new].prev = lastr;
}
}
--- 1455,1467 ----
&& (REGNO_REG_CLASS (lastr) == NO_REGS || ! FIXED_REGNO_P (lastr))
&& new >= FIRST_PSEUDO_REGISTER)
lastr = reg_eqv_table[lastr].prev;
! CHECK_SAVING_REG_EQV (new)->next = reg_eqv_table[lastr].next;
if (reg_eqv_table[lastr].next >= 0)
! CHECK_SAVING_REG_EQV (reg_eqv_table[lastr].next)->prev = new;
else
! CHECK_SAVING_QTY (&qty_table[q])->last_reg = new;
! CHECK_SAVING_REG_EQV (lastr)->next = new;
! CHECK_SAVING_REG_EQV (new)->prev = lastr;
}
}
*************** delete_reg_equiv (reg)
*** 1050,1064 ****
n = reg_eqv_table[reg].next;
if (n != -1)
! reg_eqv_table[n].prev = p;
else
! ent->last_reg = p;
if (p != -1)
! reg_eqv_table[p].next = n;
else
! ent->first_reg = n;
! REG_QTY (reg) = reg;
}
/* Remove any invalid expressions from the hash table
--- 1485,1499 ----
n = reg_eqv_table[reg].next;
if (n != -1)
! CHECK_SAVING_REG_EQV (n)->prev = p;
else
! CHECK_SAVING_QTY (ent)->last_reg = p;
if (p != -1)
! CHECK_SAVING_REG_EQV (p)->next = n;
else
! CHECK_SAVING_QTY (ent)->first_reg = n;
! LVAL_REG_QTY (reg) = reg;
}
/* Remove any invalid expressions from the hash table
*************** mention_regs (x)
*** 1099,1105 ****
if (REG_IN_TABLE (i) >= 0 && REG_IN_TABLE (i) != REG_TICK (i))
remove_invalid_refs (i);
! REG_IN_TABLE (i) = REG_TICK (i);
}
return 0;
--- 1534,1540 ----
if (REG_IN_TABLE (i) >= 0 && REG_IN_TABLE (i) != REG_TICK (i))
remove_invalid_refs (i);
! LVAL_REG_IN_TABLE (i) = REG_TICK (i);
}
return 0;
*************** mention_regs (x)
*** 1125,1131 ****
remove_invalid_subreg_refs (i, SUBREG_WORD (x), GET_MODE (x));
}
! REG_IN_TABLE (i) = REG_TICK (i);
return 0;
}
--- 1560,1566 ----
remove_invalid_subreg_refs (i, SUBREG_WORD (x), GET_MODE (x));
}
! LVAL_REG_IN_TABLE (i) = REG_TICK (i);
return 0;
}
*************** mention_regs (x)
*** 1169,1174 ****
--- 1604,1715 ----
return changed;
}
+ /* The following function saves the current value of ELT of the hash
+ table for further restoring. */
+ static struct table_elt *
+ save_table_elt (elt)
+ struct table_elt *elt;
+ {
+ struct table_elt *copy_elt;
+
+ if (stack_free == 0 || elt->save_key == stack_free)
+ abort ();
+ copy_elt = get_element (FALSE);
+ *copy_elt = *elt;
+ elt->save_key = stack_free;
+ copy_elt->orig = elt;
+ copy_elt->chain = stack[stack_free - 1].modified_element_chain;
+ stack[stack_free - 1].modified_element_chain = copy_elt;
+ if (copy_elt->save_key == stack_free)
+ abort ();
+ return elt;
+ }
+
+ /* The following function restores previous hash table. */
+ static void
+ restore_table ()
+ {
+ register struct table_elt *this, *next, *orig;
+
+ for (this = stack[stack_free - 1].new_element_chain; this; this = next)
+ {
+ next = this->chain;
+ free_element (this);
+ }
+ for (this = stack[stack_free - 1].modified_element_chain;
+ this;
+ this = next)
+ {
+ next = this->chain;
+ orig = this->orig;
+ this->orig = this->chain = NULL;
+ *orig = *this;
+ if (orig->save_key == stack_free)
+ abort ();
+ free_element (this);
+ }
+ memcpy (table, stack [stack_free - 1].table, sizeof (table));
+ }
+
+ /* The following function rejects log of changes in the hash table. */
+ static void
+ reject_table_log ()
+ {
+ register struct table_elt *this, *next;
+
+ for (this = stack[stack_free - 1].new_element_chain; this; this = next)
+ {
+ next = this->chain;
+ free_element (this);
+ }
+ for (this = stack[stack_free - 1].modified_element_chain;
+ this;
+ this = next)
+ {
+ next = this->chain;
+ this->orig = this->chain = NULL;
+ free_element (this);
+ }
+ }
+
+ #if 0
+
+ /* The following function prints the hash table. Use it for hard cases
+ in debugging cse. */
+ static void
+ print_table ()
+ {
+ int i;
+ struct table_elt *elt;
+
+ fprintf (stderr, "\n\n");
+ for (i = 0; i < HASH_SIZE; i++)
+ {
+ fprintf (stderr, "Busket = %d: %lx\n", i, (unsigned long) table[i]);
+ for (elt = table[i]; elt; elt = elt->next_same_hash)
+ {
+ fprintf (stderr,
+ " next_{hash,value}=%lx,%lx; prev_{hash,value}=%lx,%lx;\n",
+ (unsigned long) elt->next_same_hash,
+ (unsigned long) elt->next_same_value,
+ (unsigned long) elt->prev_same_hash,
+ (unsigned long) elt->prev_same_value);
+ fprintf (stderr,
+ " {first,related} value=%lx,%lx; cost=%d, mode=%d,",
+ (unsigned long) elt->first_same_value,
+ (unsigned long) elt->related_value,
+ elt->cost, elt->mode);
+ fprintf (stderr, " in_memory=%d, is_const=%d, flag=%d\n",
+ elt->in_memory, elt->is_const, elt->flag);
+ fprintf (stderr, " new=%d,save=%d, chain=%lx, orig=%lx\n",
+ elt->new_key, elt->save_key, (unsigned long) elt->chain,
+ (unsigned long) elt->orig);
+ }
+ }
+ }
+
+ #endif
+
/* Update the register quantities for inserting X into the hash table
with a value equivalent to CLASSP.
(If the class does not contain a REG, it is irrelevant.)
*************** insert_regs (x, classp, modified)
*** 1242,1248 ****
will do the right thing. */
if (REG_IN_TABLE (regno) >= 0
&& REG_TICK (regno) == REG_IN_TABLE (regno) + 1)
! REG_TICK (regno)++;
mention_regs (x);
return 1;
}
--- 1783,1789 ----
will do the right thing. */
if (REG_IN_TABLE (regno) >= 0
&& REG_TICK (regno) == REG_IN_TABLE (regno) + 1)
! LVAL_REG_TICK (regno)++;
mention_regs (x);
return 1;
}
*************** insert_regs (x, classp, modified)
*** 1252,1257 ****
--- 1793,1845 ----
/* Look in or update the hash table. */
+ /* Put the element ELT on the list of free elements. */
+
+ static void
+ free_element (elt)
+ struct table_elt *elt;
+ {
+ /* Now add it to the free element chain. */
+ if (stack_free == 0)
+ {
+ elt->chain = free_element_chain;
+ free_element_chain = elt;
+ }
+ }
+
+ /* Return an new table element that is free for use. Add the element
+ into new_element_chain if we should save CSE state and LOG_P is
+ TRUE. */
+
+ static struct table_elt *
+ get_element (log_p)
+ int log_p;
+ {
+ struct table_elt *elt = free_element_chain;
+
+ if (elt)
+ free_element_chain = elt->chain;
+ else
+ {
+ n_elements_made++;
+ elt = (struct table_elt *) oballoc (sizeof (struct table_elt));
+ }
+ if (stack_free && log_p)
+ {
+ elt->chain = stack[stack_free - 1].new_element_chain;
+ stack[stack_free - 1].new_element_chain = elt;
+ elt->new_key = stack_free;
+ }
+ else
+ {
+ elt->chain = 0;
+ elt->new_key = 0;
+ }
+ elt->save_key = 0;
+ elt->orig = NULL;
+ return elt;
+ }
+
/* Remove table element ELT from use in the table.
HASH is its hash code, made using the HASH macro.
It's an argument because often that is known in advance
*************** remove_from_table (elt, hash)
*** 1266,1272 ****
return;
/* Mark this element as removed. See cse_insn. */
! elt->first_same_value = 0;
/* Remove the table element from its equivalence class. */
--- 1854,1860 ----
return;
/* Mark this element as removed. See cse_insn. */
! CHECK_SAVING_TABLE_ELT (elt)->first_same_value = 0;
/* Remove the table element from its equivalence class. */
*************** remove_from_table (elt, hash)
*** 1274,1289 ****
register struct table_elt *prev = elt->prev_same_value;
register struct table_elt *next = elt->next_same_value;
! if (next) next->prev_same_value = prev;
if (prev)
! prev->next_same_value = next;
else
{
register struct table_elt *newfirst = next;
while (next)
{
! next->first_same_value = newfirst;
next = next->next_same_value;
}
}
--- 1862,1877 ----
register struct table_elt *prev = elt->prev_same_value;
register struct table_elt *next = elt->next_same_value;
! if (next) CHECK_SAVING_TABLE_ELT (next)->prev_same_value = prev;
if (prev)
! CHECK_SAVING_TABLE_ELT (prev)->next_same_value = next;
else
{
register struct table_elt *newfirst = next;
while (next)
{
! CHECK_SAVING_TABLE_ELT (next)->first_same_value = newfirst;
next = next->next_same_value;
}
}
*************** remove_from_table (elt, hash)
*** 1295,1304 ****
register struct table_elt *prev = elt->prev_same_hash;
register struct table_elt *next = elt->next_same_hash;
! if (next) next->prev_same_hash = prev;
if (prev)
! prev->next_same_hash = next;
else if (table[hash] == elt)
table[hash] = next;
else
--- 1883,1892 ----
register struct table_elt *prev = elt->prev_same_hash;
register struct table_elt *next = elt->next_same_hash;
! if (next) CHECK_SAVING_TABLE_ELT (next)->prev_same_hash = prev;
if (prev)
! CHECK_SAVING_TABLE_ELT (prev)->next_same_hash = next;
else if (table[hash] == elt)
table[hash] = next;
else
*************** remove_from_table (elt, hash)
*** 1320,1333 ****
register struct table_elt *p = elt->related_value;
while (p->related_value != elt)
p = p->related_value;
! p->related_value = elt->related_value;
if (p->related_value == p)
p->related_value = 0;
}
! /* Now add it to the free element chain. */
! elt->next_same_hash = free_element_chain;
! free_element_chain = elt;
}
/* Look up X in the hash table and return its table element,
--- 1908,1919 ----
register struct table_elt *p = elt->related_value;
while (p->related_value != elt)
p = p->related_value;
! CHECK_SAVING_TABLE_ELT (p)->related_value = elt->related_value;
if (p->related_value == p)
p->related_value = 0;
}
! free_element (elt);
}
/* Look up X in the hash table and return its table element,
*************** insert (x, classp, hash, mode)
*** 1479,1496 ****
recorded_label_ref = 1;
/* Put an element for X into the right hash bucket. */
-
- elt = free_element_chain;
- if (elt)
- {
- free_element_chain = elt->next_same_hash;
- }
- else
- {
- n_elements_made++;
- elt = (struct table_elt *) oballoc (sizeof (struct table_elt));
- }
elt->exp = x;
elt->cost = COST (x);
elt->next_same_value = 0;
--- 2065,2072 ----
recorded_label_ref = 1;
/* Put an element for X into the right hash bucket. */
+ elt = get_element (TRUE);
elt->exp = x;
elt->cost = COST (x);
elt->next_same_value = 0;
*************** insert (x, classp, hash, mode)
*** 1509,1515 ****
|| FIXED_BASE_PLUS_P (x));
if (table[hash])
! table[hash]->prev_same_hash = elt;
table[hash] = elt;
/* Put it into the proper value-class. */
--- 2085,2091 ----
|| FIXED_BASE_PLUS_P (x));
if (table[hash])
! CHECK_SAVING_TABLE_ELT (table[hash])->prev_same_hash = elt;
table[hash] = elt;
/* Put it into the proper value-class. */
*************** insert (x, classp, hash, mode)
*** 1520,1531 ****
/* Insert at the head of the class */
{
register struct table_elt *p;
! elt->next_same_value = classp;
! classp->prev_same_value = elt;
elt->first_same_value = elt;
for (p = classp; p; p = p->next_same_value)
! p->first_same_value = elt;
}
else
{
--- 2096,2107 ----
/* Insert at the head of the class */
{
register struct table_elt *p;
! CHECK_SAVING_TABLE_ELT (elt)->next_same_value = classp;
elt->first_same_value = elt;
+ CHECK_SAVING_TABLE_ELT (classp)->prev_same_value = elt;
for (p = classp; p; p = p->next_same_value)
! CHECK_SAVING_TABLE_ELT (p)->first_same_value = elt;
}
else
{
*************** insert (x, classp, hash, mode)
*** 1535,1550 ****
for (p = classp; (next = p->next_same_value) && CHEAPER (next, elt);
p = next);
/* Put it after P and before NEXT. */
! elt->next_same_value = next;
! if (next)
! next->prev_same_value = elt;
elt->prev_same_value = p;
- p->next_same_value = elt;
elt->first_same_value = classp;
}
}
else
! elt->first_same_value = elt;
/* If this is a constant being set equivalent to a register or a register
being set equivalent to a constant, note the constant equivalence.
--- 2111,2126 ----
for (p = classp; (next = p->next_same_value) && CHEAPER (next, elt);
p = next);
/* Put it after P and before NEXT. */
! CHECK_SAVING_TABLE_ELT (elt)->next_same_value = next;
elt->prev_same_value = p;
elt->first_same_value = classp;
+ if (next)
+ CHECK_SAVING_TABLE_ELT (next)->prev_same_value = elt;
+ CHECK_SAVING_TABLE_ELT (p)->next_same_value = elt;
}
}
else
! CHECK_SAVING_TABLE_ELT (elt)->first_same_value = elt;
/* If this is a constant being set equivalent to a register or a register
being set equivalent to a constant, note the constant equivalence.
*************** insert (x, classp, hash, mode)
*** 1567,1573 ****
int exp_q = REG_QTY (REGNO (classp->exp));
struct qty_table_elem *exp_ent = &qty_table[exp_q];
! exp_ent->const_rtx = gen_lowpart_if_possible (exp_ent->mode, x);
exp_ent->const_insn = this_insn;
}
--- 2143,2150 ----
int exp_q = REG_QTY (REGNO (classp->exp));
struct qty_table_elem *exp_ent = &qty_table[exp_q];
! CHECK_SAVING_QTY (exp_ent)->const_rtx
! = gen_lowpart_if_possible (exp_ent->mode, x);
exp_ent->const_insn = this_insn;
}
*************** insert (x, classp, hash, mode)
*** 1585,1591 ****
int x_q = REG_QTY (REGNO (x));
struct qty_table_elem *x_ent = &qty_table[x_q];
! x_ent->const_rtx = gen_lowpart_if_possible (GET_MODE (x), p->exp);
x_ent->const_insn = this_insn;
break;
}
--- 2162,2169 ----
int x_q = REG_QTY (REGNO (x));
struct qty_table_elem *x_ent = &qty_table[x_q];
! CHECK_SAVING_QTY (x_ent)->const_rtx
! = gen_lowpart_if_possible (GET_MODE (x), p->exp);
x_ent->const_insn = this_insn;
break;
}
*************** insert (x, classp, hash, mode)
*** 1595,1601 ****
else if (GET_CODE (x) == REG
&& qty_table[REG_QTY (REGNO (x))].const_rtx
&& GET_MODE (x) == qty_table[REG_QTY (REGNO (x))].mode)
! qty_table[REG_QTY (REGNO (x))].const_insn = this_insn;
/* If this is a constant with symbolic value,
and it has a term with an explicit integer value,
--- 2173,2179 ----
else if (GET_CODE (x) == REG
&& qty_table[REG_QTY (REGNO (x))].const_rtx
&& GET_MODE (x) == qty_table[REG_QTY (REGNO (x))].mode)
! CHECK_SAVING_QTY (&qty_table[REG_QTY (REGNO (x))])->const_insn = this_insn;
/* If this is a constant with symbolic value,
and it has a term with an explicit integer value,
*************** insert (x, classp, hash, mode)
*** 1615,1629 ****
subelt = insert (subexp, NULL_PTR, subhash, mode);
/* Initialize SUBELT's circular chain if it has none. */
if (subelt->related_value == 0)
! subelt->related_value = subelt;
/* Find the element in the circular chain that precedes SUBELT. */
subelt_prev = subelt;
while (subelt_prev->related_value != subelt)
subelt_prev = subelt_prev->related_value;
/* Put new ELT into SUBELT's circular chain just before SUBELT.
This way the element that follows SUBELT is the oldest one. */
! elt->related_value = subelt_prev->related_value;
! subelt_prev->related_value = elt;
}
}
--- 2193,2208 ----
subelt = insert (subexp, NULL_PTR, subhash, mode);
/* Initialize SUBELT's circular chain if it has none. */
if (subelt->related_value == 0)
! CHECK_SAVING_TABLE_ELT (subelt)->related_value = subelt;
/* Find the element in the circular chain that precedes SUBELT. */
subelt_prev = subelt;
while (subelt_prev->related_value != subelt)
subelt_prev = subelt_prev->related_value;
/* Put new ELT into SUBELT's circular chain just before SUBELT.
This way the element that follows SUBELT is the oldest one. */
! CHECK_SAVING_TABLE_ELT (elt)->related_value
! = subelt_prev->related_value;
! CHECK_SAVING_TABLE_ELT (subelt_prev)->related_value = elt;
}
}
*************** invalidate (x, full_mode)
*** 1747,1753 ****
overlap these registers. */
delete_reg_equiv (regno);
! REG_TICK (regno)++;
if (regno >= FIRST_PSEUDO_REGISTER)
{
--- 2326,2332 ----
overlap these registers. */
delete_reg_equiv (regno);
! LVAL_REG_TICK (regno)++;
if (regno >= FIRST_PSEUDO_REGISTER)
{
*************** invalidate (x, full_mode)
*** 1773,1779 ****
in_table |= TEST_HARD_REG_BIT (hard_regs_in_table, i);
CLEAR_HARD_REG_BIT (hard_regs_in_table, i);
delete_reg_equiv (i);
! REG_TICK (i)++;
}
if (in_table)
--- 2352,2358 ----
in_table |= TEST_HARD_REG_BIT (hard_regs_in_table, i);
CLEAR_HARD_REG_BIT (hard_regs_in_table, i);
delete_reg_equiv (i);
! LVAL_REG_TICK (i)++;
}
if (in_table)
*************** rehash_using_reg (x)
*** 1928,1944 ****
&& i != (hash = safe_hash (p->exp, p->mode) & HASH_MASK))
{
if (p->next_same_hash)
! p->next_same_hash->prev_same_hash = p->prev_same_hash;
if (p->prev_same_hash)
! p->prev_same_hash->next_same_hash = p->next_same_hash;
else
table[i] = p->next_same_hash;
! p->next_same_hash = table[hash];
p->prev_same_hash = 0;
if (table[hash])
! table[hash]->prev_same_hash = p;
table[hash] = p;
}
}
--- 2507,2525 ----
&& i != (hash = safe_hash (p->exp, p->mode) & HASH_MASK))
{
if (p->next_same_hash)
! CHECK_SAVING_TABLE_ELT (p->next_same_hash)->prev_same_hash
! = p->prev_same_hash;
if (p->prev_same_hash)
! CHECK_SAVING_TABLE_ELT (p->prev_same_hash)->next_same_hash
! = p->next_same_hash;
else
table[i] = p->next_same_hash;
! CHECK_SAVING_TABLE_ELT (p)->next_same_hash = table[hash];
p->prev_same_hash = 0;
if (table[hash])
! CHECK_SAVING_TABLE_ELT (table[hash])->prev_same_hash = p;
table[hash] = p;
}
}
*************** invalidate_for_call ()
*** 1966,1972 ****
{
delete_reg_equiv (regno);
if (REG_TICK (regno) >= 0)
! REG_TICK (regno)++;
in_table |= (TEST_HARD_REG_BIT (hard_regs_in_table, regno) != 0);
}
--- 2547,2553 ----
{
delete_reg_equiv (regno);
if (REG_TICK (regno) >= 0)
! LVAL_REG_TICK (regno)++;
in_table |= (TEST_HARD_REG_BIT (hard_regs_in_table, regno) != 0);
}
*************** record_jump_cond (code, mode, op0, op1,
*** 4319,4325 ****
qty = REG_QTY (REGNO (op0));
ent = &qty_table[qty];
! ent->comparison_code = code;
if (GET_CODE (op1) == REG)
{
/* Look it up again--in case op0 and op1 are the same. */
--- 4900,4906 ----
qty = REG_QTY (REGNO (op0));
ent = &qty_table[qty];
! CHECK_SAVING_QTY (ent)->comparison_code = code;
if (GET_CODE (op1) == REG)
{
/* Look it up again--in case op0 and op1 are the same. */
*************** record_jump_cond (code, mode, op0, op1,
*** 4338,4349 ****
op1_elt->in_memory = op1_in_memory;
}
! ent->comparison_const = NULL_RTX;
ent->comparison_qty = REG_QTY (REGNO (op1));
}
else
{
! ent->comparison_const = op1;
ent->comparison_qty = -1;
}
--- 4919,4930 ----
op1_elt->in_memory = op1_in_memory;
}
! CHECK_SAVING_QTY (ent)->comparison_const = NULL_RTX;
ent->comparison_qty = REG_QTY (REGNO (op1));
}
else
{
! CHECK_SAVING_QTY (ent)->comparison_const = op1;
ent->comparison_qty = -1;
}
*************** cse_insn (insn, libcall_insn)
*** 4446,4452 ****
int src_eqv_in_memory = 0;
unsigned src_eqv_hash = 0;
! struct set *sets = (struct set *) NULL_PTR;
this_insn = insn;
--- 5027,5033 ----
int src_eqv_in_memory = 0;
unsigned src_eqv_hash = 0;
! struct set *sets = NULL_PTR;
this_insn = insn;
*************** cse_insn (insn, libcall_insn)
*** 5691,5708 ****
mention_regs (x);
else
{
! /* We used to rely on all references to a register becoming
! inaccessible when a register changes to a new quantity,
! since that changes the hash code. However, that is not
! safe, since after HASH_SIZE new quantities we get a
hash 'collision' of a register with its own invalid
entries. And since SUBREGs have been changed not to
! change their hash code with the hash code of the register,
! it wouldn't work any longer at all. So we have to check
! for any invalid references lying around now.
! This code is similar to the REG case in mention_regs,
! but it knows that reg_tick has been incremented, and
! it leaves reg_in_table as -1 . */
register int regno = REGNO (x);
register int endregno
= regno + (regno >= FIRST_PSEUDO_REGISTER ? 1
--- 6272,6290 ----
mention_regs (x);
else
{
! /* We used to rely on all references to a register
! becoming inaccessible when a register changes to a
! new quantity, since that changes the hash code.
! However, that is not safe, since after number of
! buckets (which is HASH_SIZE) new quantities we get a
hash 'collision' of a register with its own invalid
entries. And since SUBREGs have been changed not to
! change their hash code with the hash code of the
! register, it wouldn't work any longer at all. So we
! have to check for any invalid references lying around
! now. This code is similar to the REG case in
! mention_regs, but it knows that reg_tick has been
! incremented, and it leaves reg_in_table as -1 . */
register int regno = REGNO (x);
register int endregno
= regno + (regno >= FIRST_PSEUDO_REGISTER ? 1
*************** cse_insn (insn, libcall_insn)
*** 5714,5720 ****
if (REG_IN_TABLE (i) >= 0)
{
remove_invalid_refs (i);
! REG_IN_TABLE (i) = -1;
}
}
}
--- 6296,6302 ----
if (REG_IN_TABLE (i) >= 0)
{
remove_invalid_refs (i);
! LVAL_REG_IN_TABLE (i) = -1;
}
}
}
*************** addr_affects_sp_p (addr)
*** 6019,6025 ****
&& REGNO (XEXP (addr, 0)) == STACK_POINTER_REGNUM)
{
if (REG_TICK (STACK_POINTER_REGNUM) >= 0)
! REG_TICK (STACK_POINTER_REGNUM)++;
/* This should be *very* rare. */
if (TEST_HARD_REG_BIT (hard_regs_in_table, STACK_POINTER_REGNUM))
--- 6601,6607 ----
&& REGNO (XEXP (addr, 0)) == STACK_POINTER_REGNUM)
{
if (REG_TICK (STACK_POINTER_REGNUM) >= 0)
! LVAL_REG_TICK (STACK_POINTER_REGNUM)++;
/* This should be *very* rare. */
if (TEST_HARD_REG_BIT (hard_regs_in_table, STACK_POINTER_REGNUM))
*************** invalidate_skipped_set (dest, set, data)
*** 6288,6294 ****
next label. This called when we wish to CSE around a block that is
conditionally executed. */
! static void
invalidate_skipped_block (start)
rtx start;
{
--- 6870,6876 ----
next label. This called when we wish to CSE around a block that is
conditionally executed. */
! static rtx
invalidate_skipped_block (start)
rtx start;
{
*************** invalidate_skipped_block (start)
*** 6310,6315 ****
--- 6892,6898 ----
invalidate_from_clobbers (PATTERN (insn));
note_stores (PATTERN (insn), invalidate_skipped_set, NULL);
}
+ return insn;
}
/* If modifying X will modify the value in *DATA (which is really an
*************** cse_set_around_loop (x, insn, loop_start
*** 6444,6449 ****
--- 7027,7070 ----
invalidate (XEXP (SET_DEST (x), 0), GET_MODE (SET_DEST (x)));
}
+
+ /* The following function initiates path DATA. */
+
+ static void
+ init_path (data)
+ struct cse_basic_block_data *data;
+ {
+ data->path_size = 0;
+ data->pathlength = INIT_PATHLENGTH;
+ data->path = xmalloc (INIT_PATHLENGTH * sizeof (struct branch_path_entry));
+ }
+
+ /* The following function finishes work with path DATA. */
+
+ static void
+ finish_path (data)
+ struct cse_basic_block_data *data;
+ {
+ free (data->path);
+ }
+
+ /* The following function checks that we have enough memory in path
+ DATA for element with index LAST. */
+
+ static void
+ check_pathlength (data, last)
+ struct cse_basic_block_data *data;
+ int last;
+ {
+ if (data->pathlength <= last)
+ {
+ data->pathlength *= 2;
+ data->path = xrealloc (data->path,
+ data->pathlength
+ * sizeof (struct branch_path_entry));
+ }
+ }
+
/* Find the end of INSN's basic block and return its range,
the total number of SETs in all the insns of the block, the last insn of the
block, and the branch path.
*************** cse_set_around_loop (x, insn, loop_start
*** 6453,6471 ****
of branches will be taken. The branch path is only used if
FLAG_CSE_FOLLOW_JUMPS or FLAG_CSE_SKIP_BLOCKS is non-zero.
! DATA is a pointer to a struct cse_basic_block_data, defined below, that is
! used to describe the block. It is filled in with the information about
! the current block. The incoming structure's branch path, if any, is used
! to construct the output branch path. */
! void
! cse_end_of_basic_block (insn, data, follow_jumps, after_loop, skip_blocks)
rtx insn;
struct cse_basic_block_data *data;
int follow_jumps;
int after_loop;
int skip_blocks;
{
rtx p = insn, q;
int nsets = 0;
int low_cuid = INSN_CUID (insn), high_cuid = INSN_CUID (insn);
--- 7074,7099 ----
of branches will be taken. The branch path is only used if
FLAG_CSE_FOLLOW_JUMPS or FLAG_CSE_SKIP_BLOCKS is non-zero.
! DATA is a pointer to a struct cse_basic_block_data, defined below,
! that is used to describe the block. It is filled in with the
! information about the current block. The incoming structure's
! branch path, if any, is used to construct the output branch path.
! The function will return insn (branch) with which we can start
! processing of the path. If it is different from INSN, we restore
! CSE state corresponing to the branch. START will contain index of
! the branch (if any). */
! static rtx
! cse_end_of_basic_block (insn, data, start,
! follow_jumps, after_loop, skip_blocks)
rtx insn;
struct cse_basic_block_data *data;
+ int *start;
int follow_jumps;
int after_loop;
int skip_blocks;
{
+ rtx start_insn = insn;
rtx p = insn, q;
int nsets = 0;
int low_cuid = INSN_CUID (insn), high_cuid = INSN_CUID (insn);
*************** cse_end_of_basic_block (insn, data, foll
*** 6478,6492 ****
previously TAKEN, mark it NOT_TAKEN. If it was previously NOT_TAKEN,
shorten the path by one and look at the previous branch. We know that
at least one branch must have been taken if PATH_SIZE is non-zero. */
while (path_size > 0)
{
! if (data->path[path_size - 1].status != NOT_TAKEN)
{
! data->path[path_size - 1].status = NOT_TAKEN;
break;
}
! else
! path_size--;
}
/* If the first instruction is marked with QImode, that means we've
--- 7106,7176 ----
previously TAKEN, mark it NOT_TAKEN. If it was previously NOT_TAKEN,
shorten the path by one and look at the previous branch. We know that
at least one branch must have been taken if PATH_SIZE is non-zero. */
+ *start = 0;
while (path_size > 0)
{
! struct branch_path_entry *path_entry = &data->path[path_size - 1];
!
! if (path_entry->status != NOT_TAKEN)
{
! if (!flag_cse_reuse_info)
! path_entry->status = NOT_TAKEN;
! else
! {
! if (path_entry->status != TAKEN)
! path_entry->status = NOT_TAKEN;
! else
! {
! path_entry->status = NOT_TAKEN;
! /* Try to find if-the-else statement. */
! if (flag_cse_skip_if_else)
! {
! for (q = NEXT_INSN (path_entry->branch);
! q;
! q = NEXT_INSN (q))
! if ((GET_CODE (q) == CODE_LABEL
! && LABEL_NUSES (q) != 0)
! || GET_CODE (q) == JUMP_INSN)
! break;
! if (q && GET_CODE (q) == JUMP_INSN
! && NEXT_INSN (q)
! && GET_CODE (NEXT_INSN (q)) == BARRIER
! && (next_nonnote_insn (NEXT_INSN (q))
! == path_entry->target_insn))
! {
! /* We found end of then-part which does not
! contain labels and jumps. Check
! else-part now. */
! rtx diamond_bottom = JUMP_LABEL (q);
!
! for (q = NEXT_INSN (path_entry->target_insn);
! q;
! q = NEXT_INSN (q))
! if ((GET_CODE (q) == CODE_LABEL
! && LABEL_NUSES (q) != 0)
! || GET_CODE (q) == JUMP_INSN)
! break;
! if (q == diamond_bottom)
! {
! /* Else-part is also ok. */
! path_entry->status = DIAMOND_AROUND;
! path_entry->target_insn = diamond_bottom;
! }
! }
! }
! }
!
! if (path_entry->saved_p)
! {
! start_insn = path_entry->branch;
! *start = path_size - 1;
! pop_state ();
! path_entry->saved_p = FALSE;
! }
! }
break;
}
! path_size--;
}
/* If the first instruction is marked with QImode, that means we've
*************** cse_end_of_basic_block (insn, data, foll
*** 6546,6555 ****
if (path_entry < path_size && data->path[path_entry].branch == p)
{
if (data->path[path_entry].status != NOT_TAKEN)
! p = JUMP_LABEL (p);
/* Point to next entry in path, if any. */
path_entry++;
}
/* If this is a conditional jump, we can follow it if -fcse-follow-jumps
--- 7230,7254 ----
if (path_entry < path_size && data->path[path_entry].branch == p)
{
if (data->path[path_entry].status != NOT_TAKEN)
! p = data->path[path_entry].target_insn;
/* Point to next entry in path, if any. */
path_entry++;
+
+ if (data->path[path_entry - 1].status == DIAMOND_AROUND
+ && LABEL_NUSES (p) != 1)
+ {
+ /* Finish the path because we found something like that
+ if () {
+ ...
+ if ()
+ ...
+ else
+ ...
+ } */
+ path_size = path_entry;
+ break;
+ }
}
/* If this is a conditional jump, we can follow it if -fcse-follow-jumps
*************** cse_end_of_basic_block (insn, data, foll
*** 6562,6568 ****
In this case invalidate_skipped_block will be called to invalidate any
registers set in the block when following the jump. */
! else if ((follow_jumps || skip_blocks) && path_size < PATHLENGTH - 1
&& GET_CODE (p) == JUMP_INSN
&& GET_CODE (PATTERN (p)) == SET
&& GET_CODE (SET_SRC (PATTERN (p))) == IF_THEN_ELSE
--- 7261,7269 ----
In this case invalidate_skipped_block will be called to invalidate any
registers set in the block when following the jump. */
! else if ((follow_jumps || skip_blocks)
! && (!flag_cse_limit_path
! || path_size < INIT_PATHLENGTH - 1)
&& GET_CODE (p) == JUMP_INSN
&& GET_CODE (PATTERN (p)) == SET
&& GET_CODE (SET_SRC (PATTERN (p))) == IF_THEN_ELSE
*************** cse_end_of_basic_block (insn, data, foll
*** 6597,6603 ****
--- 7298,7307 ----
if (i != path_entry)
break;
+ check_pathlength (data, path_entry);
data->path[path_entry].branch = p;
+ data->path[path_entry].saved_p = FALSE;
+ data->path[path_entry].target_insn = JUMP_LABEL (p);
data->path[path_entry++].status = TAKEN;
/* This branch now ends our path. It was possible that we
*************** cse_end_of_basic_block (insn, data, foll
*** 6636,6642 ****
--- 7340,7349 ----
if (tmp == q)
{
+ check_pathlength (data, path_entry);
data->path[path_entry].branch = p;
+ data->path[path_entry].saved_p = FALSE;
+ data->path[path_entry].target_insn = JUMP_LABEL (p);
data->path[path_entry++].status = AROUND;
path_size = path_entry;
*************** cse_end_of_basic_block (insn, data, foll
*** 6667,6675 ****
--- 7374,7386 ----
data->path_size = path_size;
/* End the current branch path. */
+ check_pathlength (data, path_size);
data->path[path_size].branch = 0;
+
+ return start_insn;
}
+
/* Perform cse on the instructions of a function.
F is the first instruction.
NREGS is one plus the highest pseudo-reg number used in the instruction.
*************** cse_main (f, nregs, after_loop, file)
*** 6690,6700 ****
struct cse_basic_block_data val;
register rtx insn = f;
register int i;
cse_jumps_altered = 0;
recorded_label_ref = 0;
constant_pool_entries_cost = 0;
! val.path_size = 0;
init_recog ();
init_alias_analysis ();
--- 7401,7412 ----
struct cse_basic_block_data val;
register rtx insn = f;
register int i;
+ int max_qty_peak;
cse_jumps_altered = 0;
recorded_label_ref = 0;
constant_pool_entries_cost = 0;
! init_path (&val);
init_recog ();
init_alias_analysis ();
*************** cse_main (f, nregs, after_loop, file)
*** 6704,6711 ****
max_insn_uid = get_max_uid ();
reg_eqv_table = (struct reg_eqv_elem *)
! xmalloc (nregs * sizeof (struct reg_eqv_elem));
#ifdef LOAD_EXTEND_OP
/* Allocate scratch rtl here. cse_insn will fill in the memory reference
--- 7416,7426 ----
max_insn_uid = get_max_uid ();
reg_eqv_table = (struct reg_eqv_elem *)
! xmalloc(nregs * sizeof(struct reg_eqv_elem));
! bzero ((char *) reg_eqv_table, nregs * sizeof(struct reg_eqv_elem));
+ saved_reg_eqv_table = NULL;
+
#ifdef LOAD_EXTEND_OP
/* Allocate scratch rtl here. cse_insn will fill in the memory reference
*************** cse_main (f, nregs, after_loop, file)
*** 6778,6805 ****
Compute the maximum number of qty's needed for each basic block
(which is 2 for each SET). */
insn = f;
while (insn)
{
! cse_end_of_basic_block (insn, &val, flag_cse_follow_jumps, after_loop,
! flag_cse_skip_blocks);
/* If this basic block was already processed or has no sets, skip it. */
! if (val.nsets == 0 || GET_MODE (insn) == QImode)
{
! PUT_MODE (insn, VOIDmode);
insn = (val.last ? NEXT_INSN (val.last) : 0);
val.path_size = 0;
continue;
}
cse_basic_block_start = val.low_cuid;
cse_basic_block_end = val.high_cuid;
max_qty = val.nsets * 2;
!
if (file)
! fnotice (file, ";; Processing block from %d to %d, %d sets.\n",
! INSN_UID (insn), val.last ? INSN_UID (val.last) : 0,
! val.nsets);
/* Make MAX_QTY bigger to give us room to optimize
past the end of this basic block, if that should prove useful. */
--- 7493,7557 ----
Compute the maximum number of qty's needed for each basic block
(which is 2 for each SET). */
insn = f;
+ cse_reg_info_table = xmalloc (max_reg * sizeof (struct cse_reg_info));
+ saved_cse_reg_info_table = NULL;
+ bzero ((char *) cse_reg_info_table, max_reg * sizeof (struct cse_reg_info));
+ bb_tick = 0;
+ init_stack ();
+ max_qty_peak = max_reg + 600;
+ qty_table
+ = (struct qty_table_elem *) xmalloc ((max_qty_peak - max_reg)
+ * sizeof (struct qty_table_elem));
+ saved_qty_table = NULL;
+
+ qty_table -= max_reg;
+
while (insn)
{
! rtx start_insn;
! int start;
+ start_insn = cse_end_of_basic_block (insn, &val, &start,
+ flag_cse_follow_jumps,
+ after_loop, flag_cse_skip_blocks);
+
/* If this basic block was already processed or has no sets, skip it. */
!
! if (val.nsets == 0 || flag_cse_limit_path && GET_MODE (insn) == QImode)
{
! if (flag_cse_limit_path)
! PUT_MODE (insn, VOIDmode);
insn = (val.last ? NEXT_INSN (val.last) : 0);
val.path_size = 0;
continue;
}
+ if (!flag_cse_limit_path && GET_MODE (insn) == QImode)
+ {
+ if (val.path_size != 0)
+ abort ();
+ PUT_MODE (insn, VOIDmode);
+ }
+
cse_basic_block_start = val.low_cuid;
cse_basic_block_end = val.high_cuid;
max_qty = val.nsets * 2;
!
if (file)
! {
! fnotice (file, ";; Processing block from %d(%d) to %d, %d sets.\n",
! INSN_UID (insn), INSN_UID (start_insn),
! val.last ? INSN_UID (val.last) : 0, val.nsets);
! fnotice (file, ";; Path\n");
! for (i = 0; i < val.path_size; i++)
! fnotice (file, ";; %d = %s\n",
! INSN_UID (val.path[i].branch),
! (val.path[i].status == NOT_TAKEN
! ? "NOT_TAKEN"
! : (val.path[i].status == TAKEN ? "TAKEN"
! : (val.path[i].status == AROUND
! ? "AROUND" : "DIAMOND_AROUND"))));
! }
/* Make MAX_QTY bigger to give us room to optimize
past the end of this basic block, if that should prove useful. */
*************** cse_main (f, nregs, after_loop, file)
*** 6808,6818 ****
max_qty += max_reg;
/* If this basic block is being extended by following certain jumps,
(see `cse_end_of_basic_block'), we reprocess the code from the start.
Otherwise, we start after this basic block. */
if (val.path_size > 0)
! cse_basic_block (insn, val.last, val.path, 0);
else
{
int old_cse_jumps_altered = cse_jumps_altered;
--- 7560,7580 ----
max_qty += max_reg;
+ if (max_qty_peak < max_qty)
+ {
+ max_qty_peak = max_qty;
+ qty_table = xrealloc (qty_table + max_reg,
+ (max_qty_peak - max_reg)
+ * sizeof (struct qty_table_elem));
+ qty_table -= max_reg;
+ }
+
/* If this basic block is being extended by following certain jumps,
(see `cse_end_of_basic_block'), we reprocess the code from the start.
Otherwise, we start after this basic block. */
if (val.path_size > 0)
! cse_basic_block (start_insn, val.last, insn != start_insn,
! val.path + start, 0, file);
else
{
int old_cse_jumps_altered = cse_jumps_altered;
*************** cse_main (f, nregs, after_loop, file)
*** 6822,6828 ****
jump, we want to reprocess the block, since it will give
us a new branch path to investigate. */
cse_jumps_altered = 0;
! temp = cse_basic_block (insn, val.last, val.path, ! after_loop);
if (cse_jumps_altered == 0
|| (flag_cse_follow_jumps == 0 && flag_cse_skip_blocks == 0))
insn = temp;
--- 7584,7591 ----
jump, we want to reprocess the block, since it will give
us a new branch path to investigate. */
cse_jumps_altered = 0;
! temp = cse_basic_block (start_insn, val.last, insn != start_insn,
! val.path + start, !after_loop, file);
if (cse_jumps_altered == 0
|| (flag_cse_follow_jumps == 0 && flag_cse_skip_blocks == 0))
insn = temp;
*************** cse_main (f, nregs, after_loop, file)
*** 6838,6843 ****
--- 7601,7614 ----
#endif
}
+ if (saved_qty_table)
+ free (saved_qty_table);
+ free (qty_table + max_reg);
+
+ if (saved_cse_reg_info_table)
+ free (saved_cse_reg_info_table);
+ free (cse_reg_info_table);
+
if (ggc_p)
ggc_pop_context ();
*************** cse_main (f, nregs, after_loop, file)
*** 6847,6854 ****
--- 7618,7634 ----
/* Clean up. */
end_alias_analysis ();
free (uid_cuid);
+ if (saved_reg_eqv_table)
+ free (saved_reg_eqv_table);
free (reg_eqv_table);
+ if (stack_free)
+ abort ();
+
+ finish_stack ();
+
+ finish_path (&val);
+
return cse_jumps_altered || recorded_label_ref;
}
*************** cse_main (f, nregs, after_loop, file)
*** 6856,6870 ****
block. NEXT_BRANCH points to the branch path when following jumps or
a null path when not following jumps.
! AROUND_LOOP is non-zero if we are to try to cse around to the start of a
! loop. This is true when we are being called for the last time on a
! block and this CSE pass is before loop.c. */
static rtx
! cse_basic_block (from, to, next_branch, around_loop)
register rtx from, to;
! struct branch_path *next_branch;
int around_loop;
{
register rtx insn;
int to_usage = 0;
--- 7636,7654 ----
block. NEXT_BRANCH points to the branch path when following jumps or
a null path when not following jumps.
! AROUND_LOOP is non-zero if we are to try to cse around to the start
! of a loop. This is true when we are being called for the last time
! on a block and this CSE pass is before loop.c. CONT_P is true if
! we start path not from its begin (in other words we restores a
! previous state). */
static rtx
! cse_basic_block (from, to, cont_p, next_branch, around_loop, file)
register rtx from, to;
! int cont_p;
! struct branch_path_entry *next_branch;
int around_loop;
+ FILE *file;
{
register rtx insn;
int to_usage = 0;
*************** cse_basic_block (from, to, next_branch,
*** 6873,6885 ****
/* This array is undefined before max_reg, so only allocate
the space actually needed and adjust the start. */
-
- qty_table
- = (struct qty_table_elem *) xmalloc ((max_qty - max_reg)
- * sizeof (struct qty_table_elem));
- qty_table -= max_reg;
! new_basic_block ();
/* TO might be a label. If so, protect it from being deleted. */
if (to != 0 && GET_CODE (to) == CODE_LABEL)
--- 7657,7665 ----
/* This array is undefined before max_reg, so only allocate
the space actually needed and adjust the start. */
! if (!cont_p)
! new_basic_block ();
/* TO might be a label. If so, protect it from being deleted. */
if (to != 0 && GET_CODE (to) == CODE_LABEL)
*************** cse_basic_block (from, to, next_branch,
*** 6909,6920 ****
if (next_branch->branch == insn)
{
enum taken status = next_branch++->status;
if (status != NOT_TAKEN)
{
if (status == TAKEN)
record_jump_equiv (insn, 1);
! else
invalidate_skipped_block (NEXT_INSN (insn));
/* Set the last insn as the jump insn; it doesn't affect cc0.
Then follow this branch. */
--- 7689,7721 ----
if (next_branch->branch == insn)
{
enum taken status = next_branch++->status;
+ rtx target_insn, temp;
+
if (status != NOT_TAKEN)
{
+ target_insn = next_branch[-1].target_insn;
+ if (flag_cse_reuse_info)
+ {
+ next_branch[-1].saved_p = TRUE;
+ push_state ();
+ }
if (status == TAKEN)
record_jump_equiv (insn, 1);
! else if (status == AROUND)
invalidate_skipped_block (NEXT_INSN (insn));
+ else if (status == DIAMOND_AROUND)
+ {
+ /* Don't miss the end of path. Remember that path
+ with the last branch DIAMOND_AROUND may end at
+ the corresponding CODE_LABEL (see function
+ cse_end_of_basic_block). */
+ if (target_insn == to)
+ break;
+ for (temp = insn; temp != target_insn;)
+ temp = invalidate_skipped_block (NEXT_INSN (temp));
+ }
+ else
+ abort ();
/* Set the last insn as the jump insn; it doesn't affect cc0.
Then follow this branch. */
*************** cse_basic_block (from, to, next_branch,
*** 6922,6933 ****
prev_insn_cc0 = 0;
#endif
prev_insn = insn;
! insn = JUMP_LABEL (insn);
continue;
}
}
! if (GET_MODE (insn) == QImode)
PUT_MODE (insn, VOIDmode);
if (GET_RTX_CLASS (code) == 'i')
--- 7723,7734 ----
prev_insn_cc0 = 0;
#endif
prev_insn = insn;
! insn = target_insn;
continue;
}
}
! if (flag_cse_limit_path && GET_MODE (insn) == QImode)
PUT_MODE (insn, VOIDmode);
if (GET_RTX_CLASS (code) == 'i')
*************** cse_basic_block (from, to, next_branch,
*** 6962,6971 ****
if (simplejump_p (insn))
{
if (to == 0)
! {
! free (qty_table + max_reg);
! return 0;
! }
if (JUMP_LABEL (insn) == to)
to_usage = 1;
--- 7763,7769 ----
if (simplejump_p (insn))
{
if (to == 0)
! return 0;
if (JUMP_LABEL (insn) == to)
to_usage = 1;
*************** cse_basic_block (from, to, next_branch,
*** 6992,7021 ****
{
struct cse_basic_block_data val;
rtx prev;
insn = NEXT_INSN (to);
/* If TO was the last insn in the function, we are done. */
if (insn == 0)
! {
! free (qty_table + max_reg);
! return 0;
! }
/* If TO was preceded by a BARRIER we are done with this block
because it has no continuation. */
prev = prev_nonnote_insn (to);
if (prev && GET_CODE (prev) == BARRIER)
! {
! free (qty_table + max_reg);
! return insn;
! }
/* Find the end of the following block. Note that we won't be
following branches in this case. */
to_usage = 0;
! val.path_size = 0;
! cse_end_of_basic_block (insn, &val, 0, 0, 0);
/* If the tables we allocated have enough space left
to handle all the SETs in the next basic block,
--- 7790,7817 ----
{
struct cse_basic_block_data val;
rtx prev;
+ int start;
insn = NEXT_INSN (to);
/* If TO was the last insn in the function, we are done. */
if (insn == 0)
! return 0;
/* If TO was preceded by a BARRIER we are done with this block
because it has no continuation. */
prev = prev_nonnote_insn (to);
if (prev && GET_CODE (prev) == BARRIER)
! return insn;
/* Find the end of the following block. Note that we won't be
following branches in this case. */
to_usage = 0;
! init_path (&val);
! cse_end_of_basic_block (insn, &val, &start, 0, 0, 0);
!
! if (start != 0)
! abort ();
/* If the tables we allocated have enough space left
to handle all the SETs in the next basic block,
*************** cse_basic_block (from, to, next_branch,
*** 7028,7033 ****
--- 7824,7835 ----
cse_basic_block_end = val.high_cuid;
to = val.last;
+ if (file)
+ fnotice (file, ";; Continuation of processing %d - %d, %d sets.\n",
+ INSN_UID (insn), to ? INSN_UID (to) : 0, val.nsets);
+
+ finish_path (&val);
+
/* Prevent TO from being deleted if it is a label. */
if (to != 0 && GET_CODE (to) == CODE_LABEL)
++LABEL_NUSES (to);
*************** cse_basic_block (from, to, next_branch,
*** 7053,7060 ****
&& JUMP_LABEL (PREV_INSN (to)) != 0
&& LABEL_NUSES (JUMP_LABEL (PREV_INSN (to))) == 1)
cse_around_loop (JUMP_LABEL (PREV_INSN (to)));
-
- free (qty_table + max_reg);
return to ? NEXT_INSN (to) : 0;
}
--- 7855,7860 ----