On 07/18/2011 11:27 AM, Bernd Schmidt wrote:
On 07/18/11 17:09, Vladimir Makarov wrote:
On 07/11/2011 05:09 PM, Bernd Schmidt wrote:
I came up with the notion of adding a new transition to the NDFA, one
which collapses a nondeterministic state (which is composed of multiple
possible deterministic ones) to just one of its component states. This
can be done at the end of each cycle, and gives a state that can be
processed with cpu_unit_reservation_p to identify the units chosen by
the scheduler. The following patch implements this.
Bernd, sorry for the delay. I was on vacation last week.
No problem. A week is rapid :)
IA64 actually uses the two automata, one automaton can be considered
NDFA and is used for scheduling, another one can be considered as DFA
and used for insn bundling.
I should acknowledge your solution is not trivial and more elegant and
permitting to use smaller description.
It would be interesting to rewrite IA64 in your way. Although I think
it will be never done because it is nontrivial work to do and probably
better not to fix something when it already works.
I'd been wondering about whether it could be usable for things like
ia64, but I don't actually understand the ia64 scheduling description
very well... On ia64 there's the additional complication that
end-of-cycle and end-of-bundle don't always coincide.
Probably no one cares enough about this target anyway to attempt such
changes.
Yes, it is not such popular as it was when the description was written.
It is better not touch it if it is not broken.
On the other hand, coming in 2012 Poulson i64 processor which will be
12-wide (instead of 6 insns wide as current processors) will need a new
description. I think it could be an opportunity to rewrite the old one
too.
I'll probably also need another new option, "no_comb_vectors", as I have
a slight problem with this loop:
3884568992: 7379: for (comb_vect_index = 1, i = vect_length; i<
comb_vect_els_num;
3884508354: 7380: comb_vect_index++, i++)
-: 7381: {
3884508592: 7382: comb_vect_mask = (comb_vect_mask<< 1) | 1;
7769017184: 7383: comb_vect_mask ^= (VEC_index (vect_el_t,
tab->comb_vect, i)
-: 7384: == undefined_vect_el_value);
3884508592: 7385: if ((vect_mask& comb_vect_mask) == 0)
-: 7386: goto found;
-: 7387: }
(Those are the numbers _before_ I make the changes that explode the
compile time). Any objection in principle to such an option, or any
ideas how to optimize this code? Having a description of a "comb vector"
in genautomata.c would be a good idea; I think I've figured out what
it's supposed to do, but it's not immediately obvious.
Comb-vectors is a widely used compression table technique. It is used
in (f)lex, (b)yacc/bison and as I remember it is described in the Dragon
book.
There are a lot of compression table algorithms with different
characteristics compression ratio, compression speed, access time.
About 25 years ago I read an article overviewing about 30 such
algorithms. But I don't remember its name.
So I guess the alternative would be in usage of algorithm with the same
access time, compression ratio, and faster compression speed.
But I guess comb-vector is popular for a reason. We could tolerate slow
compression time because it is done once but worse compression and
slower access would have a really bad impact on the compiler time.
