This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Patch for automaton based pipeline hazard recognizer (part #3).
- To: gcc-patches at gcc dot gnu dot org
- Subject: Patch for automaton based pipeline hazard recognizer (part #3).
- From: Vladimir Makarov <vmakarov at toke dot toronto dot redhat dot com>
- Date: Wed, 31 Jan 2001 15:17:22 -0500
This is the rest of file genautomata.c (please attach it to the 1st
part to get the all file genautomata.c).
--------------------File genautomata.c-------------------------------
/* The page contains code for building alt_states (see comments for
IR) describing all possible insns reservations of an automaton. */
/* Current state being formed for which the current alt_state
refers. */
static struct state *state_being_formed;
/* Current alt_state being formed. */
static struct alt_state *alt_state_being_formed;
/* This recursive function processes `,' and units in reservation
REGEXP for forming alt_states of AUTOMATON. It is believed that
CURR_CYCLE_NUM is start cycle of all reservation REGEXP. */
static int
process_seq_for_forming_states (regexp, automaton, curr_cycle_num)
struct regexp *regexp;
struct automaton *automaton;
int curr_cycle_num;
{
int i;
if (regexp == NULL)
return curr_cycle_num;
else if (regexp->mode == rm_unit)
{
if (regexp->regexp.unit.unit_decl->corresponding_automaton_num
== automaton->automaton_order_num)
set_state_reserv (state_being_formed, curr_cycle_num,
regexp->regexp.unit.unit_decl->unit_num);
return curr_cycle_num;
}
else if (regexp->mode == rm_sequence)
{
for (i = 0; i < regexp->regexp.sequence.regexps_num; i++)
curr_cycle_num
= process_seq_for_forming_states
(regexp->regexp.sequence.regexps [i],
automaton, curr_cycle_num) + 1;
return curr_cycle_num;
}
else if (regexp->mode == rm_allof)
{
int finish_cycle = 0;
int cycle;
for (i = 0; i < regexp->regexp.allof.regexps_num; i++)
{
cycle
= process_seq_for_forming_states (regexp->regexp.allof.regexps [i],
automaton, curr_cycle_num);
if (finish_cycle < cycle)
finish_cycle = cycle;
}
return finish_cycle;
}
else
{
assert (regexp->mode == rm_nothing);
return curr_cycle_num;
}
}
/* This recursive function finishes forming ALT_STATE of AUTOMATON and
inserts alt_state into the table. */
static void
finish_forming_alt_state (alt_state, automaton)
struct alt_state *alt_state;
struct automaton *automaton ATTRIBUTE_UNUSED;
{
struct state *state_in_table;
struct state *corresponding_state;
corresponding_state = alt_state->state;
state_in_table = insert_state (corresponding_state);
if (state_in_table != corresponding_state)
{
free_state (corresponding_state);
alt_state->state = state_in_table;
}
}
/* The following variable value is current automaton insn for whose
reservation the alt states are created. */
static struct ainsn *curr_ainsn;
/* This recursive function processes `|' in reservation REGEXP for
forming alt_states of AUTOMATON. List of the alt states should
have the same order as in the description. */
static void
process_alts_for_forming_states (regexp, automaton, inside_oneof_p)
struct regexp *regexp;
struct automaton *automaton;
int inside_oneof_p;
{
int i;
if (regexp->mode != rm_oneof)
{
alt_state_being_formed = get_free_alt_state ();
state_being_formed = get_free_state (TRUE, automaton);
alt_state_being_formed->state = state_being_formed;
/* We inserts in reverse order but we process alternatives also
in reverse order. So we have the same order of alternative
as in the description. */
alt_state_being_formed->next_alt_state = curr_ainsn->alt_states;
curr_ainsn->alt_states = alt_state_being_formed;
(void) process_seq_for_forming_states (regexp, automaton, 0);
finish_forming_alt_state (alt_state_being_formed, automaton);
}
else
{
if (inside_oneof_p)
abort ();
/* We processes it in reverse order to get list with the same
order as in the description. See also the previous
commentary. */
for (i = regexp->regexp.oneof.regexps_num - 1; i >= 0; i--)
process_alts_for_forming_states (regexp->regexp.oneof.regexps [i],
automaton, TRUE);
}
}
/* Create nodes alt_state for all AUTOMATON insns. */
static void
create_alt_states (automaton)
struct automaton *automaton;
{
struct insn_reserv_decl *curr_insn_reserv_decl;
for (curr_ainsn = automaton->ainsn_list;
curr_ainsn != NULL;
curr_ainsn = curr_ainsn->next_ainsn)
{
curr_insn_reserv_decl = curr_ainsn->insn_reserv_decl;
if (curr_insn_reserv_decl != &advance_cycle_insn_decl->decl.insn_reserv)
{
curr_ainsn->alt_states = NULL;
process_alts_for_forming_states
(curr_insn_reserv_decl->transformed_regexp, automaton, FALSE);
curr_ainsn->sorted_alt_states
= uniq_sort_alt_states (curr_ainsn->alt_states);
}
}
}
/* The page contains major code for building DFA(s) for fast pipeline
hazards recognition. */
/* The function forms list of ainsns of AUTOMATON with the same
reservation. */
static void
form_ainsn_with_same_reservs (automaton)
struct automaton *automaton;
{
struct ainsn *curr_ainsn;
size_t curr_index;
vla_ptr_t first_insns_with_same_reservs;
vla_ptr_t last_insns_with_same_reservs;
VLA_PTR_CREATE (first_insns_with_same_reservs, 150,
"first insns with the same reservs");
VLA_PTR_CREATE (last_insns_with_same_reservs, 150,
"last insns with the same reservs");
for (curr_ainsn = automaton->ainsn_list;
curr_ainsn != NULL;
curr_ainsn = curr_ainsn->next_ainsn)
if (curr_ainsn->insn_reserv_decl
== &advance_cycle_insn_decl->decl.insn_reserv)
{
curr_ainsn->next_same_reservs_insn = NULL;
curr_ainsn->first_insn_with_same_reservs = TRUE;
}
else
{
for (curr_index = 0;
curr_index < VLA_PTR_LENGTH (first_insns_with_same_reservs);
curr_index++)
if (alt_states_eq
(curr_ainsn->sorted_alt_states,
((struct ainsn *) VLA_PTR (first_insns_with_same_reservs,
curr_index))->sorted_alt_states))
break;
curr_ainsn->next_same_reservs_insn = NULL;
if (curr_index < VLA_PTR_LENGTH (first_insns_with_same_reservs))
{
curr_ainsn->first_insn_with_same_reservs = FALSE;
((struct ainsn *) VLA_PTR (last_insns_with_same_reservs,
curr_index))->next_same_reservs_insn
= curr_ainsn;
VLA_PTR (last_insns_with_same_reservs, curr_index) = curr_ainsn;
}
else
{
VLA_PTR_ADD (first_insns_with_same_reservs, curr_ainsn);
VLA_PTR_ADD (last_insns_with_same_reservs, curr_ainsn);
curr_ainsn->first_insn_with_same_reservs = TRUE;
}
}
VLA_PTR_DELETE (first_insns_with_same_reservs);
VLA_PTR_DELETE (last_insns_with_same_reservs);
}
/* The following function creates all states of nondeterministic (if
NDFA_FLAG is TRUE) or deterministic AUTOMATON. */
static void
make_automaton (automaton)
struct automaton *automaton;
{
struct ainsn *curr_ainsn;
struct insn_reserv_decl *curr_insn_reserv_decl;
struct alt_state *curr_alt_state;
struct state *state;
struct state *start_state;
struct state *state2;
struct ainsn *advance_cycle_ainsn;
struct arc *added_arc;
vla_ptr_t state_stack;
VLA_PTR_CREATE (state_stack, 150, "state stack");
/* Create the start state (empty state). */
start_state = insert_state (get_free_state (TRUE, automaton));
automaton->start_state = start_state;
start_state->it_was_placed_in_stack_for_NDFA_forming = TRUE;
VLA_PTR_ADD (state_stack, start_state);
while (VLA_PTR_LENGTH (state_stack) != 0)
{
state = VLA_PTR (state_stack, VLA_PTR_LENGTH (state_stack) - 1);
VLA_PTR_SHORTEN (state_stack, 1);
advance_cycle_ainsn = NULL;
for (curr_ainsn = automaton->ainsn_list;
curr_ainsn != NULL;
curr_ainsn = curr_ainsn->next_ainsn)
if (curr_ainsn->first_insn_with_same_reservs)
{
curr_insn_reserv_decl = curr_ainsn->insn_reserv_decl;
if (curr_insn_reserv_decl
!= &advance_cycle_insn_decl->decl.insn_reserv)
{
/* We process alt_states in the same order as they are
present in the description. */
added_arc = NULL;
for (curr_alt_state = curr_ainsn->alt_states;
curr_alt_state != NULL;
curr_alt_state = curr_alt_state->next_alt_state)
{
state2 = curr_alt_state->state;
if (!intersected_state_reservs_p (state, state2))
{
state2 = states_union (state, state2);
if (!state2->it_was_placed_in_stack_for_NDFA_forming)
{
state2->it_was_placed_in_stack_for_NDFA_forming
= TRUE;
VLA_PTR_ADD (state_stack, state2);
}
added_arc = add_arc (state, state2, curr_ainsn, 1);
if (!ndfa_flag)
break;
}
}
if (!ndfa_flag && added_arc != NULL)
{
added_arc->state_alts = 0;
for (curr_alt_state = curr_ainsn->alt_states;
curr_alt_state != NULL;
curr_alt_state = curr_alt_state->next_alt_state)
{
state2 = curr_alt_state->state;
if (!intersected_state_reservs_p (state, state2))
added_arc->state_alts++;
}
}
}
else
advance_cycle_ainsn = curr_ainsn;
}
/* Add transition to advance cycle. */
state2 = state_shift (state);
if (!state2->it_was_placed_in_stack_for_NDFA_forming)
{
state2->it_was_placed_in_stack_for_NDFA_forming = TRUE;
VLA_PTR_ADD (state_stack, state2);
}
assert (advance_cycle_ainsn != NULL);
add_arc (state, state2, advance_cycle_ainsn, 1);
}
VLA_PTR_DELETE (state_stack);
}
/* Foms lists of all arcs of STATE marked by the same ainsn. */
static void
form_arcs_marked_by_insn (state)
struct state *state;
{
struct decl *curr_decl;
struct arc *curr_arc;
int i;
for (i = 0; i < description->decls_num; i++)
{
curr_decl = description->decls [i];
if (curr_decl->mode == dm_insn_reserv)
curr_decl->decl.insn_reserv.arcs_marked_by_insn = NULL;
}
for (curr_arc = first_out_arc (state);
curr_arc != NULL;
curr_arc = next_out_arc (curr_arc))
{
assert (curr_arc->insn != NULL);
curr_arc->next_arc_marked_by_insn
= curr_arc->insn->insn_reserv_decl->arcs_marked_by_insn;
curr_arc->insn->insn_reserv_decl->arcs_marked_by_insn = curr_arc;
}
}
/* The function creates composed state (see comments for IR) from
ORIGINAL_STATE and list of arcs ARCS_MARKED_BY_INSN marked by the
same insn. If the composed state is not in STATE_STACK yet, it is
popped to STATE_STACK. */
static void
create_composed_state (original_state, arcs_marked_by_insn, state_stack)
struct state *original_state;
struct arc *arcs_marked_by_insn;
vla_ptr_t *state_stack;
{
struct state *curr_state;
struct alt_state *curr_alt_state;
struct alt_state *new_alt_state;
struct arc *curr_arc;
struct arc *next_arc;
struct state *state_in_table;
struct state *temp_state;
struct alt_state *canonical_alt_states_list;
int alts_number;
if (arcs_marked_by_insn == NULL)
return;
if (arcs_marked_by_insn->next_arc_marked_by_insn == NULL)
curr_state = arcs_marked_by_insn->to_state;
else
{
assert (ndfa_flag);
/* Create composed state. */
curr_state = get_free_state (FALSE,
arcs_marked_by_insn->to_state->automaton);
curr_alt_state = NULL;
for (curr_arc = arcs_marked_by_insn;
curr_arc != NULL;
curr_arc = curr_arc->next_arc_marked_by_insn)
{
new_alt_state = get_free_alt_state ();
new_alt_state->next_alt_state = curr_alt_state;
new_alt_state->state = curr_arc->to_state;
assert (curr_arc->to_state->component_states == NULL);
curr_alt_state = new_alt_state;
}
/* There are not identical sets in the alt state list. */
canonical_alt_states_list = uniq_sort_alt_states (curr_alt_state);
if (canonical_alt_states_list->next_sorted_alt_state == NULL)
{
temp_state = curr_state;
curr_state = canonical_alt_states_list->state;
free_state (temp_state);
}
else
{
curr_state->component_states = canonical_alt_states_list;
state_in_table = insert_state (curr_state);
if (state_in_table != curr_state)
{
assert (state_in_table->it_was_placed_in_stack_for_DFA_forming);
free_state (curr_state);
curr_state = state_in_table;
}
else
{
assert (!curr_state->it_was_placed_in_stack_for_DFA_forming);
for (curr_alt_state = curr_state->component_states;
curr_alt_state != NULL;
curr_alt_state = curr_alt_state->next_sorted_alt_state)
for (curr_arc = first_out_arc (curr_alt_state->state);
curr_arc != NULL;
curr_arc = next_out_arc (curr_arc))
add_arc (curr_state, curr_arc->to_state, curr_arc->insn, 1);
}
arcs_marked_by_insn->to_state = curr_state;
for (alts_number = 0,
curr_arc = arcs_marked_by_insn->next_arc_marked_by_insn;
curr_arc != NULL;
curr_arc = next_arc)
{
next_arc = curr_arc->next_arc_marked_by_insn;
remove_arc (original_state, curr_arc);
alts_number++;
}
arcs_marked_by_insn->state_alts = alts_number;
}
}
if (!curr_state->it_was_placed_in_stack_for_DFA_forming)
{
curr_state->it_was_placed_in_stack_for_DFA_forming = TRUE;
VLA_PTR_ADD (*state_stack, curr_state);
}
}
/* The function transformes nondeterminstic AUTOMATON into
determenistic. */
static void
NDFA_to_DFA (automaton)
struct automaton *automaton;
{
struct state *start_state;
struct state *state;
struct decl *curr_decl;
vla_ptr_t state_stack;
int i;
VLA_PTR_CREATE (state_stack, 150, "state stack");
/* Create the start state (empty state). */
start_state = automaton->start_state;
start_state->it_was_placed_in_stack_for_DFA_forming = TRUE;
VLA_PTR_ADD (state_stack, start_state);
while (VLA_PTR_LENGTH (state_stack) != 0)
{
state = VLA_PTR (state_stack, VLA_PTR_LENGTH (state_stack) - 1);
VLA_PTR_SHORTEN (state_stack, 1);
form_arcs_marked_by_insn (state);
for (i = 0; i < description->decls_num; i++)
{
curr_decl = description->decls [i];
if (curr_decl->mode == dm_insn_reserv)
create_composed_state
(state, curr_decl->decl.insn_reserv.arcs_marked_by_insn,
&state_stack);
}
}
VLA_PTR_DELETE (state_stack);
}
/* The following variable value is current number (1, 2, ...) of passing
graph of states. */
static int curr_state_graph_pass_num;
/* This recursive function passes all states achieved from START_STATE
and applies APPLIED_FUNC to them. */
static void
pass_state_graph (start_state, applied_func)
struct state *start_state;
void (*applied_func) PARAMS ((struct state *state));
{
struct arc *curr_arc;
if (start_state->pass_num == curr_state_graph_pass_num)
return;
start_state->pass_num = curr_state_graph_pass_num;
(*applied_func) (start_state);
for (curr_arc = first_out_arc (start_state);
curr_arc != NULL;
curr_arc = next_out_arc (curr_arc))
pass_state_graph (curr_arc->to_state, applied_func);
}
/* This recursive function passes all states of AUTOMATON and applies
APPLIED_FUNC to them. */
static void
pass_states (automaton, applied_func)
struct automaton *automaton;
void (*applied_func) PARAMS ((struct state *state));
{
curr_state_graph_pass_num++;
pass_state_graph (automaton->start_state, applied_func);
}
/* The function initializes code for passing of all states. */
static void
initiate_pass_states ()
{
curr_state_graph_pass_num = 0;
}
/* The following vla is used for storing pointers to all achieved
states. */
static vla_ptr_t all_achieved_states;
/* This function is called by function pass_states to add an achieved
STATE. */
static void
add_achieved_state (state)
struct state *state;
{
VLA_PTR_ADD (all_achieved_states, state);
}
/* The function sets up equivalence numbers of insns which mark all
out arcs of STATE by equiv_class_num_1 (if ODD_ITERATION_FLAG ==
TRUE) or by equiv_class_num_2 of the destination state. The
function returns number of out arcs of STATE. */
static int
set_out_arc_insns_equiv_num (state, odd_iteration_flag)
struct state *state;
int odd_iteration_flag;
{
int state_out_arcs_num;
struct arc *curr_arc;
state_out_arcs_num = 0;
for (curr_arc = first_out_arc (state);
curr_arc != NULL;
curr_arc = next_out_arc (curr_arc))
{
assert (curr_arc->insn->insn_reserv_decl->equiv_class_num == 0
&& curr_arc->insn->insn_reserv_decl->state_alts == 0);
state_out_arcs_num++;
curr_arc->insn->insn_reserv_decl->equiv_class_num
= (odd_iteration_flag
? curr_arc->to_state->equiv_class_num_1
: curr_arc->to_state->equiv_class_num_2);
curr_arc->insn->insn_reserv_decl->state_alts = curr_arc->state_alts;
assert (curr_arc->insn->insn_reserv_decl->equiv_class_num != 0
&& curr_arc->insn->insn_reserv_decl->state_alts > 0);
}
return state_out_arcs_num;
}
/* The function clears equivalence numbers and alt_states in all insns
which mark all out arcs of STATE. */
static void
clear_arc_insns_equiv_num (state)
struct state *state;
{
struct arc *curr_arc;
for (curr_arc = first_out_arc (state);
curr_arc != NULL;
curr_arc = next_out_arc (curr_arc))
{
curr_arc->insn->insn_reserv_decl->equiv_class_num = 0;
curr_arc->insn->insn_reserv_decl->state_alts = 0;
}
}
/* The function copies pointers to equivalent states from vla FROM
into vla TO. */
static void
copy_equiv_class (to, from)
vla_ptr_t *to;
const vla_ptr_t *from;
{
struct state **curr_class_ptr;
VLA_PTR_NULLIFY (*to);
for (curr_class_ptr = VLA_PTR_BEGIN (*from);
curr_class_ptr <= (struct state **) VLA_PTR_LAST (*from);
curr_class_ptr++)
VLA_PTR_ADD (*to, *curr_class_ptr);
}
/* The function returns TRUE if STATE is not equivalent to another
state from the same current partition on equivalence classes
Another state has ORIGINAL_STATE_OUT_ARCS_NUM number of output
arcs. Iteration of making equivalence partition is defined by
ODD_ITERATION_FLAG. */
static int
state_is_differed (state, original_state_out_arcs_num, odd_iteration_flag)
struct state *state;
int original_state_out_arcs_num;
int odd_iteration_flag;
{
struct arc *curr_arc;
int state_out_arcs_num;
state_out_arcs_num = 0;
for (curr_arc = first_out_arc (state);
curr_arc != NULL;
curr_arc = next_out_arc (curr_arc))
{
state_out_arcs_num++;
if ((odd_iteration_flag
? curr_arc->to_state->equiv_class_num_1
: curr_arc->to_state->equiv_class_num_2)
!= curr_arc->insn->insn_reserv_decl->equiv_class_num
|| (curr_arc->insn->insn_reserv_decl->state_alts
!= curr_arc->state_alts))
return TRUE;
}
return state_out_arcs_num != original_state_out_arcs_num;
}
/* The function makes initial partition of STATES on equivalent
classes. */
static struct state *
init_equiv_class (states, states_num)
struct state **states;
int states_num;
{
struct state **curr_state_ptr;
struct state *result_equiv_class;
result_equiv_class = NULL;
for (curr_state_ptr = states;
curr_state_ptr < states + states_num;
curr_state_ptr++)
{
(*curr_state_ptr)->equiv_class_num_1 = 1;
(*curr_state_ptr)->next_equiv_class_state = result_equiv_class;
result_equiv_class = *curr_state_ptr;
}
return result_equiv_class;
}
/* The function finds equivalent states of AUTOMATON. */
static void
evaluate_equiv_classes (automaton, equiv_classes)
struct automaton *automaton;
vla_ptr_t *equiv_classes;
{
struct state *new_equiv_class;
int new_equiv_class_num;
int odd_iteration_flag;
int finish_flag;
vla_ptr_t next_iteration_classes;
struct state *first_state;
struct state *curr_state;
struct state *prev_state;
struct state *next_state;
struct state **curr_equiv_class_ptr;
struct state **curr_state_ptr;
int first_state_out_arcs_num;
VLA_PTR_CREATE (all_achieved_states, 1500, "all achieved states");
pass_states (automaton, add_achieved_state);
new_equiv_class = init_equiv_class (VLA_PTR_BEGIN (all_achieved_states),
VLA_PTR_LENGTH (all_achieved_states));
odd_iteration_flag = FALSE;
new_equiv_class_num = 1;
VLA_PTR_CREATE (next_iteration_classes, 150, "next iteration classes");
VLA_PTR_ADD (next_iteration_classes, new_equiv_class);
do
{
odd_iteration_flag = !odd_iteration_flag;
finish_flag = TRUE;
copy_equiv_class (equiv_classes, &next_iteration_classes);
/* Transfer equiv numbers for the next iteration. */
for (curr_state_ptr = VLA_PTR_BEGIN (all_achieved_states);
curr_state_ptr
<= (struct state **) VLA_PTR_LAST (all_achieved_states);
curr_state_ptr++)
if (odd_iteration_flag)
(*curr_state_ptr)->equiv_class_num_2
= (*curr_state_ptr)->equiv_class_num_1;
else
(*curr_state_ptr)->equiv_class_num_1
= (*curr_state_ptr)->equiv_class_num_2;
for (curr_equiv_class_ptr = VLA_PTR_BEGIN (*equiv_classes);
curr_equiv_class_ptr
<= (struct state **) VLA_PTR_LAST (*equiv_classes);
curr_equiv_class_ptr++)
{
assert (*curr_equiv_class_ptr != NULL);
for (first_state = *curr_equiv_class_ptr;
first_state != NULL;
first_state = new_equiv_class)
{
new_equiv_class = NULL;
if (first_state->next_equiv_class_state != NULL)
{
/* There are more one states in the class equivalence. */
first_state_out_arcs_num
= set_out_arc_insns_equiv_num (first_state,
odd_iteration_flag);
for (prev_state = first_state,
curr_state = first_state->next_equiv_class_state;
curr_state != NULL;
curr_state = next_state)
{
next_state = curr_state->next_equiv_class_state;
if (state_is_differed (curr_state,
first_state_out_arcs_num,
odd_iteration_flag))
{
/* Remove curr state from the class
equivalence. */
prev_state->next_equiv_class_state = next_state;
/* Add curr state to the new class equivalence. */
curr_state->next_equiv_class_state = new_equiv_class;
if (new_equiv_class == NULL)
new_equiv_class_num++;
if (odd_iteration_flag)
curr_state->equiv_class_num_2
= new_equiv_class_num;
else
curr_state->equiv_class_num_1
= new_equiv_class_num;
new_equiv_class = curr_state;
finish_flag = FALSE;
}
else
prev_state = curr_state;
}
clear_arc_insns_equiv_num (first_state);
}
if (new_equiv_class != NULL)
VLA_PTR_ADD (next_iteration_classes, new_equiv_class);
}
}
}
while (!finish_flag);
VLA_PTR_DELETE (next_iteration_classes);
VLA_PTR_DELETE (all_achieved_states);
}
/* The function merges equivalent states of AUTOMATON. */
static void
merge_states (automaton, equiv_classes)
struct automaton *automaton;
vla_ptr_t *equiv_classes;
{
struct state **curr_equiv_class_ptr;
struct state *curr_state;
struct state *new_state;
struct state *first_class_state;
struct alt_state *alt_states;
struct alt_state *new_alt_state;
struct arc *curr_arc;
struct arc *next_arc;
/* Create states corresponding to equivalence classes containing two
or more states. */
for (curr_equiv_class_ptr = VLA_PTR_BEGIN (*equiv_classes);
curr_equiv_class_ptr <= (struct state **) VLA_PTR_LAST (*equiv_classes);
curr_equiv_class_ptr++)
if ((*curr_equiv_class_ptr)->next_equiv_class_state != NULL)
{
/* There are more one states in the class equivalence. */
/* Create new compound state. */
new_state = get_free_state (FALSE, automaton);
alt_states = NULL;
first_class_state = *curr_equiv_class_ptr;
for (curr_state = first_class_state;
curr_state != NULL;
curr_state = curr_state->next_equiv_class_state)
{
curr_state->equiv_class_state = new_state;
new_alt_state = get_free_alt_state ();
new_alt_state->state = curr_state;
new_alt_state->next_sorted_alt_state = alt_states;
alt_states = new_alt_state;
}
new_state->component_states = alt_states;
}
else
(*curr_equiv_class_ptr)->equiv_class_state = *curr_equiv_class_ptr;
for (curr_equiv_class_ptr = VLA_PTR_BEGIN (*equiv_classes);
curr_equiv_class_ptr <= (struct state **) VLA_PTR_LAST (*equiv_classes);
curr_equiv_class_ptr++)
if ((*curr_equiv_class_ptr)->next_equiv_class_state != NULL)
{
first_class_state = *curr_equiv_class_ptr;
/* Create new arcs output from the state corresponding to
equiv class. */
for (curr_arc = first_out_arc (first_class_state);
curr_arc != NULL;
curr_arc = next_out_arc (curr_arc))
add_arc (first_class_state->equiv_class_state,
curr_arc->to_state->equiv_class_state,
curr_arc->insn, curr_arc->state_alts);
/* Delete output arcs from states of given class equivalence. */
for (curr_state = first_class_state;
curr_state != NULL;
curr_state = curr_state->next_equiv_class_state)
{
if (automaton->start_state == curr_state)
automaton->start_state = curr_state->equiv_class_state;
/* Delete the state and its output arcs. */
for (curr_arc = first_out_arc (curr_state);
curr_arc != NULL;
curr_arc = next_arc)
{
next_arc = next_out_arc (curr_arc);
free_arc (curr_arc);
}
}
}
else
{
/* Change `to_state' of arcs output from the state of given
equivalence class. */
for (curr_arc = first_out_arc (*curr_equiv_class_ptr);
curr_arc != NULL;
curr_arc = next_out_arc (curr_arc))
curr_arc->to_state = curr_arc->to_state->equiv_class_state;
}
}
/* The function sets up new_cycle_p for states if there is arc to the
state marked by advance_cycle_insn_decl. */
static void
set_new_cycle_flags (state)
struct state *state;
{
struct arc *curr_arc;
for (curr_arc = first_out_arc (state);
curr_arc != NULL;
curr_arc = next_out_arc (curr_arc))
if (curr_arc->insn->insn_reserv_decl
== &advance_cycle_insn_decl->decl.insn_reserv)
curr_arc->to_state->new_cycle_p = TRUE;
}
/* The top level function for minimization of deterministic
AUTOMATON. */
static void
minimize_DFA (automaton)
struct automaton *automaton;
{
vla_ptr_t equiv_classes;
VLA_PTR_CREATE (equiv_classes, 1500, "equivalence classes");
evaluate_equiv_classes (automaton, &equiv_classes);
merge_states (automaton, &equiv_classes);
pass_states (automaton, set_new_cycle_flags);
VLA_PTR_DELETE (equiv_classes);
}
/* Values of two variables are counted number of states and arcs in an
automaton. */
static int curr_counted_states_num;
static int curr_counted_arcs_num;
/* The function is called by function `pass_states' to count states
and arcs of an automaton. */
static void
incr_states_and_arcs_nums (state)
struct state *state;
{
struct arc *curr_arc;
curr_counted_states_num++;
for (curr_arc = first_out_arc (state);
curr_arc != NULL;
curr_arc = next_out_arc (curr_arc))
curr_counted_arcs_num++;
}
/* The function counts states and arcs of AUTOMATON. */
static void
count_states_and_arcs (automaton, states_num, arcs_num)
struct automaton *automaton;
int *states_num;
int *arcs_num;
{
curr_counted_states_num = 0;
curr_counted_arcs_num = 0;
pass_states (automaton, incr_states_and_arcs_nums);
*states_num = curr_counted_states_num;
*arcs_num = curr_counted_arcs_num;
}
/* The function builds one DFA AUTOMATON for fast pipeline hazards
recognition after checking and simplifying IR of the
description. */
static void
build_automaton (automaton)
struct automaton *automaton;
{
int states_num;
int arcs_num;
ticker_on (&NDFA_time);
make_automaton (automaton);
ticker_off (&NDFA_time);
count_states_and_arcs (automaton, &states_num, &arcs_num);
automaton->NDFA_states_num = states_num;
automaton->NDFA_arcs_num = arcs_num;
ticker_on (&NDFA_to_DFA_time);
NDFA_to_DFA (automaton);
ticker_off (&NDFA_to_DFA_time);
count_states_and_arcs (automaton, &states_num, &arcs_num);
automaton->DFA_states_num = states_num;
automaton->DFA_arcs_num = arcs_num;
if (!no_minimization_flag)
{
ticker_on (&minimize_time);
minimize_DFA (automaton);
ticker_off (&minimize_time);
count_states_and_arcs (automaton, &states_num, &arcs_num);
automaton->minimal_DFA_states_num = states_num;
automaton->minimal_DFA_arcs_num = arcs_num;
}
}
/* The page contains code for enumeration of all states of an automaton. */
/* Variable used for enumeration of all states of an automaton. Its
value is current number of automaton states. */
static int curr_state_order_num;
/* The function is called by function `pass_states' for enumerating
states. */
static void
set_order_state_num (state)
struct state *state;
{
state->order_state_num = curr_state_order_num;
curr_state_order_num++;
}
/* The function enumerates all states of AUTOMATON. */
static void
enumerate_states (automaton)
struct automaton *automaton;
{
curr_state_order_num = 0;
pass_states (automaton, set_order_state_num);
automaton->achieved_states_num = curr_state_order_num;
}
/* The page contains code for finding equivalent automaton insns
(ainsns). */
/* The function inserts AINSN into cyclic list
CYCLIC_EQUIV_CLASS_INSN_LIST of ainsns. */
static struct ainsn *
insert_ainsn_into_equiv_class (ainsn, cyclic_equiv_class_insn_list)
struct ainsn *ainsn;
struct ainsn *cyclic_equiv_class_insn_list;
{
if (cyclic_equiv_class_insn_list == NULL)
ainsn->next_equiv_class_insn = ainsn;
else
{
ainsn->next_equiv_class_insn
= cyclic_equiv_class_insn_list->next_equiv_class_insn;
cyclic_equiv_class_insn_list->next_equiv_class_insn = ainsn;
}
return ainsn;
}
/* The function deletes equiv_class_insn into cyclic list of
equivalent ainsns. */
static void
delete_ainsn_from_equiv_class (equiv_class_insn)
struct ainsn *equiv_class_insn;
{
struct ainsn *curr_equiv_class_insn;
struct ainsn *prev_equiv_class_insn;
prev_equiv_class_insn = equiv_class_insn;
for (curr_equiv_class_insn = equiv_class_insn->next_equiv_class_insn;
curr_equiv_class_insn != equiv_class_insn;
curr_equiv_class_insn = curr_equiv_class_insn->next_equiv_class_insn)
prev_equiv_class_insn = curr_equiv_class_insn;
if (prev_equiv_class_insn != equiv_class_insn)
prev_equiv_class_insn->next_equiv_class_insn
= equiv_class_insn->next_equiv_class_insn;
}
/* The function processes AINSN of a state in order to find equivalent
ainsns. INSN_ARCS_ARRAY is table: code of insn -> out arc of the
state. */
static void
process_insn_equiv_class (ainsn, insn_arcs_array)
struct ainsn *ainsn;
struct arc **insn_arcs_array;
{
struct ainsn *next_equiv_class_insn;
struct ainsn *curr_equiv_class_insn;
struct ainsn *cyclic_equiv_class_insn_list;
struct arc *temp_arc;
assert (insn_arcs_array [ainsn->insn_reserv_decl->insn_num] != NULL);
curr_equiv_class_insn = ainsn;
/* New class of ainsns which are not equivalent to given ainsn. */
cyclic_equiv_class_insn_list = NULL;
do
{
next_equiv_class_insn = curr_equiv_class_insn->next_equiv_class_insn;
temp_arc
= insn_arcs_array [curr_equiv_class_insn->insn_reserv_decl->insn_num];
if (temp_arc == NULL
|| (insn_arcs_array [ainsn->insn_reserv_decl->insn_num]->to_state
!= temp_arc->to_state))
{
delete_ainsn_from_equiv_class (curr_equiv_class_insn);
cyclic_equiv_class_insn_list
= insert_ainsn_into_equiv_class (curr_equiv_class_insn,
cyclic_equiv_class_insn_list);
}
curr_equiv_class_insn = next_equiv_class_insn;
}
while (curr_equiv_class_insn != ainsn);
}
/* The function processes STATE in order to find equivalent ainsns. */
static void
process_state_for_insn_equiv_partition (state)
struct state *state;
{
struct arc *curr_arc;
struct arc **insn_arcs_array;
int curr_insn_num;
vla_ptr_t insn_arcs_vect;
VLA_PTR_CREATE (insn_arcs_vect, 500, "insn arcs vector");
VLA_PTR_EXPAND (insn_arcs_vect, description->insns_num);
insn_arcs_array = VLA_PTR_BEGIN (insn_arcs_vect);
/* Process insns of the arcs. */
for (curr_insn_num = 0;
curr_insn_num < description->insns_num;
curr_insn_num++)
insn_arcs_array [curr_insn_num] = NULL;
for (curr_arc = first_out_arc (state);
curr_arc != NULL;
curr_arc = next_out_arc (curr_arc))
insn_arcs_array [curr_arc->insn->insn_reserv_decl->insn_num] = curr_arc;
for (curr_arc = first_out_arc (state);
curr_arc != NULL;
curr_arc = next_out_arc (curr_arc))
process_insn_equiv_class (curr_arc->insn, insn_arcs_array);
VLA_PTR_DELETE (insn_arcs_vect);
}
/* The function searches for equivalent ainsns of AUTOMATON. */
static void
set_insn_equiv_classes (automaton)
struct automaton *automaton;
{
struct ainsn *curr_ainsn;
struct ainsn *first_equiv_class_insn;
struct ainsn *curr_equiv_class_insn;
struct ainsn *cyclic_equiv_class_insn_list;
struct ainsn *curr_insn_with_same_reservs;
int equiv_classes_num;
/* All insns are included in one equivalence class. */
cyclic_equiv_class_insn_list = NULL;
for (curr_ainsn = automaton->ainsn_list;
curr_ainsn != NULL;
curr_ainsn = curr_ainsn->next_ainsn)
if (curr_ainsn->first_insn_with_same_reservs)
cyclic_equiv_class_insn_list
= insert_ainsn_into_equiv_class (curr_ainsn,
cyclic_equiv_class_insn_list);
/* Process insns in order to make equivalence partition. */
pass_states (automaton, process_state_for_insn_equiv_partition);
/* Enumerate equiv classes. */
for (curr_ainsn = automaton->ainsn_list;
curr_ainsn != NULL;
curr_ainsn = curr_ainsn->next_ainsn)
/* Set undefined value. */
curr_ainsn->insn_equiv_class_num = -1;
equiv_classes_num = 0;
for (curr_ainsn = automaton->ainsn_list;
curr_ainsn != NULL;
curr_ainsn = curr_ainsn->next_ainsn)
if (curr_ainsn->insn_equiv_class_num < 0)
{
first_equiv_class_insn = curr_ainsn;
assert (first_equiv_class_insn->first_insn_with_same_reservs);
first_equiv_class_insn->first_ainsn_with_given_equialence_num = TRUE;
curr_equiv_class_insn = first_equiv_class_insn;
do
{
for (curr_insn_with_same_reservs = curr_equiv_class_insn;
curr_insn_with_same_reservs != NULL;
curr_insn_with_same_reservs
= curr_insn_with_same_reservs->next_same_reservs_insn)
curr_insn_with_same_reservs->insn_equiv_class_num
= equiv_classes_num;
curr_equiv_class_insn
= curr_equiv_class_insn->next_equiv_class_insn;
}
while (curr_equiv_class_insn != first_equiv_class_insn);
equiv_classes_num++;
}
automaton->insn_equiv_classes_num = equiv_classes_num;
}
/* This page contains code for creating DFA(s) and calls functions
building them. */
/* The following value is used to prevent floating point overflow for
estimating an automaton bound. The value should be less DBL_MAX on
the host machine. We use here approximate minimum of maximal
double floating point value required by ANSI C standard. It
will work for non ANSI sun compiler too. */
#define MAX_FLOATING_POINT_VALUE_FOR_AUTOMATON_BOUND 1.0E37
/* The function estimate size of the single DFA used by PHR (pipeline
hazards recognizer). */
static double
estimate_one_automaton_bound ()
{
struct decl *curr_decl;
double one_automaton_estimation_bound;
double root_value;
int i;
one_automaton_estimation_bound = 1.0;
for (i = 0; i < description->decls_num; i++)
{
curr_decl = description->decls [i];
if (curr_decl->mode == dm_unit)
{
root_value = exp (log (curr_decl->decl.unit.max_occ_cycle_num + 1.0)
/ automata_num);
if (MAX_FLOATING_POINT_VALUE_FOR_AUTOMATON_BOUND / root_value
> one_automaton_estimation_bound)
one_automaton_estimation_bound *= root_value;
}
}
return one_automaton_estimation_bound;
}
/* The function compares unit declarations acoording to their maximal
cycle in reservations. */
static int
compare_max_occ_cycle_nums (unit_decl_1, unit_decl_2)
const void *unit_decl_1;
const void *unit_decl_2;
{
if (((*(struct decl **) unit_decl_1)->decl.unit.max_occ_cycle_num)
< ((*(struct decl **) unit_decl_2)->decl.unit.max_occ_cycle_num))
return 1;
else if (((*(struct decl **) unit_decl_1)->decl.unit.max_occ_cycle_num)
== ((*(struct decl **) unit_decl_2)->decl.unit.max_occ_cycle_num))
return 0;
else
return -1;
}
/* The function makes heuristic assigning automata to units. Actually
efficacy of the algorithm has been checked yet??? */
static void
units_to_automata_heuristic_distr ()
{
double one_automaton_estimation_bound;
struct decl *curr_decl;
struct decl **curr_unit_decl_ptr;
int curr_automaton_num;
int rest_units_num;
double curr_bound_value;
vla_ptr_t unit_decls;
int i;
if (description->units_num == 0)
return;
one_automaton_estimation_bound = estimate_one_automaton_bound ();
VLA_PTR_CREATE (unit_decls, 150, "unit decls");
for (i = 0; i < description->decls_num; i++)
{
curr_decl = description->decls [i];
if (curr_decl->mode == dm_unit)
VLA_PTR_ADD (unit_decls, curr_decl);
}
qsort (VLA_PTR_BEGIN (unit_decls), VLA_PTR_LENGTH (unit_decls),
sizeof (struct decl *), compare_max_occ_cycle_nums);
curr_automaton_num = 0;
curr_unit_decl_ptr = VLA_PTR_BEGIN (unit_decls);
curr_bound_value = (*curr_unit_decl_ptr)->decl.unit.max_occ_cycle_num;
(*curr_unit_decl_ptr)->decl.unit.corresponding_automaton_num
= curr_automaton_num;
for (curr_unit_decl_ptr++;
curr_unit_decl_ptr <= (struct decl **) VLA_PTR_LAST (unit_decls);
curr_unit_decl_ptr++)
{
rest_units_num = ((struct decl **) VLA_PTR_LAST (unit_decls)
- curr_unit_decl_ptr + 1);
assert (automata_num - curr_automaton_num - 1 <= rest_units_num);
if (curr_automaton_num < automata_num - 1
&& ((automata_num - curr_automaton_num - 1 == rest_units_num)
|| (curr_bound_value
> (one_automaton_estimation_bound
/ ((*curr_unit_decl_ptr)->decl.unit.max_occ_cycle_num)))))
{
curr_bound_value
= (*curr_unit_decl_ptr)->decl.unit.max_occ_cycle_num;
curr_automaton_num++;
}
else
curr_bound_value *= (*curr_unit_decl_ptr)->decl.unit.max_occ_cycle_num;
(*curr_unit_decl_ptr)->decl.unit.corresponding_automaton_num
= curr_automaton_num;
}
assert (curr_automaton_num == automata_num - 1);
VLA_PTR_DELETE (unit_decls);
}
/* The functions creates automaton insns for each automata. Automaton
insn is simply insn for given automaton which makes reservation
only of units of the automaton. */
static struct ainsn *
create_ainsns ()
{
struct decl *curr_decl;
struct ainsn *first_ainsn;
struct ainsn *curr_ainsn;
struct ainsn *prev_ainsn;
int i;
first_ainsn = NULL;
prev_ainsn = NULL;
for (i = 0; i < description->decls_num; i++)
{
curr_decl = description->decls [i];
if (curr_decl->mode == dm_insn_reserv)
{
curr_ainsn = create_node (sizeof (struct ainsn));
curr_ainsn->insn_reserv_decl = &curr_decl->decl.insn_reserv;
curr_ainsn->next_ainsn = NULL;
if (prev_ainsn == NULL)
first_ainsn = curr_ainsn;
else
prev_ainsn->next_ainsn = curr_ainsn;
prev_ainsn = curr_ainsn;
}
}
return first_ainsn;
}
/* The function assigns automata to units according to constructions
`define_automaton' in the description. */
static void
units_to_automata_distr ()
{
struct decl *curr_decl;
int i;
for (i = 0; i < description->decls_num; i++)
{
curr_decl = description->decls [i];
if (curr_decl->mode == dm_unit)
{
if (curr_decl->decl.unit.automaton_decl == NULL
|| (curr_decl->decl.unit.automaton_decl->corresponding_automaton
== NULL))
/* Distribute to the first automaton. */
curr_decl->decl.unit.corresponding_automaton_num = 0;
else
curr_decl->decl.unit.corresponding_automaton_num
= (curr_decl->decl.unit.automaton_decl
->corresponding_automaton->automaton_order_num);
}
}
}
/* The function creates DFA(s) for fast pipeline hazards recognition
after checking and simplifying IR of the description. */
static void
create_automata ()
{
struct automaton *curr_automaton;
struct automaton *prev_automaton;
struct decl *curr_decl;
int curr_automaton_num;
int i;
if (automata_num != 0)
{
units_to_automata_heuristic_distr ();
for (prev_automaton = NULL, curr_automaton_num = 0;
curr_automaton_num < automata_num;
curr_automaton_num++, prev_automaton = curr_automaton)
{
curr_automaton = create_node (sizeof (struct automaton));
curr_automaton->ainsn_list = create_ainsns ();
curr_automaton->corresponding_automaton_decl = NULL;
curr_automaton->next_automaton = NULL;
curr_automaton->automaton_order_num = curr_automaton_num;
if (prev_automaton == NULL)
description->first_automaton = curr_automaton;
else
prev_automaton->next_automaton = curr_automaton;
}
}
else
{
curr_automaton_num = 0;
prev_automaton = NULL;
for (i = 0; i < description->decls_num; i++)
{
curr_decl = description->decls [i];
if (curr_decl->mode == dm_automaton
&& curr_decl->decl.automaton.automaton_is_used)
{
curr_automaton = create_node (sizeof (struct automaton));
curr_automaton->ainsn_list = create_ainsns ();
curr_automaton->corresponding_automaton_decl
= &curr_decl->decl.automaton;
curr_automaton->next_automaton = NULL;
curr_decl->decl.automaton.corresponding_automaton
= curr_automaton;
curr_automaton->automaton_order_num = curr_automaton_num;
if (prev_automaton == NULL)
description->first_automaton = curr_automaton;
else
prev_automaton->next_automaton = curr_automaton;
curr_automaton_num++;
prev_automaton = curr_automaton;
}
}
if (curr_automaton_num == 0)
{
curr_automaton = create_node (sizeof (struct automaton));
curr_automaton->ainsn_list = create_ainsns ();
curr_automaton->corresponding_automaton_decl = NULL;
curr_automaton->next_automaton = NULL;
description->first_automaton = curr_automaton;
}
units_to_automata_distr ();
}
NDFA_time = create_ticker ();
ticker_off (&NDFA_time);
NDFA_to_DFA_time = create_ticker ();
ticker_off (&NDFA_to_DFA_time);
minimize_time = create_ticker ();
ticker_off (&minimize_time);
equiv_time = create_ticker ();
ticker_off (&equiv_time);
for (curr_automaton = description->first_automaton;
curr_automaton != NULL;
curr_automaton = curr_automaton->next_automaton)
{
create_alt_states (curr_automaton);
form_ainsn_with_same_reservs (curr_automaton);
build_automaton (curr_automaton);
enumerate_states (curr_automaton);
ticker_on (&equiv_time);
set_insn_equiv_classes (curr_automaton);
ticker_off (&equiv_time);
}
}
/* This page contains code for forming string representation of
regexp. The representation is formed on IR obstack. So you should
not work with IR obstack between regexp_representation and
finish_regexp_representation calls. */
/* This recursive function forms string representation of regexp
(without tailing '\0'). */
static void
form_regexp (regexp)
struct regexp *regexp;
{
int i;
if (regexp->mode == rm_unit || regexp->mode == rm_reserv)
{
const char *name = (regexp->mode == rm_unit
? regexp->regexp.unit.name
: regexp->regexp.reserv.name);
IR_TOP_ADD_MEMORY (name, strlen (name));
}
else if (regexp->mode == rm_sequence)
for (i = 0; i < regexp->regexp.sequence.regexps_num; i++)
{
if (i != 0)
IR_TOP_ADD_BYTE (',');
form_regexp (regexp->regexp.sequence.regexps [i]);
}
else if (regexp->mode == rm_allof)
{
IR_TOP_ADD_BYTE ('(');
for (i = 0; i < regexp->regexp.allof.regexps_num; i++)
{
if (i != 0)
IR_TOP_ADD_BYTE ('+');
if (regexp->regexp.allof.regexps[i]->mode == rm_sequence
|| regexp->regexp.oneof.regexps[i]->mode == rm_oneof)
IR_TOP_ADD_BYTE ('(');
form_regexp (regexp->regexp.allof.regexps [i]);
if (regexp->regexp.allof.regexps[i]->mode == rm_sequence
|| regexp->regexp.oneof.regexps[i]->mode == rm_oneof)
IR_TOP_ADD_BYTE (')');
}
IR_TOP_ADD_BYTE (')');
}
else if (regexp->mode == rm_oneof)
for (i = 0; i < regexp->regexp.oneof.regexps_num; i++)
{
if (i != 0)
IR_TOP_ADD_BYTE ('|');
if (regexp->regexp.oneof.regexps[i]->mode == rm_sequence)
IR_TOP_ADD_BYTE ('(');
form_regexp (regexp->regexp.oneof.regexps [i]);
if (regexp->regexp.oneof.regexps[i]->mode == rm_sequence)
IR_TOP_ADD_BYTE (')');
}
else if (regexp->mode == rm_repeat)
{
char digits [30];
if (regexp->regexp.repeat.regexp->mode == rm_sequence
|| regexp->regexp.repeat.regexp->mode == rm_allof
|| regexp->regexp.repeat.regexp->mode == rm_oneof)
IR_TOP_ADD_BYTE ('(');
form_regexp (regexp->regexp.repeat.regexp);
if (regexp->regexp.repeat.regexp->mode == rm_sequence
|| regexp->regexp.repeat.regexp->mode == rm_allof
|| regexp->regexp.repeat.regexp->mode == rm_oneof)
IR_TOP_ADD_BYTE (')');
sprintf (digits, "*%d", regexp->regexp.repeat.repeat_num);
IR_TOP_ADD_MEMORY (digits, strlen (digits));
}
else if (regexp->mode == rm_nothing)
IR_TOP_ADD_MEMORY (NOTHING_NAME, strlen (NOTHING_NAME));
else
assert (FALSE);
}
/* The function returns string representation of REGEXP on IR
obstack. */
static const char *
regexp_representation (regexp)
struct regexp *regexp;
{
form_regexp (regexp);
IR_TOP_ADD_BYTE ('\0');
return IR_TOP_BEGIN ();
}
/* The function frees memory allocated for last formed string
representation of regexp. */
static void
finish_regexp_representation ()
{
IR_TOP_NULLIFY ();
}
/* This page contains code for output PHR (pipeline hazards recognizer). */
/* The function outputs minimal C type which is sufficient for
representation numbers in range min_range_value and
max_range_value. Because host machine and build machine may be
different, we use here minimal values required by ANSI C standard
instead of UCHAR_MAX, SHRT_MAX, SHRT_MIN, etc. This is a good
approximation. */
static void
output_range_type (f, min_range_value, max_range_value)
FILE *f;
long int min_range_value;
long int max_range_value;
{
if (min_range_value >= 0 && max_range_value <= 255)
fprintf (f, "unsigned char");
else if (min_range_value >= -127 && max_range_value <= 127)
fprintf (f, "signed char");
else if (min_range_value >= 0 && max_range_value <= 65535)
fprintf (f, "unsigned short");
else if (min_range_value >= -32767 && max_range_value <= 32767)
fprintf (f, "short");
else
fprintf (f, "int");
}
/* The function outputs all initialization values of VECT with length
vect_length. */
static void
output_vect (vect, vect_length)
vect_el_t *vect;
int vect_length;
{
int els_on_line;
els_on_line = 1;
if (vect_length == 0)
fprintf (output_file,
"0 /* This is dummy el because the vect is empty */");
else
{
do
{
fprintf (output_file, "%5ld", (long) *vect);
vect_length--;
if (els_on_line == 10)
{
els_on_line = 0;
fprintf (output_file, ",\n");
}
else if (vect_length != 0)
fprintf (output_file, ", ");
els_on_line++;
vect++;
}
while (vect_length != 0);
}
}
/* The following is name of the structure which represents DFA(s) for
PHR. */
#define CHIP_NAME "DFA_chip"
/* The following is name of member which represents state of a DFA for
PHR. */
static void
output_chip_member_name (f, automaton)
FILE *f;
struct automaton *automaton;
{
if (automaton->corresponding_automaton_decl == NULL)
fprintf (f, "automaton_state_%d", automaton->automaton_order_num);
else
fprintf (f, "%s_automaton_state",
automaton->corresponding_automaton_decl->name);
}
/* The following is name of temporary variable which stores state of a
DFA for PHR. */
static void
output_temp_chip_member_name (f, automaton)
FILE *f;
struct automaton *automaton;
{
fprintf (f, "_");
output_chip_member_name (f, automaton);
}
/* This is name of macro value which is code of pseudo_insn
representing advancing cpu cycle. Its value is used as internal
code unknown insn. */
#define ADVANCE_CYCLE_VALUE_NAME "DFA__ADVANCE_CYCLE"
/* Output name of translate vector for given automaton. */
static void
output_translate_vect_name (f, automaton)
FILE *f;
struct automaton *automaton;
{
if (automaton->corresponding_automaton_decl == NULL)
fprintf (f, "translate_%d", automaton->automaton_order_num);
else
fprintf (f, "%s_translate", automaton->corresponding_automaton_decl->name);
}
/* Output name for simple transition table representation. */
static void
output_trans_full_vect_name (f, automaton)
FILE *f;
struct automaton *automaton;
{
if (automaton->corresponding_automaton_decl == NULL)
fprintf (f, "transitions_%d", automaton->automaton_order_num);
else
fprintf (f, "%s_transitions",
automaton->corresponding_automaton_decl->name);
}
/* Output name of comb vector of the transition table for given
automaton. */
static void
output_trans_comb_vect_name (f, automaton)
FILE *f;
struct automaton *automaton;
{
if (automaton->corresponding_automaton_decl == NULL)
fprintf (f, "transitions_%d", automaton->automaton_order_num);
else
fprintf (f, "%s_transitions",
automaton->corresponding_automaton_decl->name);
}
/* Output name of check vector of the transition table for given
automaton. */
static void
output_trans_check_vect_name (f, automaton)
FILE *f;
struct automaton *automaton;
{
if (automaton->corresponding_automaton_decl == NULL)
fprintf (f, "check_%d", automaton->automaton_order_num);
else
fprintf (f, "%s_check", automaton->corresponding_automaton_decl->name);
}
/* Output name of base vector of the transition table for given
automaton. */
static void
output_trans_base_vect_name (f, automaton)
FILE *f;
struct automaton *automaton;
{
if (automaton->corresponding_automaton_decl == NULL)
fprintf (f, "base_%d", automaton->automaton_order_num);
else
fprintf (f, "%s_base", automaton->corresponding_automaton_decl->name);
}
/* Output name for simple alternatives number representation. */
static void
output_state_alts_full_vect_name (f, automaton)
FILE *f;
struct automaton *automaton;
{
if (automaton->corresponding_automaton_decl == NULL)
fprintf (f, "state_alts_%d", automaton->automaton_order_num);
else
fprintf (f, "%s_state_alts",
automaton->corresponding_automaton_decl->name);
}
/* Output name of comb vector of the alternatives number table for given
automaton. */
static void
output_state_alts_comb_vect_name (f, automaton)
FILE *f;
struct automaton *automaton;
{
if (automaton->corresponding_automaton_decl == NULL)
fprintf (f, "state_alts_%d", automaton->automaton_order_num);
else
fprintf (f, "%s_state_alts",
automaton->corresponding_automaton_decl->name);
}
/* Output name of check vector of the alternatives number table for given
automaton. */
static void
output_state_alts_check_vect_name (f, automaton)
FILE *f;
struct automaton *automaton;
{
if (automaton->corresponding_automaton_decl == NULL)
fprintf (f, "check_state_alts_%d", automaton->automaton_order_num);
else
fprintf (f, "%s_check_state_alts",
automaton->corresponding_automaton_decl->name);
}
/* Output name of base vector of the alternatives number table for given
automaton. */
static void
output_state_alts_base_vect_name (f, automaton)
FILE *f;
struct automaton *automaton;
{
if (automaton->corresponding_automaton_decl == NULL)
fprintf (f, "base_state_alts_%d", automaton->automaton_order_num);
else
fprintf (f, "%s_base_state_alts",
automaton->corresponding_automaton_decl->name);
}
/* Output name of simple min issue delay table representation. */
static void
output_min_issue_delay_vect_name (f, automaton)
FILE *f;
struct automaton *automaton;
{
if (automaton->corresponding_automaton_decl == NULL)
fprintf (f, "min_issue_delay_%d", automaton->automaton_order_num);
else
fprintf (f, "%s_min_issue_delay",
automaton->corresponding_automaton_decl->name);
}
/* Output name of deadlock vector for given automaton. */
static void
output_dead_lock_vect_name (f, automaton)
FILE *f;
struct automaton *automaton;
{
if (automaton->corresponding_automaton_decl == NULL)
fprintf (f, "dead_lock_%d", automaton->automaton_order_num);
else
fprintf (f, "%s_dead_lock", automaton->corresponding_automaton_decl->name);
}
/* Output name of reserved units table for AUTOMATON into file F. */
static void
output_reserved_units_table_name (f, automaton)
FILE *f;
struct automaton *automaton;
{
if (automaton->corresponding_automaton_decl == NULL)
fprintf (f, "reserved_units_%d", automaton->automaton_order_num);
else
fprintf (f, "%s_reserved_units",
automaton->corresponding_automaton_decl->name);
}
/* Name of the PHR interface macro. */
#define AUTOMATON_STATE_ALTS_MACRO_NAME "AUTOMATON_STATE_ALTS"
/* Name of the PHR interface macro. */
#define CPU_UNITS_QUERY_MACRO_NAME "CPU_UNITS_QUERY"
/* Names of an internal functions: */
#define INTERNAL_MIN_ISSUE_DELAY_FUNC_NAME "internal_min_issue_delay"
/* This is external type of DFA(s) state. */
#define STATE_TYPE_NAME "state_t"
#define INTERNAL_TRANSITION_FUNC_NAME "internal_state_transition"
#define INTERNAL_STATE_ALTS_FUNC_NAME "internal_state_alts"
#define INTERNAL_RESET_FUNC_NAME "internal_reset"
#define INTERNAL_DEAD_LOCK_FUNC_NAME "internal_state_dead_lock_p"
#define INTERNAL_INSN_LATENCY_FUNC_NAME "internal_insn_latency"
/* Name of cache of insn dfa codes. */
#define DFA_INSN_CODES_VARIABLE_NAME "dfa_insn_codes"
/* Names of the PHR interface functions: */
#define SIZE_FUNC_NAME "state_size"
#define TRANSITION_FUNC_NAME "state_transition"
#define STATE_ALTS_FUNC_NAME "state_alts"
#define MIN_ISSUE_DELAY_FUNC_NAME "min_issue_delay"
#define MIN_INSN_CONFLICT_DELAY_FUNC_NAME "min_insn_conflict_delay"
#define DEAD_LOCK_FUNC_NAME "state_dead_lock_p"
#define RESET_FUNC_NAME "state_reset"
#define INSN_LATENCY_FUNC_NAME "insn_latency"
#define PRINT_RESERVATION_FUNC_NAME "print_reservation"
#define GET_CPU_UNIT_CODE_FUNC_NAME "get_cpu_unit_code"
#define CPU_UNIT_RESERVATION_P_FUNC_NAME "cpu_unit_reservation_p"
#define DFA_START_FUNC_NAME "dfa_start"
#define DFA_FINISH_FUNC_NAME "dfa_finish"
/* Names of parameters of the PHR interface functions. */
#define STATE_NAME "state"
#define INSN_PARAMETER_NAME "insn"
#define INSN2_PARAMETER_NAME "insn2"
#define CHIP_PARAMETER_NAME "chip"
#define FILE_PARAMETER_NAME "f"
#define CPU_UNIT_NAME_PARAMETER_NAME "cpu_unit_name"
#define CPU_CODE_PARAMETER_NAME "cpu_unit_code"
/* Names of the variables whose values are internal insn code of rtx
insn. */
#define INTERNAL_INSN_CODE_NAME "insn_code"
#define INTERNAL_INSN2_CODE_NAME "insn2_code"
/* Names of temporary variables in some functions. */
#define TEMPORARY_VARIABLE_NAME "temp"
#define I_VARIABLE_NAME "i"
/* Name of result variable in some functions. */
#define RESULT_VARIABLE_NAME "res"
/* Name of function (attribute) to translate insn into number of insn
alternatives reservation. */
#define INSN_ALTS_FUNC_NAME "insn_alts"
/* Name of function (attribute) to translate insn into internal insn
code. */
#define INTERNAL_DFA_INSN_CODE_FUNC_NAME "internal_dfa_insn_code"
/* Name of function (attribute) to translate insn into internal insn
code with caching. */
#define DFA_INSN_CODE_FUNC_NAME "dfa_insn_code"
/* Name of function (attribute) to translate insn into internal insn
code. */
#define INSN_DEFAULT_LATENCY_FUNC_NAME "insn_default_latency"
/* Name of function (attribute) to translate insn into internal insn
code. */
#define BYPASS_P_FUNC_NAME "bypass_p"
/* Output C type which is used for representation of codes of states
of AUTOMATON. */
static void
output_state_member_type (f, automaton)
FILE *f;
struct automaton *automaton;
{
output_range_type (f, 0, automaton->achieved_states_num);
}
/* Output definition of the structure representing current DFA(s)
state(s). */
static void
output_chip_definitions ()
{
struct automaton *curr_automaton;
fprintf (output_file, "struct %s\n{\n", CHIP_NAME);
for (curr_automaton = description->first_automaton;
curr_automaton != NULL;
curr_automaton = curr_automaton->next_automaton)
{
fprintf (output_file, " ");
output_state_member_type (output_file, curr_automaton);
fprintf (output_file, " ");
output_chip_member_name (output_file, curr_automaton);
fprintf (output_file, ";\n");
}
fprintf (output_file, "};\n\n");
#if 0
fprintf (output_file, "static struct %s %s;\n\n", CHIP_NAME, CHIP_NAME);
#endif
}
/* The function outputs translate vector of internal insn code into
insn equivalence class number. The equivalence class number is
used to access to table and vectors reprewsenting DFA(s). */
static void
output_translate_vect (automaton)
struct automaton *automaton;
{
struct ainsn *curr_ainsn;
int curr_insn_value;
vla_hwint_t translate_vect;
VLA_HWINT_CREATE (translate_vect, 250, "translate vector");
VLA_HWINT_EXPAND (translate_vect, description->insns_num);
for (curr_insn_value = 0;
curr_insn_value <= description->insns_num;
curr_insn_value++)
/* Undefined value */
VLA_HWINT (translate_vect, curr_insn_value)
= automaton->insn_equiv_classes_num;
for (curr_ainsn = automaton->ainsn_list;
curr_ainsn != NULL;
curr_ainsn = curr_ainsn->next_ainsn)
VLA_HWINT (translate_vect, curr_ainsn->insn_reserv_decl->insn_num)
= curr_ainsn->insn_equiv_class_num;
fprintf (output_file,
"/* Vector translating external insn codes to internal ones.*/\n");
fprintf (output_file, "static const ");
output_range_type (output_file, 0, automaton->insn_equiv_classes_num);
fprintf (output_file, " ");
output_translate_vect_name (output_file, automaton);
fprintf (output_file, "[] = {\n");
output_vect (VLA_HWINT_BEGIN (translate_vect),
VLA_HWINT_LENGTH (translate_vect));
fprintf (output_file, "};\n\n");
VLA_HWINT_DELETE (translate_vect);
}
/* The value in a table state x ainsn -> something which represents
undefined value. */
static int undefined_vect_el_value;
/* The following function returns TRUE if the best representation of
the table is comb vector. */
static int
comb_vect_p (tab)
struct state_ainsn_table *tab;
{
return (2 * VLA_HWINT_LENGTH (tab->full_vect)
> 5 * VLA_HWINT_LENGTH (tab->comb_vect));
}
/* The following function creates new table for AUTOMATON. */
static struct state_ainsn_table *
create_state_ainsn_table (automaton)
struct automaton *automaton;
{
struct state_ainsn_table *tab;
int full_vect_length;
int i;
tab = create_node (sizeof (struct state_ainsn_table));
tab->automaton = automaton;
VLA_HWINT_CREATE (tab->comb_vect, 10000, "comb vector");
VLA_HWINT_CREATE (tab->check_vect, 10000, "check vector");
VLA_HWINT_CREATE (tab->base_vect, 1000, "base vector");
VLA_HWINT_EXPAND (tab->base_vect, automaton->achieved_states_num);
VLA_HWINT_CREATE (tab->full_vect, 10000, "full vector");
full_vect_length = (automaton->insn_equiv_classes_num
* automaton->achieved_states_num);
VLA_HWINT_EXPAND (tab->full_vect, full_vect_length);
for (i = 0; i < full_vect_length; i++)
VLA_HWINT (tab->full_vect, i) = undefined_vect_el_value;
tab->min_base_vect_el_value = 0;
tab->max_base_vect_el_value = 0;
tab->min_comb_vect_el_value = 0;
tab->max_comb_vect_el_value = 0;
return tab;
}
/* The following function outputs the best C representation of the
table TAB of given TABLE_NAME. */
static void
output_state_ainsn_table (tab, table_name, output_full_vect_name_func,
output_comb_vect_name_func,
output_check_vect_name_func,
output_base_vect_name_func)
struct state_ainsn_table *tab;
char *table_name;
void (*output_full_vect_name_func)
PARAMS ((FILE *f, struct automaton *automaton));
void (*output_comb_vect_name_func)
PARAMS ((FILE *f, struct automaton *automaton));
void (*output_check_vect_name_func)
PARAMS ((FILE *f, struct automaton *automaton));
void (*output_base_vect_name_func)
PARAMS ((FILE *f, struct automaton *automaton));
{
if (!comb_vect_p (tab))
{
fprintf (output_file, "/* Vector for %s. */\n", table_name);
fprintf (output_file, "static const ");
output_range_type (output_file, tab->min_comb_vect_el_value,
tab->max_comb_vect_el_value);
fprintf (output_file, " ");
(*output_full_vect_name_func) (output_file, tab->automaton);
fprintf (output_file, "[] = {\n");
output_vect (VLA_HWINT_BEGIN (tab->full_vect),
VLA_HWINT_LENGTH (tab->full_vect));
fprintf (output_file, "};\n\n");
}
else
{
fprintf (output_file, "/* Comb vector for %s. */\n", table_name);
fprintf (output_file, "static const ");
output_range_type (output_file, tab->min_comb_vect_el_value,
tab->max_comb_vect_el_value);
fprintf (output_file, " ");
(*output_comb_vect_name_func) (output_file, tab->automaton);
fprintf (output_file, "[] = {\n");
output_vect (VLA_HWINT_BEGIN (tab->comb_vect),
VLA_HWINT_LENGTH (tab->comb_vect));
fprintf (output_file, "};\n\n");
fprintf (output_file, "/* Check vector for %s. */\n", table_name);
fprintf (output_file, "static const ");
output_range_type (output_file, 0, tab->automaton->achieved_states_num);
fprintf (output_file, " ");
(*output_check_vect_name_func) (output_file, tab->automaton);
fprintf (output_file, "[] = {\n");
output_vect (VLA_HWINT_BEGIN (tab->check_vect),
VLA_HWINT_LENGTH (tab->check_vect));
fprintf (output_file, "};\n\n");
fprintf (output_file, "/* Base vector for %s. */\n", table_name);
fprintf (output_file, "static const ");
output_range_type (output_file, tab->min_base_vect_el_value,
tab->max_base_vect_el_value);
fprintf (output_file, " ");
(*output_base_vect_name_func) (output_file, tab->automaton);
fprintf (output_file, "[] = {\n");
output_vect (VLA_HWINT_BEGIN (tab->base_vect),
VLA_HWINT_LENGTH (tab->base_vect));
fprintf (output_file, "};\n\n");
}
}
static void
add_vect (tab, vect_num, vect, vect_length)
struct state_ainsn_table *tab;
int vect_num;
vect_el_t *vect;
int vect_length;
{
int real_vect_length;
vect_el_t *comb_vect_start;
vect_el_t *check_vect_start;
int comb_vect_index;
int comb_vect_els_num;
int vect_index;
int first_unempty_vect_index;
int additional_els_num;
int no_state_value;
vect_el_t vect_el;
int i;
assert (vect_length != 0);
real_vect_length = tab->automaton->insn_equiv_classes_num;
assert (vect [vect_length - 1] != undefined_vect_el_value);
/* Form full vector: */
for (i = 0; i < vect_length; i++)
VLA_HWINT (tab->full_vect,
i + tab->automaton->insn_equiv_classes_num * vect_num)
= vect [i];
/* Form comb vector: */
assert (VLA_HWINT_LENGTH (tab->comb_vect)
== VLA_HWINT_LENGTH (tab->check_vect));
comb_vect_start = VLA_HWINT_BEGIN (tab->comb_vect);
comb_vect_els_num = VLA_HWINT_LENGTH (tab->comb_vect);
for (first_unempty_vect_index = 0;
first_unempty_vect_index < vect_length;
first_unempty_vect_index++)
if (vect [first_unempty_vect_index] != undefined_vect_el_value)
break;
/* Search for the place in comb vect for the inserted vect. */
for (comb_vect_index = 0;
comb_vect_index < comb_vect_els_num;
comb_vect_index++)
{
for (vect_index = first_unempty_vect_index;
vect_index < vect_length
&& vect_index + comb_vect_index < comb_vect_els_num;
vect_index++)
if (vect [vect_index] != undefined_vect_el_value
&& (comb_vect_start [vect_index + comb_vect_index]
!= undefined_vect_el_value))
break;
if (vect_index >= vect_length
|| vect_index + comb_vect_index >= comb_vect_els_num)
break;
}
/* Slot was found. */
additional_els_num = comb_vect_index + real_vect_length - comb_vect_els_num;
if (additional_els_num < 0)
additional_els_num = 0;
/* Expand comb and check vectors. */
vect_el = undefined_vect_el_value;
no_state_value = tab->automaton->achieved_states_num;
while (additional_els_num > 0)
{
VLA_HWINT_ADD (tab->comb_vect, vect_el);
VLA_HWINT_ADD (tab->check_vect, no_state_value);
additional_els_num--;
}
comb_vect_start = VLA_HWINT_BEGIN (tab->comb_vect);
check_vect_start = VLA_HWINT_BEGIN (tab->check_vect);
assert (VLA_HWINT_LENGTH (tab->comb_vect)
>= (size_t) (comb_vect_index + real_vect_length));
/* Fill comb and check vectors. */
for (vect_index = 0; vect_index < vect_length; vect_index++)
if (vect [vect_index] != undefined_vect_el_value)
{
assert (comb_vect_start [comb_vect_index + vect_index]
== undefined_vect_el_value);
comb_vect_start [comb_vect_index + vect_index] = vect [vect_index];
assert (vect [vect_index] >= 0);
if (tab->max_comb_vect_el_value < vect [vect_index])
tab->max_comb_vect_el_value = vect [vect_index];
if (tab->min_comb_vect_el_value > vect [vect_index])
tab->min_comb_vect_el_value = vect [vect_index];
check_vect_start [comb_vect_index + vect_index] = vect_num;
}
if (tab->max_base_vect_el_value < comb_vect_index)
tab->max_base_vect_el_value = comb_vect_index;
if (tab->min_base_vect_el_value > comb_vect_index)
tab->min_base_vect_el_value = comb_vect_index;
VLA_HWINT (tab->base_vect, vect_num) = comb_vect_index;
}
/* Return number of out arcs of STATE. */
static int
out_state_arcs_num (state)
struct state *state;
{
int result;
struct arc *curr_arc;
result = 0;
for (curr_arc = first_out_arc (state);
curr_arc != NULL;
curr_arc = next_out_arc (curr_arc))
{
assert (curr_arc->insn != NULL);
if (curr_arc->insn->first_ainsn_with_given_equialence_num)
result++;
}
return result;
}
/* Compare number of possible transitions from the states. */
static int
compare_transition_els_num (state_ptr_1, state_ptr_2)
const void *state_ptr_1;
const void *state_ptr_2;
{
int transition_els_num_1;
int transition_els_num_2;
transition_els_num_1 = out_state_arcs_num (*(struct state **) state_ptr_1);
transition_els_num_2 = out_state_arcs_num (*(struct state **) state_ptr_2);
if (transition_els_num_1 < transition_els_num_2)
return 1;
else if (transition_els_num_1 == transition_els_num_2)
return 0;
else
return -1;
}
/* The function adds element EL_VALUE to vector VECT for a table state
x AINSN. */
static void
add_vect_el (vect, ainsn, el_value)
vla_hwint_t *vect;
struct ainsn *ainsn;
int el_value;
{
int equiv_class_num;
int vect_index;
assert (ainsn != NULL);
equiv_class_num = ainsn->insn_equiv_class_num;
for (vect_index = VLA_HWINT_LENGTH (*vect);
vect_index <= equiv_class_num;
vect_index++)
VLA_HWINT_ADD (*vect, undefined_vect_el_value);
VLA_HWINT (*vect, equiv_class_num) = el_value;
}
/* This is for forming vector of states of an automaton. */
static vla_ptr_t output_states_vect;
/* The function is called by function pass_states. The function adds
STATE to `output_states_vect'. */
static void
add_states_vect_el (state)
struct state *state;
{
VLA_PTR_ADD (output_states_vect, state);
}
/* Form and output vectors (comb, check, base or full vector)
representing transition table of AUTOMATON. */
static void
output_trans_table (automaton)
struct automaton *automaton;
{
struct state **curr_state_ptr;
struct arc *curr_arc;
vla_hwint_t transition_vect;
undefined_vect_el_value = automaton->achieved_states_num;
automaton->trans_table = create_state_ainsn_table (automaton);
/* Create vect of pointers to states ordered by num of transitions
from the state (state with the maximum num is the first). */
VLA_PTR_CREATE (output_states_vect, 1500, "output states vector");
pass_states (automaton, add_states_vect_el);
qsort (VLA_PTR_BEGIN (output_states_vect),
VLA_PTR_LENGTH (output_states_vect),
sizeof (struct state *), compare_transition_els_num);
VLA_HWINT_CREATE (transition_vect, 500, "transition vector");
for (curr_state_ptr = VLA_PTR_BEGIN (output_states_vect);
curr_state_ptr <= (struct state **) VLA_PTR_LAST (output_states_vect);
curr_state_ptr++)
{
VLA_HWINT_NULLIFY (transition_vect);
for (curr_arc = first_out_arc (*curr_state_ptr);
curr_arc != NULL;
curr_arc = next_out_arc (curr_arc))
{
assert (curr_arc->insn != NULL);
if (curr_arc->insn->first_ainsn_with_given_equialence_num)
add_vect_el (&transition_vect, curr_arc->insn,
curr_arc->to_state->order_state_num);
}
add_vect (automaton->trans_table, (*curr_state_ptr)->order_state_num,
VLA_HWINT_BEGIN (transition_vect),
VLA_HWINT_LENGTH (transition_vect));
}
output_state_ainsn_table (automaton->trans_table,
(char *) "state transitions",
output_trans_full_vect_name,
output_trans_comb_vect_name,
output_trans_check_vect_name,
output_trans_base_vect_name);
VLA_PTR_DELETE (output_states_vect);
VLA_HWINT_DELETE (transition_vect);
}
/* Form and output vectors (comb, check, base or simple vect)
representing alts number table of AUTOMATON. The table is state x
ainsn -> number of possible alternative reservations by the
ainsn. */
static void
output_state_alts_table (automaton)
struct automaton *automaton;
{
struct state **curr_state_ptr;
struct arc *curr_arc;
vla_hwint_t state_alts_vect;
undefined_vect_el_value = 0; /* no alts when transition is not possible */
automaton->state_alts_table = create_state_ainsn_table (automaton);
/* Create vect of pointers to states ordered by num of transitions
from the state (state with the maximum num is the first). */
VLA_PTR_CREATE (output_states_vect, 1500, "output states vector");
pass_states (automaton, add_states_vect_el);
qsort (VLA_PTR_BEGIN (output_states_vect),
VLA_PTR_LENGTH (output_states_vect),
sizeof (struct state *), compare_transition_els_num);
/* Create base, comb, and check vectors. */
VLA_HWINT_CREATE (state_alts_vect, 500, "state alts vector");
for (curr_state_ptr = VLA_PTR_BEGIN (output_states_vect);
curr_state_ptr <= (struct state **) VLA_PTR_LAST (output_states_vect);
curr_state_ptr++)
{
VLA_HWINT_NULLIFY (state_alts_vect);
for (curr_arc = first_out_arc (*curr_state_ptr);
curr_arc != NULL;
curr_arc = next_out_arc (curr_arc))
{
assert (curr_arc->insn != NULL);
if (curr_arc->insn->first_ainsn_with_given_equialence_num)
add_vect_el (&state_alts_vect, curr_arc->insn,
curr_arc->state_alts);
}
add_vect (automaton->state_alts_table,
(*curr_state_ptr)->order_state_num,
VLA_HWINT_BEGIN (state_alts_vect),
VLA_HWINT_LENGTH (state_alts_vect));
}
output_state_ainsn_table (automaton->state_alts_table,
(char *) "state insn alternatives",
output_state_alts_full_vect_name,
output_state_alts_comb_vect_name,
output_state_alts_check_vect_name,
output_state_alts_base_vect_name);
VLA_PTR_DELETE (output_states_vect);
VLA_HWINT_DELETE (state_alts_vect);
}
/* The current number of passing states to find minimal issue delay
value for an ainsn and state. */
static int current_state_pass_number;
/* This recursive function passes states to find minimal issue delay
value for AINSN. The state being visited is STATE. */
static void
min_issue_delay_pass_states (state, ainsn)
struct state *state;
struct ainsn *ainsn;
{
struct arc *curr_arc;
int min_insn_issue_delay, insn_issue_delay;
if (state->pass_number == current_state_pass_number)
return;
state->pass_number = current_state_pass_number;
min_insn_issue_delay = state->min_insn_issue_delay = -1;
for (curr_arc = first_out_arc (state);
curr_arc != NULL;
curr_arc = next_out_arc (curr_arc))
if (curr_arc->insn == ainsn)
{
min_insn_issue_delay = 0;
break;
}
else
{
min_issue_delay_pass_states (curr_arc->to_state, ainsn);
if (curr_arc->to_state->min_insn_issue_delay != -1)
{
insn_issue_delay
= (curr_arc->to_state->min_insn_issue_delay
+ (curr_arc->insn->insn_reserv_decl
== &advance_cycle_insn_decl->decl.insn_reserv
? 1 : 0));
if (min_insn_issue_delay == -1
|| min_insn_issue_delay > insn_issue_delay)
min_insn_issue_delay = insn_issue_delay;
}
}
state->min_insn_issue_delay = min_insn_issue_delay;
}
/* The function searches minimal issue delay value for AINSN in STATE.
The function can return negative can not issue AINSN. We will
report about it later. */
static int
min_issue_delay (state, ainsn)
struct state *state;
struct ainsn *ainsn;
{
current_state_pass_number++;
min_issue_delay_pass_states (state, ainsn);
return state->min_insn_issue_delay;
}
/* The function initiates code for finding minimal issue delay values.
It should be called only once. */
static void
initiate_min_issue_delay_pass_states ()
{
current_state_pass_number = 0;
}
/* Form and output vectors representing minimal issue delay table of
AUTOMATON. The table is state x ainsn -> minimal issue delay of
the ainsn. */
static void
output_min_issue_delay_table (automaton)
struct automaton *automaton;
{
vla_hwint_t min_issue_delay_vect;
vla_hwint_t compressed_min_issue_delay_vect;
vect_el_t min_delay;
struct ainsn *curr_ainsn;
struct state **curr_state_ptr;
int i;
/* Create vect of pointers to states ordered by num of transitions
from the state (state with the maximum num is the first). */
VLA_PTR_CREATE (output_states_vect, 1500, "output states vector");
pass_states (automaton, add_states_vect_el);
VLA_HWINT_CREATE (min_issue_delay_vect, 1500, "min issue delay vector");
VLA_HWINT_EXPAND (min_issue_delay_vect,
VLA_HWINT_LENGTH (output_states_vect)
* automaton->insn_equiv_classes_num);
for (i = 0;
i < ((int) VLA_HWINT_LENGTH (output_states_vect)
* automaton->insn_equiv_classes_num);
i++)
VLA_HWINT (min_issue_delay_vect, i) = 0;
automaton->max_min_delay = 0;
for (curr_state_ptr = VLA_PTR_BEGIN (output_states_vect);
curr_state_ptr <= (struct state **) VLA_PTR_LAST (output_states_vect);
curr_state_ptr++)
{
for (curr_ainsn = automaton->ainsn_list;
curr_ainsn != NULL;
curr_ainsn = curr_ainsn->next_ainsn)
if (curr_ainsn->first_ainsn_with_given_equialence_num)
{
min_delay = min_issue_delay (*curr_state_ptr, curr_ainsn);
if (automaton->max_min_delay < min_delay)
automaton->max_min_delay = min_delay;
VLA_HWINT (min_issue_delay_vect,
(*curr_state_ptr)->order_state_num
* automaton->insn_equiv_classes_num
+ curr_ainsn->insn_equiv_class_num) = min_delay;
}
}
fprintf (output_file,
"/* Vector of min issue delay of insns.*/\n");
fprintf (output_file, "static const ");
output_range_type (output_file, 0, automaton->max_min_delay);
fprintf (output_file, " ");
output_min_issue_delay_vect_name (output_file, automaton);
fprintf (output_file, "[] = {\n");
/* Compress the vector */
if (automaton->max_min_delay < 2)
automaton->min_issue_delay_table_compression_factor = 8;
else if (automaton->max_min_delay < 4)
automaton->min_issue_delay_table_compression_factor = 4;
else if (automaton->max_min_delay < 16)
automaton->min_issue_delay_table_compression_factor = 2;
else
automaton->min_issue_delay_table_compression_factor = 1;
VLA_HWINT_CREATE (compressed_min_issue_delay_vect, 1500,
"compressed min issue delay vector");
VLA_HWINT_EXPAND (compressed_min_issue_delay_vect,
(VLA_HWINT_LENGTH (min_issue_delay_vect)
+ automaton->min_issue_delay_table_compression_factor
- 1)
/ automaton->min_issue_delay_table_compression_factor);
for (i = 0;
i < (int) VLA_HWINT_LENGTH (compressed_min_issue_delay_vect);
i++)
VLA_HWINT (compressed_min_issue_delay_vect, i) = 0;
for (i = 0; i < (int) VLA_HWINT_LENGTH (min_issue_delay_vect); i++)
VLA_HWINT (compressed_min_issue_delay_vect,
i / automaton->min_issue_delay_table_compression_factor)
|= (VLA_HWINT (min_issue_delay_vect, i)
<< (8
- (i % automaton->min_issue_delay_table_compression_factor
+ 1)
* (8
/ automaton->min_issue_delay_table_compression_factor)));
output_vect (VLA_HWINT_BEGIN (compressed_min_issue_delay_vect),
VLA_HWINT_LENGTH (compressed_min_issue_delay_vect));
fprintf (output_file, "};\n\n");
VLA_PTR_DELETE (output_states_vect);
VLA_HWINT_DELETE (min_issue_delay_vect);
VLA_HWINT_DELETE (compressed_min_issue_delay_vect);
}
#ifndef NDEBUG
/* Number of states which contains transition only by advancing cpu
cycle. */
static int locked_states_num;
#endif
/* Form and output vector representing the locked states of
AUTOMATON. */
static void
output_dead_lock_vect (automaton)
struct automaton *automaton;
{
struct state **curr_state_ptr;
struct arc *curr_arc;
vla_hwint_t dead_lock_vect;
/* Create vect of pointers to states ordered by num of
transitions from the state (state with the maximum num is the
first). */
VLA_PTR_CREATE (output_states_vect, 1500, "output states vector");
pass_states (automaton, add_states_vect_el);
VLA_HWINT_CREATE (dead_lock_vect, 1500, "is dead locked vector");
VLA_HWINT_EXPAND (dead_lock_vect, VLA_HWINT_LENGTH (output_states_vect));
for (curr_state_ptr = VLA_PTR_BEGIN (output_states_vect);
curr_state_ptr <= (struct state **) VLA_PTR_LAST (output_states_vect);
curr_state_ptr++)
{
curr_arc = first_out_arc (*curr_state_ptr);
assert (curr_arc != NULL);
VLA_HWINT (dead_lock_vect, (*curr_state_ptr)->order_state_num)
= (next_out_arc (curr_arc) == NULL
&& (curr_arc->insn->insn_reserv_decl
== &advance_cycle_insn_decl->decl.insn_reserv)
? 1 : 0);
#ifndef NDEBUG
if (VLA_HWINT (dead_lock_vect, (*curr_state_ptr)->order_state_num))
locked_states_num++;
#endif
}
fprintf (output_file, "/* Vector for locked state flags. */\n");
fprintf (output_file, "static const ");
output_range_type (output_file, 0, 1);
fprintf (output_file, " ");
output_dead_lock_vect_name (output_file, automaton);
fprintf (output_file, "[] = {\n");
output_vect (VLA_HWINT_BEGIN (dead_lock_vect),
VLA_HWINT_LENGTH (dead_lock_vect));
fprintf (output_file, "};\n\n");
VLA_HWINT_DELETE (dead_lock_vect);
VLA_PTR_DELETE (output_states_vect);
}
/* Form and output vector representing reserved units of the states of
AUTOMATON. */
static void
output_reserved_units_table (automaton)
struct automaton *automaton;
{
struct state **curr_state_ptr;
vla_hwint_t reserved_units_table;
size_t state_byte_size;
int i;
/* Create vect of pointers to states. */
VLA_PTR_CREATE (output_states_vect, 1500, "output states vector");
pass_states (automaton, add_states_vect_el);
/* Create vector. */
VLA_HWINT_CREATE (reserved_units_table, 1500, "reserved units vector");
state_byte_size = (description->query_units_num + 7) / 8;
VLA_HWINT_EXPAND (reserved_units_table,
VLA_HWINT_LENGTH (output_states_vect) * state_byte_size);
for (i = 0;
i < (int) (VLA_HWINT_LENGTH (output_states_vect) * state_byte_size);
i++)
VLA_HWINT (reserved_units_table, i) = 0;
for (curr_state_ptr = VLA_PTR_BEGIN (output_states_vect);
curr_state_ptr <= (struct state **) VLA_PTR_LAST (output_states_vect);
curr_state_ptr++)
{
for (i = 0; i < description->units_num; i++)
if (units_array [i]->query_p)
{
if (test_unit_reserv ((*curr_state_ptr)->reservs, 0, i))
VLA_HWINT (reserved_units_table,
(*curr_state_ptr)->order_state_num * state_byte_size
+ units_array [i]->query_num / 8)
+= (1 << (units_array [i]->query_num % 8));
}
}
fprintf (output_file, "/* Vector for reserved units of states. */\n");
fprintf (output_file, "static const ");
output_range_type (output_file, 0, 255);
fprintf (output_file, " ");
output_reserved_units_table_name (output_file, automaton);
fprintf (output_file, "[] = {\n");
output_vect (VLA_HWINT_BEGIN (reserved_units_table),
VLA_HWINT_LENGTH (reserved_units_table));
fprintf (output_file, "};\n\n");
VLA_HWINT_DELETE (reserved_units_table);
VLA_PTR_DELETE (output_states_vect);
}
/* The function outputs all tables representing DFA(s) used for fast
pipeline hazards recognition. */
static void
output_tables ()
{
struct automaton *curr_automaton;
#ifndef NDEBUG
locked_states_num = 0;
#endif
initiate_min_issue_delay_pass_states ();
for (curr_automaton = description->first_automaton;
curr_automaton != NULL;
curr_automaton = curr_automaton->next_automaton)
{
output_translate_vect (curr_automaton);
output_trans_table (curr_automaton);
fprintf (output_file, "\n#if %s\n", AUTOMATON_STATE_ALTS_MACRO_NAME);
output_state_alts_table (curr_automaton);
fprintf (output_file, "\n#endif /* #if %s */\n\n",
AUTOMATON_STATE_ALTS_MACRO_NAME);
output_min_issue_delay_table (curr_automaton);
output_dead_lock_vect (curr_automaton);
if (no_minimization_flag)
{
fprintf (output_file, "\n#if %s\n\n", CPU_UNITS_QUERY_MACRO_NAME);
output_reserved_units_table (curr_automaton);
fprintf (output_file, "\n#endif /* #if %s */\n\n",
CPU_UNITS_QUERY_MACRO_NAME);
}
}
fprintf (output_file, "\n#define %s %d\n\n", ADVANCE_CYCLE_VALUE_NAME,
advance_cycle_insn_decl->decl.insn_reserv.insn_num);
}
/* The function outputs definition and value of PHR interface variable
`max_insn_queue_index' */
static void
output_max_insn_queue_index_def ()
{
int i;
for (i = 0; (1 << i) <= description->max_insn_reserv_cycles; i++)
;
assert (i >= 0);
fprintf (output_file, "\nint max_insn_queue_index = %d;\n\n", (1 << i) - 1);
}
/* Output function `internal_min_issue_delay'. */
static void
output_internal_min_issue_delay_func ()
{
struct automaton *curr_automaton;
fprintf (output_file,
"static int\n%s (%s, %s)\n\tint %s;\n\tstruct %s *%s;\n",
INTERNAL_MIN_ISSUE_DELAY_FUNC_NAME, INTERNAL_INSN_CODE_NAME,
CHIP_PARAMETER_NAME, INTERNAL_INSN_CODE_NAME, CHIP_NAME,
CHIP_PARAMETER_NAME);
fprintf (output_file, "{\n int %s;\n int %s;\n",
TEMPORARY_VARIABLE_NAME, RESULT_VARIABLE_NAME);
for (curr_automaton = description->first_automaton;
curr_automaton != NULL;
curr_automaton = curr_automaton->next_automaton)
{
fprintf (output_file, "\n %s = ", TEMPORARY_VARIABLE_NAME);
output_min_issue_delay_vect_name (output_file, curr_automaton);
fprintf (output_file,
(curr_automaton->min_issue_delay_table_compression_factor != 1
? " [(" : " ["));
output_translate_vect_name (output_file, curr_automaton);
fprintf (output_file, " [%s] + ", INTERNAL_INSN_CODE_NAME);
fprintf (output_file, "%s->", CHIP_PARAMETER_NAME);
output_chip_member_name (output_file, curr_automaton);
fprintf (output_file, " * %d",
curr_automaton->insn_equiv_classes_num);
if (curr_automaton->min_issue_delay_table_compression_factor == 1)
fprintf (output_file, "];\n");
else
{
fprintf (output_file, ") / %d];\n",
curr_automaton->min_issue_delay_table_compression_factor);
fprintf (output_file, " %s = (%s >> (8 - (",
TEMPORARY_VARIABLE_NAME, TEMPORARY_VARIABLE_NAME);
output_translate_vect_name (output_file, curr_automaton);
fprintf
(output_file, " [%s] %% %d + 1) * %d)) & %d;\n",
INTERNAL_INSN_CODE_NAME,
curr_automaton->min_issue_delay_table_compression_factor,
8 / curr_automaton->min_issue_delay_table_compression_factor,
(1 <<
(8 / curr_automaton->min_issue_delay_table_compression_factor))
- 1);
}
if (curr_automaton == description->first_automaton)
fprintf (output_file, " %s = %s;\n",
RESULT_VARIABLE_NAME, TEMPORARY_VARIABLE_NAME);
else
{
fprintf (output_file, " if (%s > %s)\n",
TEMPORARY_VARIABLE_NAME, RESULT_VARIABLE_NAME);
fprintf (output_file, " %s = %s;\n",
RESULT_VARIABLE_NAME, TEMPORARY_VARIABLE_NAME);
}
}
fprintf (output_file, " return %s;\n", RESULT_VARIABLE_NAME);
fprintf (output_file, "}\n\n");
}
/* Output function `internal_state_transition'. */
static void
output_internal_trans_func ()
{
struct automaton *curr_automaton;
struct automaton *next_automaton;
fprintf (output_file,
"static int\n%s (%s, %s)\n\tint %s;\n\tstruct %s *%s;\n",
INTERNAL_TRANSITION_FUNC_NAME, INTERNAL_INSN_CODE_NAME,
CHIP_PARAMETER_NAME, INTERNAL_INSN_CODE_NAME,
CHIP_NAME, CHIP_PARAMETER_NAME);
fprintf (output_file, "{\n int %s;\n", TEMPORARY_VARIABLE_NAME);
if (description->first_automaton != NULL)
for (curr_automaton = description->first_automaton;;
curr_automaton = next_automaton)
{
next_automaton = curr_automaton->next_automaton;
if (next_automaton == NULL)
break;
fprintf (output_file, " ");
output_state_member_type (output_file, curr_automaton);
fprintf (output_file, " ");
output_temp_chip_member_name (output_file, curr_automaton);
fprintf (output_file, ";\n");
}
for (curr_automaton = description->first_automaton;
curr_automaton != NULL;
curr_automaton = curr_automaton->next_automaton)
if (comb_vect_p (curr_automaton->trans_table))
{
fprintf (output_file, "\n %s = ", TEMPORARY_VARIABLE_NAME);
output_trans_base_vect_name (output_file, curr_automaton);
fprintf (output_file, " [%s->", CHIP_PARAMETER_NAME);
output_chip_member_name (output_file, curr_automaton);
fprintf (output_file, "] + ");
output_translate_vect_name (output_file, curr_automaton);
fprintf (output_file, " [%s];\n", INTERNAL_INSN_CODE_NAME);
fprintf (output_file, " if (");
output_trans_check_vect_name (output_file, curr_automaton);
fprintf (output_file, " [%s] != %s->",
TEMPORARY_VARIABLE_NAME, CHIP_PARAMETER_NAME);
output_chip_member_name (output_file, curr_automaton);
fprintf (output_file, ")\n");
fprintf (output_file, " return %s (%s, %s);\n",
INTERNAL_MIN_ISSUE_DELAY_FUNC_NAME, INTERNAL_INSN_CODE_NAME,
CHIP_PARAMETER_NAME);
fprintf (output_file, " else\n");
fprintf (output_file, " ");
if (curr_automaton->next_automaton != NULL)
output_temp_chip_member_name (output_file, curr_automaton);
else
{
fprintf (output_file, "%s->", CHIP_PARAMETER_NAME);
output_chip_member_name (output_file, curr_automaton);
}
fprintf (output_file, " = ");
output_trans_comb_vect_name (output_file, curr_automaton);
fprintf (output_file, " [%s];\n", TEMPORARY_VARIABLE_NAME);
}
else
{
fprintf (output_file, "\n %s = ", TEMPORARY_VARIABLE_NAME);
output_trans_full_vect_name (output_file, curr_automaton);
fprintf (output_file, " [");
output_translate_vect_name (output_file, curr_automaton);
fprintf (output_file, " [%s] + ", INTERNAL_INSN_CODE_NAME);
fprintf (output_file, "%s->", CHIP_PARAMETER_NAME);
output_chip_member_name (output_file, curr_automaton);
fprintf (output_file, " * %d];\n",
curr_automaton->insn_equiv_classes_num);
fprintf (output_file, " if (%s >= %d)\n", TEMPORARY_VARIABLE_NAME,
curr_automaton->achieved_states_num);
fprintf (output_file, " return %s (%s, %s);\n",
INTERNAL_MIN_ISSUE_DELAY_FUNC_NAME, INTERNAL_INSN_CODE_NAME,
CHIP_PARAMETER_NAME);
fprintf (output_file, " else\n ");
if (curr_automaton->next_automaton != NULL)
output_temp_chip_member_name (output_file, curr_automaton);
else
{
fprintf (output_file, "%s->", CHIP_PARAMETER_NAME);
output_chip_member_name (output_file, curr_automaton);
}
fprintf (output_file, " = %s;\n", TEMPORARY_VARIABLE_NAME);
}
if (description->first_automaton != NULL)
for (curr_automaton = description->first_automaton;;
curr_automaton = next_automaton)
{
next_automaton = curr_automaton->next_automaton;
if (next_automaton == NULL)
break;
fprintf (output_file, " %s->", CHIP_PARAMETER_NAME);
output_chip_member_name (output_file, curr_automaton);
fprintf (output_file, " = ");
output_temp_chip_member_name (output_file, curr_automaton);
fprintf (output_file, ";\n");
}
fprintf (output_file, " return -1;\n");
fprintf (output_file, "}\n\n");
}
/* Output code
if (insn != 0)
{
insn_code = dfa_insn_code (insn);
if (insn_code > DFA__ADVANCE_CYCLE)
return code;
}
else
insn_code = DFA__ADVANCE_CYCLE;
where insn denotes INSN_NAME, insn_code denotes INSN_CODE_NAME, and
code denotes CODE. */
static void
output_internal_insn_code_evaluation (insn_name, insn_code_name, code)
const char *insn_name;
const char *insn_code_name;
int code;
{
fprintf (output_file, "\n if (%s != 0)\n {\n", insn_name);
fprintf (output_file, " %s = %s (%s);\n", insn_code_name,
DFA_INSN_CODE_FUNC_NAME, insn_name);
fprintf (output_file, " if (%s > %s)\n return %d;\n",
insn_code_name, ADVANCE_CYCLE_VALUE_NAME, code);
fprintf (output_file, " }\n else\n %s = %s;\n\n",
insn_code_name, ADVANCE_CYCLE_VALUE_NAME);
}
/* The function outputs function `dfa_insn_code'. */
static void
output_dfa_insn_code_func ()
{
fprintf (output_file, "#ifdef __GNUC__\n__inline__\n#endif\n");
fprintf (output_file, "static int\n%s (%s)\n\trtx %s;\n",
DFA_INSN_CODE_FUNC_NAME, INSN_PARAMETER_NAME, INSN_PARAMETER_NAME);
fprintf (output_file, "{\n int %s;\n\n", INTERNAL_INSN_CODE_NAME);
fprintf (output_file, " if ((%s = %s [INSN_UID (%s)]) < 0)\n {\n",
INTERNAL_INSN_CODE_NAME, DFA_INSN_CODES_VARIABLE_NAME,
INSN_PARAMETER_NAME);
fprintf (output_file, " %s = %s (%s);\n", INTERNAL_INSN_CODE_NAME,
INTERNAL_DFA_INSN_CODE_FUNC_NAME, INSN_PARAMETER_NAME);
fprintf (output_file, " %s [INSN_UID (%s)] = %s;\n",
DFA_INSN_CODES_VARIABLE_NAME, INSN_PARAMETER_NAME,
INTERNAL_INSN_CODE_NAME);
fprintf (output_file, " }\n return %s;\n}\n\n",
INTERNAL_INSN_CODE_NAME);
}
/* The function outputs PHR interface function `state_transition'. */
static void
output_trans_func ()
{
fprintf (output_file, "int\n%s (%s, %s)\n\t%s %s;\n\trtx %s;\n",
TRANSITION_FUNC_NAME, STATE_NAME, INSN_PARAMETER_NAME,
STATE_TYPE_NAME, STATE_NAME, INSN_PARAMETER_NAME);
fprintf (output_file, "{\n int %s;\n", INTERNAL_INSN_CODE_NAME);
output_internal_insn_code_evaluation (INSN_PARAMETER_NAME,
INTERNAL_INSN_CODE_NAME, -1);
fprintf (output_file, " return %s (%s, %s);\n}\n\n",
INTERNAL_TRANSITION_FUNC_NAME, INTERNAL_INSN_CODE_NAME, STATE_NAME);
}
/* Output function `internal_state_alts'. */
static void
output_internal_state_alts_func ()
{
struct automaton *curr_automaton;
fprintf (output_file,
"static int\n%s (%s, %s)\n\tint %s;\n\tstruct %s *%s;\n",
INTERNAL_STATE_ALTS_FUNC_NAME, INTERNAL_INSN_CODE_NAME,
CHIP_PARAMETER_NAME, INTERNAL_INSN_CODE_NAME, CHIP_NAME,
CHIP_PARAMETER_NAME);
fprintf (output_file, "{\n int %s;\n", RESULT_VARIABLE_NAME);
for (curr_automaton = description->first_automaton;
curr_automaton != NULL;
curr_automaton = curr_automaton->next_automaton)
if (comb_vect_p (curr_automaton->state_alts_table))
{
fprintf (output_file, " int %s;\n", TEMPORARY_VARIABLE_NAME);
break;
}
for (curr_automaton = description->first_automaton;
curr_automaton != NULL;
curr_automaton = curr_automaton->next_automaton)
if (comb_vect_p (curr_automaton->state_alts_table))
{
fprintf (output_file, "\n %s = ", TEMPORARY_VARIABLE_NAME);
output_state_alts_base_vect_name (output_file, curr_automaton);
fprintf (output_file, " [%s->", CHIP_PARAMETER_NAME);
output_chip_member_name (output_file, curr_automaton);
fprintf (output_file, "] + ");
output_translate_vect_name (output_file, curr_automaton);
fprintf (output_file, " [%s];\n", INTERNAL_INSN_CODE_NAME);
fprintf (output_file, " if (");
output_state_alts_check_vect_name (output_file, curr_automaton);
fprintf (output_file, " [%s] != %s->",
TEMPORARY_VARIABLE_NAME, CHIP_PARAMETER_NAME);
output_chip_member_name (output_file, curr_automaton);
fprintf (output_file, ")\n");
fprintf (output_file, " return 0;\n");
fprintf (output_file, " else\n");
fprintf (output_file,
(curr_automaton == description->first_automaton
? " %s = " : " %s += "), RESULT_VARIABLE_NAME);
output_state_alts_comb_vect_name (output_file, curr_automaton);
fprintf (output_file, " [%s];\n", TEMPORARY_VARIABLE_NAME);
}
else
{
fprintf (output_file,
(curr_automaton == description->first_automaton
? "\n %s = " : " %s += "), RESULT_VARIABLE_NAME);
output_state_alts_full_vect_name (output_file, curr_automaton);
fprintf (output_file, " [");
output_translate_vect_name (output_file, curr_automaton);
fprintf (output_file, " [%s] + ", INTERNAL_INSN_CODE_NAME);
fprintf (output_file, "%s->", CHIP_PARAMETER_NAME);
output_chip_member_name (output_file, curr_automaton);
fprintf (output_file, " * %d];\n",
curr_automaton->insn_equiv_classes_num);
}
fprintf (output_file, " return %s;\n", RESULT_VARIABLE_NAME);
fprintf (output_file, "}\n\n");
}
/* The function outputs PHR interface function `state_alts'. */
static void
output_state_alts_func ()
{
fprintf (output_file, "int\n%s (%s, %s)\n\t%s %s;\n\trtx %s;\n",
STATE_ALTS_FUNC_NAME, STATE_NAME, INSN_PARAMETER_NAME,
STATE_TYPE_NAME, STATE_NAME, INSN_PARAMETER_NAME);
fprintf (output_file, "{\n int %s;\n", INTERNAL_INSN_CODE_NAME);
output_internal_insn_code_evaluation (INSN_PARAMETER_NAME,
INTERNAL_INSN_CODE_NAME, 0);
fprintf (output_file, " return %s (%s, %s);\n}\n\n",
INTERNAL_STATE_ALTS_FUNC_NAME, INTERNAL_INSN_CODE_NAME, STATE_NAME);
}
/* Output function `min_issue_delay'. */
static void
output_min_issue_delay_func ()
{
fprintf (output_file, "int\n%s (%s, %s)\n\t%s %s;\n\trtx %s;\n",
MIN_ISSUE_DELAY_FUNC_NAME, STATE_NAME, INSN_PARAMETER_NAME,
STATE_TYPE_NAME, STATE_NAME, INSN_PARAMETER_NAME);
fprintf (output_file, "{\n int %s;\n", INTERNAL_INSN_CODE_NAME);
fprintf (output_file, "\n if (%s != 0)\n {\n", INSN_PARAMETER_NAME);
fprintf (output_file, " %s = %s (%s);\n", INTERNAL_INSN_CODE_NAME,
DFA_INSN_CODE_FUNC_NAME, INSN_PARAMETER_NAME);
fprintf (output_file, " if (%s > %s)\n return 0;\n",
INTERNAL_INSN_CODE_NAME, ADVANCE_CYCLE_VALUE_NAME);
fprintf (output_file, " }\n else\n %s = %s;\n",
INTERNAL_INSN_CODE_NAME, ADVANCE_CYCLE_VALUE_NAME);
fprintf (output_file, "\n return %s (%s, %s);\n",
INTERNAL_MIN_ISSUE_DELAY_FUNC_NAME, INTERNAL_INSN_CODE_NAME,
STATE_NAME);
fprintf (output_file, "}\n\n");
}
/* Output function `internal_dead_lock'. */
static void
output_internal_dead_lock_func ()
{
struct automaton *curr_automaton;
fprintf (output_file, "static int\n%s (%s)\n\tstruct %s *%s;\n",
INTERNAL_DEAD_LOCK_FUNC_NAME, CHIP_PARAMETER_NAME, CHIP_NAME,
CHIP_PARAMETER_NAME);
fprintf (output_file, "{\n");
for (curr_automaton = description->first_automaton;
curr_automaton != NULL;
curr_automaton = curr_automaton->next_automaton)
{
fprintf (output_file, " if (");
output_dead_lock_vect_name (output_file, curr_automaton);
fprintf (output_file, " [%s->", CHIP_PARAMETER_NAME);
output_chip_member_name (output_file, curr_automaton);
fprintf (output_file, "])\n return 1/* TRUE */;\n");
}
fprintf (output_file, " return 0/* FALSE */;\n}\n\n");
}
/* The function outputs PHR interface function `state_dead_lock_p'. */
static void
output_dead_lock_func ()
{
fprintf (output_file, "int\n%s (%s)\n\t%s %s;\n",
DEAD_LOCK_FUNC_NAME, STATE_NAME, STATE_TYPE_NAME, STATE_NAME);
fprintf (output_file, "{\n return %s (%s);\n}\n\n",
INTERNAL_DEAD_LOCK_FUNC_NAME, STATE_NAME);
}
/* Output function `internal_reset'. */
static void
output_internal_reset_func ()
{
fprintf (output_file, "static void\n%s (%s)\n\tstruct %s *%s;\n",
INTERNAL_RESET_FUNC_NAME, CHIP_PARAMETER_NAME,
CHIP_NAME, CHIP_PARAMETER_NAME);
fprintf (output_file, "{\n memset (%s, 0, sizeof (struct %s));\n}\n\n",
CHIP_PARAMETER_NAME, CHIP_NAME);
}
/* The function outputs PHR interface function `state_size'. */
static void
output_size_func ()
{
fprintf (output_file, "int\n%s ()\n", SIZE_FUNC_NAME);
fprintf (output_file, "{\n return sizeof (struct %s);\n}\n\n", CHIP_NAME);
}
/* The function outputs PHR interface function `state_reset'. */
static void
output_reset_func ()
{
fprintf (output_file, "void\n%s (%s)\n\t %s %s;\n",
RESET_FUNC_NAME, STATE_NAME, STATE_TYPE_NAME, STATE_NAME);
fprintf (output_file, "{\n %s (%s);\n}\n\n", INTERNAL_RESET_FUNC_NAME,
STATE_NAME);
}
/* Output function `min_insn_conflict_delay'. */
static void
output_min_insn_conflict_delay_func ()
{
fprintf (output_file,
"int\n%s (%s, %s, %s)\n\t%s %s;\n\trtx %s;\n\trtx %s;\n",
MIN_INSN_CONFLICT_DELAY_FUNC_NAME,
STATE_NAME, INSN_PARAMETER_NAME, INSN2_PARAMETER_NAME,
STATE_TYPE_NAME, STATE_NAME,
INSN_PARAMETER_NAME, INSN2_PARAMETER_NAME);
fprintf (output_file, "{\n struct %s %s;\n int %s, %s;\n",
CHIP_NAME, CHIP_NAME, INTERNAL_INSN_CODE_NAME,
INTERNAL_INSN2_CODE_NAME);
output_internal_insn_code_evaluation (INSN_PARAMETER_NAME,
INTERNAL_INSN_CODE_NAME, 0);
output_internal_insn_code_evaluation (INSN2_PARAMETER_NAME,
INTERNAL_INSN2_CODE_NAME, 0);
fprintf (output_file, " memcpy (&%s, %s, sizeof (%s));\n",
CHIP_NAME, STATE_NAME, CHIP_NAME);
fprintf (output_file, " %s (&%s);\n", INTERNAL_RESET_FUNC_NAME, CHIP_NAME);
fprintf (output_file, " if (%s (%s, &%s) > 0)\n abort ();\n",
INTERNAL_TRANSITION_FUNC_NAME, INTERNAL_INSN_CODE_NAME, CHIP_NAME);
fprintf (output_file, " return %s (%s, &%s);\n",
INTERNAL_MIN_ISSUE_DELAY_FUNC_NAME, INTERNAL_INSN2_CODE_NAME,
CHIP_NAME);
fprintf (output_file, "}\n\n");
}
/* Output function `internal_insn_latency'. */
static void
output_internal_insn_latency_func ()
{
struct decl *curr_decl;
struct bypass_decl *curr_bypass;
int i;
fprintf (output_file, "static int\n%s (%s, %s, %s, %s)",
INTERNAL_INSN_LATENCY_FUNC_NAME, INTERNAL_INSN_CODE_NAME,
INTERNAL_INSN2_CODE_NAME,
INSN_PARAMETER_NAME, INSN2_PARAMETER_NAME);
fprintf (output_file, "\n\tint %s;\n\tint %s;\n\trtx %s;\n\trtx %s;\n",
INTERNAL_INSN_CODE_NAME, INTERNAL_INSN2_CODE_NAME,
INSN_PARAMETER_NAME, INSN2_PARAMETER_NAME);
fprintf (output_file, "{\n switch (%s)\n {\n", INTERNAL_INSN_CODE_NAME);
for (i = 0; i < description->decls_num; i++)
{
curr_decl = description->decls [i];
if (curr_decl->mode == dm_insn_reserv)
{
fprintf (output_file, " case %d:\n",
curr_decl->decl.insn_reserv.insn_num);
if (curr_decl->decl.insn_reserv.bypass_list == NULL)
fprintf (output_file, " return (%s != %s ? %d : 0);\n",
INTERNAL_INSN2_CODE_NAME, ADVANCE_CYCLE_VALUE_NAME,
curr_decl->decl.insn_reserv.default_latency);
else
{
fprintf (output_file, " switch (%s)\n {\n",
INTERNAL_INSN2_CODE_NAME);
for (curr_bypass = curr_decl->decl.insn_reserv.bypass_list;
curr_bypass != NULL;
curr_bypass = curr_bypass->next)
{
fprintf (output_file, " case %d:\n",
curr_bypass->in_insn_reserv->insn_num);
if (curr_bypass->bypass_guard_name == NULL)
fprintf (output_file, " return %d;\n",
curr_bypass->latency);
else
fprintf (output_file,
" return (%s (%s, %s) ? %d : %d);\n",
curr_bypass->bypass_guard_name,
INSN_PARAMETER_NAME, INSN2_PARAMETER_NAME,
curr_bypass->latency,
curr_decl->decl.insn_reserv.default_latency);
}
fprintf (output_file, " default:\n");
fprintf (output_file,
" return (%s != %s ? %d : 0);\n }\n",
INTERNAL_INSN2_CODE_NAME, ADVANCE_CYCLE_VALUE_NAME,
curr_decl->decl.insn_reserv.default_latency);
}
}
}
fprintf (output_file, " default:\n return 0;\n }\n}\n\n");
}
/* The function outputs PHR interface function `insn_latency'. */
static void
output_insn_latency_func ()
{
fprintf (output_file, "int\n%s (%s, %s)\n\trtx %s;\n\trtx %s;\n",
INSN_LATENCY_FUNC_NAME, INSN_PARAMETER_NAME, INSN2_PARAMETER_NAME,
INSN_PARAMETER_NAME, INSN2_PARAMETER_NAME);
fprintf (output_file, "{\n int %s, %s;\n",
INTERNAL_INSN_CODE_NAME, INTERNAL_INSN2_CODE_NAME);
output_internal_insn_code_evaluation (INSN_PARAMETER_NAME,
INTERNAL_INSN_CODE_NAME, 0);
output_internal_insn_code_evaluation (INSN2_PARAMETER_NAME,
INTERNAL_INSN2_CODE_NAME, 0);
fprintf (output_file, " return %s (%s, %s, %s, %s);\n}\n\n",
INTERNAL_INSN_LATENCY_FUNC_NAME,
INTERNAL_INSN_CODE_NAME, INTERNAL_INSN2_CODE_NAME,
INSN_PARAMETER_NAME, INSN2_PARAMETER_NAME);
}
/* The function outputs PHR interface function `print_reservation'. */
static void
output_print_reservation_func ()
{
struct decl *curr_decl;
int i;
fprintf (output_file, "void\n%s (%s, %s)\n\tFILE *%s;\n\trtx %s;\n",
PRINT_RESERVATION_FUNC_NAME, FILE_PARAMETER_NAME,
INSN_PARAMETER_NAME, FILE_PARAMETER_NAME,
INSN_PARAMETER_NAME);
fprintf (output_file, "{\n int %s;\n", INTERNAL_INSN_CODE_NAME);
fprintf (output_file, "\n if (%s != 0)\n {\n", INSN_PARAMETER_NAME);
fprintf (output_file, " %s = %s (%s);\n",
INTERNAL_INSN_CODE_NAME, DFA_INSN_CODE_FUNC_NAME,
INSN_PARAMETER_NAME);
fprintf (output_file, " if (%s > %s)\n",
INTERNAL_INSN_CODE_NAME, ADVANCE_CYCLE_VALUE_NAME);
fprintf (output_file, " {\n fprintf (%s, \"%s\");\n",
FILE_PARAMETER_NAME, NOTHING_NAME);
fprintf (output_file, " return;\n }\n");
fprintf (output_file, " }\n else\n");
fprintf (output_file,
" {\n fprintf (%s, \"%s\");\n return;\n }\n",
FILE_PARAMETER_NAME, NOTHING_NAME);
fprintf (output_file, " switch (%s)\n {\n", INTERNAL_INSN_CODE_NAME);
for (i = 0; i < description->decls_num; i++)
{
curr_decl = description->decls [i];
if (curr_decl->mode == dm_insn_reserv
&& curr_decl != advance_cycle_insn_decl)
{
fprintf (output_file,
" case %d:\n", curr_decl->decl.insn_reserv.insn_num);
fprintf (output_file,
" fprintf (%s, \"%s\");\n break;\n",
FILE_PARAMETER_NAME,
regexp_representation (curr_decl->decl.insn_reserv.regexp));
finish_regexp_representation ();
}
}
fprintf (output_file, " default:\n fprintf (%s, \"%s\");\n }\n",
FILE_PARAMETER_NAME, NOTHING_NAME);
fprintf (output_file, "}\n\n");
}
/* The following function is used to sort unit declaration by their
names. */
static int
units_cmp (unit1, unit2)
const void *unit1, *unit2;
{
const struct unit_decl *u1 = *(struct unit_decl **) unit1;
const struct unit_decl *u2 = *(struct unit_decl **) unit2;
return strcmp (u1->name, u2->name);
}
/* The following macro value is name of struct containing unit name
and unit code. */
#define NAME_CODE_STRUCT_NAME "name_code"
/* The following macro value is name of table of struct name_code. */
#define NAME_CODE_TABLE_NAME "name_code_table"
/* The following macro values are member names for struct name_code. */
#define NAME_MEMBER_NAME "name"
#define CODE_MEMBER_NAME "code"
/* The following macro values are local variable names for function
`get_cpu_unit_code'. */
#define CMP_VARIABLE_NAME "cmp"
#define LOW_VARIABLE_NAME "l"
#define MIDDLE_VARIABLE_NAME "m"
#define HIGH_VARIABLE_NAME "h"
/* The following function outputs function to obtain internal cpu unit
code by the cpu unit name. */
static void
output_get_cpu_unit_code_func ()
{
int i;
struct unit_decl **units;
fprintf (output_file, "int\n%s (%s)\n\tconst char *%s;\n",
GET_CPU_UNIT_CODE_FUNC_NAME, CPU_UNIT_NAME_PARAMETER_NAME,
CPU_UNIT_NAME_PARAMETER_NAME);
fprintf (output_file, "{\n struct %s {const char *%s; int %s;};\n",
NAME_CODE_STRUCT_NAME, NAME_MEMBER_NAME, CODE_MEMBER_NAME);
fprintf (output_file, " int %s, %s, %s, %s;\n", CMP_VARIABLE_NAME,
LOW_VARIABLE_NAME, MIDDLE_VARIABLE_NAME, HIGH_VARIABLE_NAME);
fprintf (output_file, " static struct %s %s [] =\n {\n",
NAME_CODE_STRUCT_NAME, NAME_CODE_TABLE_NAME);
units = (struct unit_decl **) xmalloc (sizeof (struct unit_decl *)
* description->units_num);
memcpy (units, units_array,
sizeof (struct unit_decl *) * description->units_num);
qsort (units, description->units_num,
sizeof (struct unit_decl *), units_cmp);
for (i = 0; i < description->units_num; i++)
if (units [i]->query_p)
fprintf (output_file, " {\"%s\", %d},\n",
units[i]->name, units[i]->query_num);
fprintf (output_file, " };\n\n");
fprintf (output_file, " /* The following is binary search: */\n");
fprintf (output_file, " %s = 0;\n", LOW_VARIABLE_NAME);
fprintf (output_file, " %s = sizeof (%s) / sizeof (struct %s) - 1;\n",
HIGH_VARIABLE_NAME, NAME_CODE_TABLE_NAME, NAME_CODE_STRUCT_NAME);
fprintf (output_file, " while (%s <= %s)\n {\n",
LOW_VARIABLE_NAME, HIGH_VARIABLE_NAME);
fprintf (output_file, " %s = (%s + %s) / 2;\n",
MIDDLE_VARIABLE_NAME, LOW_VARIABLE_NAME, HIGH_VARIABLE_NAME);
fprintf (output_file, " %s = strcmp (%s, %s [%s].%s);\n",
CMP_VARIABLE_NAME, CPU_UNIT_NAME_PARAMETER_NAME,
NAME_CODE_TABLE_NAME, MIDDLE_VARIABLE_NAME, NAME_MEMBER_NAME);
fprintf (output_file, " if (%s < 0)\n", CMP_VARIABLE_NAME);
fprintf (output_file, " %s = %s - 1;\n",
HIGH_VARIABLE_NAME, MIDDLE_VARIABLE_NAME);
fprintf (output_file, " else if (%s > 0)\n", CMP_VARIABLE_NAME);
fprintf (output_file, " %s = %s + 1;\n",
LOW_VARIABLE_NAME, MIDDLE_VARIABLE_NAME);
fprintf (output_file, " else\n");
fprintf (output_file, " return %s [%s].%s;\n }\n",
NAME_CODE_TABLE_NAME, MIDDLE_VARIABLE_NAME, CODE_MEMBER_NAME);
fprintf (output_file, " return -1;\n}\n\n");
free (units);
}
/* The following function outputs function to check reservation of cpu
unit (its internal code will be passed as the function argument) in
given cpu state. */
static void
output_cpu_unit_reservation_p ()
{
struct automaton *curr_automaton;
fprintf (output_file, "int\n%s (%s, %s)\n\t%s %s;\n\tint %s;\n",
CPU_UNIT_RESERVATION_P_FUNC_NAME, STATE_NAME,
CPU_CODE_PARAMETER_NAME, STATE_TYPE_NAME, STATE_NAME,
CPU_CODE_PARAMETER_NAME);
fprintf (output_file, "{\n if (%s < 0 || %s >= %d)\n abort ();\n",
CPU_CODE_PARAMETER_NAME, CPU_CODE_PARAMETER_NAME,
description->query_units_num);
for (curr_automaton = description->first_automaton;
curr_automaton != NULL;
curr_automaton = curr_automaton->next_automaton)
{
fprintf (output_file, " if ((");
output_reserved_units_table_name (output_file, curr_automaton);
fprintf (output_file, " [((struct %s *) %s)->", CHIP_NAME, STATE_NAME);
output_chip_member_name (output_file, curr_automaton);
fprintf (output_file, " * %d + %s / 8] >> (%s %% 8)) & 1)\n",
(description->query_units_num + 7) / 8,
CPU_CODE_PARAMETER_NAME, CPU_CODE_PARAMETER_NAME);
fprintf (output_file, " return 1;\n");
}
fprintf (output_file, " return 0;\n}\n\n");
}
/* The function outputs PHR interface function `dfa_start'. */
static void
output_dfa_start_func ()
{
fprintf (output_file,
"void\n%s ()\n{\n int %s;\n int %s = get_max_uid ();\n\n",
DFA_START_FUNC_NAME, I_VARIABLE_NAME, TEMPORARY_VARIABLE_NAME);
fprintf (output_file, " %s = (int *) xmalloc (%s * sizeof (int));\n",
DFA_INSN_CODES_VARIABLE_NAME, TEMPORARY_VARIABLE_NAME);
fprintf (output_file,
" for (%s = 0; %s < %s; %s++)\n %s [%s] = -1;\n}\n\n",
I_VARIABLE_NAME, I_VARIABLE_NAME, TEMPORARY_VARIABLE_NAME,
I_VARIABLE_NAME, DFA_INSN_CODES_VARIABLE_NAME, I_VARIABLE_NAME);
}
/* The function outputs PHR interface function `dfa_finish'. */
static void
output_dfa_finish_func ()
{
fprintf (output_file, "void\n%s ()\n{\n free (%s);\n}\n\n",
DFA_FINISH_FUNC_NAME, DFA_INSN_CODES_VARIABLE_NAME);
}
/* The page contains code for output description file (readable
representation of original description and generated DFA(s). */
/* The function outputs string representation of IR reservation. */
static void
output_regexp (regexp)
struct regexp *regexp;
{
fprintf (output_description_file, "%s", regexp_representation (regexp));
finish_regexp_representation ();
}
/* Output names of units in LIST separated by comma. */
static void
output_unit_set_el_list (list)
struct unit_set_el *list;
{
struct unit_set_el *curr_el;
for (curr_el = list; curr_el != NULL; curr_el = curr_el->next_unit_set_el)
{
if (curr_el != list)
fprintf (output_description_file, ",");
fprintf (output_description_file, "%s", curr_el->unit_decl->name);
}
}
/* The function outputs string representation of IR define_reservation
and define_insn_reservation. */
static void
output_description ()
{
struct decl *curr_decl;
int i;
for (i = 0; i < description->decls_num; i++)
{
curr_decl = description->decls [i];
if (curr_decl->mode == dm_unit)
{
if (curr_decl->decl.unit.excl_list != NULL)
{
fprintf (output_description_file, "unit %s exlusion_set: ",
curr_decl->decl.unit.name);
output_unit_set_el_list (curr_decl->decl.unit.excl_list);
fprintf (output_description_file, "\n");
}
if (curr_decl->decl.unit.presence_list != NULL)
{
fprintf (output_description_file, "unit %s presence_set: ",
curr_decl->decl.unit.name);
output_unit_set_el_list (curr_decl->decl.unit.presence_list);
fprintf (output_description_file, "\n");
}
if (curr_decl->decl.unit.absence_list != NULL)
{
fprintf (output_description_file, "unit %s absence_set: ",
curr_decl->decl.unit.name);
output_unit_set_el_list (curr_decl->decl.unit.absence_list);
fprintf (output_description_file, "\n");
}
}
}
fprintf (output_description_file, "\n");
for (i = 0; i < description->decls_num; i++)
{
curr_decl = description->decls [i];
if (curr_decl->mode == dm_reserv)
{
fprintf (output_description_file, "reservation ");
fprintf (output_description_file, curr_decl->decl.reserv.name);
fprintf (output_description_file, ": ");
output_regexp (curr_decl->decl.reserv.regexp);
fprintf (output_description_file, "\n");
}
else if (curr_decl->mode == dm_insn_reserv
&& curr_decl != advance_cycle_insn_decl)
{
fprintf (output_description_file, "insn reservation %s ",
curr_decl->decl.insn_reserv.name);
print_rtl (output_description_file,
curr_decl->decl.insn_reserv.condexp);
fprintf (output_description_file, ": ");
output_regexp (curr_decl->decl.insn_reserv.regexp);
fprintf (output_description_file, "\n");
}
else if (curr_decl->mode == dm_bypass)
fprintf (output_description_file, "bypass %d %s %s\n",
curr_decl->decl.bypass.latency,
curr_decl->decl.bypass.out_insn_name,
curr_decl->decl.bypass.in_insn_name);
}
fprintf (output_description_file, "\n\f\n");
}
/* The function outputs name of AUTOMATON. */
static void
output_automaton_name (f, automaton)
FILE *f;
struct automaton *automaton;
{
if (automaton->corresponding_automaton_decl == NULL)
fprintf (f, "#%d", automaton->automaton_order_num);
else
fprintf (f, "`%s'", automaton->corresponding_automaton_decl->name);
}
/* Maximal length of line for pretty printing into description
file. */
#define MAX_LINE_LENGTH 70
/* The function outputs units name belonging to AUTOMATON. */
static void
output_automaton_units (automaton)
struct automaton *automaton;
{
struct decl *curr_decl;
char *name;
int curr_line_length;
int there_is_an_automaton_unit;
int i;
fprintf (output_description_file, "\n Coresponding units:\n");
fprintf (output_description_file, " ");
curr_line_length = 4;
there_is_an_automaton_unit = FALSE;
for (i = 0; i < description->decls_num; i++)
{
curr_decl = description->decls [i];
if (curr_decl->mode == dm_unit
&& (curr_decl->decl.unit.corresponding_automaton_num
== automaton->automaton_order_num))
{
there_is_an_automaton_unit = TRUE;
name = curr_decl->decl.unit.name;
if (curr_line_length + strlen (name) + 1 > MAX_LINE_LENGTH )
{
curr_line_length = strlen (name) + 4;
fprintf (output_description_file, "\n ");
}
else
{
curr_line_length += strlen (name) + 1;
fprintf (output_description_file, " ");
}
fprintf (output_description_file, name);
}
}
if (!there_is_an_automaton_unit)
fprintf (output_description_file, "<None>");
fprintf (output_description_file, "\n\n");
}
/* The following variable is used for forming array of all possible cpu unit
reservations described by the current DFA state. */
static vla_ptr_t state_reservs;
/* The function forms `state_reservs' for STATE. */
static void
add_state_reservs (state)
struct state *state;
{
struct alt_state *curr_alt_state;
reserv_sets_t reservs;
if (state->component_states != NULL)
for (curr_alt_state = state->component_states;
curr_alt_state != NULL;
curr_alt_state = curr_alt_state->next_sorted_alt_state)
add_state_reservs (curr_alt_state->state);
else
{
reservs = state->reservs;
VLA_PTR_ADD (state_reservs, reservs);
}
}
/* The function outputs readable represenatation of all out arcs of
STATE. */
static void
output_state_arcs (state)
struct state *state;
{
struct arc *curr_arc;
struct ainsn *curr_ainsn;
char *insn_name;
int curr_line_length;
for (curr_arc = first_out_arc (state);
curr_arc != NULL;
curr_arc = next_out_arc (curr_arc))
{
curr_ainsn = curr_arc->insn;
assert (curr_ainsn->first_insn_with_same_reservs);
fprintf (output_description_file, " ");
curr_line_length = 7;
fprintf (output_description_file, "%2d: ",
curr_ainsn->insn_equiv_class_num);
do
{
insn_name = curr_ainsn->insn_reserv_decl->name;
if (curr_line_length + strlen (insn_name) > MAX_LINE_LENGTH)
{
if (curr_ainsn != curr_arc->insn)
{
fprintf (output_description_file, ",\n ");
curr_line_length = strlen (insn_name) + 6;
}
else
curr_line_length += strlen (insn_name);
}
else
{
curr_line_length += strlen (insn_name);
if (curr_ainsn != curr_arc->insn)
{
curr_line_length += 2;
fprintf (output_description_file, ", ");
}
}
fprintf (output_description_file, insn_name);
curr_ainsn = curr_ainsn->next_same_reservs_insn;
}
while (curr_ainsn != NULL);
fprintf (output_description_file, " %d (%d)\n",
curr_arc->to_state->order_state_num,
curr_arc->state_alts);
}
fprintf (output_description_file, "\n");
}
/* The following function is used for sorting possible cpu unit
reservation of a DFA state. */
static int
state_reservs_cmp (reservs_ptr_1, reservs_ptr_2)
const void *reservs_ptr_1;
const void *reservs_ptr_2;
{
return reserv_sets_cmp (*(reserv_sets_t *) reservs_ptr_1,
*(reserv_sets_t *) reservs_ptr_2);
}
/* The following function is used for sorting possible cpu unit
reservation of a DFA state. */
static void
remove_state_duplicate_reservs ()
{
reserv_sets_t *curr_reservs_ptr;
reserv_sets_t *last_formed_reservs_ptr;
last_formed_reservs_ptr = NULL;
for (curr_reservs_ptr = VLA_PTR_BEGIN (state_reservs);
curr_reservs_ptr <= (reserv_sets_t *) VLA_PTR_LAST (state_reservs);
curr_reservs_ptr++)
if (last_formed_reservs_ptr == NULL)
last_formed_reservs_ptr = curr_reservs_ptr;
else if (reserv_sets_cmp (*last_formed_reservs_ptr, *curr_reservs_ptr)
!= 0)
{
++last_formed_reservs_ptr;
*last_formed_reservs_ptr = *curr_reservs_ptr;
}
VLA_PTR_SHORTEN (state_reservs,
curr_reservs_ptr - last_formed_reservs_ptr - 1);
}
/* The following function output readable representation of DFA(s)
state used for fast recognition of pipeline hazards. State is
described by possible (current and scehduled) cpu unit
reservations. */
static void
output_state (state)
struct state *state;
{
reserv_sets_t *curr_reservs_ptr;
VLA_PTR_CREATE (state_reservs, 150, "state reservations");
fprintf (output_description_file, " State #%d", state->order_state_num);
fprintf (output_description_file,
state->new_cycle_p ? " (new cycle)\n" : "\n");
add_state_reservs (state);
qsort (VLA_PTR_BEGIN (state_reservs), VLA_PTR_LENGTH (state_reservs),
sizeof (reserv_sets_t), state_reservs_cmp);
remove_state_duplicate_reservs ();
for (curr_reservs_ptr = VLA_PTR_BEGIN (state_reservs);
curr_reservs_ptr <= (reserv_sets_t *) VLA_PTR_LAST (state_reservs);
curr_reservs_ptr++)
{
fprintf (output_description_file, " ");
output_reserv_sets (output_description_file, *curr_reservs_ptr);
fprintf (output_description_file, "\n");
}
fprintf (output_description_file, "\n");
output_state_arcs (state);
VLA_PTR_DELETE (state_reservs);
}
/* The following function output readable representation of
DFAs used for fast recognition of pipeline hazards. */
static void
output_automaton_descriptions ()
{
struct automaton *curr_automaton;
for (curr_automaton = description->first_automaton;
curr_automaton != NULL;
curr_automaton = curr_automaton->next_automaton)
{
fprintf (output_description_file, "\nAutomaton ");
output_automaton_name (output_description_file, curr_automaton);
fprintf (output_description_file, "\n");
output_automaton_units (curr_automaton);
pass_states (curr_automaton, output_state);
}
}
/* The page contains top level function for generation DFA(s) used for
PHR. */
/* The function outputs statistics about work of different phases of
DFA generator. */
static void
output_statistics (f)
FILE *f;
{
struct automaton *curr_automaton;
#ifndef NDEBUG
int transition_comb_vect_els = 0;
int transition_full_vect_els = 0;
int state_alts_comb_vect_els = 0;
int state_alts_full_vect_els = 0;
int min_issue_delay_vect_els = 0;
#endif
for (curr_automaton = description->first_automaton;
curr_automaton != NULL;
curr_automaton = curr_automaton->next_automaton)
{
fprintf (f, "\nAutomaton ");
output_automaton_name (f, curr_automaton);
fprintf (f, "\n %5d NDFA states, %5d NDFA arcs\n",
curr_automaton->NDFA_states_num, curr_automaton->NDFA_arcs_num);
fprintf (f, " %5d DFA states, %5d DFA arcs\n",
curr_automaton->DFA_states_num, curr_automaton->DFA_arcs_num);
if (!no_minimization_flag)
fprintf (f, " %5d minimal DFA states, %5d minimal DFA arcs\n",
curr_automaton->minimal_DFA_states_num,
curr_automaton->minimal_DFA_arcs_num);
fprintf (f, " %5d all insns %5d insn equivalence classes\n",
description->insns_num, curr_automaton->insn_equiv_classes_num);
#ifndef NDEBUG
fprintf
(f, "%5ld transition comb vector els, %5ld trans table els: %s\n",
(long) VLA_HWINT_LENGTH (curr_automaton->trans_table->comb_vect),
(long) VLA_HWINT_LENGTH (curr_automaton->trans_table->full_vect),
(comb_vect_p (curr_automaton->trans_table)
? "use comb vect" : "use simple vect"));
fprintf
(f, "%5ld state alts comb vector els, %5ld state alts table els: %s\n",
(long) VLA_HWINT_LENGTH (curr_automaton->state_alts_table->comb_vect),
(long) VLA_HWINT_LENGTH (curr_automaton->state_alts_table->full_vect),
(comb_vect_p (curr_automaton->state_alts_table)
? "use comb vect" : "use simple vect"));
fprintf
(f, "%5ld min delay table els, compression factor %d\n",
(long) curr_automaton->DFA_states_num
* curr_automaton->insn_equiv_classes_num,
curr_automaton->min_issue_delay_table_compression_factor);
transition_comb_vect_els
+= VLA_HWINT_LENGTH (curr_automaton->trans_table->comb_vect);
transition_full_vect_els
+= VLA_HWINT_LENGTH (curr_automaton->trans_table->full_vect);
state_alts_comb_vect_els
+= VLA_HWINT_LENGTH (curr_automaton->state_alts_table->comb_vect);
state_alts_full_vect_els
+= VLA_HWINT_LENGTH (curr_automaton->state_alts_table->full_vect);
min_issue_delay_vect_els
+= (curr_automaton->DFA_states_num
* curr_automaton->insn_equiv_classes_num);
#endif
}
#ifndef NDEBUG
fprintf (f, "\n%5d all allocated states, %5d all allocated arcs\n",
allocated_states_num, allocated_arcs_num);
fprintf (f, "%5d all allocated alternative states\n",
allocated_alt_states_num);
fprintf (f, "%5d all transition comb vector els, %5d all trans table els\n",
transition_comb_vect_els, transition_full_vect_els);
fprintf
(f, "%5d all state alts comb vector els, %5d all state alts table els\n",
state_alts_comb_vect_els, state_alts_full_vect_els);
fprintf (f, "%5d all min delay table els\n", min_issue_delay_vect_els);
fprintf (f, "%5d locked states num\n", locked_states_num);
#endif
}
/* The function output times of work of different phases of DFA
generator. */
static void
output_time_statistics (f)
FILE *f;
{
fprintf (f, "\n transformation: ");
print_active_time (f, transform_time);
fprintf (f, (!ndfa_flag ? ", building DFA: " : ", building NDFA: "));
print_active_time (f, NDFA_time);
if (ndfa_flag)
{
fprintf (f, ", NDFA -> DFA: ");
print_active_time (f, NDFA_to_DFA_time);
}
fprintf (f, "\n DFA minimization: ");
print_active_time (f, minimize_time);
fprintf (f, ", making insn equivalence: ");
print_active_time (f, equiv_time);
fprintf (f, "\n all automaton generation: ");
print_active_time (f, automaton_generation_time);
fprintf (f, ", output: ");
print_active_time (f, output_time);
fprintf (f, "\n");
}
/* The function generates DFA (deterministic finate state automaton)
for fast recognition of pipeline hazards. No errors during
checking must be fixed before this function call. */
static void
generate ()
{
automata_num = split_argument;
if (description->units_num < automata_num)
automata_num = description->units_num;
initiate_states ();
initiate_arcs ();
initiate_pass_states ();
initiate_excl_sets ();
initiate_presence_absence_sets ();
automaton_generation_time = create_ticker ();
transform_time = create_ticker ();
add_advance_cycle_insn_decl ();
transform_insn_regexps ();
ticker_off (&transform_time);
create_automata ();
ticker_off (&automaton_generation_time);
}
/* The following function creates attribute which order number of insn
in pipeline hazard description translator. */
static void
make_insn_alts_attr ()
{
int i, insn_num;
struct decl *curr_decl;
rtx condexp;
condexp = rtx_alloc (COND);
XVEC (condexp, 0) = rtvec_alloc ((description->insns_num - 1) * 2);
XEXP (condexp, 1) = make_numeric_value (0);
for (i = insn_num = 0; i < description->decls_num; i++)
{
curr_decl = description->decls [i];
if (curr_decl->mode == dm_insn_reserv
&& curr_decl != advance_cycle_insn_decl)
{
XVECEXP (condexp, 0, 2 * insn_num)
= curr_decl->decl.insn_reserv.condexp;
XVECEXP (condexp, 0, 2 * insn_num + 1)
= make_numeric_value (curr_decl->decl.insn_reserv
.transformed_regexp
->regexp.oneof.regexps_num);
insn_num++;
}
}
assert (description->insns_num == insn_num + 1);
make_internal_attr (attr_printf (sizeof ("*")
+ strlen (INSN_ALTS_FUNC_NAME) + 1,
"*%s", INSN_ALTS_FUNC_NAME),
condexp, 0);
}
/* The following function creates attribute which is order number of
insn in pipeline hazard description translator. */
static void
make_internal_dfa_insn_code_attr ()
{
int i, insn_num;
struct decl *curr_decl;
rtx condexp;
condexp = rtx_alloc (COND);
XVEC (condexp, 0) = rtvec_alloc ((description->insns_num - 1) * 2);
XEXP (condexp, 1) = make_numeric_value (advance_cycle_insn_decl
->decl.insn_reserv.insn_num + 1);
for (i = insn_num = 0; i < description->decls_num; i++)
{
curr_decl = description->decls [i];
if (curr_decl->mode == dm_insn_reserv
&& curr_decl != advance_cycle_insn_decl)
{
XVECEXP (condexp, 0, 2 * insn_num)
= curr_decl->decl.insn_reserv.condexp;
XVECEXP (condexp, 0, 2 * insn_num + 1)
= make_numeric_value (curr_decl->decl.insn_reserv.insn_num);
insn_num++;
}
}
assert (description->insns_num == insn_num + 1);
make_internal_attr
(attr_printf (sizeof ("*")
+ strlen (INTERNAL_DFA_INSN_CODE_FUNC_NAME) + 1,
"*%s", INTERNAL_DFA_INSN_CODE_FUNC_NAME),
condexp, 0);
}
/* The following function creates attribute which order number of insn
in pipeline hazard description translator. */
static void
make_default_insn_latency_attr ()
{
int i, insn_num;
struct decl *curr_decl;
rtx condexp;
condexp = rtx_alloc (COND);
XVEC (condexp, 0) = rtvec_alloc ((description->insns_num - 1) * 2);
XEXP (condexp, 1) = make_numeric_value (0);
for (i = insn_num = 0; i < description->decls_num; i++)
{
curr_decl = description->decls [i];
if (curr_decl->mode == dm_insn_reserv
&& curr_decl != advance_cycle_insn_decl)
{
XVECEXP (condexp, 0, 2 * insn_num)
= curr_decl->decl.insn_reserv.condexp;
XVECEXP (condexp, 0, 2 * insn_num + 1)
= make_numeric_value (curr_decl->decl.insn_reserv.default_latency);
insn_num++;
}
}
assert (description->insns_num == insn_num + 1);
make_internal_attr (attr_printf (sizeof ("*")
+ strlen (INSN_DEFAULT_LATENCY_FUNC_NAME)
+ 1, "*%s", INSN_DEFAULT_LATENCY_FUNC_NAME),
condexp, 0);
}
/* The following function creates attribute which returns 1 if given
output insn has bypassing and 0 otherwise. */
static void
make_bypass_attr ()
{
int i, bypass_insn;
int bypass_insns = 0;
struct decl *curr_decl;
rtx result_rtx;
for (i = 0; i < description->decls_num; i++)
{
curr_decl = description->decls [i];
if (curr_decl->mode == dm_insn_reserv
&& curr_decl->decl.insn_reserv.condexp != NULL
&& curr_decl->decl.insn_reserv.bypass_list != NULL)
bypass_insns++;
}
if (bypass_insns == 0)
result_rtx = make_numeric_value (0);
else
{
result_rtx = rtx_alloc (COND);
XVEC (result_rtx, 0) = rtvec_alloc (bypass_insns * 2);
XEXP (result_rtx, 1) = make_numeric_value (0);
for (i = bypass_insn = 0; i < description->decls_num; i++)
{
curr_decl = description->decls [i];
if (curr_decl->mode == dm_insn_reserv
&& curr_decl->decl.insn_reserv.condexp != NULL
&& curr_decl->decl.insn_reserv.bypass_list != NULL)
{
XVECEXP (result_rtx, 0, 2 * bypass_insn)
= curr_decl->decl.insn_reserv.condexp;
XVECEXP (result_rtx, 0, 2 * bypass_insn + 1)
= make_numeric_value (1);
bypass_insn++;
}
}
}
make_internal_attr (attr_printf (sizeof ("*")
+ strlen (BYPASS_P_FUNC_NAME) + 1,
"*%s", BYPASS_P_FUNC_NAME),
result_rtx, 0);
}
/* This page mainly contains top level functions of pipeline hazards
description translator. */
/* The following macro value is suffix of name of description file of
pipeline hazards description translator. */
#define STANDARD_OUTPUT_DESCRIPTION_FILE_SUFFIX ".dfa"
/* The function returns suffix of given file name. The returned
string can not be changed. */
static const char *
file_name_suffix (file_name)
const char *file_name;
{
const char *last_period;
for (last_period = NULL; *file_name != '\0'; file_name++)
if (*file_name == '.')
last_period = file_name;
return (last_period == NULL ? file_name : last_period);
}
/* The function returns base name of given file name, i.e. pointer to
first char after last `/' (or `\' for WIN32) in given file name,
given file name itself if the directory name is absent. The
returned string can not be changed. */
static const char *
base_file_name (file_name)
const char *file_name;
{
int directory_name_length;
directory_name_length = strlen (file_name);
#ifdef WIN32
while (directory_name_length >= 0 && file_name[directory_name_length] != '/'
&& file_name[directory_name_length] != '\\')
#else
while (directory_name_length >= 0 && file_name[directory_name_length] != '/')
#endif
directory_name_length--;
return file_name + directory_name_length + 1;
}
/* The following is top level function to initialize the work of
pipeline hazards description translator. */
static void
initiate_automaton_gen (argc, argv)
int argc;
char **argv;
{
const char *base_name;
int i;
ndfa_flag = FALSE;
split_argument = 0; /* default value */
no_minimization_flag = FALSE;
time_flag = FALSE;
v_flag = FALSE;
w_flag = FALSE;
for (i = 2; i < argc; i++)
if (strcmp (argv [i], NO_MINIMIZATION_OPTION) == 0)
no_minimization_flag = TRUE;
else if (strcmp (argv [i], "-time") == 0)
time_flag = TRUE;
else if (strcmp (argv [i], "-v") == 0)
v_flag = TRUE;
else if (strcmp (argv [i], W_OPTION) == 0)
w_flag = TRUE;
else if (strcmp (argv [i], NDFA_OPTION) == 0)
ndfa_flag = TRUE;
else if (strcmp (argv [i], "-split") == 0)
{
if (i + 1 >= argc)
fatal ("-split has no argument.");
fatal ("option `-split' has not been implemented yet\n");
/* split_argument = atoi (argument_vect [i + 1]); */
}
VLA_PTR_CREATE (decls, 150, "decls");
IR_START_ALLOC ();
initiate_automaton_decl_table ();
initiate_insn_decl_table ();
initiate_decl_table ();
output_file = stdout;
output_description_file = NULL;
base_name = base_file_name (argv[1]);
IR_TOP_ADD_MEMORY (base_name,
strlen (base_name)
- strlen (file_name_suffix (base_name)));
IR_TOP_ADD_STRING (STANDARD_OUTPUT_DESCRIPTION_FILE_SUFFIX);
IR_TOP_ADD_BYTE ('\0');
output_description_file_name = IR_TOP_BEGIN ();
IR_TOP_FINISH ();
}
/* The following function checks existence at least one arc marked by
each insn. */
static void
check_automata ()
{
struct automaton *curr_automaton;
struct ainsn *ainsn, *curr_ainsn;
for (curr_automaton = description->first_automaton;
curr_automaton != NULL;
curr_automaton = curr_automaton->next_automaton)
{
for (ainsn = curr_automaton->ainsn_list;
ainsn != NULL;
ainsn = ainsn->next_ainsn)
if (ainsn->first_insn_with_same_reservs && !ainsn->arc_exists_p)
{
for (curr_ainsn = ainsn;
curr_ainsn != NULL;
curr_ainsn = curr_ainsn->next_same_reservs_insn)
if (curr_automaton->corresponding_automaton_decl != NULL)
{
if (!w_flag)
error ("Automaton `%s': Insn `%s' will never be issued",
curr_automaton->corresponding_automaton_decl->name,
curr_ainsn->insn_reserv_decl->name);
else
warning
("Automaton `%s': Insn `%s' will never be issued",
curr_automaton->corresponding_automaton_decl->name,
curr_ainsn->insn_reserv_decl->name);
}
else
{
if (!w_flag)
error ("Insn `%s' will never be issued",
curr_ainsn->insn_reserv_decl->name);
else
warning ("Insn `%s' will never be issued",
curr_ainsn->insn_reserv_decl->name);
}
}
}
}
/* The following is top level function to generate automat(a,on) for
fast recognition of pipeline hazards. */
static void
expand_automata ()
{
int i;
if (VLA_PTR_LENGTH (decls) != 0)
{
description = create_node (sizeof (struct description)
+ sizeof (struct decl *)
/* One entry for cycle advancing insn. */
* VLA_PTR_LENGTH (decls));
description->decls_num = VLA_PTR_LENGTH (decls);
description->query_units_num = 0;
for (i = 0; i < description->decls_num; i++)
{
description->decls [i] = VLA_PTR (decls, i);
if (description->decls [i]->mode == dm_unit
&& description->decls [i]->decl.unit.query_p)
description->decls [i]->decl.unit.query_num
= description->query_units_num++;
}
all_time = create_ticker ();
check_time = create_ticker ();
check_all_description ();
ticker_off (&check_time);
generation_time = create_ticker ();
if (!have_error)
{
generate ();
check_automata ();
if (!have_error)
{
make_internal_dfa_insn_code_attr ();
make_insn_alts_attr ();
make_default_insn_latency_attr ();
make_bypass_attr ();
}
}
ticker_off (&generation_time);
ticker_off (&all_time);
}
}
/* The following is top level function to output PHR and to finish
work with pipeline description translator. */
static void
write_automata ()
{
if (have_error)
fatal ("Errors in DFA description");
ticker_on (&all_time);
output_time = create_ticker ();
output_tables ();
output_chip_definitions ();
output_max_insn_queue_index_def ();
output_internal_min_issue_delay_func ();
output_internal_trans_func ();
/* Cache of insn dfa codes: */
fprintf (output_file, "\nstatic int *%s;\n\n", DFA_INSN_CODES_VARIABLE_NAME);
output_dfa_insn_code_func ();
output_trans_func ();
fprintf (output_file, "\n#if %s\n\n", AUTOMATON_STATE_ALTS_MACRO_NAME);
output_internal_state_alts_func ();
output_state_alts_func ();
fprintf (output_file, "\n#endif /* #if %s */\n\n",
AUTOMATON_STATE_ALTS_MACRO_NAME);
output_min_issue_delay_func ();
output_internal_dead_lock_func ();
output_dead_lock_func ();
output_size_func ();
output_internal_reset_func ();
output_reset_func ();
output_min_insn_conflict_delay_func ();
output_internal_insn_latency_func ();
output_insn_latency_func ();
output_print_reservation_func ();
if (no_minimization_flag)
{
fprintf (output_file, "\n#if %s\n\n", CPU_UNITS_QUERY_MACRO_NAME);
output_get_cpu_unit_code_func ();
output_cpu_unit_reservation_p ();
fprintf (output_file, "\n#endif /* #if %s */\n\n",
CPU_UNITS_QUERY_MACRO_NAME);
}
output_dfa_start_func ();
output_dfa_finish_func ();
if (v_flag)
{
output_description_file = fopen (output_description_file_name, "w");
if (output_description_file == NULL)
{
perror (output_description_file_name);
exit (FATAL_EXIT_CODE);
}
output_description ();
output_automaton_descriptions ();
output_statistics (output_description_file);
}
output_statistics (stderr);
ticker_off (&output_time);
output_time_statistics (stderr);
finish_states ();
finish_arcs ();
if (time_flag)
{
fprintf (stderr, "Summary:\n");
fprintf (stderr, " check time ");
print_active_time (stderr, check_time);
fprintf (stderr, ", generation time ");
print_active_time (stderr, generation_time);
fprintf (stderr, ", all time ");
print_active_time (stderr, all_time);
fprintf (stderr, "\n");
}
/* Finish all work. */
if (output_description_file != NULL)
{
fflush (output_description_file);
if (ferror (stdout) != 0)
fatal ("Error in writing DFA description file %s",
output_description_file_name);
fclose (output_description_file);
}
finish_automaton_decl_table ();
finish_insn_decl_table ();
finish_decl_table ();
IR_STOP_ALLOC();
if (have_error && output_description_file != NULL)
remove (output_description_file_name);
}