<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<p>Hi all,</p>
<p>I'm quite interested in this project and think that it's feasible
to get WCET analysis support from LLVM with this proposal. I'm
willing to co-mentor but as discussed previously we're still
looking for someone with more involvement within the LLVM project
to mentor this together with me. Is there anyone interested in
volunteering for (co-)mentorship here?</p>
<p>Cheers,</p>
<p> Roel<br>
</p>
<br>
<div class="moz-cite-prefix">On 21-03-17 13:20, Rick Veens via
llvm-dev wrote:<br>
</div>
<blockquote
cite="mid:CAEeui8JPUej=nxNEfXhMTfsX6JYuEbez09sc1FwrdezR8yo=2Q@mail.gmail.com"
type="cite">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<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 moz-do-not-send="true"
href="http://lists.llvm.org/pipermail/llvm-dev/2017-March/111126.html">http://lists.llvm.org/pipermail/llvm-dev/2017-March/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-Apple-tab-span" style="white-space:pre"> </span>ALFPrinter:
adding static WCET analysis to LLVM</div>
<div><br>
</div>
<div><br>
</div>
<div>Abstract:</div>
<div><span class="gmail-Apple-tab-span" style="white-space:pre"> </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-Apple-tab-span" style="white-space:pre"> </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-Apple-tab-span" style="white-space:pre"> </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-Apple-tab-span" style="white-space:pre"> </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-Apple-tab-span" style="white-space:pre"> </span>-
Possibly using Mälardalen WCET benchmark</div>
<div><span class="gmail-Apple-tab-span" style="white-space:pre"> </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-Apple-tab-span" style="white-space:pre"> </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 moz-do-not-send="true"
href="http://www.mrtc.mdh.se/projects/wcet/sweet/index.html">http://www.mrtc.mdh.se/projects/wcet/sweet/index.html</a></div>
<div>[2] <a moz-do-not-send="true"
href="http://www.mrtc.mdh.se/projects/all-times/documents/ALF/ALF-spec.pdf">http://www.mrtc.mdh.se/projects/all-times/documents/ALF/ALF-spec.pdf</a></div>
<div>[3] <a moz-do-not-send="true"
href="https://github.com/visq/ALF-llvm">https://github.com/visq/ALF-llvm</a></div>
<div>[4] <a moz-do-not-send="true"
href="https://www.absint.com/ait/index.htm">https://www.absint.com/ait/index.htm</a></div>
<div><br>
</div>
</div>
</blockquote>
<br>
</body>
</html>