<div dir="ltr">Ping...<div><br></div><div>I'm still wondering if there is interest for adding WCET static analysis to LLVM. I have had no responses yet. </div><div><br></div><div>I will be working on this anyway if it will not result in a GSOC project, so i really would like to know if there is a bit of interest in the addition to LLVM i am proposing. GSOC might only improve the quality of the end result.<br></div><div><br></div><div>Furthermore, i'm looking for a mentor for this GSOC project. Preferably, someone with a bit of knowledge of the MC layer. But anyone who is experienced with LLVM and has contributed to it will do. A co-mentorship is also a possibility as mentioned by [0].</div><div><br></div><div>Best regards,</div><div>Rick</div><div><br></div><div><br></div><div>[0] <a href="http://lists.llvm.org/pipermail/llvm-dev/2017-March/111471.html">http://lists.llvm.org/pipermail/llvm-dev/2017-March/111471.html</a></div><div><div class="gmail_extra"><br><div class="gmail_quote">2017-03-21 13:20 GMT+01:00 Rick Veens <span dir="ltr"><<a href="mailto:rickveens92@gmail.com" target="_blank">rickveens92@gmail.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div>Hi LLVM dev community.</div><div><br></div><div>A while ago I send an e-mail with an idea for GSOC that was not on the llvm-gsoc page <a href="http://lists.llvm.org/pipermail/llvm-dev/2017-March/111126.html" target="_blank">http://lists.llvm.org/<wbr>pipermail/llvm-dev/2017-March/<wbr>111126.html</a>).</div><div><br></div><div>I did not get a response unfortunately so I would like to make my idea a bit more clear with the draft-proposal for gsoc included below.</div><div><br></div><div>Your feedback is highly appreciated.</div><div><br></div><div>Best regards,</div><div><br></div><div>Rick Veens</div><div><br></div><div><br></div><div>Title:</div><div><span class="gmail-m_3242518127622891533gmail-Apple-tab-span" style="white-space:pre-wrap"> </span>ALFPrinter: adding static WCET analysis to LLVM</div><div><br></div><div><br></div><div>Abstract:</div><div><span class="gmail-m_3242518127622891533gmail-Apple-tab-span" style="white-space:pre-wrap">      </span>For software that runs on an embedded processor that is to be used in a hard real-time system, it is important to know how long a particular task might run in the worst case. This is called the Worst Case Execution Time (WCET).  There exist tools for computing the WCET that analyse the binary. They can compute the WCET without executing the code (static-analysis) using a complex mathematical model. It might be the case that not all possible paths in the code are executed when executing the code very often.</div><div>Adding new targets to these WCET tools is a bit of a problem. Typically, they have the decompilation and reconstruction of the CFG build-in. Adding a new target is then either under contract if the tool is commercial, or requires extensive knowledge of the tool if it is open-source. The WCET tool SWEET is a bit of an exception to this, as it has an interface language called ALF. ALF is developped in such a way that various Instruction Set Architectures (ISA) can be expressed in it.</div><div>Unfortunatelly, no compilers allow a mappings to ALF as of now. This is the problem that this project aims to solve, by adding an interface for outputting ALF code from the LLVM compiler. The main idea is to subclass MCStreamer (say we name it ALFPrinter) that allows transforming MCInsts from the MC layer to ALF code. The project will also include a proof-of-concept with a simple ISA.</div><div> </div><div><br></div><div><br></div><div>1 Summary:</div><div><span class="gmail-m_3242518127622891533gmail-Apple-tab-span" style="white-space:pre-wrap">    </span>By adding an ALFPrinter interface in the MC layer, this project aims to make it easy for supporting new targets for the static analyisis tool SWEET.  SWEET can compute the Worst Case Execution Time of your code by looking at the code statically using flow-analysis. This has applications for embedded processors that are to be applied in a hard real-time system.</div><div><br></div><div><br></div><div>2 The project:</div><div><span class="gmail-m_3242518127622891533gmail-Apple-tab-span" style="white-space:pre-wrap">     </span>A WCET tool is a tool that can determine the longest possible execution time of your code (Worst-Case Execution Time). This WCET is important in hard real-time applications where multiple tasks are scheduled on the same (embedded) processor, where each task needs to finish by a specified deadline.  Missing the deadline can have disastrous results (e.g. air-bag in a car does not open in time).</div><div><br></div><div>Static-analysis WCET tools decompile a binary and do analysis on the flow of the code (so they do not actually run the code). These tools typically manage the decompilation themselves, and adding a new target architecture is either not possible or is under contract and will be costly if the tool is commercial.</div><div><br></div><div>The open-source WCET static-analysis tool SWEET [1] has a novel approach to this problem. It has an interface language (called ALF [2]) that is designed to allow ISA code like AVR, ARM to be described in it. The idea is to make it easier to add a new target architecture, as you would only need to decompile and transform it to this ALF.</div><div><br></div><div>The goal of this project, is to add a new interface to LLVM in the MC layer (an MCStreamer), that allows printing to ALF just like printing is done to .o object files or .s assembler text. Thus making it very easy to decompile into MCInsts and output ALF. This would make it very easy to add WCET analysis to existing and upcoming architectures.</div><div><br></div><div>Apart from ALF code, SWEET also requires the cycle count of the basic blocks in order to determine a good WCET bound. This can either come from a cycle-accurate simulator or could be outputted from LLVM directly, if the cycle costs of the instructions are simple to determine. Perhaps there already exists data structures in LLVM that keep track of the cycle count of a particular basic block. This will have to be investigated.</div><div><br></div><div>The ALFBackend project [3], build upon LLVM 3.4, contains code to output to ALF which can possibly be re-used. ALFBackend implements an IR Pass, and allows outputting ALF code from IR code directly. This is different from what I aim to achieve. The issue is that the structure of IR code is a lot different from the code in the final binary due to optimizations in the back-end. The MC layer is supposed to closely resemble the output binary. </div><div><br></div><div><br></div><div>3 Benefits for LLVM:</div><div>- Add WCET analysis to LLVM by adding support for an external open-source tool.</div><div>- Saves implementing Abstract Interpretation and other complex WCET analysis stuff into LLVM.</div><div>- New targets would be added easily, the developer would only have to map MCInsts to ALF using ALFPrinter.</div><div>- Allows computing the WCET right away with compilation of your code.</div><div><br></div><div><br></div><div>4 Timeline:</div><div><br></div><div>Community bonding period:</div><div><span class="gmail-m_3242518127622891533gmail-Apple-tab-span" style="white-space:pre-wrap"> </span>Investigate what parts of ALFBackend can be re-used. Take a look at the MC </div><div>layer and the MCStreamer API. Learn about the LLVM development model.</div><div><br></div><div>Week 1: Get more familiar with ALF & how memory is represented in ALF. Choose target test setup. Obtain a dev board with a simple embedded processor such as ARM cortex-M0/3, AVR. Preferably one that is supported by the major commercial WCET tool, aiT from AbsInt [4] to compare against this tool.</div><div>Week 2: Take another good look at the MC layer, and at an implementation of ASMPrinter.</div><div>Week 3: Subclass MCStreamer, reuse the classes from ALFBackend that model and print ALF. </div><div>Week 4: Attempt mapping some simple instructions (e.g. add, mul). See if I can get working output.</div><div>Week 5: Try to output the required basic-block costs from ALFPrinter. First hard-coded, then maybe from an existing datastructure in LLVM that allows me to derive cycle costs from a given basic-block.</div><div>Week 6: Map the other instructions to ALF. Possibly use the undefined ALF instruction if it is not possible.</div><div>Week 7: Buffer week for working on mapping.</div><div>Week 8: Buffer week for working on mapping.</div><div>Week 9: Attempt to execute some tests from the Mälardalen benchmark suite. Try to get a license for aiT and compare with this tool.</div><div>Week 10: Write documentation on how to add a new ALFPrinter target.</div><div>Week 11: Try to port ALFBackend to mainline, get all the tests working.</div><div>Week 12: Compare ALFBackend (IR->ALF), with ALFPrinter (MC->ALF), with aiT.</div><div><br></div><div><br></div><div>5 Deliverables:</div><div>- ALFPrinter interface in the MC layer </div><div>- ALFPrinter interface implemented for a simple target architecture</div><div><br></div><div><br></div><div>6 Nice to have:</div><div>- Test setup that compares ALFBackend WCET bounds and ALFPrinter WCET bounds</div><div><span class="gmail-m_3242518127622891533gmail-Apple-tab-span" style="white-space:pre-wrap">      </span>- Possibly using Mälardalen WCET benchmark</div><div><span class="gmail-m_3242518127622891533gmail-Apple-tab-span" style="white-space:pre-wrap">    </span>- If obtaining an aiT [4] license is possible, we might compare against the industry standard tool.</div><div>- Documentation on how to add a new target using ALFPrinter.</div><div>- Port ALFBackend to LLVM mainline</div><div><br></div><div><br></div><div>About me:</div><div><span class="gmail-m_3242518127622891533gmail-Apple-tab-span" style="white-space:pre-wrap">      </span>I'm an second-year Embedded Systems graduate student from the Eindhoven  University of Technology in the Netherlands. I've been introduced to LLVM by the course "Parallelism, compilers and platforms" where it has been used extensively as a learning tool. I did a bachelor in computer science at the Avans University of Applied Sciences in Den Bosch in the Netherlands where I learned to program in a bunch of programming languages such as C, C++, Java, C#, Python.</div><div><br></div><div>In the last five to six weeks I have been looking into WCET tools (both commercial and open source) and into SWEET and ALF.</div><div><br></div><div><br></div><div>References:</div><div>[1] <a href="http://www.mrtc.mdh.se/projects/wcet/sweet/index.html" target="_blank">http://www.mrtc.mdh.se/<wbr>projects/wcet/sweet/index.html</a></div><div>[2] <a href="http://www.mrtc.mdh.se/projects/all-times/documents/ALF/ALF-spec.pdf" target="_blank">http://www.mrtc.mdh.se/<wbr>projects/all-times/documents/<wbr>ALF/ALF-spec.pdf</a></div><div>[3] <a href="https://github.com/visq/ALF-llvm" target="_blank">https://github.com/visq/ALF-<wbr>llvm</a></div><div>[4] <a href="https://www.absint.com/ait/index.htm" target="_blank">https://www.absint.com/ait/<wbr>index.htm</a></div><div><br></div></div>
</blockquote></div><br></div></div></div>