*****************************
From the IR to the executable
*****************************

This document aims to describe how to obtain a working executable from the IR
generated by ``revng lift``. This for documentation purposes only, standard
users can simply use the ``revng translate`` command, which will take care of
everything.

Use ``revng --verbose translate`` to see all the commands invoked by the script.

In the following we will assume the output of ``revng lift`` is an LLVM IR file
named ``translated.ll``.

Support functions
=================

The IR produced by ``revng lift`` is mostly self-contained, since all the QEMU
helper functions are statically linked in the output module. However, besides
the QEMU helper functions, some additional support functions are required to
obtain a working program, in particular for initialization purposes.

``support.c`` provides the default implementation for them. In the following we
provide a quick summary of the required functions as they are implemented in
``support.c``:

:main: The entry point of the program, maps in memory the stack and the heap. It
       also performs the stack initialization, which is a very delicate
       operation. As it can be seen in the ``prepare_stack`` function the
       environment variables, the arguments and the auxiliary vectors are
       initialized mimicking the stack initialization performed by the Linux
       kernel. ``main`` also performs a call to ``syscall_init`` a function
       defined in the generated module, taken from QEMU, which carries on some
       syscall-related initializations. Finally, the entry point of the module
       generated by ``revng lift`` (the ``root`` function) is called.

:path: Function invoked by the QEMU Linux syscall emulation layer to *filter*
       the path being opened by the translated program. For instance, it is
       possible to catch attempts to open ``/proc/self/map`` and redirect it
       somewhere else transparently.

:unknownPC: Function handling the situation in which the code at an address that
            should be executed has not been translated (see
            `GeneratedIRReference.rst`_). It is basically an error handling
            function that is supposed to never return.

:newpc: As seen in `GeneratedIRReference.rst`_, each input instruction is
        delimited by a call to a ``newpc`` function. This function is not just a
        placeholder, but the user can actually provide it. It is particularly
        useful to access the status of the CPU and perform tracing.

The remaining functions in ``support.c`` are of little interest and might be
removed in the future. Note also that ``support.c`` works automatically with all
the supported architectures, but needs to know which was the input
architecture. For this reason, a macro ``TARGET_arch`` (e.g., ``TARGET_arm``)
needs to be defined on the compilation command line.

The provided ``support.c`` offers two modes of operations: ``normal`` and
``trace``. The only difference between the two modes is that the latter
activates the program counter tracing support (which is implemented through
``newpc``). This means that while running the program a list of the execute
program counters will be dumped to the path specified by ``REVNG_TRACE_PATH``,
if available. This is optional at compile-time, since it introduces an overhead
even if disabled at run-time.

``revng`` distribution provide a pre-compiled version of both the flavors in the
form of LLVM IR: ``support-x86_64-normal.ll`` and
``support-x86_64-trace.ll``. They have to be linked into the module generated by
``revng lift``:

.. code-block:: sh

    llvm-link -S translated.ll support-x86_64-normal.ll -o translated.linked.ll

From the IR to the object file
==============================

As an optional step, before proceeding in compiling the IR, it's possible to run
the optimization pipeline on the generated IR using the LLVM ``opt`` tool:

.. code-block:: sh

    revng opt -O2 -S translated.linked.ll -o translated.opt.ll

Depending on the size of the input program this might take some time.

The first step to obtain the final executable consists in compiling the IR. To
do this, we can use ``llc``, the LLVM static compiler, which takes an LLVM IR
file and produces an object file:

.. code-block:: sh

    llc -O0 translated.linked.ll -filetype=obj -o translated.o

``llc`` exposes the compiler backend. The backend can do another series of
optimizations:

.. code-block:: sh

    llc \
      -O2 \
      translated.linked.ll \
      -filetype=obj \
      -o translated.o \
      -regalloc=fast \
      -disable-machine-licm

Note: as for ``opt``, optimizations can take a considerable amount of time, in
particular if slow register allocation methods are used (i.e., make sure to use
``-regalloc=fast``). Non-trivial register allocation techniques on the ``root``
function can be prohibitively costly (see also `GeneratedIRReference.rst`_).

Linking
=======

Once we have the object file we have to link it to link to ``libm.so``,
``libz.so`` and ``librt.so``.

In addition to this, we also have to tell the linker to force the *segment
variables* (see `GeneratedIRReference.rst`_) at the appropriate location in
memory. In fact, each segment of the original binary should be loaded exactly at
the same address where it was originally supposed to be loaded. ``revng lift``
emits the required mapping automatically in a file with the same name as the
output file plus a ``.li.csv`` suffix. This file is a CSV file composed by three
columns:

:name: The name of the section in the generated module containing the data of
       the considered segment.
:start: Start address where the segment originally was located and, therefore,
        where it should be placed by the linker.
:end: Corresponding end address.

For each segment, add a linking option such as
``-Wl,--section-start={name}={start}``.

It is also required to position the ``.elfheaderhelper``
(``-Wl,--section-start={name}=``) one byte before the segment with the lowest
address. This ensures the linker will allocate a page before that segment where
the ELF headers can be placed.

Finally, we need to tell the linker where to put the real code with
``-Wl,-Ttext-segment=``. The ideal place, is the first free page after the last
segment.

As a result of this operation, the actual translated code might end up in an
unusual location, but the linker should be able to figure this out.

In conclusion, to link the final program:

.. code-block:: sh

    c++ -no-pie \
        -Wl,-z,max-page-size=4096 \
        -Wl,--section-start=.o_rx_0x400000=0x400000 \
        -Wl,--section-start=.o_rw_0x416fb0=0x416fb0 \
        -fuse-ld=bfd \
        -Wl,--section-start=.elfheaderhelper=0x3fffff \
        -Wl,-Ttext-segment=0x418000 \
        translated.o \
        -lz -lm -lrt -lpthread \
        -o translated.elf.tmp

The final step, which should be necessary only to translate non-static binaries,
is to invoke the ``revng-merge-dynamic`` script, which will take care of merging
the translated binary and the original one preserving information for the
dynamic loader from both binaries.  These include dynamic string table,
relocations, symbols, libraries (``DT_NEEDED``) and so on.

.. code-block:: sh

    revng merge-dynamic \
        translated.elf.tmp \
        translated \
        translated.elf

.. _`GeneratedIRReference.rst`: GeneratedIRReference.rst
