<html><head><meta http-equiv="Content-Type" content="text/html; charset=us-ascii"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div class="">Hi Michal,</div><div class=""><br class=""></div><div class="">Thank you for sending such a detailed write up. I have some related thoughts that I wanted to share in case they are useful to you.</div><div class=""><br class=""></div><div class="">I'm working on a project that has a similar need for canonicalizing program representations. In our case one of the problems we were trying to address is that functionally equivalent programs could be represented differently based on ordering of various internal data structures, like the order of the uses list. While the order is deterministic for a given input source for a specific version of our compiler, there are trivial changes to the inputs and simple changes in our transformation algorithms that could cause the same functional program to have a different ordering, which then would impact our debug print layout.</div><div class=""><br class=""></div><div class="">In our case, we start with the assumption that the relative ordering of some inputs and outputs can't change without changing the meaning of the program (like function parameters). We also assume that the topological ordering of our canonicalized program must be a valid topological ordering of the source program. Meaning if instruction B depends on the output of instruction A, B must be after A. Given these constraints, the problem we tried to solve is how do we generate a consistent ordering for all variations of a program that are functionally equivalent. This problem is basically a graph isomorphism problem, but with specially constrained graphs.</div><div class=""><br class=""></div><div class="">The solution we came up with to address this problem takes advantage of a property of SSA-style program representations, that might be applicable to your tool. By definition SSA IR values are assigned once, but may be used many times. When doing a top-down traversal you need to decide which use to traverse to from a given value. That decision might be dictated by the order of the uses list, or it could be heuristic driven, but in either case we found it to be fraught with problems. In our solution we traverse bottom up. We start at the immutable outputs, which have predetermined and unalterable ordering, then we traverse up from the use to the value. Since each value is only assigned once, we don't have any tiebreaker input ordering issues.</div><div class=""><br class=""></div><div class="">I've thought about, but haven't had time, to apply this technique to LLVM-IR, but in our program representation it works really well.</div><div class=""><br class=""></div><div class="">Hope this is useful,</div><div class="">-Chris</div><div><br class=""><blockquote type="cite" class=""><div class="">On Aug 9, 2019, at 6:18 PM, Puyan Lotfi via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" class="">Nice work guys! Thanks for the shoutout. <div class=""><br class=""></div><div class="">High level comments:</div><div class=""><br class=""></div><div class="">1) I think it could be useful to move your Canonicalizer ModulePass from llvm/tool/llvm-canon to somewhere in llvm/lib/Transforms so that it could possibly be used by llc or clang. I think it could be really useful to do something like clang -o - -S -emit-llvm -femit-canonical-ir foo.c and get the canonicalized output directly. Keep in mind, anything that is accessible through clang or llc can also be really easily accessed through the webapp <a href="http://godbolt.org/" class="">godbolt.org</a> :-). I still think llvm-canon.cpp and llvm-canon executable tool is fine, but I think it would be cool if the ModulePass part were reusable in other parts of llvm. </div><div class="">2) clang-format</div><div class="">3) Add lit tests. </div><div class=""><br class=""></div><div class="">I am all for this being added to llvm. I'll post additional comments in Phabricator. </div><div class=""><br class=""></div><div class="">Puyan</div><div class=""><br class=""></div></div><br class=""><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Fri, Aug 9, 2019 at 1:37 PM Paszkowski, Michal via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a>> wrote:<br class=""></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hi all,<br class="">
<br class="">
Many of us find ourselves spending a great chunk of time comparing LLVM IR dumps at various stages of compilation pipeline or after a given optimization pass. Said process can be extremely laborious, and this is especially true when comparing shaders or compute modules. Important semantic differences are often difficult to spot because of the irregular naming and ordering of instructions.<br class="">
<br class="">
Looking for a solution we have come across Puyan Lotfi's talk at 2018 EuroLLVM on mir-canon (<a href="https://www.youtube.com/watch?v=RHT-bh_xo6U" rel="noreferrer" target="_blank" class="">https://www.youtube.com/watch?v=RHT-bh_xo6U</a>). His project inspired us to invest some time into developing a tool called llvm-canon aiming to achieve a very similar goal - a clean and obvious diff but for LLVM IR dumps.<br class="">
<br class="">
Currently the tool is used internally. We have decided to post here to receive some feedback from the community, spark a discussion on various canonicalization techniques, and ask for a general code review to eventually push the tool to the public trunk.<br class="">
<br class="">
The aim of this project is to develop a tool which will transform the LLVM IR code into a canonical form by reducing non-semantic differences. Therefore, in ideal conditions such canonical form will lead to a clean diff based upon the fact that:<br class="">
1) Two semantically identical modules should show no differences when diffed after canonicalization.<br class="">
2) When modules are not identical the semantic differences should stand out.<br class="">
<br class="">
The tool processes just one file/module at a time - there is no intention for this to be a diff tool. The canonicalization techniques are universal for all modules. Additionally, we want the tool to be as modular as possible allowing for easy changes in the future.<br class="">
<br class="">
All of the canonicalization techniques are focused only on reordering and naming. Having experimented with many options for removing redundant code we came to conclusion that this topic is definitely out of scope of this project and should be left out for other passes. <br class="">
<br class="">
Scope of this project:<br class="">
* Reordering instructions<br class="">
* Naming values (naming initial instructions, naming regular instructions)<br class="">
* Folding instruction names<br class="">
* Naming function arguments<br class="">
* Naming basic blocks<br class="">
<br class="">
One of the biggest challenges in the development of this project was finding a point of reference for canonicalization - naming and ordering must be based on something. It would be unacceptable for a trivial change (such as different opcode, single operand, name of the called function) in a single instruction to affect the canonicalization of other instructions in the same basic block or even function. Therefore, the point of reference should be fairly "constant". Currently, the canonicalization is highly based on the order of side-effecting instructions (also referred to as outputs) and how they relate to the very first instructions in each basic block (non-redundant instructions with only immediate operands; we call them initial instructions). We have found this reference to be relatively effective in our use cases, yet this is the biggest weakness of this canonicalizer. Modules with different layout of side-effecting instructions may require some tinkering by reordering those instructions by hand. We are still looking for some ways to automate this process. <br class="">
<br class="">
Below I will briefly describe each component of the canonicalizer.<br class="">
<br class="">
1. Reordering instructions<br class="">
Instruction reordering starts by iterating through the vector of output instructions (side-effecting instructions + ReturnInst) collected top-down in a given function. On each of these instructions a recursive reordering method is called. This method walks up the def-use tree (starting from the first operand of an output instruction and going up) and reduces the distance between the definition and the user. Each instruction may be moved just once. In case the user is in a different basic block, the definition is placed at the end of the current basic block.<br class="">
<br class="">
The method works surprisingly well yet it does not reorder side-effecting instructions. It is one of the subjects for future discussion and improvement of this tool. Another thing to note is that this algorithm only works on a vector of outputs collected top-down. Moving every instruction just once while making sure that it is as close as possible to the first use guarantees that the def-use chain will be valid upon completion.<br class="">
<br class="">
2. Naming instructions<br class="">
Naming also starts with a vector of output instructions collected top-down. On each of these instructions a recursive naming method is called. This method identifies the type of an instruction and names it accordingly.<br class="">
<br class="">
Currently, we distinguish two types of instructions when it comes to naming:<br class="">
a) Initial instruction (non-redundant instructions with only immediate operands)<br class="">
b) Regular instruction (all other non-redundant instructions)<br class="">
<br class="">
In case of initial instructions, the naming follows this general model:<br class="">
vl <hash> <callee name> ( <operands> )<br class="">
<br class="">
A sample name is given below:<br class="">
vl12345Foo (2, 4)<br class="">
<br class="">
The hash is calculated considering instruction's opcode and output footprint. Output footprint is a vector of unique indices (distance from the beginning of the basic block) of output instructions generated for each initial instruction. This being said, an initial instruction with an output footprint 5, 7, 9, 11 is used by those outputs at least once.<br class="">
<br class="">
The callee name is only included when the named instruction is a CallInst.<br class="">
<br class="">
The very last part of the initial instruction name consists of a list of operands in parentheses. The list is sorted when the instruction is commutative.<br class="">
<br class="">
<br class="">
In case of regular instructions, the naming follows this general model:<br class="">
op <hash> <callee name> ( <operands call chain> )<br class="">
<br class="">
With a sample name given below:<br class="">
op11111Foo (op99999Bar(op55555(...), op22222(...)), op77777(...), vl44444(7))<br class="">
<br class="">
The hash is calculated considering instruction's opcode and opcodes of all operands.<br class="">
<br class="">
The callee name is only included when the named instruction is a CallInst.<br class="">
<br class="">
The last part of the regular instruction name model is a recursively generated list of all operands, and their operands, and so on until we reach initial instructions (depth-first). This may remind more of a call chain than operand list. This naming approach makes differences stand out on all instructions that are affected. This is a desired effect on output instructions as we can instantly see that the semantics have changed. In cases when an output instruction is void, this type of naming is useful on pre-output instructions (direct operands of an output instruction). Besides that this technique pollutes the diff as a single change resonates down the block. This is why names are "folded" in the next phase of canonicalization.<br class="">
<br class="">
3. Folding instruction names<br class="">
As I have mentioned before, recursively generated long operand lists are quite useful when comparing output instructions or their proximate operands in case of void output. In all other cases a simple operand list should result in a much more readable diff. This is why after naming all the instructions, we iterate through them one more time to "fold"/shorten their names. In this phase the operands call chain is substituted with an operand list, and the callee name is removed.<br class="">
<br class="">
Folding initial instructions:<br class="">
vl00000Calle(1, 2) -> vl00000(1, 2)<br class="">
<br class="">
Folding regular instructions:<br class="">
op00000Calle(op00001Calle(...), vl00000Calle(1, 2), ...) -> op00000(op00001, vl00000, ...)<br class="">
<br class="">
<br class="">
Therefore naming and folding give us this kind of effect:<br class="">
Folded (no changes): vl00001(1, 2) = ...<br class="">
Folded (removed callee name): vl00002(6, 5) = call ...<br class="">
Folded (kept only hash): op10001(vl00001, vl00002) = ...<br class="">
Unfolded (output): op10002(op10001(vl00001(1, 2), vl00002Foo(6, 5)), vl00001(1, 2)) = ...<br class="">
<br class="">
4. Other<br class="">
We have been looking for various ways to canonicalize the names of function arguments. But because of their marginal impact on the overall diff we have decided to stick to just numbering them.<br class="">
<br class="">
We are also naming basic blocks following a scheme: bb <hash> where the hash value is calculated considering the opcodes and order of output instructions in a given basic block.<br class="">
<br class="">
5. Areas of further research<br class="">
- As mentioned before we are constantly looking for some different points of reference for canonicalization.<br class="">
- Approaches allowing for automatic reordering of side-effecting instructions.<br class="">
- How sorting operand list on commutative instructions could affect instruction reordering.<br class="">
<br class="">
The canonicalizer is highly modular allowing for easy modifications and future expansion.<br class="">
<br class="">
We hope the community will find this tool useful like we have.<br class="">
<br class="">
I would like to thank Radoslaw Drabinski who really helped me a lot by suggesting numerous improvements and testing the tool.<br class="">
<br class="">
I have uploaded the tool to the Phabricator and would be very grateful for your review!<br class="">
<a href="https://reviews.llvm.org/D66029" rel="noreferrer" target="_blank" class="">https://reviews.llvm.org/D66029</a><br class="">
<br class="">
Thank you,<br class="">
Michal Paszkowski<br class="">
<br class="">
<br class="">
--------------------------------------------------------------------<br class="">
<br class="">
Intel Technology Poland sp. z o.o.<br class="">
ul. Slowackiego 173 | 80-298 Gdansk | Sad Rejonowy Gdansk Polnoc | VII Wydzial Gospodarczy Krajowego Rejestru Sadowego - KRS 101882 | NIP 957-07-52-316 | Kapital zakladowy 200.000 PLN.<br class="">
<br class="">
Ta wiadomosc wraz z zalacznikami jest przeznaczona dla okreslonego adresata i moze zawierac informacje poufne. W razie przypadkowego otrzymania tej wiadomosci, prosimy o powiadomienie nadawcy oraz trwale jej usuniecie; jakiekolwiek<br class="">
przegladanie lub rozpowszechnianie jest zabronione.<br class="">
This e-mail and any attachments may contain confidential material for the sole use of the intended recipient(s). If you are not the intended recipient, please contact the sender and delete all copies; any review or distribution by<br class="">
others is strictly prohibited.<br class="">
<br class="">
_______________________________________________<br class="">
LLVM Developers mailing list<br class="">
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a><br class="">
<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank" class="">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br class="">
</blockquote></div>
_______________________________________________<br class="">LLVM Developers mailing list<br class=""><a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a><br class="">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev<br class=""></div></blockquote></div><br class=""></body></html>