-/* Move constant computations out of loops.
- Copyright (C) 1987, 88, 89, 91, 92, 93, 1994 Free Software Foundation, Inc.
+/* Perform various loop optimizations, including strength reduction.
+ Copyright (C) 1987, 88, 89, 91-6, 1997 Free Software Foundation, Inc.
This file is part of GNU CC.
You should have received a copy of the GNU General Public License
along with GNU CC; see the file COPYING. If not, write to
-the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
+the Free Software Foundation, 59 Temple Place - Suite 330,
+Boston, MA 02111-1307, USA. */
/* This is the loop optimization pass of the compiler.
Most of the complexity is in heuristics to decide when it is worth
while to do these things. */
-#include <stdio.h>
#include "config.h"
+#include <stdio.h>
#include "rtl.h"
#include "obstack.h"
#include "expr.h"
#include "flags.h"
#include "real.h"
#include "loop.h"
+#include "except.h"
/* Vector mapping INSN_UIDs to luids.
The luids are like uids but increase monotonically always.
int *loop_outer_loop;
+#ifdef HAIFA
+/* The main output of analyze_loop_iterations is placed here */
+
+int *loop_can_insert_bct;
+
+/* For each loop, determines whether some of its inner loops has used
+ count register */
+
+int *loop_used_count_register;
+
+/* loop parameters for arithmetic loops. These loops have a loop variable
+ which is initialized to loop_start_value, incremented in each iteration
+ by "loop_increment". At the end of the iteration the loop variable is
+ compared to the loop_comparison_value (using loop_comparison_code). */
+
+rtx *loop_increment;
+rtx *loop_comparison_value;
+rtx *loop_start_value;
+enum rtx_code *loop_comparison_code;
+#endif /* HAIFA */
+
+/* For each loop, keep track of its unrolling factor.
+ Potential values:
+ 0: unrolled
+ 1: not unrolled.
+ -1: completely unrolled
+ >0: holds the unroll exact factor. */
+int *loop_unroll_factor;
+
/* Indexed by loop number, contains a nonzero value if the "loop" isn't
really a loop (an insn outside the loop branches into it). */
rtx *loop_number_exit_labels;
+/* Indexed by loop number, counts the number of LABEL_REFs on
+ loop_number_exit_labels for this loop and all loops nested inside it. */
+
+int *loop_number_exit_count;
+
/* Holds the number of loop iterations. It is zero if the number could not be
calculated. Must be unsigned since the number of iterations can
be as high as 2^wordsize-1. For loops with a wider iterator, this number
unsigned HOST_WIDE_INT loop_n_iterations;
-/* Nonzero if there is a subroutine call in the current loop.
- (unknown_address_altered is also nonzero in this case.) */
+/* Nonzero if there is a subroutine call in the current loop. */
static int loop_has_call;
Therefore, at all times, == 0 indicates an invariant register;
< 0 a conditionally invariant one. */
-static short *n_times_set;
+static int *n_times_set;
/* Original value of n_times_set; same except that this value
is not set negative for a reg whose sets have been made candidates
and not set to 0 for a reg that is moved. */
-static short *n_times_used;
+static int *n_times_used;
/* Index by register number, 1 indicates that the register
cannot be moved or strength reduced. */
/* Array of MEMs that are stored in this loop. If there are too many to fit
here, we just turn on unknown_address_altered. */
-#define NUM_STORES 20
+#define NUM_STORES 30
static rtx loop_store_mems[NUM_STORES];
/* Index of first available slot in above array. */
struct movable
{
rtx insn; /* A movable insn */
- rtx set_src; /* The expression this reg is set from. */
- rtx set_dest; /* The destination of this SET. */
+ rtx set_src; /* The expression this reg is set from. */
+ rtx set_dest; /* The destination of this SET. */
rtx dependencies; /* When INSN is libcall, this is an EXPR_LIST
- of any registers used within the LIBCALL. */
+ of any registers used within the LIBCALL. */
int consec; /* Number of consecutive following insns
that must be moved with this one. */
int regno; /* The register it sets */
invariant. */
unsigned int move_insn : 1; /* 1 means that we call emit_move_insn to
load SRC, rather than copying INSN. */
- unsigned int is_equiv : 1; /* 1 means a REG_EQUIV is present on INSN. */
+ unsigned int is_equiv : 1; /* 1 means a REG_EQUIV is present on INSN. */
enum machine_mode savemode; /* Nonzero means it is a mode for a low part
that we should avoid changing when clearing
the rest of the reg. */
static void note_addr_stored ();
static int loop_reg_used_before_p ();
static void scan_loop ();
+#if 0
static void replace_call_address ();
+#endif
static rtx skip_consec_insns ();
static int libcall_benefit ();
static void ignore_some_movables ();
static int last_use_this_basic_block ();
static void record_initial ();
static void update_reg_last_use ();
+
+#ifdef HAIFA
+/* This is extern from unroll.c */
+void iteration_info ();
+
+/* Two main functions for implementing bct:
+ first - to be called before loop unrolling, and the second - after */
+static void analyze_loop_iterations ();
+static void insert_bct ();
+
+/* Auxiliary function that inserts the bct pattern into the loop */
+static void instrument_loop_bct ();
+#endif /* HAIFA */
+
+/* Indirect_jump_in_function is computed once per function. */
+int indirect_jump_in_function = 0;
+static int indirect_jump_in_function_p ();
+
\f
/* Relative gain of eliminating various kinds of operations. */
int add_cost;
init_loop ()
{
char *free_point = (char *) oballoc (1);
- rtx reg = gen_rtx (REG, word_mode, 0);
+ rtx reg = gen_rtx (REG, word_mode, LAST_VIRTUAL_REGISTER + 1);
add_cost = rtx_cost (gen_rtx (PLUS, word_mode, reg, reg), SET);
regs_may_share = 0;
- /* Count the number of loops. */
+ /* Count the number of loops. */
max_loop_num = 0;
for (insn = f; insn; insn = NEXT_INSN (insn))
loop_outer_loop = (int *) alloca (max_loop_num * sizeof (int));
loop_invalid = (char *) alloca (max_loop_num * sizeof (char));
loop_number_exit_labels = (rtx *) alloca (max_loop_num * sizeof (rtx));
+ loop_number_exit_count = (int *) alloca (max_loop_num * sizeof (int));
+
+ /* This is initialized by the unrolling code, so we go ahead
+ and clear them just in case we are not performing loop
+ unrolling. */
+ loop_unroll_factor = (int *) alloca (max_loop_num *sizeof (int));
+ bzero ((char *) loop_unroll_factor, max_loop_num * sizeof (int));
+
+#ifdef HAIFA
+ /* Allocate for BCT optimization */
+ loop_can_insert_bct = (int *) alloca (max_loop_num * sizeof (int));
+ bzero ((char *) loop_can_insert_bct, max_loop_num * sizeof (int));
+
+ loop_used_count_register = (int *) alloca (max_loop_num * sizeof (int));
+ bzero ((char *) loop_used_count_register, max_loop_num * sizeof (int));
+
+ loop_increment = (rtx *) alloca (max_loop_num * sizeof (rtx));
+ loop_comparison_value = (rtx *) alloca (max_loop_num * sizeof (rtx));
+ loop_start_value = (rtx *) alloca (max_loop_num * sizeof (rtx));
+ bzero ((char *) loop_increment, max_loop_num * sizeof (rtx));
+ bzero ((char *) loop_comparison_value, max_loop_num * sizeof (rtx));
+ bzero ((char *) loop_start_value, max_loop_num * sizeof (rtx));
+
+ loop_comparison_code
+ = (enum rtx_code *) alloca (max_loop_num * sizeof (enum rtx_code));
+ bzero ((char *) loop_comparison_code, max_loop_num * sizeof (enum rtx_code));
+#endif /* HAIFA */
/* Find and process each loop.
First, find them, and record them in order of their beginnings. */
if (flag_unroll_loops && write_symbols != NO_DEBUG)
find_loop_tree_blocks ();
+ /* Determine if the function has indirect jump. On some systems
+ this prevents low overhead loop instructions from being used. */
+ indirect_jump_in_function = indirect_jump_in_function_p (f);
+
/* Now scan the loops, last ones first, since this means inner ones are done
before outer ones. */
for (i = max_loop_num-1; i >= 0; i--)
/* Nonzero if we are scanning instructions in a sub-loop. */
int loop_depth = 0;
- n_times_set = (short *) alloca (nregs * sizeof (short));
- n_times_used = (short *) alloca (nregs * sizeof (short));
+ n_times_set = (int *) alloca (nregs * sizeof (int));
+ n_times_used = (int *) alloca (nregs * sizeof (int));
may_not_optimize = (char *) alloca (nregs);
/* Determine whether this loop starts with a jump down to a test at
the setting of register I. If this loop has calls, set
reg_single_usage[I]. */
- bzero ((char *) n_times_set, nregs * sizeof (short));
+ bzero ((char *) n_times_set, nregs * sizeof (int));
bzero (may_not_optimize, nregs);
if (loop_has_call)
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
may_not_optimize[i] = 1, n_times_set[i] = 1;
- bcopy ((char *) n_times_set, (char *) n_times_used, nregs * sizeof (short));
+ bcopy ((char *) n_times_set, (char *) n_times_used, nregs * sizeof (int));
if (loop_dump_stream)
{
if (reg_single_usage && reg_single_usage[regno] != 0
&& reg_single_usage[regno] != const0_rtx
- && regno_first_uid[regno] == INSN_UID (p)
- && (regno_last_uid[regno]
+ && REGNO_FIRST_UID (regno) == INSN_UID (p)
+ && (REGNO_LAST_UID (regno)
== INSN_UID (reg_single_usage[regno]))
&& n_times_set[REGNO (SET_DEST (set))] == 1
&& ! side_effects_p (SET_SRC (set))
&& ! find_reg_note (p, REG_RETVAL, NULL_RTX)
-#ifdef SMALL_REGISTER_CLASSES
- && ! (GET_CODE (SET_SRC (set)) == REG
- && REGNO (SET_SRC (set)) < FIRST_PSEUDO_REGISTER)
-#endif
+ && (! SMALL_REGISTER_CLASSES
+ || (! (GET_CODE (SET_SRC (set)) == REG
+ && REGNO (SET_SRC (set)) < FIRST_PSEUDO_REGISTER)))
/* This test is not redundant; SET_SRC (set) might be
a call-clobbered register and the life of REGNO
might span a call. */
/* Set M->cond if either invariant_p or consec_sets_invariant_p
returned 2 (only conditionally invariant). */
m->cond = ((tem | tem1 | tem2) > 1);
- m->global = (uid_luid[regno_last_uid[regno]] > INSN_LUID (end)
- || uid_luid[regno_first_uid[regno]] < INSN_LUID (loop_start));
+ m->global = (uid_luid[REGNO_LAST_UID (regno)] > INSN_LUID (end)
+ || uid_luid[REGNO_FIRST_UID (regno)] < INSN_LUID (loop_start));
m->match = 0;
- m->lifetime = (uid_luid[regno_last_uid[regno]]
- - uid_luid[regno_first_uid[regno]]);
+ m->lifetime = (uid_luid[REGNO_LAST_UID (regno)]
+ - uid_luid[REGNO_FIRST_UID (regno)]);
m->savings = n_times_used[regno];
if (find_reg_note (p, REG_RETVAL, NULL_RTX))
m->savings += libcall_benefit (p);
If this insn was made by loop, we don't know its
INSN_LUID and hence must make a conservative
- assumption. */
+ assumption. */
m->global = (INSN_UID (p) >= max_uid_for_loop
- || (uid_luid[regno_last_uid[regno]]
+ || (uid_luid[REGNO_LAST_UID (regno)]
> INSN_LUID (end))
- || (uid_luid[regno_first_uid[regno]]
+ || (uid_luid[REGNO_FIRST_UID (regno)]
< INSN_LUID (p))
|| (labels_in_range_p
- (p, uid_luid[regno_first_uid[regno]])));
+ (p, uid_luid[REGNO_FIRST_UID (regno)])));
if (maybe_never && m->global)
m->savemode = GET_MODE (SET_SRC (set1));
else
m->regno = regno;
m->cond = 0;
m->match = 0;
- m->lifetime = (uid_luid[regno_last_uid[regno]]
- - uid_luid[regno_first_uid[regno]]);
+ m->lifetime = (uid_luid[REGNO_LAST_UID (regno)]
+ - uid_luid[REGNO_FIRST_UID (regno)]);
m->savings = 1;
n_times_set[regno] = -1;
/* Add M to the end of the chain MOVABLES. */
executed during each iteration. Therefore, we can
only move out sets of trivial variables
(those not used after the loop). */
- /* This code appears in three places, once in scan_loop, and twice
- in strength_reduce. */
+ /* Similar code appears twice in strength_reduce. */
else if ((GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
/* If we enter the loop in the middle, and scan around to the
beginning, don't set maybe_never for that. This must be an
&& ! reg_mentioned_p (in_this, not_in_this))
*output = gen_rtx (EXPR_LIST, VOIDmode, in_this, *output);
return;
+
+ default:
+ break;
}
fmt = GET_RTX_FORMAT (code);
int regno = REGNO (reg);
rtx p;
- if (regno_first_uid[regno] != INSN_UID (insn))
+ if (REGNO_FIRST_UID (regno) != INSN_UID (insn))
return 0;
/* Search this basic block for the already recorded last use of the reg. */
case INSN:
case CALL_INSN:
/* Ordinary insn: if this is the last use, we win. */
- if (regno_last_uid[regno] == INSN_UID (p))
+ if (REGNO_LAST_UID (regno) == INSN_UID (p))
return 1;
break;
case JUMP_INSN:
/* Jump insn: if this is the last use, we win. */
- if (regno_last_uid[regno] == INSN_UID (p))
+ if (REGNO_LAST_UID (regno) == INSN_UID (p))
return 1;
/* Otherwise, it's the end of the basic block, so we lose. */
return 0;
case BARRIER:
/* It's the end of the basic block, so we lose. */
return 0;
+
+ default:
+ break;
}
}
{
if (GET_CODE (insn) == CALL_INSN)
benefit += 10; /* Assume at least this many insns in a library
- routine. */
+ routine. */
else if (GET_CODE (insn) == INSN
&& GET_CODE (PATTERN (insn)) != USE
&& GET_CODE (PATTERN (insn)) != CLOBBER)
this insn M->insn might not be where it dies.
But very likely this doesn't matter; what matters is
that M's reg is computed from M1's reg. */
- if (INSN_UID (m->insn) == regno_last_uid[regno]
+ if (INSN_UID (m->insn) == REGNO_LAST_UID (regno)
&& !m->done)
break;
if (m != 0 && m->set_src == m1->set_dest
bzero (matched_regs, nregs);
matched_regs[regno] = 1;
- for (m1 = movables; m1; m1 = m1->next)
+ /* We want later insns to match the first one. Don't make the first
+ one match any later ones. So start this loop at m->next. */
+ for (m1 = m->next; m1; m1 = m1->next)
if (m != m1 && m1->match == 0 && n_times_used[m1->regno] == 1
/* A reg used outside the loop mustn't be eliminated. */
&& !m1->global
&& mode == GET_MODE (SET_SRC (PATTERN (NEXT_INSN (m->insn)))))
{
register struct movable *m1;
- int first = uid_luid[regno_first_uid[m->regno]];
- int last = uid_luid[regno_last_uid[m->regno]];
+ int first = uid_luid[REGNO_FIRST_UID (m->regno)];
+ int last = uid_luid[REGNO_LAST_UID (m->regno)];
if (m0 == 0)
{
already combined together. */
for (m1 = movables; m1 != m; m1 = m1->next)
if (m1 == m0 || (m1->partial && m1->match == m0))
- if (! (uid_luid[regno_first_uid[m1->regno]] > last
- || uid_luid[regno_last_uid[m1->regno]] < first))
+ if (! (uid_luid[REGNO_FIRST_UID (m1->regno)] > last
+ || uid_luid[REGNO_LAST_UID (m1->regno)] < first))
goto overlap;
/* No overlap: we can combine this with the others. */
extra cost because something else was already moved. */
if (already_moved[regno]
+ || flag_move_all_movables
|| (threshold * savings * m->lifetime) >= insn_count
|| (m->forces && m->forces->done
&& n_times_used[m->forces->regno] == 1))
{
rtx i1, temp;
- /* If first insn of libcall sequence, skip to end. */
+ /* If first insn of libcall sequence, skip to end. */
/* Do this at start of loop, since p is guaranteed to
be an insn here. */
if (GET_CODE (p) != NOTE
contains objects other than hard registers
we need to copy it. */
if (CALL_INSN_FUNCTION_USAGE (temp))
- CALL_INSN_FUNCTION_USAGE (i1) =
- copy_rtx (CALL_INSN_FUNCTION_USAGE (temp));
+ CALL_INSN_FUNCTION_USAGE (i1)
+ = copy_rtx (CALL_INSN_FUNCTION_USAGE (temp));
}
else
i1 = emit_insn_before (body, loop_start);
contains objects other than hard registers
we need to copy it. */
if (CALL_INSN_FUNCTION_USAGE (p))
- CALL_INSN_FUNCTION_USAGE (i1) =
- copy_rtx (CALL_INSN_FUNCTION_USAGE (p));
+ CALL_INSN_FUNCTION_USAGE (i1)
+ = copy_rtx (CALL_INSN_FUNCTION_USAGE (p));
}
else
i1 = emit_insn_before (PATTERN (p), loop_start);
/* This isn't needed because REG_NOTES is copied
below and is wrong since P might be a PARALLEL. */
if (REG_NOTES (i1) == 0
- && ! m->partial /* But not if it's a zero-extend clr. */
+ && ! m->partial /* But not if it's a zero-extend clr. */
&& ! m->global /* and not if used outside the loop
(since it might get set outside). */
&& CONSTANT_P (SET_SRC (PATTERN (p))))
to say it lives at least the full length of this loop.
This will help guide optimizations in outer loops. */
- if (uid_luid[regno_first_uid[regno]] > INSN_LUID (loop_start))
+ if (uid_luid[REGNO_FIRST_UID (regno)] > INSN_LUID (loop_start))
/* This is the old insn before all the moved insns.
We can't use the moved insn because it is out of range
in uid_luid. Only the old insns have luids. */
- regno_first_uid[regno] = INSN_UID (loop_start);
- if (uid_luid[regno_last_uid[regno]] < INSN_LUID (end))
- regno_last_uid[regno] = INSN_UID (end);
+ REGNO_FIRST_UID (regno) = INSN_UID (loop_start);
+ if (uid_luid[REGNO_LAST_UID (regno)] < INSN_LUID (end))
+ REGNO_LAST_UID (regno) = INSN_UID (end);
/* Combine with this moved insn any other matching movables. */
abort ();
XEXP (x, 0) = addr;
return;
+
+ default:
+ break;
}
fmt = GET_RTX_FORMAT (code);
case MEM:
return ((invariant_p (XEXP (x, 0)) != 1)
+ count_nonfixed_reads (XEXP (x, 0)));
+
+ default:
+ break;
}
value = 0;
}
else if (GET_CODE (insn) == CALL_INSN)
{
- unknown_address_altered = 1;
+ if (! CONST_CALL_P (insn))
+ unknown_address_altered = 1;
loop_has_call = 1;
}
else
loop_outer_loop[next_loop] = current_loop;
loop_invalid[next_loop] = 0;
loop_number_exit_labels[next_loop] = 0;
+ loop_number_exit_count[next_loop] = 0;
current_loop = next_loop;
break;
current_loop = loop_outer_loop[current_loop];
break;
+ default:
+ break;
}
/* Note that this will mark the NOTE_INSN_LOOP_END note as being in the
loop_invalid[loop_num] = 1;
}
+ /* Any loop containing a label used for an exception handler must be
+ invalidated, because it can be jumped into from anywhere. */
+
+ for (label = exception_handler_labels; label; label = XEXP (label, 1))
+ {
+ int loop_num;
+
+ for (loop_num = uid_loop_num[INSN_UID (XEXP (label, 0))];
+ loop_num != -1;
+ loop_num = loop_outer_loop[loop_num])
+ loop_invalid[loop_num] = 1;
+ }
+
/* Now scan all insn's in the function. If any JUMP_INSN branches into a
loop that it is not contained within, that loop is marked invalid.
If any INSN or CALL_INSN uses a label's address, then the loop containing
{
rtx p;
rtx our_next = next_real_insn (insn);
+ int dest_loop;
+ int outer_loop = -1;
/* Go backwards until we reach the start of the loop, a label,
or a JUMP_INSN. */
p = PREV_INSN (p))
;
+ /* Check for the case where we have a jump to an inner nested
+ loop, and do not perform the optimization in that case. */
+
+ if (JUMP_LABEL (insn))
+ {
+ dest_loop = uid_loop_num[INSN_UID (JUMP_LABEL (insn))];
+ if (dest_loop != -1)
+ {
+ for (outer_loop = dest_loop; outer_loop != -1;
+ outer_loop = loop_outer_loop[outer_loop])
+ if (outer_loop == this_loop_num)
+ break;
+ }
+ }
+
+ /* Make sure that the target of P is within the current loop. */
+
+ if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p)
+ && uid_loop_num[INSN_UID (JUMP_LABEL (p))] != this_loop_num)
+ outer_loop = this_loop_num;
+
/* If we stopped on a JUMP_INSN to the next insn after INSN,
we have a block of code to try to move.
of the block, invert the jump in P and point it to that label,
and move the block of code to the spot we found. */
- if (GET_CODE (p) == JUMP_INSN
+ if (outer_loop == -1
+ && GET_CODE (p) == JUMP_INSN
&& JUMP_LABEL (p) != 0
/* Just ignore jumps to labels that were never emitted.
These always indicate compilation errors. */
LABEL_NUSES (cond_label)++;
/* Verify that uid_loop_num is large enough and that
- we can invert P. */
+ we can invert P. */
if (invert_jump (p, new_label))
{
rtx q, r;
LABEL_OUTSIDE_LOOP_P bit. */
if (JUMP_LABEL (insn))
{
+ int loop_num;
+
for (q = 0,
r = loop_number_exit_labels[this_loop_num];
r; q = r, r = LABEL_NEXTREF (r))
break;
}
- /* If we didn't find it, then something is wrong. */
+ for (loop_num = this_loop_num;
+ loop_num != -1 && loop_num != target_loop_num;
+ loop_num = loop_outer_loop[loop_num])
+ loop_number_exit_count[loop_num]--;
+
+ /* If we didn't find it, then something is wrong. */
if (! r)
abort ();
}
mark this LABEL_REF so we know that this branch should predict
false. */
- if (dest_loop != loop_num && loop_num != -1)
+ /* A check to make sure the label is not in an inner nested loop,
+ since this does not count as a loop exit. */
+ if (dest_loop != -1)
+ {
+ for (outer_loop = dest_loop; outer_loop != -1;
+ outer_loop = loop_outer_loop[outer_loop])
+ if (outer_loop == loop_num)
+ break;
+ }
+ else
+ outer_loop = -1;
+
+ if (loop_num != -1 && outer_loop == -1)
{
LABEL_OUTSIDE_LOOP_P (x) = 1;
LABEL_NEXTREF (x) = loop_number_exit_labels[loop_num];
loop_number_exit_labels[loop_num] = x;
+
+ for (outer_loop = loop_num;
+ outer_loop != -1 && outer_loop != dest_loop;
+ outer_loop = loop_outer_loop[outer_loop])
+ loop_number_exit_count[outer_loop]++;
}
/* If this is inside a loop, but not in the current loop or one enclosed
if (loop_num != -1)
{
+#ifdef HAIFA
LABEL_OUTSIDE_LOOP_P (x) = 1;
LABEL_NEXTREF (x) = loop_number_exit_labels[loop_num];
+#endif /* HAIFA */
+
loop_number_exit_labels[loop_num] = x;
- }
+ for (outer_loop = loop_num; outer_loop != -1;
+ outer_loop = loop_outer_loop[outer_loop])
+ loop_number_exit_count[outer_loop]++;
+ }
return;
}
}
case REG:
/* We used to check RTX_UNCHANGING_P (x) here, but that is invalid
since the reg might be set by initialization within the loop. */
- if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
- || x == arg_pointer_rtx)
+
+ if ((x == frame_pointer_rtx || x == hard_frame_pointer_rtx
+ || x == arg_pointer_rtx)
+ && ! current_function_has_nonlocal_goto)
return 1;
+
if (loop_has_call
&& REGNO (x) < FIRST_PSEUDO_REGISTER && call_used_regs[REGNO (x)])
return 0;
+
if (n_times_set[REGNO (x)] < 0)
return 2;
+
return n_times_set[REGNO (x)] == 0;
case MEM:
/* See if there is any dependence between a store and this load. */
for (i = loop_store_mems_idx - 1; i >= 0; i--)
- if (true_dependence (loop_store_mems[i], x))
+ if (true_dependence (loop_store_mems[i], VOIDmode, x, rtx_varies_p))
return 0;
/* It's not invalidated by a store in memory
/* Don't mess with insns declared volatile. */
if (MEM_VOLATILE_P (x))
return 0;
+ break;
+
+ default:
+ break;
}
fmt = GET_RTX_FORMAT (code);
it is safe to keep the value in a register for the duration of the
loop. One tricky thing is that the copying of the value back from the
register has to be done on all exits from the loop. You need to check that
- all the exits from the loop go to the same place. */
+ all the exits from the loop go to the same place. */
/* ??? The interaction of biv elimination, and recognition of 'constant'
- bivs, may cause problems. */
+ bivs, may cause problems. */
/* ??? Add heuristics so that DEST_ADDR strength reduction does not cause
performance problems.
/* Past CODE_LABEL, we get to insns that may be executed multiple
times. The only way we can be sure that they can't is if every
every jump insn between here and the end of the loop either
- returns, exits the loop, or is a forward jump. */
+ returns, exits the loop, is a forward jump, or is a jump
+ to the loop start. */
if (GET_CODE (p) == CODE_LABEL)
{
&& GET_CODE (PATTERN (insn)) != RETURN
&& (! condjump_p (insn)
|| (JUMP_LABEL (insn) != 0
+ && JUMP_LABEL (insn) != scan_start
&& (INSN_UID (JUMP_LABEL (insn)) >= max_uid_for_loop
|| INSN_UID (insn) >= max_uid_for_loop
|| (INSN_LUID (JUMP_LABEL (insn))
< INSN_LUID (insn))))))
- {
- maybe_multiple = 1;
- break;
- }
+ {
+ maybe_multiple = 1;
+ break;
+ }
}
}
- /* Past a label or a jump, we get to insns for which we can't count
- on whether or how many times they will be executed during each
- iteration. */
- /* This code appears in three places, once in scan_loop, and twice
- in strength_reduce. */
- if ((GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
+ /* Past a jump, we get to insns for which we can't count
+ on whether they will be executed during each iteration. */
+ /* This code appears twice in strength_reduce. There is also similar
+ code in scan_loop. */
+ if (GET_CODE (p) == JUMP_INSN
/* If we enter the loop in the middle, and scan around to the
beginning, don't set not_every_iteration for that.
This can be any kind of jump, since we want to know if insns
will be executed if the loop is executed. */
- && ! (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == loop_top
+ && ! (JUMP_LABEL (p) == loop_top
&& ((NEXT_INSN (NEXT_INSN (p)) == loop_end && simplejump_p (p))
|| (NEXT_INSN (p) == loop_end && condjump_p (p)))))
- not_every_iteration = 1;
+ {
+ rtx label = 0;
+
+ /* If this is a jump outside the loop, then it also doesn't
+ matter. Check to see if the target of this branch is on the
+ loop_number_exits_labels list. */
+
+ for (label = loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]];
+ label;
+ label = LABEL_NEXTREF (label))
+ if (XEXP (label, 0) == JUMP_LABEL (p))
+ break;
+
+ if (! label)
+ not_every_iteration = 1;
+ }
else if (GET_CODE (p) == NOTE)
{
Therefore, if we have just passed a label and have no more labels
between here and the test insn of the loop, we know these insns
- will be executed each iteration. This can also happen if we
- have just passed a jump, for example, when there are nested loops. */
+ will be executed each iteration. */
if (not_every_iteration && GET_CODE (p) == CODE_LABEL
&& no_labels_between_p (p, loop_end))
((benefit = general_induction_var (SET_SRC (set),
&src_reg, &add_val,
&mult_val))
- /* Equivalent expression is a giv. */
+ /* Equivalent expression is a giv. */
|| ((regnote = find_reg_note (p, REG_EQUAL, NULL_RTX))
&& (benefit = general_induction_var (XEXP (regnote, 0),
&src_reg,
&& dest_reg != src_reg
/* This must be the only place where the register is set. */
&& (n_times_set[REGNO (dest_reg)] == 1
- /* or all sets must be consecutive and make a giv. */
+ /* or all sets must be consecutive and make a giv. */
|| (benefit = consec_sets_giv (benefit, p,
src_reg, dest_reg,
&add_val, &mult_val))))
|| GET_CODE (p) == CODE_LABEL)
update_giv_derive (p);
- /* Past a label or a jump, we get to insns for which we can't count
- on whether or how many times they will be executed during each
- iteration. */
- /* This code appears in three places, once in scan_loop, and twice
- in strength_reduce. */
- if ((GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
- /* If we enter the loop in the middle, and scan around
- to the beginning, don't set not_every_iteration for that.
+ /* Past a jump, we get to insns for which we can't count
+ on whether they will be executed during each iteration. */
+ /* This code appears twice in strength_reduce. There is also similar
+ code in scan_loop. */
+ if (GET_CODE (p) == JUMP_INSN
+ /* If we enter the loop in the middle, and scan around to the
+ beginning, don't set not_every_iteration for that.
This can be any kind of jump, since we want to know if insns
will be executed if the loop is executed. */
- && ! (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == loop_top
+ && ! (JUMP_LABEL (p) == loop_top
&& ((NEXT_INSN (NEXT_INSN (p)) == loop_end && simplejump_p (p))
|| (NEXT_INSN (p) == loop_end && condjump_p (p)))))
- not_every_iteration = 1;
+ {
+ rtx label = 0;
+
+ /* If this is a jump outside the loop, then it also doesn't
+ matter. Check to see if the target of this branch is on the
+ loop_number_exits_labels list. */
+
+ for (label = loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]];
+ label;
+ label = LABEL_NEXTREF (label))
+ if (XEXP (label, 0) == JUMP_LABEL (p))
+ break;
+
+ if (! label)
+ not_every_iteration = 1;
+ }
else if (GET_CODE (p) == NOTE)
{
so that "decrement and branch until zero" insn can be used. */
check_dbra_loop (loop_end, insn_count, loop_start);
+#ifdef HAIFA
+ /* record loop-variables relevant for BCT optimization before unrolling
+ the loop. Unrolling may update part of this information, and the
+ correct data will be used for generating the BCT. */
+#ifdef HAVE_decrement_and_branch_on_count
+ if (HAVE_decrement_and_branch_on_count)
+ analyze_loop_iterations (loop_start, loop_end);
+#endif
+#endif /* HAIFA */
+
/* Create reg_map to hold substitutions for replaceable giv regs. */
reg_map = (rtx *) alloca (max_reg_before_loop * sizeof (rtx));
bzero ((char *) reg_map, max_reg_before_loop * sizeof (rtx));
long as init_insn doesn't use the biv itself.
March 14, 1989 -- self@bayes.arc.nasa.gov */
- if ((uid_luid[regno_last_uid[bl->regno]] < INSN_LUID (loop_end)
+ if ((uid_luid[REGNO_LAST_UID (bl->regno)] < INSN_LUID (loop_end)
&& bl->init_insn
&& INSN_UID (bl->init_insn) < max_uid_for_loop
- && uid_luid[regno_first_uid[bl->regno]] >= INSN_LUID (bl->init_insn)
+ && uid_luid[REGNO_FIRST_UID (bl->regno)] >= INSN_LUID (bl->init_insn)
#ifdef HAVE_decrement_and_branch_until_zero
&& ! bl->nonneg
#endif
bl->regno);
fprintf (loop_dump_stream,
"First use: insn %d, last use: insn %d.\n",
- regno_first_uid[bl->regno],
- regno_last_uid[bl->regno]);
+ REGNO_FIRST_UID (bl->regno),
+ REGNO_LAST_UID (bl->regno));
}
}
unchanged (recompute it from the biv each time it is used).
This decision can be made independently for each giv. */
- /* ??? Perhaps attempt to guess whether autoincrement will handle
- some of the new add insns; if so, can increase BENEFIT
- (undo the subtraction of add_cost that was done above). */
+#ifdef AUTO_INC_DEC
+ /* Attempt to guess whether autoincrement will handle some of the
+ new add insns; if so, increase BENEFIT (undo the subtraction of
+ add_cost that was done above). */
+ if (v->giv_type == DEST_ADDR
+ && GET_CODE (v->mult_val) == CONST_INT)
+ {
+#if defined (HAVE_POST_INCREMENT) || defined (HAVE_PRE_INCREMENT)
+ if (INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
+ benefit += add_cost * bl->biv_count;
+#endif
+#if defined (HAVE_POST_DECREMENT) || defined (HAVE_PRE_DECREMENT)
+ if (-INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
+ benefit += add_cost * bl->biv_count;
+#endif
+ }
+#endif
/* If an insn is not to be strength reduced, then set its ignore
flag, and clear all_reduced. */
of such giv's whether or not we know they are used after the loop
exit. */
- if (v->lifetime * threshold * benefit < insn_count
- && ! bl->reversed)
+ if ( ! flag_reduce_all_givs && v->lifetime * threshold * benefit < insn_count
+ && ! bl->reversed )
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
struct induction *tv;
if (! v->ignore && v->same == 0)
{
+ int auto_inc_opt = 0;
+
v->new_reg = gen_reg_rtx (v->mode);
- /* For each place where the biv is incremented,
- add an insn to increment the new, reduced reg for the giv. */
+#ifdef AUTO_INC_DEC
+ /* If the target has auto-increment addressing modes, and
+ this is an address giv, then try to put the increment
+ immediately after its use, so that flow can create an
+ auto-increment addressing mode. */
+ if (v->giv_type == DEST_ADDR && bl->biv_count == 1
+ && bl->biv->always_executed && ! bl->biv->maybe_multiple
+ /* We don't handle reversed biv's because bl->biv->insn
+ does not have a valid INSN_LUID. */
+ && ! bl->reversed
+ && v->always_executed && ! v->maybe_multiple)
+ {
+ /* If other giv's have been combined with this one, then
+ this will work only if all uses of the other giv's occur
+ before this giv's insn. This is difficult to check.
+
+ We simplify this by looking for the common case where
+ there is one DEST_REG giv, and this giv's insn is the
+ last use of the dest_reg of that DEST_REG giv. If the
+ the increment occurs after the address giv, then we can
+ perform the optimization. (Otherwise, the increment
+ would have to go before other_giv, and we would not be
+ able to combine it with the address giv to get an
+ auto-inc address.) */
+ if (v->combined_with)
+ {
+ struct induction *other_giv = 0;
+
+ for (tv = bl->giv; tv; tv = tv->next_iv)
+ if (tv->same == v)
+ {
+ if (other_giv)
+ break;
+ else
+ other_giv = tv;
+ }
+ if (! tv && other_giv
+ && REGNO (other_giv->dest_reg) < max_reg_before_loop
+ && (REGNO_LAST_UID (REGNO (other_giv->dest_reg))
+ == INSN_UID (v->insn))
+ && INSN_LUID (v->insn) < INSN_LUID (bl->biv->insn))
+ auto_inc_opt = 1;
+ }
+ /* Check for case where increment is before the the address
+ giv. */
+ else if (INSN_LUID (v->insn) > INSN_LUID (bl->biv->insn))
+ auto_inc_opt = -1;
+ else
+ auto_inc_opt = 1;
+
+#ifdef HAVE_cc0
+ {
+ rtx prev;
+
+ /* We can't put an insn immediately after one setting
+ cc0, or immediately before one using cc0. */
+ if ((auto_inc_opt == 1 && sets_cc0_p (PATTERN (v->insn)))
+ || (auto_inc_opt == -1
+ && (prev = prev_nonnote_insn (v->insn)) != 0
+ && GET_RTX_CLASS (GET_CODE (prev)) == 'i'
+ && sets_cc0_p (PATTERN (prev))))
+ auto_inc_opt = 0;
+ }
+#endif
+
+ if (auto_inc_opt)
+ v->auto_inc_opt = 1;
+ }
+#endif
+
+ /* For each place where the biv is incremented, add an insn
+ to increment the new, reduced reg for the giv. */
for (tv = bl->biv; tv; tv = tv->next_iv)
{
+ rtx insert_before;
+
+ if (! auto_inc_opt)
+ insert_before = tv->insn;
+ else if (auto_inc_opt == 1)
+ insert_before = NEXT_INSN (v->insn);
+ else
+ insert_before = v->insn;
+
if (tv->mult_val == const1_rtx)
emit_iv_add_mult (tv->add_val, v->mult_val,
- v->new_reg, v->new_reg, tv->insn);
+ v->new_reg, v->new_reg, insert_before);
else /* tv->mult_val == const0_rtx */
/* A multiply is acceptable here
since this is presumed to be seldom executed. */
emit_iv_add_mult (tv->add_val, v->mult_val,
- v->add_val, v->new_reg, tv->insn);
+ v->add_val, v->new_reg, insert_before);
}
/* Add code at loop start to initialize giv's reduced reg. */
continue;
if (v->giv_type == DEST_REG
- && regno_first_uid[REGNO (v->dest_reg)] == INSN_UID (v->insn))
+ && REGNO_FIRST_UID (REGNO (v->dest_reg)) == INSN_UID (v->insn))
{
struct induction *v1;
for (v1 = bl->giv; v1; v1 = v1->next_iv)
- if (regno_last_uid[REGNO (v->dest_reg)] == INSN_UID (v1->insn))
+ if (REGNO_LAST_UID (REGNO (v->dest_reg)) == INSN_UID (v1->insn))
v->maybe_dead = 1;
}
loop to ensure that it will always be executed no matter
how the loop exits. Otherwise, emit the insn after the loop,
since this is slightly more efficient. */
- if (loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]])
+ if (loop_number_exit_count[uid_loop_num[INSN_UID (loop_start)]])
insert_before = loop_start;
else
insert_before = end_insert_before;
or otherwise drop straight in, based on this test, then
we might want to rewrite it also. This way some later
pass has more hope of removing the initialization of this
- biv entirely. */
+ biv entirely. */
/* If final_value != 0, then the biv may be used after loop end
and we must emit an insn to set it just in case.
Reversed bivs already have an insn after the loop setting their
value, so we don't need another one. We can't calculate the
- proper final value for such a biv here anyways. */
+ proper final value for such a biv here anyways. */
if (final_value != 0 && ! bl->reversed)
{
rtx insert_before;
loop to ensure that it will always be executed no matter
how the loop exits. Otherwise, emit the insn after the
loop, since this is slightly more efficient. */
- if (loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]])
+ if (loop_number_exit_count[uid_loop_num[INSN_UID (loop_start)]])
insert_before = loop_start;
else
insert_before = end_insert_before;
if (flag_unroll_loops)
unroll_loop (loop_end, insn_count, loop_start, end_insert_before, 1);
+#ifdef HAIFA
+ /* instrument the loop with bct insn */
+#ifdef HAVE_decrement_and_branch_on_count
+ if (HAVE_decrement_and_branch_on_count)
+ insert_bct (loop_start, loop_end);
+#endif
+#endif /* HAIFA */
+
if (loop_dump_stream)
fprintf (loop_dump_stream, "\n");
}
/* Don't use call-clobbered registers across a call which clobbers it. On
some machines, don't use any hard registers at all. */
if (REGNO (x) < FIRST_PSEUDO_REGISTER
-#ifndef SMALL_REGISTER_CLASSES
- && call_used_regs[REGNO (x)] && call_seen
-#endif
- )
+ && (SMALL_REGISTER_CLASSES
+ || (call_used_regs[REGNO (x)] && call_seen)))
return 0;
/* Don't use registers that have been clobbered before the start of the
v->mem_mode = GET_MODE (x);
}
- return;
}
+ return;
+
+ default:
+ break;
}
/* Recursively scan the subexpressions for other mem refs. */
v->add_val = inc_val;
v->mode = GET_MODE (dest_reg);
v->always_computable = ! not_every_iteration;
+ v->always_executed = ! not_every_iteration;
v->maybe_multiple = maybe_multiple;
/* Add this to the reg's iv_class, creating a class
v->new_reg = 0;
v->final_value = 0;
v->same_insn = 0;
+ v->auto_inc_opt = 0;
+ v->unrolled = 0;
+ v->shared = 0;
/* The v->always_computable field is used in update_giv_derive, to
determine whether a giv can be used to derive another giv. For a
else
v->always_computable = ! not_every_iteration;
+ v->always_executed = ! not_every_iteration;
+
if (type == DEST_ADDR)
{
v->mode = GET_MODE (*location);
{
v->mode = GET_MODE (SET_DEST (set));
- v->lifetime = (uid_luid[regno_last_uid[REGNO (dest_reg)]]
- - uid_luid[regno_first_uid[REGNO (dest_reg)]]);
+ v->lifetime = (uid_luid[REGNO_LAST_UID (REGNO (dest_reg))]
+ - uid_luid[REGNO_FIRST_UID (REGNO (dest_reg))]);
v->times_used = n_times_used[REGNO (dest_reg)];
/* If the lifetime is zero, it means that this register is
really a dead store. So mark this as a giv that can be
- ignored. This will not prevent the biv from being eliminated. */
+ ignored. This will not prevent the biv from being eliminated. */
if (v->lifetime == 0)
v->ignore = 1;
- the giv is not used outside the loop
- no assignments to the biv occur during the giv's lifetime. */
- if (regno_first_uid[REGNO (dest_reg)] == INSN_UID (insn)
+ if (REGNO_FIRST_UID (REGNO (dest_reg)) == INSN_UID (insn)
/* Previous line always fails if INSN was moved by loop opt. */
- && uid_luid[regno_last_uid[REGNO (dest_reg)]] < INSN_LUID (loop_end)
+ && uid_luid[REGNO_LAST_UID (REGNO (dest_reg))] < INSN_LUID (loop_end)
&& (! not_every_iteration
|| last_use_this_basic_block (dest_reg, insn)))
{
{
if (INSN_UID (b->insn) >= max_uid_for_loop
|| ((uid_luid[INSN_UID (b->insn)]
- >= uid_luid[regno_first_uid[REGNO (dest_reg)]])
+ >= uid_luid[REGNO_FIRST_UID (REGNO (dest_reg))])
&& (uid_luid[INSN_UID (b->insn)]
- <= uid_luid[regno_last_uid[REGNO (dest_reg)]])))
+ <= uid_luid[REGNO_LAST_UID (REGNO (dest_reg))])))
{
v->replaceable = 0;
v->not_replaceable = 1;
}
}
- /* Check each insn between the first and last use of the giv,
- and fail if any of them are branches that jump to a named label
- outside this range, but still inside the loop. This catches
- cases of spaghetti code where the execution order of insns
- is not linear, and hence the above test fails. For example,
- in the following code, j is not replaceable:
- for (i = 0; i < 100; ) {
- L0: j = 4*i; goto L1;
- L2: k = j; goto L3;
- L1: i++; goto L2;
- L3: ; }
- printf ("k = %d\n", k); }
- This test is conservative, but this test succeeds rarely enough
- that it isn't a problem. See also check_final_value below. */
-
+ /* If there are any backwards branches that go from after the
+ biv update to before it, then this giv is not replaceable. */
if (v->replaceable)
- for (p = insn;
- INSN_UID (p) >= max_uid_for_loop
- || INSN_LUID (p) < uid_luid[regno_last_uid[REGNO (dest_reg)]];
- p = NEXT_INSN (p))
- {
- if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p)
- && LABEL_NAME (JUMP_LABEL (p))
- && ((INSN_LUID (JUMP_LABEL (p)) > INSN_LUID (loop_start)
- && (INSN_LUID (JUMP_LABEL (p))
- < uid_luid[regno_first_uid[REGNO (dest_reg)]]))
- || (INSN_LUID (JUMP_LABEL (p)) < INSN_LUID (loop_end)
- && (INSN_LUID (JUMP_LABEL (p))
- > uid_luid[regno_last_uid[REGNO (dest_reg)]]))))
- {
- v->replaceable = 0;
- v->not_replaceable = 1;
-
- if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "Found branch outside giv lifetime.\n");
-
- break;
- }
- }
+ for (b = bl->biv; b; b = b->next_iv)
+ if (back_branch_in_range_p (b->insn, loop_start, loop_end))
+ {
+ v->replaceable = 0;
+ v->not_replaceable = 1;
+ break;
+ }
}
else
{
break;
}
}
- else if (GET_CODE (PATTERN (p)) == SET
- && SET_DEST (PATTERN (p)) == v->src_reg)
+ else if (reg_set_p (v->src_reg, PATTERN (p)))
biv_increment_seen = 1;
else if (reg_mentioned_p (v->dest_reg, PATTERN (p)))
last_giv_use = p;
if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p)
&& LABEL_NAME (JUMP_LABEL (p))
- && ((INSN_LUID (JUMP_LABEL (p)) < INSN_LUID (v->insn)
- && INSN_LUID (JUMP_LABEL (p)) > INSN_LUID (loop_start))
+ && ((INSN_UID (JUMP_LABEL (p)) >= max_uid_for_loop)
+ || (INSN_UID (v->insn) >= max_uid_for_loop)
+ || (INSN_UID (last_giv_use) >= max_uid_for_loop)
+ || (INSN_LUID (JUMP_LABEL (p)) < INSN_LUID (v->insn)
+ && INSN_LUID (JUMP_LABEL (p)) > INSN_LUID (loop_start))
|| (INSN_LUID (JUMP_LABEL (p)) > INSN_LUID (last_giv_use)
&& INSN_LUID (JUMP_LABEL (p)) < INSN_LUID (loop_end))))
{
if (SUBREG_PROMOTED_VAR_P (x))
return basic_induction_var (SUBREG_REG (x), GET_MODE (SUBREG_REG (x)),
dest_reg, p, inc_val, mult_val);
+ return 0;
case REG:
/* If this register is assigned in the previous insn, look at its
: GET_MODE (SET_SRC (set))),
dest_reg, insn,
inc_val, mult_val);
- /* ... fall through ... */
+ /* ... fall through ... */
/* Can accept constant setting of biv only when inside inner most loop.
Otherwise, a biv of an inner loop may be incorrectly recognized
case CONST_INT:
case USE:
/* Both invariant. Only valid if sum is machine operand.
- First strip off possible USE on first operand. */
+ First strip off possible USE on the operands. */
if (GET_CODE (arg0) == USE)
arg0 = XEXP (arg0, 0);
+ if (GET_CODE (arg1) == USE)
+ arg1 = XEXP (arg1, 0);
+
tem = 0;
if (CONSTANT_P (arg0) && GET_CODE (arg1) == CONST_INT)
{
if (GET_CODE (tem) != CONST_INT)
tem = gen_rtx (USE, mode, tem);
}
+ else
+ {
+ /* Adding two invariants must result in an invariant,
+ so enclose addition operation inside a USE and
+ return it. */
+ tem = gen_rtx (USE, mode, gen_rtx (PLUS, mode, arg0, arg1));
+ }
return tem;
benefit);
case MINUS:
- /* Handle "a - b" as "a + b * (-1)". */
+ /* Handle "a - b" as "a + b * (-1)". */
return simplify_giv_expr (gen_rtx (PLUS, mode,
XEXP (x, 0),
gen_rtx (MULT, mode,
return GEN_INT (INTVAL (arg0) * INTVAL (arg1));
case USE:
- /* invar * invar. Not giv. */
+ /* invar * invar. Not giv. */
return 0;
case MULT:
tem = gen_rtx (MINUS, mode, tem, v->derive_adjustment);
return simplify_giv_expr (tem, benefit);
}
+
+ default:
+ break;
}
/* Fall through to general case. */
return 0;
}
\f
+#ifdef GIV_SORT_CRITERION
+/* Compare two givs and sort the most desirable one for combinations first.
+ This is used only in one qsort call below. */
+
+static int
+giv_sort (x, y)
+ struct induction **x, **y;
+{
+ GIV_SORT_CRITERION (*x, *y);
+
+ return 0;
+}
+#endif
+
/* Check all pairs of givs for iv_class BL and see if any can be combined with
any other. If so, point SAME to the giv combined with and set NEW_REG to
be an expression (in terms of the other giv's DEST_REG) equivalent to the
combine_givs (bl)
struct iv_class *bl;
{
- struct induction *g1, *g2;
- int pass;
+ struct induction *g1, *g2, **giv_array, *temp_iv;
+ int i, j, giv_count, pass;
+ /* Count givs, because bl->giv_count is incorrect here. */
+ giv_count = 0;
for (g1 = bl->giv; g1; g1 = g1->next_iv)
- for (pass = 0; pass <= 1; pass++)
- for (g2 = bl->giv; g2; g2 = g2->next_iv)
- if (g1 != g2
- /* First try to combine with replaceable givs, then all givs. */
- && (g1->replaceable || pass == 1)
- /* If either has already been combined or is to be ignored, can't
- combine. */
- && ! g1->ignore && ! g2->ignore && ! g1->same && ! g2->same
- /* If something has been based on G2, G2 cannot itself be based
- on something else. */
- && ! g2->combined_with
- && combine_givs_p (g1, g2))
+ giv_count++;
+
+ giv_array
+ = (struct induction **) alloca (giv_count * sizeof (struct induction *));
+ i = 0;
+ for (g1 = bl->giv; g1; g1 = g1->next_iv)
+ giv_array[i++] = g1;
+
+#ifdef GIV_SORT_CRITERION
+ /* Sort the givs if GIV_SORT_CRITERION is defined.
+ This is usually defined for processors which lack
+ negative register offsets so more givs may be combined. */
+
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream, "%d givs counted, sorting...\n", giv_count);
+
+ qsort (giv_array, giv_count, sizeof (struct induction *), giv_sort);
+#endif
+
+ for (i = 0; i < giv_count; i++)
+ {
+ g1 = giv_array[i];
+ for (pass = 0; pass <= 1; pass++)
+ for (j = 0; j < giv_count; j++)
{
- /* g2->new_reg set by `combine_givs_p' */
- g2->same = g1;
- g1->combined_with = 1;
- g1->benefit += g2->benefit;
- /* ??? The new final_[bg]iv_value code does a much better job
- of finding replaceable giv's, and hence this code may no
- longer be necessary. */
- if (! g2->replaceable && REG_USERVAR_P (g2->dest_reg))
- g1->benefit -= copy_cost;
- g1->lifetime += g2->lifetime;
- g1->times_used += g2->times_used;
-
- if (loop_dump_stream)
- fprintf (loop_dump_stream, "giv at %d combined with giv at %d\n",
- INSN_UID (g2->insn), INSN_UID (g1->insn));
+ g2 = giv_array[j];
+ if (g1 != g2
+ /* First try to combine with replaceable givs, then all givs. */
+ && (g1->replaceable || pass == 1)
+ /* If either has already been combined or is to be ignored, can't
+ combine. */
+ && ! g1->ignore && ! g2->ignore && ! g1->same && ! g2->same
+ /* If something has been based on G2, G2 cannot itself be based
+ on something else. */
+ && ! g2->combined_with
+ && combine_givs_p (g1, g2))
+ {
+ /* g2->new_reg set by `combine_givs_p' */
+ g2->same = g1;
+ g1->combined_with = 1;
+
+ /* If one of these givs is a DEST_REG that was only used
+ once, by the other giv, this is actually a single use.
+ The DEST_REG has the correct cost, while the other giv
+ counts the REG use too often. */
+ if (g2->giv_type == DEST_REG
+ && n_times_used[REGNO (g2->dest_reg)] == 1
+ && reg_mentioned_p (g2->dest_reg, PATTERN (g1->insn)))
+ g1->benefit = g2->benefit;
+ else if (g1->giv_type != DEST_REG
+ || n_times_used[REGNO (g1->dest_reg)] != 1
+ || ! reg_mentioned_p (g1->dest_reg,
+ PATTERN (g2->insn)))
+ {
+ g1->benefit += g2->benefit;
+ g1->times_used += g2->times_used;
+ }
+ /* ??? The new final_[bg]iv_value code does a much better job
+ of finding replaceable giv's, and hence this code may no
+ longer be necessary. */
+ if (! g2->replaceable && REG_USERVAR_P (g2->dest_reg))
+ g1->benefit -= copy_cost;
+ g1->lifetime += g2->lifetime;
+
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream, "giv at %d combined with giv at %d\n",
+ INSN_UID (g2->insn), INSN_UID (g1->insn));
+ }
}
+ }
}
\f
/* EMIT code before INSERT_BEFORE to set REG = B * M + A. */
a = copy_rtx (a);
b = copy_rtx (b);
- /* Increase the lifetime of any invariants moved further in code. */
+ /* Increase the lifetime of any invariants moved further in code. */
update_reg_last_use (a, insert_before);
update_reg_last_use (b, insert_before);
update_reg_last_use (m, insert_before);
end_sequence ();
emit_insn_before (seq, insert_before);
+
+ record_base_value (REGNO (reg), b);
}
\f
/* Test whether A * B can be computed without
char *storage = (char *) obstack_alloc (&temp_obstack, 0);
int win = 1;
- /* If only one is constant, make it B. */
+ /* If only one is constant, make it B. */
if (GET_CODE (a) == CONST_INT)
tmp = a, a = b, b = tmp;
if (GET_CODE (bl->initial_value) == CONST_INT
&& INTVAL (bl->initial_value) > 0
- && (INTVAL (bl->initial_value) %
- (-INTVAL (bl->biv->add_val))) == 0)
+ && (INTVAL (bl->initial_value)
+ % (-INTVAL (bl->biv->add_val))) == 0)
{
/* register always nonnegative, add REG_NOTE to branch */
REG_NOTES (PREV_INSN (loop_end))
all memory references have non-overlapping addresses
(obviously true if only one write)
allow 2 insns for the compare/jump at the end of the loop. */
+ /* Also, we must avoid any instructions which use both the reversed
+ biv and another biv. Such instructions will fail if the loop is
+ reversed. We meet this condition by requiring that either
+ no_use_except_counting is true, or else that there is only
+ one biv. */
int num_nonfixed_reads = 0;
/* 1 if the iteration var is used only to count iterations. */
int no_use_except_counting = 0;
num_nonfixed_reads += count_nonfixed_reads (PATTERN (p));
if (bl->giv_count == 0
- && ! loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]])
+ && ! loop_number_exit_count[uid_loop_num[INSN_UID (loop_start)]])
{
rtx bivreg = regno_reg_rtx[bl->regno];
&& !loop_has_volatile
&& reversible_mem_store
&& (no_use_except_counting
- || (bl->giv_count + bl->biv_count + num_mem_sets
- + num_movables + 2 == insn_count)))
+ || ((bl->giv_count + bl->biv_count + num_mem_sets
+ + num_movables + 2 == insn_count)
+ && (bl == loop_iv_list && bl->next == 0))))
{
rtx tem;
fprintf (loop_dump_stream, "Can reverse loop\n");
/* Now check other conditions:
- initial_value must be zero,
- final_value % add_val == 0, so that when reversed, the
- biv will be zero on the last iteration.
+
+ The increment must be a constant and the comparison code
+ must be LT.
This test can probably be improved since +/- 1 in the constant
can be obtained by changing LT to LE and vice versa; this is
confusing. */
- if (comparison && bl->initial_value == const0_rtx
+ if (comparison
&& GET_CODE (XEXP (comparison, 1)) == CONST_INT
/* LE gets turned into LT */
- && GET_CODE (comparison) == LT
- && (INTVAL (XEXP (comparison, 1))
- % INTVAL (bl->biv->add_val)) == 0)
+ && GET_CODE (comparison) == LT)
{
+ HOST_WIDE_INT add_val, comparison_val;
+ rtx initial_value;
+
+ add_val = INTVAL (bl->biv->add_val);
+ comparison_val = INTVAL (XEXP (comparison, 1));
+ initial_value = bl->initial_value;
+
+ /* Normalize the initial value if it has no other use
+ except as a counter. This will allow a few more loops
+ to be reversed. */
+ if (no_use_except_counting)
+ {
+ comparison_val = comparison_val - INTVAL (bl->initial_value);
+ initial_value = const0_rtx;
+ }
+
+ /* If the initial value is not zero, or if the comparison
+ value is not an exact multiple of the increment, then we
+ can not reverse this loop. */
+ if (initial_value != const0_rtx
+ || (comparison_val % add_val) != 0)
+ return 0;
+
+ /* Reset these in case we normalized the initial value
+ and comparison value above. */
+ bl->initial_value = initial_value;
+ XEXP (comparison, 1) = GEN_INT (comparison_val);
+
/* Register will always be nonnegative, with value
0 on last iteration if loop reversed */
/* Save some info needed to produce the new insns. */
reg = bl->biv->dest_reg;
jump_label = XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 1);
+ if (jump_label == pc_rtx)
+ jump_label = XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 2);
new_add_val = GEN_INT (- INTVAL (bl->biv->add_val));
final_value = XEXP (comparison, 1);
/* Emit an insn after the end of the loop to set the biv's
proper exit value if it is used anywhere outside the loop. */
- if ((regno_last_uid[bl->regno]
+ if ((REGNO_LAST_UID (bl->regno)
!= INSN_UID (PREV_INSN (PREV_INSN (loop_end))))
|| ! bl->init_insn
- || regno_first_uid[bl->regno] != INSN_UID (bl->init_insn))
+ || REGNO_FIRST_UID (bl->regno) != INSN_UID (bl->init_insn))
emit_insn_after (gen_move_insn (reg, final_value),
loop_end);
{
JUMP_LABEL (tem) = XEXP (jump_label, 0);
- /* Increment of LABEL_NUSES done above. */
+ /* Increment of LABEL_NUSES done above. */
/* Register is now always nonnegative,
so add REG_NONNEG note to the branch. */
REG_NOTES (tem) = gen_rtx (EXPR_LIST, REG_NONNEG, NULL_RTX,
{
/* Can replace with any giv that was reduced and
that has (MULT_VAL != 0) and (ADD_VAL == 0).
- Require a constant for MULT_VAL, so we know it's nonzero. */
+ Require a constant for MULT_VAL, so we know it's nonzero.
+ ??? We disable this optimization to avoid potential
+ overflows. */
for (v = bl->giv; v; v = v->next_iv)
if (CONSTANT_P (v->mult_val) && v->mult_val != const0_rtx
&& v->add_val == const0_rtx
&& ! v->ignore && ! v->maybe_dead && v->always_computable
- && v->mode == mode)
+ && v->mode == mode
+ && 0)
{
+ /* If the giv V had the auto-inc address optimization applied
+ to it, and INSN occurs between the giv insn and the biv
+ insn, then we must adjust the value used here.
+ This is rare, so we don't bother to do so. */
+ if (v->auto_inc_opt
+ && ((INSN_LUID (v->insn) < INSN_LUID (insn)
+ && INSN_LUID (insn) < INSN_LUID (bl->biv->insn))
+ || (INSN_LUID (v->insn) > INSN_LUID (insn)
+ && INSN_LUID (insn) > INSN_LUID (bl->biv->insn))))
+ continue;
+
if (! eliminate_p)
return 1;
/* Look for a giv with (MULT_VAL != 0) and (ADD_VAL != 0);
replace test insn with a compare insn (cmp REDUCED_GIV ADD_VAL).
- Require a constant for MULT_VAL, so we know it's nonzero. */
+ Require a constant for MULT_VAL, so we know it's nonzero.
+ ??? Do this only if ADD_VAL is a pointer to avoid a potential
+ overflow problem. */
for (v = bl->giv; v; v = v->next_iv)
if (CONSTANT_P (v->mult_val) && v->mult_val != const0_rtx
&& ! v->ignore && ! v->maybe_dead && v->always_computable
- && v->mode == mode)
+ && v->mode == mode
+ && (GET_CODE (v->add_val) == SYMBOL_REF
+ || GET_CODE (v->add_val) == LABEL_REF
+ || GET_CODE (v->add_val) == CONST
+ || (GET_CODE (v->add_val) == REG
+ && REGNO_POINTER_FLAG (REGNO (v->add_val)))))
{
+ /* If the giv V had the auto-inc address optimization applied
+ to it, and INSN occurs between the giv insn and the biv
+ insn, then we must adjust the value used here.
+ This is rare, so we don't bother to do so. */
+ if (v->auto_inc_opt
+ && ((INSN_LUID (v->insn) < INSN_LUID (insn)
+ && INSN_LUID (insn) < INSN_LUID (bl->biv->insn))
+ || (INSN_LUID (v->insn) > INSN_LUID (insn)
+ && INSN_LUID (insn) > INSN_LUID (bl->biv->insn))))
+ continue;
+
if (! eliminate_p)
return 1;
emit_insn_before (gen_move_insn (tem, copy_rtx (v->add_val)),
where);
- if (validate_change (insn, &SET_SRC (PATTERN (insn)),
- gen_rtx (COMPARE, VOIDmode,
- v->new_reg, tem), 0))
+ /* Substitute the new register for its invariant value in
+ the compare expression. */
+ XEXP (new, (INTVAL (v->mult_val) < 0) ? 0 : 1) = tem;
+ if (validate_change (insn, &SET_SRC (PATTERN (insn)), new, 0))
return 1;
}
}
for (v = bl->giv; v; v = v->next_iv)
if (CONSTANT_P (v->mult_val) && INTVAL (v->mult_val) > 0
- && CONSTANT_P (v->add_val)
+ && (GET_CODE (v->add_val) == SYMBOL_REF
+ || GET_CODE (v->add_val) == LABEL_REF
+ || GET_CODE (v->add_val) == CONST
+ || (GET_CODE (v->add_val) == REG
+ && REGNO_POINTER_FLAG (REGNO (v->add_val))))
&& ! v->ignore && ! v->maybe_dead && v->always_computable
&& v->mode == mode)
{
+ /* If the giv V had the auto-inc address optimization applied
+ to it, and INSN occurs between the giv insn and the biv
+ insn, then we must adjust the value used here.
+ This is rare, so we don't bother to do so. */
+ if (v->auto_inc_opt
+ && ((INSN_LUID (v->insn) < INSN_LUID (insn)
+ && INSN_LUID (insn) < INSN_LUID (bl->biv->insn))
+ || (INSN_LUID (v->insn) > INSN_LUID (insn)
+ && INSN_LUID (insn) > INSN_LUID (bl->biv->insn))))
+ continue;
+
if (! eliminate_p)
return 1;
}
/* Look for giv with positive constant mult_val and nonconst add_val.
- Insert insns to calculate new compare value. */
+ Insert insns to calculate new compare value.
+ ??? Turn this off due to possible overflow. */
for (v = bl->giv; v; v = v->next_iv)
if (CONSTANT_P (v->mult_val) && INTVAL (v->mult_val) > 0
&& ! v->ignore && ! v->maybe_dead && v->always_computable
- && v->mode == mode)
+ && v->mode == mode
+ && 0)
{
rtx tem;
+ /* If the giv V had the auto-inc address optimization applied
+ to it, and INSN occurs between the giv insn and the biv
+ insn, then we must adjust the value used here.
+ This is rare, so we don't bother to do so. */
+ if (v->auto_inc_opt
+ && ((INSN_LUID (v->insn) < INSN_LUID (insn)
+ && INSN_LUID (insn) < INSN_LUID (bl->biv->insn))
+ || (INSN_LUID (v->insn) > INSN_LUID (insn)
+ && INSN_LUID (insn) > INSN_LUID (bl->biv->insn))))
+ continue;
+
if (! eliminate_p)
return 1;
if (invariant_p (arg) == 1)
{
/* Look for giv with constant positive mult_val and nonconst
- add_val. Insert insns to compute new compare value. */
+ add_val. Insert insns to compute new compare value.
+ ??? Turn this off due to possible overflow. */
for (v = bl->giv; v; v = v->next_iv)
if (CONSTANT_P (v->mult_val) && INTVAL (v->mult_val) > 0
&& ! v->ignore && ! v->maybe_dead && v->always_computable
- && v->mode == mode)
+ && v->mode == mode
+ && 0)
{
rtx tem;
+ /* If the giv V had the auto-inc address optimization applied
+ to it, and INSN occurs between the giv insn and the biv
+ insn, then we must adjust the value used here.
+ This is rare, so we don't bother to do so. */
+ if (v->auto_inc_opt
+ && ((INSN_LUID (v->insn) < INSN_LUID (insn)
+ && INSN_LUID (insn) < INSN_LUID (bl->biv->insn))
+ || (INSN_LUID (v->insn) > INSN_LUID (insn)
+ && INSN_LUID (insn) > INSN_LUID (bl->biv->insn))))
+ continue;
+
if (! eliminate_p)
return 1;
&& rtx_equal_p (tv->add_val, v->add_val)
&& tv->mode == mode)
{
+ /* If the giv V had the auto-inc address optimization applied
+ to it, and INSN occurs between the giv insn and the biv
+ insn, then we must adjust the value used here.
+ This is rare, so we don't bother to do so. */
+ if (v->auto_inc_opt
+ && ((INSN_LUID (v->insn) < INSN_LUID (insn)
+ && INSN_LUID (insn) < INSN_LUID (bl->biv->insn))
+ || (INSN_LUID (v->insn) > INSN_LUID (insn)
+ && INSN_LUID (insn) > INSN_LUID (bl->biv->insn))))
+ continue;
+
if (! eliminate_p)
return 1;
if (v->giv_type == DEST_ADDR && v->location == &XEXP (x, 0))
return 1;
break;
+
+ default:
+ break;
}
/* See if any subexpression fails elimination. */
n && GET_CODE (n) != CODE_LABEL && GET_CODE (n) != JUMP_INSN;
n = NEXT_INSN (n))
{
- if (regno_last_uid[REGNO (reg)] == INSN_UID (n))
+ if (REGNO_LAST_UID (REGNO (reg)) == INSN_UID (n))
return 1;
}
return 0;
and hence this insn will never be the last use of x. */
if (GET_CODE (x) == REG && REGNO (x) < max_reg_before_loop
&& INSN_UID (insn) < max_uid_for_loop
- && uid_luid[regno_last_uid[REGNO (x)]] < uid_luid[INSN_UID (insn)])
- regno_last_uid[REGNO (x)] = INSN_UID (insn);
+ && uid_luid[REGNO_LAST_UID (REGNO (x))] < uid_luid[INSN_UID (insn)])
+ REGNO_LAST_UID (REGNO (x)) = INSN_UID (insn);
else
{
register int i, j;
/* If this is setting OP0, get what it sets it to if it looks
relevant. */
- if (SET_DEST (set) == op0)
+ if (rtx_equal_p (SET_DEST (set), op0))
{
enum machine_mode inner_mode = GET_MODE (SET_SRC (set));
if (uconst_val != 0)
code = GTU, op1 = GEN_INT (uconst_val - 1);
break;
+
+ default:
+ break;
}
}
return gen_rtx (swap_condition (GET_CODE (comparison)), VOIDmode,
XEXP (comparison, 1), XEXP (comparison, 0));
}
+
+#ifdef HAIFA
+/* Analyze a loop in order to instrument it with the use of count register.
+ loop_start and loop_end are the first and last insns of the loop.
+ This function works in cooperation with insert_bct ().
+ loop_can_insert_bct[loop_num] is set according to whether the optimization
+ is applicable to the loop. When it is applicable, the following variables
+ are also set:
+ loop_start_value[loop_num]
+ loop_comparison_value[loop_num]
+ loop_increment[loop_num]
+ loop_comparison_code[loop_num] */
+
+static
+void analyze_loop_iterations (loop_start, loop_end)
+ rtx loop_start, loop_end;
+{
+ rtx comparison, comparison_value;
+ rtx iteration_var, initial_value, increment;
+ enum rtx_code comparison_code;
+
+ rtx last_loop_insn;
+ rtx insn;
+ int i;
+
+ /* loop_variable mode */
+ enum machine_mode original_mode;
+
+ /* find the number of the loop */
+ int loop_num = uid_loop_num [INSN_UID (loop_start)];
+
+ /* we change our mind only when we are sure that loop will be instrumented */
+ loop_can_insert_bct[loop_num] = 0;
+
+ /* is the optimization suppressed. */
+ if ( !flag_branch_on_count_reg )
+ return;
+
+ /* make sure that count-reg is not in use */
+ if (loop_used_count_register[loop_num]){
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "analyze_loop_iterations %d: BCT instrumentation failed: count register already in use\n",
+ loop_num);
+ return;
+ }
+
+ /* make sure that the function has no indirect jumps. */
+ if (indirect_jump_in_function){
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "analyze_loop_iterations %d: BCT instrumentation failed: indirect jump in function\n",
+ loop_num);
+ return;
+ }
+
+ /* make sure that the last loop insn is a conditional jump */
+ last_loop_insn = PREV_INSN (loop_end);
+ if (GET_CODE (last_loop_insn) != JUMP_INSN || !condjump_p (last_loop_insn)) {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "analyze_loop_iterations %d: BCT instrumentation failed: invalid jump at loop end\n",
+ loop_num);
+ return;
+ }
+
+ /* First find the iteration variable. If the last insn is a conditional
+ branch, and the insn preceding it tests a register value, make that
+ register the iteration variable. */
+
+ /* We used to use prev_nonnote_insn here, but that fails because it might
+ accidentally get the branch for a contained loop if the branch for this
+ loop was deleted. We can only trust branches immediately before the
+ loop_end. */
+
+ comparison = get_condition_for_loop (last_loop_insn);
+ /* ??? Get_condition may switch position of induction variable and
+ invariant register when it canonicalizes the comparison. */
+
+ if (comparison == 0) {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "analyze_loop_iterations %d: BCT instrumentation failed: comparison not found\n",
+ loop_num);
+ return;
+ }
+
+ comparison_code = GET_CODE (comparison);
+ iteration_var = XEXP (comparison, 0);
+ comparison_value = XEXP (comparison, 1);
+
+ original_mode = GET_MODE (iteration_var);
+ if (GET_MODE_CLASS (original_mode) != MODE_INT
+ || GET_MODE_SIZE (original_mode) != UNITS_PER_WORD) {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "analyze_loop_iterations %d: BCT Instrumentation failed: loop variable not integer\n",
+ loop_num);
+ return;
+ }
+
+ /* get info about loop bounds and increment */
+ iteration_info (iteration_var, &initial_value, &increment,
+ loop_start, loop_end);
+
+ /* make sure that all required loop data were found */
+ if (!(initial_value && increment && comparison_value
+ && invariant_p (comparison_value) && invariant_p (increment)
+ && ! indirect_jump_in_function))
+ {
+ if (loop_dump_stream) {
+ fprintf (loop_dump_stream,
+ "analyze_loop_iterations %d: BCT instrumentation failed because of wrong loop: ", loop_num);
+ if (!(initial_value && increment && comparison_value)) {
+ fprintf (loop_dump_stream, "\tbounds not available: ");
+ if ( ! initial_value )
+ fprintf (loop_dump_stream, "initial ");
+ if ( ! increment )
+ fprintf (loop_dump_stream, "increment ");
+ if ( ! comparison_value )
+ fprintf (loop_dump_stream, "comparison ");
+ fprintf (loop_dump_stream, "\n");
+ }
+ if (!invariant_p (comparison_value) || !invariant_p (increment))
+ fprintf (loop_dump_stream, "\tloop bounds not invariant\n");
+ }
+ return;
+ }
+
+ /* make sure that the increment is constant */
+ if (GET_CODE (increment) != CONST_INT) {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "analyze_loop_iterations %d: instrumentation failed: not arithmetic loop\n",
+ loop_num);
+ return;
+ }
+
+ /* make sure that the loop contains neither function call, nor jump on table.
+ (the count register might be altered by the called function, and might
+ be used for a branch on table). */
+ for (insn = loop_start; insn && insn != loop_end; insn = NEXT_INSN (insn)) {
+ if (GET_CODE (insn) == CALL_INSN){
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "analyze_loop_iterations %d: BCT instrumentation failed: function call in the loop\n",
+ loop_num);
+ return;
+ }
+
+ if (GET_CODE (insn) == JUMP_INSN
+ && (GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC
+ || GET_CODE (PATTERN (insn)) == ADDR_VEC)){
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "analyze_loop_iterations %d: BCT instrumentation failed: computed branch in the loop\n",
+ loop_num);
+ return;
+ }
+ }
+
+ /* At this point, we are sure that the loop can be instrumented with BCT.
+ Some of the loops, however, will not be instrumented - the final decision
+ is taken by insert_bct () */
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "analyze_loop_iterations: loop (luid =%d) can be BCT instrumented.\n",
+ loop_num);
+
+ /* mark all enclosing loops that they cannot use count register */
+ /* ???: In fact, since insert_bct may decide not to instrument this loop,
+ marking here may prevent instrumenting an enclosing loop that could
+ actually be instrumented. But since this is rare, it is safer to mark
+ here in case the order of calling (analyze/insert)_bct would be changed. */
+ for (i=loop_num; i != -1; i = loop_outer_loop[i])
+ loop_used_count_register[i] = 1;
+
+ /* Set data structures which will be used by the instrumentation phase */
+ loop_start_value[loop_num] = initial_value;
+ loop_comparison_value[loop_num] = comparison_value;
+ loop_increment[loop_num] = increment;
+ loop_comparison_code[loop_num] = comparison_code;
+ loop_can_insert_bct[loop_num] = 1;
+}
+
+
+/* instrument loop for insertion of bct instruction. We distinguish between
+ loops with compile-time bounds, to those with run-time bounds. The loop
+ behaviour is analized according to the following characteristics/variables:
+ ; Input variables:
+ ; comparison-value: the value to which the iteration counter is compared.
+ ; initial-value: iteration-counter initial value.
+ ; increment: iteration-counter increment.
+ ; Computed variables:
+ ; increment-direction: the sign of the increment.
+ ; compare-direction: '1' for GT, GTE, '-1' for LT, LTE, '0' for NE.
+ ; range-direction: sign (comparison-value - initial-value)
+ We give up on the following cases:
+ ; loop variable overflow.
+ ; run-time loop bounds with comparison code NE.
+ */
+
+static void
+insert_bct (loop_start, loop_end)
+ rtx loop_start, loop_end;
+{
+ rtx initial_value, comparison_value, increment;
+ enum rtx_code comparison_code;
+
+ int increment_direction, compare_direction;
+ int unsigned_p = 0;
+
+ /* if the loop condition is <= or >=, the number of iteration
+ is 1 more than the range of the bounds of the loop */
+ int add_iteration = 0;
+
+ /* the only machine mode we work with - is the integer of the size that the
+ machine has */
+ enum machine_mode loop_var_mode = SImode;
+
+ int loop_num = uid_loop_num [INSN_UID (loop_start)];
+
+ /* get loop-variables. No need to check that these are valid - already
+ checked in analyze_loop_iterations (). */
+ comparison_code = loop_comparison_code[loop_num];
+ initial_value = loop_start_value[loop_num];
+ comparison_value = loop_comparison_value[loop_num];
+ increment = loop_increment[loop_num];
+
+ /* check analyze_loop_iterations decision for this loop. */
+ if (! loop_can_insert_bct[loop_num]){
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "insert_bct: [%d] - was decided not to instrument by analyze_loop_iterations ()\n",
+ loop_num);
+ return;
+ }
+
+ /* It's impossible to instrument a competely unrolled loop. */
+ if (loop_unroll_factor [loop_num] == -1)
+ return;
+
+ /* make sure that the last loop insn is a conditional jump .
+ This check is repeated from analyze_loop_iterations (),
+ because unrolling might have changed that. */
+ if (GET_CODE (PREV_INSN (loop_end)) != JUMP_INSN
+ || !condjump_p (PREV_INSN (loop_end))) {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "insert_bct: not instrumenting BCT because of invalid branch\n");
+ return;
+ }
+
+ /* fix increment in case loop was unrolled. */
+ if (loop_unroll_factor [loop_num] > 1)
+ increment = GEN_INT ( INTVAL (increment) * loop_unroll_factor [loop_num] );
+
+ /* determine properties and directions of the loop */
+ increment_direction = (INTVAL (increment) > 0) ? 1:-1;
+ switch ( comparison_code ) {
+ case LEU:
+ unsigned_p = 1;
+ /* fallthrough */
+ case LE:
+ compare_direction = 1;
+ add_iteration = 1;
+ break;
+ case GEU:
+ unsigned_p = 1;
+ /* fallthrough */
+ case GE:
+ compare_direction = -1;
+ add_iteration = 1;
+ break;
+ case EQ:
+ /* in this case we cannot know the number of iterations */
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "insert_bct: %d: loop cannot be instrumented: == in condition\n",
+ loop_num);
+ return;
+ case LTU:
+ unsigned_p = 1;
+ /* fallthrough */
+ case LT:
+ compare_direction = 1;
+ break;
+ case GTU:
+ unsigned_p = 1;
+ /* fallthrough */
+ case GT:
+ compare_direction = -1;
+ break;
+ case NE:
+ compare_direction = 0;
+ break;
+ default:
+ abort ();
+ }
+
+
+ /* make sure that the loop does not end by an overflow */
+ if (compare_direction != increment_direction) {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "insert_bct: %d: loop cannot be instrumented: terminated by overflow\n",
+ loop_num);
+ return;
+ }
+
+ /* try to instrument the loop. */
+
+ /* Handle the simpler case, where the bounds are known at compile time. */
+ if (GET_CODE (initial_value) == CONST_INT && GET_CODE (comparison_value) == CONST_INT)
+ {
+ int n_iterations;
+ int increment_value_abs = INTVAL (increment) * increment_direction;
+
+ /* check the relation between compare-val and initial-val */
+ int difference = INTVAL (comparison_value) - INTVAL (initial_value);
+ int range_direction = (difference > 0) ? 1 : -1;
+
+ /* make sure the loop executes enough iterations to gain from BCT */
+ if (difference > -3 && difference < 3) {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "insert_bct: loop %d not BCT instrumented: too small iteration count.\n",
+ loop_num);
+ return;
+ }
+
+ /* make sure that the loop executes at least once */
+ if ((range_direction == 1 && compare_direction == -1)
+ || (range_direction == -1 && compare_direction == 1))
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "insert_bct: loop %d: does not iterate even once. Not instrumenting.\n",
+ loop_num);
+ return;
+ }
+
+ /* make sure that the loop does not end by an overflow (in compile time
+ bounds we must have an additional check for overflow, because here
+ we also support the compare code of 'NE'. */
+ if (comparison_code == NE
+ && increment_direction != range_direction) {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "insert_bct (compile time bounds): %d: loop not instrumented: terminated by overflow\n",
+ loop_num);
+ return;
+ }
+
+ /* Determine the number of iterations by:
+ ;
+ ; compare-val - initial-val + (increment -1) + additional-iteration
+ ; num_iterations = -----------------------------------------------------------------
+ ; increment
+ */
+ difference = (range_direction > 0) ? difference : -difference;
+#if 0
+ fprintf (stderr, "difference is: %d\n", difference); /* @*/
+ fprintf (stderr, "increment_value_abs is: %d\n", increment_value_abs); /* @*/
+ fprintf (stderr, "add_iteration is: %d\n", add_iteration); /* @*/
+ fprintf (stderr, "INTVAL (comparison_value) is: %d\n", INTVAL (comparison_value)); /* @*/
+ fprintf (stderr, "INTVAL (initial_value) is: %d\n", INTVAL (initial_value)); /* @*/
+#endif
+
+ if (increment_value_abs == 0) {
+ fprintf (stderr, "insert_bct: error: increment == 0 !!!\n");
+ abort ();
+ }
+ n_iterations = (difference + increment_value_abs - 1 + add_iteration)
+ / increment_value_abs;
+
+#if 0
+ fprintf (stderr, "number of iterations is: %d\n", n_iterations); /* @*/
+#endif
+ instrument_loop_bct (loop_start, loop_end, GEN_INT (n_iterations));
+
+ /* Done with this loop. */
+ return;
+ }
+
+ /* Handle the more complex case, that the bounds are NOT known at compile time. */
+ /* In this case we generate run_time calculation of the number of iterations */
+
+ /* With runtime bounds, if the compare is of the form '!=' we give up */
+ if (comparison_code == NE) {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "insert_bct: fail for loop %d: runtime bounds with != comparison\n",
+ loop_num);
+ return;
+ }
+
+ else {
+ /* We rely on the existence of run-time guard to ensure that the
+ loop executes at least once. */
+ rtx sequence;
+ rtx iterations_num_reg;
+
+ int increment_value_abs = INTVAL (increment) * increment_direction;
+
+ /* make sure that the increment is a power of two, otherwise (an
+ expensive) divide is needed. */
+ if (exact_log2 (increment_value_abs) == -1)
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "insert_bct: not instrumenting BCT because the increment is not power of 2\n");
+ return;
+ }
+
+ /* compute the number of iterations */
+ start_sequence ();
+ {
+ /* CYGNUS LOCAL: HAIFA bug fix */
+ rtx temp_reg;
+
+ /* Again, the number of iterations is calculated by:
+ ;
+ ; compare-val - initial-val + (increment -1) + additional-iteration
+ ; num_iterations = -----------------------------------------------------------------
+ ; increment
+ */
+ /* ??? Do we have to call copy_rtx here before passing rtx to
+ expand_binop? */
+ if (compare_direction > 0) {
+ /* <, <= :the loop variable is increasing */
+ temp_reg = expand_binop (loop_var_mode, sub_optab, comparison_value,
+ initial_value, NULL_RTX, 0, OPTAB_LIB_WIDEN);
+ }
+ else {
+ temp_reg = expand_binop (loop_var_mode, sub_optab, initial_value,
+ comparison_value, NULL_RTX, 0, OPTAB_LIB_WIDEN);
+ }
+
+ if (increment_value_abs - 1 + add_iteration != 0)
+ temp_reg = expand_binop (loop_var_mode, add_optab, temp_reg,
+ GEN_INT (increment_value_abs - 1 + add_iteration),
+ NULL_RTX, 0, OPTAB_LIB_WIDEN);
+
+ if (increment_value_abs != 1)
+ {
+ /* ??? This will generate an expensive divide instruction for
+ most targets. The original authors apparently expected this
+ to be a shift, since they test for power-of-2 divisors above,
+ but just naively generating a divide instruction will not give
+ a shift. It happens to work for the PowerPC target because
+ the rs6000.md file has a divide pattern that emits shifts.
+ It will probably not work for any other target. */
+ iterations_num_reg = expand_binop (loop_var_mode, sdiv_optab,
+ temp_reg,
+ GEN_INT (increment_value_abs),
+ NULL_RTX, 0, OPTAB_LIB_WIDEN);
+ }
+ else
+ iterations_num_reg = temp_reg;
+ /* END CYGNUS LOCAL: HAIFA bug fix */
+ }
+ sequence = gen_sequence ();
+ end_sequence ();
+ emit_insn_before (sequence, loop_start);
+ instrument_loop_bct (loop_start, loop_end, iterations_num_reg);
+ }
+}
+
+/* instrument loop by inserting a bct in it. This is done in the following way:
+ 1. A new register is created and assigned the hard register number of the count
+ register.
+ 2. In the head of the loop the new variable is initialized by the value passed in the
+ loop_num_iterations parameter.
+ 3. At the end of the loop, comparison of the register with 0 is generated.
+ The created comparison follows the pattern defined for the
+ decrement_and_branch_on_count insn, so this insn will be generated in assembly
+ generation phase.
+ 4. The compare&branch on the old variable is deleted. So, if the loop-variable was
+ not used elsewhere, it will be eliminated by data-flow analisys. */
+
+static void
+instrument_loop_bct (loop_start, loop_end, loop_num_iterations)
+ rtx loop_start, loop_end;
+ rtx loop_num_iterations;
+{
+ rtx temp_reg1, temp_reg2;
+ rtx start_label;
+
+ rtx sequence;
+ enum machine_mode loop_var_mode = SImode;
+
+#ifdef HAVE_decrement_and_branch_on_count
+ if (HAVE_decrement_and_branch_on_count)
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream, "Loop: Inserting BCT\n");
+
+ /* eliminate the check on the old variable */
+ delete_insn (PREV_INSN (loop_end));
+ delete_insn (PREV_INSN (loop_end));
+
+ /* insert the label which will delimit the start of the loop */
+ start_label = gen_label_rtx ();
+ emit_label_after (start_label, loop_start);
+
+ /* insert initialization of the count register into the loop header */
+ start_sequence ();
+ temp_reg1 = gen_reg_rtx (loop_var_mode);
+ emit_insn (gen_move_insn (temp_reg1, loop_num_iterations));
+
+ /* this will be count register */
+ temp_reg2 = gen_rtx (REG, loop_var_mode, COUNT_REGISTER_REGNUM);
+ /* we have to move the value to the count register from an GPR
+ because rtx pointed to by loop_num_iterations could contain
+ expression which cannot be moved into count register */
+ emit_insn (gen_move_insn (temp_reg2, temp_reg1));
+
+ sequence = gen_sequence ();
+ end_sequence ();
+ emit_insn_after (sequence, loop_start);
+
+ /* insert new comparison on the count register instead of the
+ old one, generating the needed BCT pattern (that will be
+ later recognized by assembly generation phase). */
+ emit_jump_insn_before (gen_decrement_and_branch_on_count (temp_reg2, start_label),
+ loop_end);
+ LABEL_NUSES (start_label)++;
+ }
+
+#endif /* HAVE_decrement_and_branch_on_count */
+}
+#endif /* HAIFA */
+
+/* Scan the function and determine whether it has indirect (computed) jumps.
+
+ This is taken mostly from flow.c; similar code exists elsewhere
+ in the compiler. It may be useful to put this into rtlanal.c. */
+static int
+indirect_jump_in_function_p (start)
+ rtx start;
+{
+ rtx insn;
+ int is_indirect_jump = 0;
+
+ for (insn = start; insn; insn = NEXT_INSN (insn))
+ if (computed_jump_p (insn))
+ return 1;
+
+ return 0;
+}
OSDN Git Service
