llvm dev - Jul 2017 - [X86] Memory folding tables in x86 backend

Hi all,

Memory fold tables: Two way mapping of each register-form instruction to its
corresponding memory-form instruction. E.g. Mapping 'X86::ADD32rr' to
'X86::ADD32rm'.

Few months ago I started an effort to auto-generate the X86 memory folding
tables currently held under lib/Target/X86/X86InstInfo.cpp as huge
manually-maintained static arrays.
Automating the tables would reduce the maintenance burden for developers to
repeatedly update them with every new (foldable) instruction added to X86
backend, and would provide us with all the missing entries (mostly AVX512
instructions).

After considering different approaches for generating the tables, it was decided
that a TableGen backend would fit our needs the best, using the encoding
information of the instructions (from .td files) to apply the matching between
pairs.

Our main assumption was that two forms of the same instruction (register &
memory forms) must share the same encoding information except for the part
responsible for "How are the parameters passed to the instruction",
where one version defines one of its parameters to be a register while the other
version defines it to be a memory operand, and all other parameters passed the
same way in both versions.

Throughout the development of the backend, some exceptions were discovered. Some
instructions has different behavior in their register and memory forms, for
example, "bt" instruction (bit-test), which in its register form the
relevant bits of the register parameter are the first 4, 5 or 6 bits (depending
on mode and register size) while in the memory-folded instruction, the relevant
bits of the memory operand are the first 16, 32 or 64 bits.

A TableGen backend was created for this purpose and committed in
https://reviews.llvm.org/rL304088, including a small list of exceptions for
cases similar to the bit-test instruction above.

After the patch was committed, two more exceptions were found which led to
reverting the patch (https://reviews.llvm.org/rL304762).

Looking for safe-alternatives that will assure us correctness of each added
entry, we narrowed our options to the following 3:

1-     Recommitting TableGen's backend as "disable by default":

a-     prepare a full instruction list of the exceptions in X86 ISA.

b-     Mark these instructions with special flag to indicate illegal folding.

c-      Integrate the backend into llorg while disabling it by default.

d-     Provide a compile-time validation mechanism to make sure the pass does
not break (as it's not included in LLVM's build).

e-     Run the pass every defined period of time (1 week/2 weeks/1 month/2
months):

*        If changes appear (new entries):

-        Make sure the entries are legal.

-        If they are not, add them to the exception list.

*        If any changes made, commit them.



2-     Recommitting TableGen's backend while limiting the instructions to
AVX512 and earlier.

a-     prepare a full instruction list of the exceptions in X86 ISA.

b-     Mark these instructions with special flag to indicate illegal folding.

c-      Integrate the backend into llorg while limiting the generated
instructions to be part of AVX512 extension or earlier.

d-     If a new generation of instructions is added, go back to step
'a', and after we are sure everything is ok allow these instructions to
be tablegened.


3-     Give up on the auto-generation idea and manually update the current
tables iteratively with new chunks of instructions until full state is achieved.

P.s. The TableGen backend emits more than 5200 entries, while the known
exception at this point are ~20.

We prefer options #1/#2 as they remove the manual maintenance of these huge
tables where there is high potential of adding new bugs, and reduce it to a
one-man once-a-month/once for each new instruction generatiom work.
Please share your opinions with us.

Thanks,
Ayman Musa


---------------------------------------------------------------------
Intel Israel (74) Limited

This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170723/a338cc5a/attachment.html>

On Sun, Jul 23, 2017 at 08:48:00AM +0000, Musa, Ayman via llvm-dev
wrote:
> 3-     Give up on the auto-generation idea and manually update the current
tables iteratively with new chunks of instructions until full state is achieved.
> 
> P.s. The TableGen backend emits more than 5200 entries, while the known
exception at this point are ~20.
Why can't you do a variation of this by tagging the instructions with a
flag? I.e. for the rm variant, add a flag that says "this has an
equivalent register operand version". Given that a lot of the instruction
patterns are created via multi-classes, I would expect that to require a
lot less than 5200 updates.

Joerg

> On 23 Jul 2017, at 12:19, Joerg Sonnenberger via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> On Sun, Jul 23, 2017 at 08:48:00AM +0000, Musa, Ayman via llvm-dev wrote:
>> 3-     Give up on the auto-generation idea and manually update the
current tables iteratively with new chunks of instructions until full state is
achieved.
>> 
>> P.s. The TableGen backend emits more than 5200 entries, while the known
exception at this point are ~20.
> 
> Why can't you do a variation of this by tagging the instructions with a
> flag? I.e. for the rm variant, add a flag that says "this has an
> equivalent register operand version". Given that a lot of the
instruction
> patterns are created via multi-classes, I would expect that to require a
> lot less than 5200 updates.
+1 An opt-in ‘GenerateMemoryFolding’ style flag (defaulting to false) seems
safer to me than than trying to ensure you’ve correctly flagged all illegal
instruction fold.

You could then enable the flag on individual groups of
instructions/multi-classes, testing and removing them from the manual tables in
a relatively controlled fashion.

Similarly, new instructions can be enabled in a safe, staged approach without
needing a ‘regenerate a full exceptions list’ stage.

Thanks for persevering with this Ayman!

Simon.