llvm dev - Jan 2021 - Proposing a small change to the SelectionDAG class to support recover from LLVM IR

Hello, llvm-dev.
     I am trying to commit in the following weeks the back end I wrote for our
research
lab's Connex SIMD processor, a promising vector processor which we hope to
make it visible
(please see if you have the time these links related to the Connex processor: 
https://dl.acm.org/doi/10.1145/3406536, 
http://users.dcae.pub.ro/~gstefan/2ndLevel/functional_electronics.html ).

     But, since our back end has the exotic feature of handling symbolic
immediate
assembler operands to achieve vector-length portability by using JIT assembling
I had to
make a small change to the SelectionDAG class which I now would like to commit
on Github.

     So I come to ask you what do you think about adding this useful small
feature in the
SelectionDAG class (a DenseMap<const Value*, SDValue> *crtNodeMapPtr
datastructure and a
bit of book-keeping for it).

     From https://reviews.llvm.org/D60052#change-7t38wfUuDjbR (my previous
attempt to
commit the Connex backend):
     >      As written
at http://lists.llvm.org/pipermail/llvm-dev/2019-May/132133.html:
     >         There is one thing a bit more special with this back end,
namely our back
     > end handles symbolic immediate operands (C/C++ expressions written as
strings in
     INLINEASM MachineInstrs). This means the back end can output vector
assembly code like:
     >         VLOAD Reg0, N * 10 + 5 // where N is a variable in the
original C program,
       which means that to assign to register Reg0 the value N*10 + 5. This
instruction is
later JIT assembled (at runtime) in order to have a constant immediate operand
equal to
N*10 + 5
     >       Therefore, in order to support recovering from a SelectionDAG
node to LLVM IR
(and then all the way back to the original source C/C++ code), something
possible with the
current LLVM distribution, which is implemented in our Connex LLVM compiler
project, we
require adding a simple data structure in the LLVM source file:
     >           include/llvm/CodeGen/SelectionDAG.h (and helper methods in
the related
     > SelectionDAG.cpp file)
     >         that maps an SDValue to the LLVM IR Value object it was used
to translate
from called:
     > DenseMap<const Value*, SDValue> *crtNodeMapPtr .

     Roman Lebedev asked me about this new feature that I propose, at 
https://lists.llvm.org/pipermail/llvm-dev/2019-May/132136.html
     > I'm not sure how that is supposed to work. What if IR does not
originate from C?
     > How do you verify that the "C string" is in the form that
will be understood
     > by whatever will handle it later on? Is there a clang part of the
patch?
    My answer to his question is: the IR originates from C and there is no clang
patch,
since there is no need to alter clang. To recover a C/C++ expression from
SelectionDAG
node to LLVM IR (and then all the way back to the original source C/C++ code) we
only need
to add this crtNodeMapPtr data structure. The recovery is performed by walking
recursively
on the LLVM IR code starting from the immediate operand of the assembler
instruction until
the end: the moment we visit an LLVM IR add instruction we simply put in the
resulting
C/C++ string we create a "+" operator.

    This recovery from SelectionDAG node to LLVM IR and then to C/C++ is working
very well
in my LLVM build. It is well tested on a few tenths of small benchmarks.

    Please let me know if you have any questions related to this proposed small
change to
the SelectionDAG class. You can find some more explanation on how we recover to
C/C++ in
my PhD thesis: see Section 4.1.8 ("Symbolic Scalar Immediate
Operands") at
https://sites.google.com/site/alexsusu/myfilecabinet/PhDThesis_AlexSusu.pdf .


   Thank you,
     Alex

Hi Alex,

I'm not sure I understand how this map works. A single Value * may have a
StructType which is initially represented by a MERGE_VALUES node. But that
node will be removed in DAGCombine by connecting each operand of the
MERGE_VALUES to the users of each of the results. At that point there is no
single SDValue that represents the Value *. How does the map model this?

~Craig


On Sun, Jan 31, 2021 at 10:38 AM Alex Susu via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
>    Hello, llvm-dev.
>      I am trying to commit in the following weeks the back end I wrote for
> our research
> lab's Connex SIMD processor, a promising vector processor which we hope
to
> make it visible
> (please see if you have the time these links related to the Connex
> processor:
> https://dl.acm.org/doi/10.1145/3406536,
> http://users.dcae.pub.ro/~gstefan/2ndLevel/functional_electronics.html ).
>
>      But, since our back end has the exotic feature of handling symbolic
> immediate
> assembler operands to achieve vector-length portability by using JIT
> assembling I had to
> make a small change to the SelectionDAG class which I now would like to
> commit on Github.
>
>      So I come to ask you what do you think about adding this useful small
> feature in the
> SelectionDAG class (a DenseMap<const Value*, SDValue> *crtNodeMapPtr
> datastructure and a
> bit of book-keeping for it).
>
>      From https://reviews.llvm.org/D60052#change-7t38wfUuDjbR (my
> previous attempt to
> commit the Connex backend):
>      >      As written at
> http://lists.llvm.org/pipermail/llvm-dev/2019-May/132133.html:
>      >         There is one thing a bit more special with this back end,
> namely our back
>      > end handles symbolic immediate operands (C/C++ expressions
written
> as strings in
>      INLINEASM MachineInstrs). This means the back end can output vector
> assembly code like:
>      >         VLOAD Reg0, N * 10 + 5 // where N is a variable in the
> original C program,
>        which means that to assign to register Reg0 the value N*10 + 5.
> This instruction is
> later JIT assembled (at runtime) in order to have a constant immediate
> operand equal to
> N*10 + 5
>      >       Therefore, in order to support recovering from a
SelectionDAG
> node to LLVM IR
> (and then all the way back to the original source C/C++ code), something
> possible with the
> current LLVM distribution, which is implemented in our Connex LLVM
> compiler project, we
> require adding a simple data structure in the LLVM source file:
>      >           include/llvm/CodeGen/SelectionDAG.h (and helper methods
> in the related
>      > SelectionDAG.cpp file)
>      >         that maps an SDValue to the LLVM IR Value object it was
> used to translate
> from called:
>      > DenseMap<const Value*, SDValue> *crtNodeMapPtr .
>
>      Roman Lebedev asked me about this new feature that I propose, at
> https://lists.llvm.org/pipermail/llvm-dev/2019-May/132136.html
>      > I'm not sure how that is supposed to work. What if IR does
not
> originate from C?
>      > How do you verify that the "C string" is in the form
that will be
> understood
>      > by whatever will handle it later on? Is there a clang part of the
> patch?
>     My answer to his question is: the IR originates from C and there is no
> clang patch,
> since there is no need to alter clang. To recover a C/C++ expression from
> SelectionDAG
> node to LLVM IR (and then all the way back to the original source C/C++
> code) we only need
> to add this crtNodeMapPtr data structure. The recovery is performed by
> walking recursively
> on the LLVM IR code starting from the immediate operand of the assembler
> instruction until
> the end: the moment we visit an LLVM IR add instruction we simply put in
> the resulting
> C/C++ string we create a "+" operator.
>
>     This recovery from SelectionDAG node to LLVM IR and then to C/C++ is
> working very well
> in my LLVM build. It is well tested on a few tenths of small benchmarks.
>
>     Please let me know if you have any questions related to this proposed
> small change to
> the SelectionDAG class. You can find some more explanation on how we
> recover to C/C++ in
> my PhD thesis: see Section 4.1.8 ("Symbolic Scalar Immediate
Operands") at
> https://sites.google.com/site/alexsusu/myfilecabinet/PhDThesis_AlexSusu.pdf
> .
>
>
>    Thank you,
>      Alex
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210131/57c0f683/attachment.html>

Hi, Craig,
     The added map to the SelectionDAG class was meant to help my own back end.
     The crtNodeMapPtr map is not meant as it is to model the case with several
SDValues
that represent a Value* (the example with StructType you provide). If we would
be
interested to care about this case then maybe we should use C++'s
std::unordered_multimap
instead of a DenseMap - would you be interested in having that changed like
this:
     std::unordered_multimap<const Value*, SDValue> *crtNodeMapPtr ?

     I have to add that I do not care about such complex cases as the one from
your
example: I have only 2 assembler instructions that check for crtNodeMapPtr (just
for
information, one Connex vector instruction is called VLOAD and the other
REPEAT).


     Please note that I also changed besides the source file 
lib/CodeGen/SelectionDAG/SelectionDAG.cpp, the following source files a bit
(please see
https://reviews.llvm.org/D60052#change-SowgZab8ZLD7):
       lib/CodeGen/SelectionDAG/DAGCombiner.cpp
       lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h
       lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp

   Thank you very much,
     Alex


On 1/31/2021 9:26 PM, Craig Topper wrote:
> Hi Alex,
> 
> I'm not sure I understand how this map works. A single Value * may have
a StructType which
> is initially represented by a MERGE_VALUES node. But that node will be
removed in
> DAGCombine by connecting each operand of the MERGE_VALUES to the users of
each of the
> results. At that point there is no single SDValue that represents the Value
*. How does
> the map model this?
> 
> ~Craig
> 
> 
> On Sun, Jan 31, 2021 at 10:38 AM Alex Susu via llvm-dev <llvm-dev at
lists.llvm.org
> <mailto:llvm-dev at lists.llvm.org>> wrote:
> 
>         Hello, llvm-dev.
>           I am trying to commit in the following weeks the back end I wrote
for our research
>     lab's Connex SIMD processor, a promising vector processor which we
hope to make it
>     visible
>     (please see if you have the time these links related to the Connex
processor:
>     https://dl.acm.org/doi/10.1145/3406536
<https://dl.acm.org/doi/10.1145/3406536>,
>     http://users.dcae.pub.ro/~gstefan/2ndLevel/functional_electronics.html
>    
<http://users.dcae.pub.ro/~gstefan/2ndLevel/functional_electronics.html>
).
> 
>           But, since our back end has the exotic feature of handling
symbolic immediate
>     assembler operands to achieve vector-length portability by using JIT
assembling I had to
>     make a small change to the SelectionDAG class which I now would like to
commit on Github.
> 
>           So I come to ask you what do you think about adding this useful
small feature in
>     the
>     SelectionDAG class (a DenseMap<const Value*, SDValue>
*crtNodeMapPtr datastructure and a
>     bit of book-keeping for it).
> 
>           From https://reviews.llvm.org/D60052#change-7t38wfUuDjbR
>     <https://reviews.llvm.org/D60052#change-7t38wfUuDjbR> (my
previous attempt to
>     commit the Connex backend):
>           >      As written at
>     http://lists.llvm.org/pipermail/llvm-dev/2019-May/132133.html
>     <http://lists.llvm.org/pipermail/llvm-dev/2019-May/132133.html>:
>           >         There is one thing a bit more special with this back
end, namely our back
>           > end handles symbolic immediate operands (C/C++ expressions
written as strings in
>           INLINEASM MachineInstrs). This means the back end can output
vector assembly
>     code like:
>           >         VLOAD Reg0, N * 10 + 5 // where N is a variable in
the original C program,
>             which means that to assign to register Reg0 the value N*10 + 5.
This
>     instruction is
>     later JIT assembled (at runtime) in order to have a constant immediate
operand equal to
>     N*10 + 5
>           >       Therefore, in order to support recovering from a
SelectionDAG node to
>     LLVM IR
>     (and then all the way back to the original source C/C++ code),
something possible with
>     the
>     current LLVM distribution, which is implemented in our Connex LLVM
compiler project, we
>     require adding a simple data structure in the LLVM source file:
>           >           include/llvm/CodeGen/SelectionDAG.h (and helper
methods in the related
>           > SelectionDAG.cpp file)
>           >         that maps an SDValue to the LLVM IR Value object it
was used to translate
>     from called:
>           > DenseMap<const Value*, SDValue> *crtNodeMapPtr .
> 
>           Roman Lebedev asked me about this new feature that I propose, at
>     https://lists.llvm.org/pipermail/llvm-dev/2019-May/132136.html
>     <https://lists.llvm.org/pipermail/llvm-dev/2019-May/132136.html>
>           > I'm not sure how that is supposed to work. What if IR
does not originate from C?
>           > How do you verify that the "C string" is in the
form that will be understood
>           > by whatever will handle it later on? Is there a clang part
of the patch?
>          My answer to his question is: the IR originates from C and there
is no clang patch,
>     since there is no need to alter clang. To recover a C/C++ expression
from SelectionDAG
>     node to LLVM IR (and then all the way back to the original source C/C++
code) we only
>     need
>     to add this crtNodeMapPtr data structure. The recovery is performed by
walking
>     recursively
>     on the LLVM IR code starting from the immediate operand of the
assembler instruction
>     until
>     the end: the moment we visit an LLVM IR add instruction we simply put
in the resulting
>     C/C++ string we create a "+" operator.
> 
>          This recovery from SelectionDAG node to LLVM IR and then to C/C++
is working very
>     well
>     in my LLVM build. It is well tested on a few tenths of small
benchmarks.
> 
>          Please let me know if you have any questions related to this
proposed small
>     change to
>     the SelectionDAG class. You can find some more explanation on how we
recover to C/C++ in
>     my PhD thesis: see Section 4.1.8 ("Symbolic Scalar Immediate
Operands") at
>    
https://sites.google.com/site/alexsusu/myfilecabinet/PhDThesis_AlexSusu.pdf
>    
<https://sites.google.com/site/alexsusu/myfilecabinet/PhDThesis_AlexSusu.pdf>
.
> 
> 
>         Thank you,
>           Alex
>     _______________________________________________
>     LLVM Developers mailing list
>     llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
>     https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>     <https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
>