llvm dev - Feb 2018 - Finding and replacing instruction patterns

Hi all -- first time poster, hoping that this is going to the right list.
Also a complete LLVM newbie, so please correct any glaring errors in my
understanding.


I am an architecture researcher at Penn State working on Processing in
Memory (PIM) architectures. Currently, I plan to use LLVM to detect and
replace groups of instructions which can be accelerated in memory. Once a
group of instructions is detected, they will be replaced with the
corresponding PIM instruction. For a toy example, take a series of
instructions such as "load A, load B, add C=A+B, store C". My goal in
this
case would be to detect this series of four instructions and replace it
with a single "memory_add" or "cache_add" instruction. When
compiled to
machine code, these cache_add instructions will compile to some unused x86
opcode; we will then run this binary through gem5, which has been modified
to handle PIM instructions.

Knowing that this is my goal, I have a number of questions:

   1. Is this a misuse/abuse of LLVM? From an LLVM newbie's perspective,
   LLVM seemed like the right tool, as I'm doing transformations of source
   code and trying to produce binaries with new PIM instructions. However, if
   there's a better tool, or if LLVM is just purely the wrong tool, please
   tell me.
   2. Is there a standard way to do this sort of "pattern matching" in
   LLVM, e.g. finding load-load-op-store patterns? I found the InstCombinePass
   class and AggressiveInstCombine directory, which seems to be very close to
   what I need. I even see mention of "pattern matching" in these
files.
   However, I'm confused as to whether there is a standard way to write
   patterns and replacements (e.g. specifying that load-load-op-store gets
   replaced with cache_op), or if I'll just have to roll my own version.
   3. When I eventually find a matching load-load-op-store pattern in the
   IR, my thought was to replace it using an intrinsic function (
   https://llvm.org/docs/ExtendingLLVM.html#intrinsic-function) so that it
   can later be compiled to x86 by the backend. Would this be the
"right" way
   to do it?


Thanks for the help!
Gus Smith, Penn State
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180221/21a268dd/attachment.html>

Hi Gus,

Response inlined.

Thanks,
Shahid

From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of Gus
Smith via llvm-dev
Sent: Wednesday, February 21, 2018 8:56 PM
To: llvm-dev at lists.llvm.org
Subject: [llvm-dev] Finding and replacing instruction patterns

Hi all -- first time poster, hoping that this is going to the right list. Also a
complete LLVM newbie, so please correct any glaring errors in my understanding.


I am an architecture researcher at Penn State working on Processing in Memory
(PIM) architectures. Currently, I plan to use LLVM to detect and replace groups
of instructions which can be accelerated in memory. Once a group of instructions
is detected, they will be replaced with the corresponding PIM instruction. For a
toy example, take a series of instructions such as "load A, load B, add
C=A+B, store C". My goal in this case would be to detect this series of
four instructions and replace it with a single "memory_add" or
"cache_add" instruction. When compiled to machine code, these
cache_add instructions will compile to some unused x86 opcode; we will then run
this binary through gem5, which has been modified to handle PIM instructions.

Knowing that this is my goal, I have a number of questions:

  1.  Is this a misuse/abuse of LLVM? From an LLVM newbie's perspective,
LLVM seemed like the right tool, as I'm doing transformations of source code
and trying to produce binaries with new PIM instructions. However, if
there's a better tool, or if LLVM is just purely the wrong tool, please tell
me.
No, this will not be misuse of LLVM. LLVM’s backend uses Tablegen tool to
generate C++ code to match instruction patterns based on the pattern description
provided through target dependent .td files

  1.  Is there a standard way to do this sort of "pattern matching" in
LLVM, e.g. finding load-load-op-store patterns? I found the InstCombinePass
class and AggressiveInstCombine directory, which seems to be very close to what
I need. I even see mention of "pattern matching" in these files.
However, I'm confused as to whether there is a standard way to write
patterns and replacements (e.g. specifying that load-load-op-store gets replaced
with cache_op), or if I'll just have to roll my own version.
Target description file(.td) along with TableGen which llvm uses to commonly
match patterns with its replacement. These patterns are basically LISP like
record which can be used to contain information about instruction Opcode,
Register classes, ABI constraints, Instruction encoding etc
https://llvm.org/docs/TableGen/index.html


  1.  When I eventually find a matching load-load-op-store pattern in the IR, my
thought was to replace it using an intrinsic function
(https://llvm.org/docs/ExtendingLLVM.html#intrinsic-function) so that it can
later be compiled to x86 by the backend. Would this be the "right" way
to do it?
LLVM target intrinsic is another way which can be used to accomplish the kind of
task you have described. IMO, this is easier than pattern matching with
TableGen.

Thanks for the help!
Gus Smith, Penn State
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180221/a2449175/attachment.html>