vrp?
Richard Henderson
rth@redhat.com
Wed Feb 12 21:03:00 GMT 2003
On Wed, Feb 12, 2003 at 10:59:45AM -0800, Richard Henderson wrote:
> At the moment I'm bootstrapping to find out how exactly how much
> compile time I'm going to save by removing the cse code. That'll
> give me some idea if this is worth persuing at all for 3.4.
Before: 1168.34user 35.03system 5:05.02elapsed 394%CPU
After: 1109.25user 35.07system 4:50.41elapsed 394%CPU
That's a 5% decrease in user time.
I'll have to think about what I want to do here though.
For the record, here's the patch I was testing.
cse.c | 875 +++++-----------------------------------------------------
rtl.h | 7
toplev.c | 8
3 files changed, 87 insertions, 803 deletions
r~
-------------- next part --------------
Index: cse.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cse.c,v
retrieving revision 1.253
diff -c -p -d -u -r1.253 cse.c
--- cse.c 28 Jan 2003 21:29:40 -0000 1.253
+++ cse.c 12 Feb 2003 20:52:19 -0000
@@ -43,16 +43,34 @@ Software Foundation, 59 Temple Place - S
#include "except.h"
#include "target.h"
+/* XYZZY FIXME split blocks at NOTE_INSN_LOOP_END.
+
+ Don't cse out the end of a loop. This makes a difference
+ only for the unusual loops that always execute at least once;
+ all other loops have labels there so we will stop in any case.
+ Cse'ing out the end of the loop is dangerous because it
+ might cause an invariant expression inside the loop
+ to be reused after the end of the loop. This would make it
+ hard to move the expression out of the loop in loop.c,
+ especially if it is one of several equivalent expressions
+ and loop.c would like to eliminate it.
+
+ ??? Split blocks at SETJMP. Argument is that setjmp clobbers
+ registers, but isn't that undefined? One must use volatile to
+ guarantee behaviour?
+
+ ??? TO might be a label. If so, protect it from being deleted.
+ if (to != 0 && GET_CODE (to) == CODE_LABEL)
+ ++LABEL_NUSES (to);
+
+*/
/* 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.
+ We no longer track values across extended basic blocks, but
+ instead leave this to GCSE, since that's it's job.
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
@@ -368,9 +386,6 @@ static int cse_basic_block_end;
static int *uid_cuid;
-/* Highest UID in UID_CUID. */
-static int max_uid;
-
/* Get the cuid of an insn. */
#define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)])
@@ -565,36 +580,6 @@ static struct table_elt *last_jump_equiv
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
-{
- /* Lowest CUID value of insns in block. */
- int low_cuid;
- /* Highest CUID value of insns in block. */
- int high_cuid;
- /* Total number of SETs in block. */
- int nsets;
- /* Last insn in the block. */
- 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];
-};
-
static bool fixed_base_plus_p PARAMS ((rtx x));
static int notreg_cost PARAMS ((rtx, enum rtx_code));
static int approx_reg_cost_1 PARAMS ((rtx *, void *));
@@ -638,15 +623,10 @@ static void record_jump_equiv PARAMS ((r
static void record_jump_cond PARAMS ((enum rtx_code, enum machine_mode,
rtx, rtx, int));
static void cse_insn PARAMS ((rtx, rtx));
-static int addr_affects_sp_p PARAMS ((rtx));
static void invalidate_from_clobbers PARAMS ((rtx));
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 int cse_count_sets_in_basic_block PARAMS ((basic_block));
+static void cse_basic_block PARAMS ((basic_block));
static void count_reg_usage PARAMS ((rtx, int *, rtx, int));
static int check_for_label_ref PARAMS ((rtx *, void *));
extern void dump_class PARAMS ((struct table_elt*));
@@ -6388,34 +6368,6 @@ invalidate_memory ()
}
}
-/* If ADDR is an address that implicitly affects the stack pointer, return
- 1 and update the register tables to show the effect. Else, return 0. */
-
-static int
-addr_affects_sp_p (addr)
- rtx addr;
-{
- if (GET_RTX_CLASS (GET_CODE (addr)) == 'a'
- && GET_CODE (XEXP (addr, 0)) == REG
- && REGNO (XEXP (addr, 0)) == STACK_POINTER_REGNUM)
- {
- if (REG_TICK (STACK_POINTER_REGNUM) >= 0)
- {
- REG_TICK (STACK_POINTER_REGNUM)++;
- /* Is it possible to use a subreg of SP? */
- SUBREG_TICKED (STACK_POINTER_REGNUM) = -1;
- }
-
- /* This should be *very* rare. */
- if (TEST_HARD_REG_BIT (hard_regs_in_table, STACK_POINTER_REGNUM))
- invalidate (stack_pointer_rtx, VOIDmode);
-
- return 1;
- }
-
- return 0;
-}
-
/* Perform invalidation on the basis of everything about an insn
except for invalidating the actual places that are SET in it.
This includes the places CLOBBERed, and anything that might
@@ -6549,553 +6501,57 @@ cse_process_notes (x, object)
return x;
}
-/* Find common subexpressions between the end test of a loop and the beginning
- of the loop. LOOP_START is the CODE_LABEL at the start of a loop.
-
- Often we have a loop where an expression in the exit test is used
- in the body of the loop. For example "while (*p) *q++ = *p++;".
- Because of the way we duplicate the loop exit test in front of the loop,
- however, we don't detect that common subexpression. This will be caught
- when global cse is implemented, but this is a quite common case.
-
- This function handles the most common cases of these common expressions.
- It is called after we have processed the basic block ending with the
- NOTE_INSN_LOOP_END note that ends a loop and the previous JUMP_INSN
- jumps to a label used only once. */
-
-static void
-cse_around_loop (loop_start)
- rtx loop_start;
-{
- rtx insn;
- int i;
- struct table_elt *p;
-
- /* If the jump at the end of the loop doesn't go to the start, we don't
- do anything. */
- for (insn = PREV_INSN (loop_start);
- insn && (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) >= 0);
- insn = PREV_INSN (insn))
- ;
-
- if (insn == 0
- || GET_CODE (insn) != NOTE
- || NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG)
- return;
-
- /* If the last insn of the loop (the end test) was an NE comparison,
- we will interpret it as an EQ comparison, since we fell through
- the loop. Any equivalences resulting from that comparison are
- therefore not valid and must be invalidated. */
- if (last_jump_equiv_class)
- for (p = last_jump_equiv_class->first_same_value; p;
- p = p->next_same_value)
- {
- if (GET_CODE (p->exp) == MEM || GET_CODE (p->exp) == REG
- || (GET_CODE (p->exp) == SUBREG
- && GET_CODE (SUBREG_REG (p->exp)) == REG))
- invalidate (p->exp, VOIDmode);
- else if (GET_CODE (p->exp) == STRICT_LOW_PART
- || GET_CODE (p->exp) == ZERO_EXTRACT)
- invalidate (XEXP (p->exp, 0), GET_MODE (p->exp));
- }
-
- /* Process insns starting after LOOP_START until we hit a CALL_INSN or
- a CODE_LABEL (we could handle a CALL_INSN, but it isn't worth it).
-
- The only thing we do with SET_DEST is invalidate entries, so we
- can safely process each SET in order. It is slightly less efficient
- to do so, but we only want to handle the most common cases.
-
- The gen_move_insn call in cse_set_around_loop may create new pseudos.
- These pseudos won't have valid entries in any of the tables indexed
- by register number, such as reg_qty. We avoid out-of-range array
- accesses by not processing any instructions created after cse started. */
-
- for (insn = NEXT_INSN (loop_start);
- GET_CODE (insn) != CALL_INSN && GET_CODE (insn) != CODE_LABEL
- && INSN_UID (insn) < max_insn_uid
- && ! (GET_CODE (insn) == NOTE
- && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END);
- insn = NEXT_INSN (insn))
- {
- if (INSN_P (insn)
- && (GET_CODE (PATTERN (insn)) == SET
- || GET_CODE (PATTERN (insn)) == CLOBBER))
- cse_set_around_loop (PATTERN (insn), insn, loop_start);
- else if (INSN_P (insn) && GET_CODE (PATTERN (insn)) == PARALLEL)
- for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
- if (GET_CODE (XVECEXP (PATTERN (insn), 0, i)) == SET
- || GET_CODE (XVECEXP (PATTERN (insn), 0, i)) == CLOBBER)
- cse_set_around_loop (XVECEXP (PATTERN (insn), 0, i), insn,
- loop_start);
- }
-}
-
-/* Process one SET of an insn that was skipped. We ignore CLOBBERs
- since they are done elsewhere. This function is called via note_stores. */
-
-static void
-invalidate_skipped_set (dest, set, data)
- rtx set;
- rtx dest;
- void *data ATTRIBUTE_UNUSED;
-{
- enum rtx_code code = GET_CODE (dest);
-
- if (code == MEM
- && ! addr_affects_sp_p (dest) /* If this is not a stack push ... */
- /* There are times when an address can appear varying and be a PLUS
- during this scan when it would be a fixed address were we to know
- the proper equivalences. So invalidate all memory if there is
- a BLKmode or nonscalar memory reference or a reference to a
- variable address. */
- && (MEM_IN_STRUCT_P (dest) || GET_MODE (dest) == BLKmode
- || cse_rtx_varies_p (XEXP (dest, 0), 0)))
- {
- invalidate_memory ();
- return;
- }
-
- if (GET_CODE (set) == CLOBBER
-#ifdef HAVE_cc0
- || dest == cc0_rtx
-#endif
- || dest == pc_rtx)
- return;
-
- if (code == STRICT_LOW_PART || code == ZERO_EXTRACT)
- invalidate (XEXP (dest, 0), GET_MODE (dest));
- else if (code == REG || code == SUBREG || code == MEM)
- invalidate (dest, VOIDmode);
-}
-
-/* Invalidate all insns from START up to the end of the function or the
- next label. This called when we wish to CSE around a block that is
- conditionally executed. */
-
-static void
-invalidate_skipped_block (start)
- rtx start;
-{
- rtx insn;
-
- for (insn = start; insn && GET_CODE (insn) != CODE_LABEL;
- insn = NEXT_INSN (insn))
- {
- if (! INSN_P (insn))
- continue;
-
- if (GET_CODE (insn) == CALL_INSN)
- {
- if (! CONST_OR_PURE_CALL_P (insn))
- invalidate_memory ();
- invalidate_for_call ();
- }
-
- invalidate_from_clobbers (PATTERN (insn));
- note_stores (PATTERN (insn), invalidate_skipped_set, NULL);
- }
-}
-
-/* If modifying X will modify the value in *DATA (which is really an
- `rtx *'), indicate that fact by setting the pointed to value to
- NULL_RTX. */
-
-static void
-cse_check_loop_start (x, set, data)
- rtx x;
- rtx set ATTRIBUTE_UNUSED;
- void *data;
-{
- rtx *cse_check_loop_start_value = (rtx *) data;
-
- if (*cse_check_loop_start_value == NULL_RTX
- || GET_CODE (x) == CC0 || GET_CODE (x) == PC)
- return;
-
- if ((GET_CODE (x) == MEM && GET_CODE (*cse_check_loop_start_value) == MEM)
- || reg_overlap_mentioned_p (x, *cse_check_loop_start_value))
- *cse_check_loop_start_value = NULL_RTX;
-}
-
-/* X is a SET or CLOBBER contained in INSN that was found near the start of
- a loop that starts with the label at LOOP_START.
-
- If X is a SET, we see if its SET_SRC is currently in our hash table.
- If so, we see if it has a value equal to some register used only in the
- loop exit code (as marked by jump.c).
-
- If those two conditions are true, we search backwards from the start of
- the loop to see if that same value was loaded into a register that still
- retains its value at the start of the loop.
-
- If so, we insert an insn after the load to copy the destination of that
- load into the equivalent register and (try to) replace our SET_SRC with that
- register.
-
- In any event, we invalidate whatever this SET or CLOBBER modifies. */
-
-static void
-cse_set_around_loop (x, insn, loop_start)
- rtx x;
- rtx insn;
- rtx loop_start;
-{
- struct table_elt *src_elt;
-
- /* If this is a SET, see if we can replace SET_SRC, but ignore SETs that
- are setting PC or CC0 or whose SET_SRC is already a register. */
- if (GET_CODE (x) == SET
- && GET_CODE (SET_DEST (x)) != PC && GET_CODE (SET_DEST (x)) != CC0
- && GET_CODE (SET_SRC (x)) != REG)
- {
- src_elt = lookup (SET_SRC (x),
- HASH (SET_SRC (x), GET_MODE (SET_DEST (x))),
- GET_MODE (SET_DEST (x)));
-
- if (src_elt)
- for (src_elt = src_elt->first_same_value; src_elt;
- src_elt = src_elt->next_same_value)
- if (GET_CODE (src_elt->exp) == REG && REG_LOOP_TEST_P (src_elt->exp)
- && COST (src_elt->exp) < COST (SET_SRC (x)))
- {
- rtx p, set;
-
- /* Look for an insn in front of LOOP_START that sets
- something in the desired mode to SET_SRC (x) before we hit
- a label or CALL_INSN. */
-
- for (p = prev_nonnote_insn (loop_start);
- p && GET_CODE (p) != CALL_INSN
- && GET_CODE (p) != CODE_LABEL;
- p = prev_nonnote_insn (p))
- if ((set = single_set (p)) != 0
- && GET_CODE (SET_DEST (set)) == REG
- && GET_MODE (SET_DEST (set)) == src_elt->mode
- && rtx_equal_p (SET_SRC (set), SET_SRC (x)))
- {
- /* We now have to ensure that nothing between P
- and LOOP_START modified anything referenced in
- SET_SRC (x). We know that nothing within the loop
- can modify it, or we would have invalidated it in
- the hash table. */
- rtx q;
- rtx cse_check_loop_start_value = SET_SRC (x);
- for (q = p; q != loop_start; q = NEXT_INSN (q))
- if (INSN_P (q))
- note_stores (PATTERN (q),
- cse_check_loop_start,
- &cse_check_loop_start_value);
-
- /* If nothing was changed and we can replace our
- SET_SRC, add an insn after P to copy its destination
- to what we will be replacing SET_SRC with. */
- if (cse_check_loop_start_value
- && single_set (p)
- && !can_throw_internal (insn)
- && validate_change (insn, &SET_SRC (x),
- src_elt->exp, 0))
- {
- /* If this creates new pseudos, this is unsafe,
- because the regno of new pseudo is unsuitable
- to index into reg_qty when cse_insn processes
- the new insn. Therefore, if a new pseudo was
- created, discard this optimization. */
- int nregs = max_reg_num ();
- rtx move
- = gen_move_insn (src_elt->exp, SET_DEST (set));
- if (nregs != max_reg_num ())
- {
- if (! validate_change (insn, &SET_SRC (x),
- SET_SRC (set), 0))
- abort ();
- }
- else
- emit_insn_after (move, p);
- }
- break;
- }
- }
- }
-
- /* Deal with the destination of X affecting the stack pointer. */
- addr_affects_sp_p (SET_DEST (x));
-
- /* See comment on similar code in cse_insn for explanation of these
- tests. */
- if (GET_CODE (SET_DEST (x)) == REG || GET_CODE (SET_DEST (x)) == SUBREG
- || GET_CODE (SET_DEST (x)) == MEM)
- invalidate (SET_DEST (x), VOIDmode);
- else if (GET_CODE (SET_DEST (x)) == STRICT_LOW_PART
- || GET_CODE (SET_DEST (x)) == ZERO_EXTRACT)
- invalidate (XEXP (SET_DEST (x), 0), GET_MODE (SET_DEST (x)));
-}
-
-/* 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.
-
- The branch path indicates which branches should be followed. If a nonzero
- path size is specified, the block should be rescanned and a different set
- of branches will be taken. The branch path is only used if
- FLAG_CSE_FOLLOW_JUMPS or FLAG_CSE_SKIP_BLOCKS is nonzero.
-
- 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. */
+/* Return the total number of SETs in all the insns of the block. */
-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;
+static int
+cse_count_sets_in_basic_block (bb)
+ basic_block bb;
{
- rtx p = insn, q;
+ rtx p = bb->head;
int nsets = 0;
- int low_cuid = INSN_CUID (insn), high_cuid = INSN_CUID (insn);
- rtx next = INSN_P (insn) ? insn : next_real_insn (insn);
- int path_size = data->path_size;
- int path_entry = 0;
- int i;
- /* Update the previous branch path, if any. If the last branch was
- 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 nonzero. */
- 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
- already processed this block. Our caller will look at DATA->LAST
- to figure out where to go next. We want to return the next block
- in the instruction stream, not some branched-to block somewhere
- else. We accomplish this by pretending our called forbid us to
- follow jumps, or skip blocks. */
- if (GET_MODE (insn) == QImode)
- follow_jumps = skip_blocks = 0;
-
- /* Scan to end of this basic block. */
- while (p && GET_CODE (p) != CODE_LABEL)
+ while (1)
{
- /* Don't cse out the end of a loop. This makes a difference
- only for the unusual loops that always execute at least once;
- all other loops have labels there so we will stop in any case.
- Cse'ing out the end of the loop is dangerous because it
- might cause an invariant expression inside the loop
- to be reused after the end of the loop. This would make it
- hard to move the expression out of the loop in loop.c,
- especially if it is one of several equivalent expressions
- and loop.c would like to eliminate it.
-
- If we are running after loop.c has finished, we can ignore
- the NOTE_INSN_LOOP_END. */
-
- if (! after_loop && GET_CODE (p) == NOTE
- && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)
- break;
-
- /* Don't cse over a call to setjmp; on some machines (eg VAX)
- the regs restored by the longjmp come from
- a later time than the setjmp. */
- if (PREV_INSN (p) && GET_CODE (PREV_INSN (p)) == CALL_INSN
- && find_reg_note (PREV_INSN (p), REG_SETJMP, NULL))
- break;
-
/* A PARALLEL can have lots of SETs in it,
especially if it is really an ASM_OPERANDS. */
- if (INSN_P (p) && GET_CODE (PATTERN (p)) == PARALLEL)
- nsets += XVECLEN (PATTERN (p), 0);
- else if (GET_CODE (p) != NOTE)
- nsets += 1;
-
- /* Ignore insns made by CSE; they cannot affect the boundaries of
- the basic block. */
-
- if (INSN_UID (p) <= max_uid && INSN_CUID (p) > high_cuid)
- high_cuid = INSN_CUID (p);
- if (INSN_UID (p) <= max_uid && INSN_CUID (p) < low_cuid)
- low_cuid = INSN_CUID (p);
-
- /* See if this insn is in our branch path. If it is and we are to
- take it, do so. */
- 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
- was specified, we haven't reached our maximum path length, there are
- insns following the target of the jump, this is the only use of the
- jump label, and the target label is preceded by a BARRIER.
-
- Alternatively, we can follow the jump if it branches around a
- block of code and there are no other branches into the block.
- 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
- && JUMP_LABEL (p) != 0
- && LABEL_NUSES (JUMP_LABEL (p)) == 1
- && NEXT_INSN (JUMP_LABEL (p)) != 0)
- {
- for (q = PREV_INSN (JUMP_LABEL (p)); q; q = PREV_INSN (q))
- if ((GET_CODE (q) != NOTE
- || NOTE_LINE_NUMBER (q) == NOTE_INSN_LOOP_END
- || (PREV_INSN (q) && GET_CODE (PREV_INSN (q)) == CALL_INSN
- && find_reg_note (PREV_INSN (q), REG_SETJMP, NULL)))
- && (GET_CODE (q) != CODE_LABEL || LABEL_NUSES (q) != 0))
- break;
-
- /* If we ran into a BARRIER, this code is an extension of the
- basic block when the branch is taken. */
- if (follow_jumps && q != 0 && GET_CODE (q) == BARRIER)
- {
- /* Don't allow ourself to keep walking around an
- always-executed loop. */
- if (next_real_insn (q) == next)
- {
- p = NEXT_INSN (p);
- continue;
- }
-
- /* Similarly, don't put a branch in our path more than once. */
- for (i = 0; i < path_entry; i++)
- if (data->path[i].branch == p)
- break;
-
- if (i != path_entry)
- break;
-
- data->path[path_entry].branch = p;
- data->path[path_entry++].status = TAKEN;
-
- /* This branch now ends our path. It was possible that we
- didn't see this branch the last time around (when the
- insn in front of the target was a JUMP_INSN that was
- turned into a no-op). */
- path_size = path_entry;
-
- p = JUMP_LABEL (p);
- /* Mark block so we won't scan it again later. */
- PUT_MODE (NEXT_INSN (p), QImode);
- }
- /* Detect a branch around a block of code. */
- else if (skip_blocks && q != 0 && GET_CODE (q) != CODE_LABEL)
- {
- rtx tmp;
-
- if (next_real_insn (q) == next)
- {
- p = NEXT_INSN (p);
- continue;
- }
-
- for (i = 0; i < path_entry; i++)
- if (data->path[i].branch == p)
- break;
-
- if (i != path_entry)
- break;
-
- /* This is no_labels_between_p (p, q) with an added check for
- reaching the end of a function (in case Q precedes P). */
- for (tmp = NEXT_INSN (p); tmp && tmp != q; tmp = NEXT_INSN (tmp))
- if (GET_CODE (tmp) == CODE_LABEL)
- break;
-
- if (tmp == q)
- {
- data->path[path_entry].branch = p;
- data->path[path_entry++].status = AROUND;
-
- path_size = path_entry;
+ if (INSN_P (p))
+ nsets += (GET_CODE (PATTERN (p)) == PARALLEL
+ ? XVECLEN (PATTERN (p), 0) : 1);
- p = JUMP_LABEL (p);
- /* Mark block so we won't scan it again later. */
- PUT_MODE (NEXT_INSN (p), QImode);
- }
- }
- }
+ if (p == bb->end)
+ break;
p = NEXT_INSN (p);
}
- data->low_cuid = low_cuid;
- data->high_cuid = high_cuid;
- data->nsets = nsets;
- data->last = p;
-
- /* If all jumps in the path are not taken, set our path length to zero
- so a rescan won't be done. */
- for (i = path_size - 1; i >= 0; i--)
- if (data->path[i].status != NOT_TAKEN)
- break;
-
- if (i == -1)
- data->path_size = 0;
- else
- data->path_size = path_size;
-
- /* End the current branch path. */
- data->path[path_size].branch = 0;
+ return nsets;
}
-/* 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.
-
- AFTER_LOOP is 1 if this is the cse call done after loop optimization
- (only if -frerun-cse-after-loop).
-
- Returns 1 if jump_optimize should be redone due to simplifications
- in conditional jump instructions. */
+/* Perform cse on the instructions of a function. AFTER_LOOP is true
+ if this is the cse call done after loop optimization. Returns true
+ if we simplified any conditional jump instructions. */
int
-cse_main (f, nregs, after_loop, file)
- rtx f;
- int nregs;
- int after_loop;
- FILE *file;
+cse_main (after_loop)
+ int after_loop ATTRIBUTE_UNUSED;
{
- struct cse_basic_block_data val;
- rtx insn = f;
+ rtx insn;
+ basic_block bb;
int i;
cse_jumps_altered = 0;
recorded_label_ref = 0;
constant_pool_entries_cost = 0;
- val.path_size = 0;
init_recog ();
init_alias_analysis ();
- max_reg = nregs;
-
+ max_reg = max_reg_num ();
max_insn_uid = get_max_uid ();
reg_eqv_table = (struct reg_eqv_elem *)
- xmalloc (nregs * sizeof (struct reg_eqv_elem));
+ xmalloc (max_reg * sizeof (struct reg_eqv_elem));
#ifdef LOAD_EXTEND_OP
-
/* Allocate scratch rtl here. cse_insn will fill in the memory reference
and change the code and mode as appropriate. */
memory_extend_rtx = gen_rtx_ZERO_EXTEND (VOIDmode, NULL_RTX);
@@ -7105,18 +6561,13 @@ cse_main (f, nregs, after_loop, file)
thus far. */
n_elements_made = 0;
- /* Find the largest uid. */
-
- max_uid = get_max_uid ();
- uid_cuid = (int *) xcalloc (max_uid + 1, sizeof (int));
-
- /* Compute the mapping from uids to cuids.
- CUIDs are numbers assigned to insns, like uids,
- except that cuids increase monotonically through the code.
- Don't assign cuids to line-number NOTEs, so that the distance in cuids
- between two insns is not affected by -g. */
+ /* Compute the mapping from uids to cuids. CUIDs are numbers assigned to
+ insns, like uids, except that cuids increase monotonically through the
+ code. Don't assign cuids to line-number NOTEs, so that the distance
+ in cuids between two insns is not affected by -g. */
- for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
+ uid_cuid = (int *) xcalloc (max_insn_uid + 1, sizeof (int));
+ for (insn = get_insns (), i = 0; insn; insn = NEXT_INSN (insn))
{
if (GET_CODE (insn) != NOTE
|| NOTE_LINE_NUMBER (insn) < 0)
@@ -7128,63 +6579,32 @@ cse_main (f, nregs, after_loop, file)
ggc_push_context ();
- /* Loop over basic blocks.
- Compute the maximum number of qty's needed for each basic block
- (which is 2 for each SET). */
- insn = f;
- while (insn)
+ /* Main loop. */
+ FOR_EACH_BB (bb)
{
- cse_altered = 0;
- cse_end_of_basic_block (insn, &val, flag_cse_follow_jumps, after_loop,
- flag_cse_skip_blocks);
+ int nsets;
- /* 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;
- }
+ /* Compute the maximum number of qty's needed for the basic block. */
+ nsets = cse_count_sets_in_basic_block (bb);
- cse_basic_block_start = val.low_cuid;
- cse_basic_block_end = val.high_cuid;
- max_qty = val.nsets * 2;
+ /* Old commentary claims that max 2 qtys are needed for each set.
+ This is a lie. Maximum is one qty per operand, plus one for
+ the set destination. Previously we succeeded because we
+ incorporated slop "for optimizing past the end of the block".
+ Maintain that here, though not for the previously stated reason. */
+ max_qty = (nsets < 250 ? 500 : 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);
+ cse_basic_block_start = INSN_CUID (bb->head);
+ cse_basic_block_end = INSN_CUID (bb->end);
- /* Make MAX_QTY bigger to give us room to optimize
- past the end of this basic block, if that should prove useful. */
- if (max_qty < 500)
- max_qty = 500;
+ if (rtl_dump_file)
+ fnotice (rtl_dump_file, ";; Processing block from %d to %d, %d sets.\n",
+ INSN_UID (bb->head), INSN_UID (bb->end), nsets);
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;
- rtx temp;
-
- /* When cse changes a conditional jump to an unconditional
- 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;
-
- cse_jumps_altered |= old_cse_jumps_altered;
- }
-
+ cse_altered = 0;
+ cse_basic_block (bb);
if (cse_altered)
ggc_collect ();
@@ -7206,22 +6626,11 @@ cse_main (f, nregs, after_loop, file)
return cse_jumps_altered || recorded_label_ref;
}
-/* Process a single basic block. FROM and TO and the limits of the basic
- block. NEXT_BRANCH points to the branch path when following jumps or
- a null path when not following jumps.
-
- AROUND_LOOP is nonzero 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)
- rtx from, to;
- struct branch_path *next_branch;
- int around_loop;
+static void
+cse_basic_block (bb)
+ basic_block bb;
{
- rtx insn;
- int to_usage = 0;
+ rtx insn, end;
rtx libcall_insn = NULL_RTX;
int num_insns = 0;
@@ -7235,11 +6644,12 @@ cse_basic_block (from, to, next_branch,
new_basic_block ();
- /* TO might be a label. If so, protect it from being deleted. */
- if (to != 0 && GET_CODE (to) == CODE_LABEL)
- ++LABEL_NUSES (to);
+ /* Careful: bb->end can change inside the loop. Usually this happens
+ when we simplify a branch insn to a noop. */
+ insn = bb->head;
+ end = bb->end;
- for (insn = from; insn != to; insn = NEXT_INSN (insn))
+ while (1)
{
enum rtx_code code = GET_CODE (insn);
@@ -7258,32 +6668,6 @@ cse_basic_block (from, to, next_branch,
num_insns = 0;
}
- /* See if this is a branch that is part of the path. If so, and it is
- to be taken, do so. */
- 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. */
-#ifdef HAVE_cc0
- prev_insn_cc0 = 0;
- prev_insn = insn;
-#endif
- insn = JUMP_LABEL (insn);
- continue;
- }
- }
-
- if (GET_MODE (insn) == QImode)
- PUT_MODE (insn, VOIDmode);
-
if (GET_RTX_CLASS (code) == 'i')
{
rtx p;
@@ -7318,110 +6702,15 @@ cse_basic_block (from, to, next_branch,
recorded_label_ref = 1;
}
- /* If INSN is now an unconditional jump, skip to the end of our
- basic block by pretending that we just did the last insn in the
- basic block. If we are jumping to the end of our block, show
- that we can have one usage of TO. */
-
- if (any_uncondjump_p (insn))
- {
- if (to == 0)
- {
- free (qty_table + max_reg);
- return 0;
- }
-
- if (JUMP_LABEL (insn) == to)
- to_usage = 1;
-
- /* Maybe TO was deleted because the jump is unconditional.
- If so, there is nothing left in this basic block. */
- /* ??? Perhaps it would be smarter to set TO
- to whatever follows this insn,
- and pretend the basic block had always ended here. */
- if (INSN_DELETED_P (to))
- break;
-
- insn = PREV_INSN (to);
- }
-
- /* See if it is ok to keep on going past the label
- which used to end our basic block. Remember that we incremented
- the count of that label, so we decrement it here. If we made
- a jump unconditional, TO_USAGE will be one; in that case, we don't
- want to count the use in that jump. */
-
- if (to != 0 && NEXT_INSN (insn) == to
- && GET_CODE (to) == CODE_LABEL && --LABEL_NUSES (to) == to_usage)
- {
- 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,
- continue through it. Otherwise, return,
- and that block will be scanned individually. */
- if (val.nsets * 2 + next_qty > max_qty)
- break;
-
- cse_basic_block_start = val.low_cuid;
- cse_basic_block_end = val.high_cuid;
- to = val.last;
-
- /* Prevent TO from being deleted if it is a label. */
- if (to != 0 && GET_CODE (to) == CODE_LABEL)
- ++LABEL_NUSES (to);
-
- /* Back up so we process the first insn in the extension. */
- insn = PREV_INSN (insn);
- }
+ if (insn == end)
+ break;
+ insn = NEXT_INSN (insn);
}
if (next_qty > max_qty)
abort ();
- /* If we are running before loop.c, we stopped on a NOTE_INSN_LOOP_END, and
- the previous insn is the only insn that branches to the head of a loop,
- we can cse into the loop. Don't do this if we changed the jump
- structure of a loop unless we aren't going to be following jumps. */
-
- insn = prev_nonnote_insn (to);
- if ((cse_jumps_altered == 0
- || (flag_cse_follow_jumps == 0 && flag_cse_skip_blocks == 0))
- && around_loop && to != 0
- && GET_CODE (to) == NOTE && NOTE_LINE_NUMBER (to) == NOTE_INSN_LOOP_END
- && GET_CODE (insn) == JUMP_INSN
- && JUMP_LABEL (insn) != 0
- && LABEL_NUSES (JUMP_LABEL (insn)) == 1)
- cse_around_loop (JUMP_LABEL (insn));
-
free (qty_table + max_reg);
-
- return to ? NEXT_INSN (to) : 0;
}
/* Called via for_each_rtx to see if an insn is using a LABEL_REF for which
Index: rtl.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/rtl.h,v
retrieving revision 1.383
diff -c -p -d -u -r1.383 rtl.h
--- rtl.h 5 Feb 2003 00:56:40 -0000 1.383
+++ rtl.h 12 Feb 2003 20:52:19 -0000
@@ -1944,12 +1944,7 @@ struct cse_basic_block_data;
extern int rtx_cost PARAMS ((rtx, enum rtx_code));
extern int address_cost PARAMS ((rtx, enum machine_mode));
extern int 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));
+extern int cse_main PARAMS ((int));
/* In jump.c */
extern int comparison_dominates_p PARAMS ((enum rtx_code, enum rtx_code));
Index: toplev.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/toplev.c,v
retrieving revision 1.708
diff -c -p -d -u -r1.708 toplev.c
--- toplev.c 12 Feb 2003 01:01:19 -0000 1.708
+++ toplev.c 12 Feb 2003 20:52:20 -0000
@@ -2828,7 +2828,7 @@ rest_of_compilation (decl)
reg_scan (insns, max_reg_num (), 1);
- tem = cse_main (insns, max_reg_num (), 0, rtl_dump_file);
+ tem = cse_main (0);
if (tem)
rebuild_jump_labels (insns);
purge_all_dead_edges (0);
@@ -2894,7 +2894,7 @@ rest_of_compilation (decl)
{
timevar_push (TV_CSE);
reg_scan (insns, max_reg_num (), 1);
- tem2 = cse_main (insns, max_reg_num (), 0, rtl_dump_file);
+ tem2 = cse_main (0);
purge_all_dead_edges (0);
delete_trivially_dead_insns (insns, max_reg_num ());
timevar_pop (TV_CSE);
@@ -2915,7 +2915,7 @@ rest_of_compilation (decl)
{
timevar_push (TV_CSE);
reg_scan (insns, max_reg_num (), 1);
- tem2 = cse_main (insns, max_reg_num (), 0, rtl_dump_file);
+ tem2 = cse_main (0);
purge_all_dead_edges (0);
delete_trivially_dead_insns (insns, max_reg_num ());
timevar_pop (TV_CSE);
@@ -3126,7 +3126,7 @@ rest_of_compilation (decl)
if (rtl_dump_file)
dump_flow_info (rtl_dump_file);
/* CFG is no longer maintained up-to-date. */
- tem = cse_main (insns, max_reg_num (), 1, rtl_dump_file);
+ tem = cse_main (1);
purge_all_dead_edges (0);
delete_trivially_dead_insns (insns, max_reg_num ());
More information about the Gcc
mailing list