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

Musa, Ayman via llvm-dev llvm-dev at lists.llvm.org
Sun Jul 23 01:48:00 PDT 2017

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.

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>

More information about the llvm-dev mailing list