<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman",serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
span.EmailStyle17
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:#1F497D;}
span.EmailStyle18
{mso-style-type:personal-compose;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri",sans-serif;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
/* List Definitions */
@list l0
{mso-list-id:1734083125;
mso-list-template-ids:-922852470;}
ol
{margin-bottom:0in;}
ul
{margin-bottom:0in;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-US" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Hi Gus,<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Response inlined.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Thanks,<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Shahid<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<div style="border:none;border-left:solid blue 1.5pt;padding:0in 0in 0in 4.0pt">
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">From:</span></b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> llvm-dev [mailto:llvm-dev-bounces@lists.llvm.org]
<b>On Behalf Of </b>Gus Smith via llvm-dev<br>
<b>Sent:</b> Wednesday, February 21, 2018 8:56 PM<br>
<b>To:</b> llvm-dev@lists.llvm.org<br>
<b>Subject:</b> [llvm-dev] Finding and replacing instruction patterns<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif;color:black">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.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif;color:black"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif;color:black"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif;color:black">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.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif;color:black"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif;color:black">Knowing that this is my goal, I have a number of questions:<o:p></o:p></span></p>
</div>
<div>
<ol start="1" type="1">
<li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l0 level1 lfo1">
<span style="font-family:"Arial",sans-serif;color:black">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.</span><o:p></o:p></li></ol>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">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<o:p></o:p></span></p>
<ol start="2" type="1">
<li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l0 level1 lfo1">
<span style="font-family:"Arial",sans-serif;color:black">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.</span><o:p></o:p></li></ol>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">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
<a href="https://llvm.org/docs/TableGen/index.html">https://llvm.org/docs/TableGen/index.html</a><o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<ol start="3" type="1">
<li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l0 level1 lfo1">
<span style="font-family:"Arial",sans-serif;color:black">When I eventually find a matching load-load-op-store pattern in the IR, my thought was to replace it using an intrinsic function (<a href="https://llvm.org/docs/ExtendingLLVM.html#intrinsic-function">https://llvm.org/docs/ExtendingLLVM.html#intrinsic-function</a>)
so that it can later be compiled to x86 by the backend. Would this be the "right" way to do it?</span><o:p></o:p></li></ol>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">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. <o:p></o:p></span></p>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Thanks for the help! <o:p></o:p></p>
</div>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif;color:black">Gus Smith, Penn State</span><span style="font-family:"Arial",sans-serif;color:#1F497D"><o:p></o:p></span></p>
</div>
</div>
</div>
</div>
</body>
</html>