Re: query automaton

[Vladimir Makarov <vmakarov at redhat dot com>]

Alex Turjan wrote:
> Vladimir thanks for help!
>
> With respect to your answer I would like to point to you a possible way to solve the scheduling problem 
> (which I think wont be too difficult to be implemented in genautomata). 
>
>   
Alex, thanks for sharing your thoughts.  I also thought about this a few 
years ago when I tried to implement automatic splitting of original 
automaton.  In this case we could rid off define_automata construction 
but I see that it would be a sacrifice in debugging automaton as your 
proposal (because automatic generation of automata and fake instructions 
in <target_name>.dfa file could be confusing for people).  On the other 
hand people might be confused about rules to assign units to automata.

I would not say your proposal will be easy to implement.  I'd evaluate 
it as 2-3 weeks of additional work to a patch I am working on.   I 
recently practically finished this patch checking the correctness of 
assigning functional units to automata.  This code could be used to 
implement your proposal (to check when we need insn_reservation 
splitting).  I found only three incorrect target automata:

m68k (coldfire)
power4
power5

The first description can be easily corrected by removing one 
automaton.  The last two required more changes because removing automata 
does not permit to create reasonable size automata.  Power5 description 
changes did not result in different code generation (at least on 
SPEC2000).  Power4 changes result in different code generation but 
practically the same SPEC scores.

So I'll stop on this patch for now and put your proposal on my TODO list 
because it has some merits.

Splitting automaton is a complicated issue and it needs some research.  
Rubin (see reference to articles in genautomata.c) did this but only  
for automaton generated from regexps without alternatives.  GCC is the 
first compiler which permits alternatives (and even their 
non-deterministic treatment).  I also thought about more advanced models 
than DFA and NDFA to describe more sophisticated pipeline hazards (as 
hidden registers for renaming or different insn queues  constraints in 
OOO processors) but I think the current model already achieved a good 
balance of complexity description and its outcome for insn scheduler.  
All these areas are good for research if somebody wants to do a research.

> To explain it, I will make use of the âmove insnâ example pointed in the previous email. 
> First of all I do not change anything in the 2 automatons (aut1 and aut2); they are correctly built by the genautomata. 
> Next to the original 
>   
> > (define_reservation "move"  "(  (unit1_aut1, unit1_aut2) |              
> >                                                    (unit2_aut1, unit2_aut2)  ) 
> >     
>
> I define two separate fake move instructions (i.e., âmove_fake1â and âmove_fake2â) of which semantic does play any role; each of them
> having a unit reservation one of the alternatives of the âmoveâ:
>
> (define_reservation "move_fake1"  "( (unit1_aut1, unit1_aut2)), and 
> (define_reservation "move_fake2"  "( (unit2_aut1, unit2_aut2) ).
>
> Those two extra moves are then used during the sched2 target hook TARGET_SCHED_DFA_NEW_CYCLE to decide which of the move alternative unit reservations can be correctly claimed.
> Suppose the ready instruction is a âmoveâ.
> First I make 2 copies of the current state: temp_state1 and temp_state2.
> Then I check which of the two fake moves ( âmove_fake1â and âmove_fake2â) with different unit occupation can be issued at the current state:
> cost_move_fake1 = internal_state_transition (insn_code_move_fake1, temp_state1);
> cost_move_fake2 = internal_state_transition (insn_code_move_fake2, temp_state2);
>
> Once I find the correct choice (suppose cost_move_fake1 <0),  I set dfa_insn_codes[] of the ready instruction to the one of  move_fake1.
>
>   int uid = INSN_UID (ready);
>      if (uid >= dfa_insn_codes_length)
>     dfa_insn_code_enlarge (uid);   
>     dfa_insn_codes[uid] = internal_dfa_insn_code (insn_code_move_fake1);
>
> In this way when the scheduler calls internal_state_transition, the ready instruction has been already set its dfa_insn_codes to a unit reservation schedulable in the current state.
>