[llvm-dev] [GSOC] [RFC] ALFPrinter: adding static WCET analysis to LLVM

Thu Mar 30 04:08:44 PDT 2017

Ping...

I'm still wondering if there is interest for adding WCET static analysis to
LLVM. I have had no responses yet.

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.

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].

Best regards,
Rick

[0] http://lists.llvm.org/pipermail/llvm-dev/2017-March/111471.html

2017-03-21 13:20 GMT+01:00 Rick Veens <rickveens92 at gmail.com>:

> Hi LLVM dev community.
>
> A while ago I send an e-mail with an idea for GSOC that was not on the
> llvm-gsoc page http://lists.llvm.org/pipermail/llvm-dev/2017-March/
> 111126.html).
>
> 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.
>
> Your feedback is highly appreciated.
>
> Best regards,
>
> Rick Veens
>
>
> Title:
> ALFPrinter: adding static WCET analysis to LLVM
>
>
> Abstract:
> 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.
> 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.
> 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.
>
>
>
> 1 Summary:
> 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.
>
>
> 2 The project:
> 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).
>
> 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.
>
> 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.
>
> 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.
>
> 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.
>
> 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.
>
>
> 3 Benefits for LLVM:
> - Add WCET analysis to LLVM by adding support for an external open-source
> tool.
> - Saves implementing Abstract Interpretation and other complex WCET
> analysis stuff into LLVM.
> - New targets would be added easily, the developer would only have to map
> MCInsts to ALF using ALFPrinter.
> - Allows computing the WCET right away with compilation of your code.
>
>
> 4 Timeline:
>
> Community bonding period:
> Investigate what parts of ALFBackend can be re-used. Take a look at the MC
> layer and the MCStreamer API. Learn about the LLVM development model.
>
> 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.
> Week 2: Take another good look at the MC layer, and at an implementation
> of ASMPrinter.
> Week 3: Subclass MCStreamer, reuse the classes from ALFBackend that model
> and print ALF.
> Week 4: Attempt mapping some simple instructions (e.g. add, mul). See if I
> can get working output.
> 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.
> Week 6: Map the other instructions to ALF. Possibly use the undefined ALF
> instruction if it is not possible.
> Week 7: Buffer week for working on mapping.
> Week 8: Buffer week for working on mapping.
> 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.
> Week 10: Write documentation on how to add a new ALFPrinter target.
> Week 11: Try to port ALFBackend to mainline, get all the tests working.
> Week 12: Compare ALFBackend (IR->ALF), with ALFPrinter (MC->ALF), with aiT.
>
>
> 5 Deliverables:
> - ALFPrinter interface in the MC layer
> - ALFPrinter interface implemented for a simple target architecture
>
>
> 6 Nice to have:
> - Test setup that compares ALFBackend WCET bounds and ALFPrinter WCET
> bounds
> - Possibly using Mälardalen WCET benchmark
> - If obtaining an aiT [4] license is possible, we might compare against
> the industry standard tool.
> - Documentation on how to add a new target using ALFPrinter.
> - Port ALFBackend to LLVM mainline
>
>
> About me:
> 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.
>
> In the last five to six weeks I have been looking into WCET tools (both
> commercial and open source) and into SWEET and ALF.
>
>
> References:
> [1] http://www.mrtc.mdh.se/projects/wcet/sweet/index.html
> [2] http://www.mrtc.mdh.se/projects/all-times/documents/ALF/ALF-spec.pdf
> [3] https://github.com/visq/ALF-llvm
> [4] https://www.absint.com/ait/index.htm
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170330/eeab3094/attachment-0001.html>