[Libre-soc-bugs] [Bug 550] binutils support needed for svp64

[bugzilla-daemon at libre-soc.org]

https://bugs.libre-soc.org/show_bug.cgi?id=550

--- Comment #69 from Luke Kenneth Casson Leighton <lkcl at lkcl.net> ---
(In reply to dmitry.selyutin from comment #68)

> OK, so we both agree that there must be at least _some_ array, even if this
> array contains only uint64_t (I doubt, though: there must be at least
> something which binds svp64 entry and ppc opcode, be it instruction name or
> opcode itself).

errr oh yes, you're right: instruction name (as an ascii string) followed
by uint64_t.  doh.

> > there should not be a list of 10,000 entries like in binutils,
> > that would be insane and also tie the codegenerator to the state
> > of binutils.
> 
> 283 entries totally. :-)

fuuun

> > my thoughts here were to have an empty (0x0) value in the binutils
> > table (struct ppc_something) QTY 10,000 and, deep breath, when
> > creating the hashtable in binutils to at that
> > time *also* make a lookup for the corresponding
> > svp64 entry and fill in the empty field.
> 
> I thought of standalone hash but I think that's mostly implementation detail.

true.  my thoughts there were that the lexicographical O(N) trick during
actual creating of the ppc_something binutils hashtree would avoid the
need for a standalone hash.

and, also, avoid the CPU cycles of double hashtree lookups, which has
to be taken into consideration due to the sheer overwhelming size of
executables these days.

> > the 10000 binutils entries and the 200-or-so svp64 
> > entries are in strict alphabetical order then the LEFT JOIN
> > algorithm is O(N) because a lexicographic comparison can
> > simply increment each list index by one.
> 
> PPC entries are alphabetically ordered, inevitably, so will be ours due to
> the same rationale. :-) 

ah superb.  so yes, a LEFT-JOIN style trick relying on lexicographic order
would work.  the only thing being, names need to match without the "o"
"." and "o." on them (or, re-create those names).

> There's no comparison or sorting yet in Python, but
> yes, this is needed. Again, not sure if we need to touch existing structures
> by adding the pointer, I'd rather prefer a separate stuff to keep the code
> as decoupled as possible.

high performance in binutils is essential, and having double hashtable lookups
would likely raise legitimate complaints.

plus, by doing a LEFT-JOIN-like merge, that is only done once [and is
pretty optimal as long as the two lists are pre-sorted], whereas double
hashtable lookups are on every single instruction.

-- 
You are receiving this mail because:
You are on the CC list for the bug.