===================================================================
@@ -62,6 +62,45 @@
#define OUTPUT_LABEL(INDENT_STRING, LABEL_NUMBER) \
printf("%sL%d: ATTRIBUTE_UNUSED_LABEL\n", (INDENT_STRING), (LABEL_NUMBER))
+/* Ways of obtaining an rtx to be tested. */
+enum position_type {
+ /* PATTERN (peep2_next_insn (ARG)). */
+ POS_PEEP2_INSN,
+
+ /* XEXP (BASE, ARG). */
+ POS_XEXP,
+
+ /* XVECEXP (BASE, 0, ARG). */
+ POS_XVECEXP0
+};
+
+/* The position of an rtx relative to X0. Each useful position is
+ represented by exactly one instance of this structure. */
+struct position
+{
+ /* The parent rtx. This is the root position for POS_PEEP2_INSNs. */
+ struct position *base;
+
+ /* A position with the same BASE and TYPE, but with the next value
+ of ARG. */
+ struct position *next;
+
+ /* POS_XEXP positions that use this one as their base. */
+ struct position *xexps;
+
+ /* POS_XVECEXP0 positions that use this one as their base. */
+ struct position *xvecexp0s;
+
+ /* The type of position. */
+ enum position_type type;
+
+ /* The argument to TYPE (shown as ARG in the position_type comments). */
+ int arg;
+
+ /* The depth of this position, with 0 as the root. */
+ int depth;
+};
+
/* A listhead of decision trees. The alternatives to a node are kept
in a doubly-linked list so we can easily add nodes to the proper
place when merging. */
@@ -132,7 +171,7 @@ struct decision
struct decision *afterward; /* Node to test on success,
but failure of successor nodes. */
- const char *position; /* String denoting position in pattern. */
+ struct position *position; /* Position in pattern. */
struct decision_test *tests; /* The tests for this node. */
@@ -170,9 +209,16 @@ #define IS_SPLIT(X) ((X) != RECOG)
/* The line number of the start of the pattern currently being processed. */
static int pattern_lineno;
+
+/* The root position (x0). */
+static struct position root_pos;
+
+/* A list of all POS_PEEP2_INSNs. The entry for insn 0 is the root position,
+ since we are given that instruction's pattern as x0. */
+static struct position *peep2_insn_pos_list = &root_pos;
static struct decision *new_decision
- (const char *, struct decision_head *);
+ (struct position *, struct decision_head *);
static struct decision_test *new_decision_test
(enum decision_type, struct decision_test ***);
static rtx find_operand
@@ -182,7 +228,7 @@ #define IS_SPLIT(X) ((X) != RECOG)
static void validate_pattern
(rtx, rtx, rtx, int);
static struct decision *add_to_sequence
- (rtx, struct decision_head *, const char *, enum routine_type, int);
+ (rtx, struct decision_head *, struct position *, enum routine_type, int);
static int maybe_both_true_2
(struct decision_test *, struct decision_test *);
@@ -210,7 +256,7 @@ #define IS_SPLIT(X) ((X) != RECOG)
(struct decision_head *, struct decision *);
static void change_state
- (const char *, const char *, const char *);
+ (struct position *, struct position *, const char *);
static void print_code
(enum rtx_code);
static void write_afterward
@@ -229,7 +275,7 @@ #define IS_SPLIT(X) ((X) != RECOG)
static void write_tree_1
(struct decision_head *, int, enum routine_type);
static void write_tree
- (struct decision_head *, const char *, enum routine_type, int);
+ (struct decision_head *, struct position *, enum routine_type, int);
static void write_subroutine
(struct decision_head *, enum routine_type);
static void write_subroutines
@@ -253,15 +299,64 @@ #define IS_SPLIT(X) ((X) != RECOG)
extern void debug_decision_list
(struct decision *);
+/* Return a position with the given BASE, TYPE and ARG. NEXT_PTR
+ points to where this position should be stored. */
+
+static struct position *
+next_position (struct position **next_ptr, struct position *base,
+ enum position_type type, int arg)
+{
+ struct position *pos;
+
+ pos = *next_ptr;
+ if (!pos)
+ {
+ pos = XCNEW (struct position);
+ pos->base = base;
+ pos->type = type;
+ pos->arg = arg;
+ pos->depth = base->depth + 1;
+ *next_ptr = pos;
+ }
+ return pos;
+}
+
+/* Compare positions POS1 and POS2 lexicographically. */
+
+static int
+compare_positions (struct position *pos1, struct position *pos2)
+{
+ int diff;
+
+ diff = pos1->depth - pos2->depth;
+ if (diff < 0)
+ do
+ pos2 = pos2->base;
+ while (pos1->depth != pos2->depth);
+ else if (diff > 0)
+ do
+ pos1 = pos1->base;
+ while (pos1->depth != pos2->depth);
+ while (pos1 != pos2)
+ {
+ diff = (int) pos1->type - (int) pos2->type;
+ if (diff == 0)
+ diff = pos1->arg - pos2->arg;
+ pos1 = pos1->base;
+ pos2 = pos2->base;
+ }
+ return diff;
+}
+
/* Create a new node in sequence after LAST. */
static struct decision *
-new_decision (const char *position, struct decision_head *last)
+new_decision (struct position *pos, struct decision_head *last)
{
struct decision *new_decision = XCNEW (struct decision);
new_decision->success = *last;
- new_decision->position = xstrdup (position);
+ new_decision->position = pos;
new_decision->number = next_number++;
last->first = last->last = new_decision;
@@ -636,35 +731,31 @@ validate_pattern (rtx pattern, rtx insn,
LAST is a pointer to the listhead in the previous node in the chain (or
in the calling function, for the first node).
- POSITION is the string representing the current position in the insn.
+ POSITION is the current position in the insn.
INSN_TYPE is the type of insn for which we are emitting code.
A pointer to the final node in the chain is returned. */
static struct decision *
-add_to_sequence (rtx pattern, struct decision_head *last, const char *position,
- enum routine_type insn_type, int top)
+add_to_sequence (rtx pattern, struct decision_head *last,
+ struct position *pos, enum routine_type insn_type, int top)
{
RTX_CODE code;
struct decision *this_decision, *sub;
struct decision_test *test;
struct decision_test **place;
- char *subpos;
+ struct position *subpos, **subpos_ptr;
size_t i;
const char *fmt;
- int depth = strlen (position);
int len;
enum machine_mode mode;
+ enum position_type pos_type;
- if (depth > max_depth)
- max_depth = depth;
+ if (pos->depth > max_depth)
+ max_depth = pos->depth;
- subpos = XNEWVAR (char, depth + 2);
- strcpy (subpos, position);
- subpos[depth + 1] = 0;
-
- sub = this_decision = new_decision (position, last);
+ sub = this_decision = new_decision (pos, last);
place = &this_decision->tests;
restart:
@@ -694,15 +785,15 @@ add_to_sequence (rtx pattern, struct dec
last->first = last->last = NULL;
}
+ subpos_ptr = &peep2_insn_pos_list;
for (i = 0; i < (size_t) XVECLEN (pattern, 0); i++)
{
- /* Which insn we're looking at is represented by A-Z. We don't
- ever use 'A', however; it is always implied. */
-
- subpos[depth] = (i > 0 ? 'A' + i : 0);
+ subpos = next_position (subpos_ptr, &root_pos,
+ POS_PEEP2_INSN, i);
sub = add_to_sequence (XVECEXP (pattern, 0, i),
last, subpos, insn_type, 0);
last = &sub->success;
+ subpos_ptr = &subpos->next;
}
goto ret;
}
@@ -786,12 +877,22 @@ add_to_sequence (rtx pattern, struct dec
if (was_code == MATCH_OPERATOR || was_code == MATCH_PARALLEL)
{
- char base = (was_code == MATCH_OPERATOR ? '0' : 'a');
+ if (was_code == MATCH_OPERATOR)
+ {
+ pos_type = POS_XEXP;
+ subpos_ptr = &pos->xexps;
+ }
+ else
+ {
+ pos_type = POS_XVECEXP0;
+ subpos_ptr = &pos->xvecexp0s;
+ }
for (i = 0; i < (size_t) XVECLEN (pattern, 2); i++)
{
- subpos[depth] = i + base;
+ subpos = next_position (subpos_ptr, pos, pos_type, i);
sub = add_to_sequence (XVECEXP (pattern, 2, i),
&sub->success, subpos, insn_type, 0);
+ subpos_ptr = &subpos->next;
}
}
goto fini;
@@ -806,11 +907,13 @@ add_to_sequence (rtx pattern, struct dec
test = new_decision_test (DT_accept_op, &place);
test->u.opno = XINT (pattern, 0);
+ subpos_ptr = &pos->xvecexp0s;
for (i = 0; i < (size_t) XVECLEN (pattern, 1); i++)
{
- subpos[depth] = i + '0';
+ subpos = next_position (subpos_ptr, pos, POS_XVECEXP0, i);
sub = add_to_sequence (XVECEXP (pattern, 1, i),
&sub->success, subpos, insn_type, 0);
+ subpos_ptr = &subpos->next;
}
goto fini;
@@ -874,24 +977,29 @@ add_to_sequence (rtx pattern, struct dec
}
/* Now test our sub-patterns. */
+ subpos_ptr = &pos->xexps;
for (i = 0; i < (size_t) len; i++)
{
+ subpos = next_position (subpos_ptr, pos, POS_XEXP, i);
switch (fmt[i])
{
case 'e': case 'u':
- subpos[depth] = '0' + i;
sub = add_to_sequence (XEXP (pattern, i), &sub->success,
subpos, insn_type, 0);
break;
case 'E':
{
+ struct position *subpos2, **subpos2_ptr;
int j;
+
+ subpos2_ptr = &pos->xvecexp0s;
for (j = 0; j < XVECLEN (pattern, i); j++)
{
- subpos[depth] = 'a' + j;
+ subpos2 = next_position (subpos2_ptr, pos, POS_XVECEXP0, j);
sub = add_to_sequence (XVECEXP (pattern, i, j),
- &sub->success, subpos, insn_type, 0);
+ &sub->success, subpos2, insn_type, 0);
+ subpos2_ptr = &subpos2->next;
}
break;
}
@@ -905,6 +1013,7 @@ add_to_sequence (rtx pattern, struct dec
default:
gcc_unreachable ();
}
+ subpos_ptr = &subpos->next;
}
fini:
@@ -928,7 +1037,6 @@ add_to_sequence (rtx pattern, struct dec
gcc_assert (this_decision->tests);
ret:
- free (subpos);
return sub;
}
@@ -1094,12 +1202,12 @@ maybe_both_true (struct decision *d1, st
of a node's success nodes (from the loop at the end of this function).
Skip forward until we come to a position that matches.
- Due to the way position strings are constructed, we know that iterating
- forward from the lexically lower position (e.g. "00") will run into
- the lexically higher position (e.g. "1") and not the other way around.
- This saves a bit of effort. */
+ Due to the way positions are constructed, we know that iterating
+ forward from the lexically lower position will run into the lexically
+ higher position and not the other way around. This saves a bit
+ of effort. */
- cmp = strcmp (d1->position, d2->position);
+ cmp = compare_positions (d1->position, d2->position);
if (cmp != 0)
{
gcc_assert (!toplevel);
@@ -1214,7 +1322,7 @@ nodes_identical (struct decision *d1, st
invoked. */
if (d1->success.first
&& d2->success.first
- && strcmp (d1->success.first->position, d2->success.first->position))
+ && d1->success.first->position != d2->success.first->position)
return 0;
return 1;
@@ -1284,7 +1392,7 @@ merge_trees (struct decision_head *oldh,
}
/* Trying to merge bits at different positions isn't possible. */
- gcc_assert (!strcmp (oldh->first->position, addh->first->position));
+ gcc_assert (oldh->first->position == addh->first->position);
for (add = addh->first; add ; add = next)
{
@@ -1543,33 +1651,31 @@ find_afterward (struct decision_head *he
match multiple insns and we try to step past the end of the stream. */
static void
-change_state (const char *oldpos, const char *newpos, const char *indent)
+change_state (struct position *oldpos, struct position *newpos,
+ const char *indent)
{
- int odepth = strlen (oldpos);
- int ndepth = strlen (newpos);
- int depth;
+ while (oldpos->depth > newpos->depth)
+ oldpos = oldpos->base;
- /* Pop up as many levels as necessary. */
- for (depth = odepth; strncmp (oldpos, newpos, depth) != 0; --depth)
- continue;
+ if (oldpos != newpos)
+ switch (newpos->type)
+ {
+ case POS_PEEP2_INSN:
+ printf ("%stem = peep2_next_insn (%d);\n", indent, newpos->arg);
+ printf ("%sx%d = PATTERN (tem);\n", indent, newpos->depth);
+ break;
+
+ case POS_XEXP:
+ change_state (oldpos, newpos->base, indent);
+ printf ("%sx%d = XEXP (x%d, %d);\n",
+ indent, newpos->depth, newpos->depth - 1, newpos->arg);
+ break;
- /* Go down to desired level. */
- while (depth < ndepth)
- {
- /* It's a different insn from the first one. */
- if (ISUPPER (newpos[depth]))
- {
- printf ("%stem = peep2_next_insn (%d);\n",
- indent, newpos[depth] - 'A');
- printf ("%sx%d = PATTERN (tem);\n", indent, depth + 1);
- }
- else if (ISLOWER (newpos[depth]))
+ case POS_XVECEXP0:
+ change_state (oldpos, newpos->base, indent);
printf ("%sx%d = XVECEXP (x%d, 0, %d);\n",
- indent, depth + 1, depth, newpos[depth] - 'a');
- else
- printf ("%sx%d = XEXP (x%d, %c);\n",
- indent, depth + 1, depth, newpos[depth]);
- ++depth;
+ indent, newpos->depth, newpos->depth - 1, newpos->arg);
+ break;
}
}
@@ -1942,12 +2048,13 @@ write_action (struct decision *p, struct
case PEEPHOLE2:
{
- int match_len = 0, i;
+ int match_len = 0;
+ struct position *pos;
- for (i = strlen (p->position) - 1; i >= 0; --i)
- if (ISUPPER (p->position[i]))
+ for (pos = p->position; pos; pos = pos->base)
+ if (pos->type == POS_PEEP2_INSN)
{
- match_len = p->position[i] - 'A';
+ match_len = pos->arg;
break;
}
printf ("%s*_pmatch_len = %d;\n", indent, match_len);
@@ -2089,7 +2196,7 @@ write_tree_1 (struct decision_head *head
position at the node that branched to this node. */
static void
-write_tree (struct decision_head *head, const char *prevpos,
+write_tree (struct decision_head *head, struct position *prevpos,
enum routine_type type, int initial)
{
struct decision *p = head->first;
@@ -2131,10 +2238,8 @@ write_tree (struct decision_head *head,
}
else
{
- int depth = strlen (p->position);
-
change_state (prevpos, p->position, " ");
- write_tree_1 (head, depth, type);
+ write_tree_1 (head, p->position->depth, type);
for (p = head->first; p; p = p->next)
if (p->success.first)
@@ -2190,7 +2295,7 @@ peephole2%s (rtx x0 ATTRIBUTE_UNUSED,\n\
printf (" recog_data.insn = NULL_RTX;\n");
if (head->first)
- write_tree (head, "", type, 1);
+ write_tree (head, &root_pos, type, 1);
else
printf (" goto ret0;\n");
@@ -2287,12 +2392,12 @@ make_insn_sequence (rtx insn, enum routi
struct decision *last;
struct decision_test *test, **place;
struct decision_head head;
- char c_test_pos[2];
+ struct position *c_test_pos, **pos_ptr;
/* We should never see an insn whose C test is false at compile time. */
gcc_assert (truth);
- c_test_pos[0] = '\0';
+ c_test_pos = &root_pos;
if (type == PEEPHOLE2)
{
int i, j;
@@ -2304,19 +2409,20 @@ make_insn_sequence (rtx insn, enum routi
x = rtx_alloc (PARALLEL);
PUT_MODE (x, VOIDmode);
XVEC (x, 0) = rtvec_alloc (XVECLEN (insn, 0));
+ pos_ptr = &peep2_insn_pos_list;
for (i = j = 0; i < XVECLEN (insn, 0); i++)
{
rtx tmp = XVECEXP (insn, 0, i);
if (GET_CODE (tmp) != MATCH_SCRATCH && GET_CODE (tmp) != MATCH_DUP)
{
+ c_test_pos = next_position (pos_ptr, &root_pos,
+ POS_PEEP2_INSN, i);
XVECEXP (x, 0, j) = tmp;
j++;
+ pos_ptr = &c_test_pos->next;
}
}
XVECLEN (x, 0) = j;
-
- c_test_pos[0] = 'A' + j - 1;
- c_test_pos[1] = '\0';
}
else if (XVECLEN (insn, type == RECOG) == 1)
x = XVECEXP (insn, type == RECOG, 0);
@@ -2330,7 +2436,7 @@ make_insn_sequence (rtx insn, enum routi
validate_pattern (x, insn, NULL_RTX, 0);
memset(&head, 0, sizeof(head));
- last = add_to_sequence (x, &head, "", type, 1);
+ last = add_to_sequence (x, &head, &root_pos, type, 1);
/* Find the end of the test chain on the last node. */
for (test = last->tests; test->next; test = test->next)
@@ -2396,7 +2502,8 @@ make_insn_sequence (rtx insn, enum routi
/* Recognize it. */
memset (&clobber_head, 0, sizeof(clobber_head));
- last = add_to_sequence (new_rtx, &clobber_head, "", type, 1);
+ last = add_to_sequence (new_rtx, &clobber_head, &root_pos,
+ type, 1);
/* Find the end of the test chain on the last node. */
for (test = last->tests; test->next; test = test->next)
@@ -2407,7 +2514,7 @@ make_insn_sequence (rtx insn, enum routi
place = &test->next;
if (test->type == DT_accept_op)
{
- last = new_decision ("", &last->success);
+ last = new_decision (&root_pos, &last->success);
place = &last->tests;
}