On 13/02/2018 05:09, John Fastabend wrote:
To find these we do the following
    1.a: Build the CFG of all the instructions so we can walk around the
         program easily.
    1.b: Find the basic blocks and build the basic block CFG. After this
         with a few helper calls we can move around the CFG both at block
         level and insn level.
    1.c: Build the dom tree and post dom tree. This is a data structure that
         allows us to actually find the natural loops. I can write more about
         this later.
    1.d: Using the post dom tree verify all the CFG loops are in fact
         natural loops. I made some simplifications here and threw
         out loops that have multiple jumps to the header node and nested
         loops for now. Both can be handled with some additional complexity.

   Versions of the above can be found in gcc and llvm so it appears to be
   fairly regular stuff from the compiler side. For LLVM the passes are
   --loops, --postdomtree. I dumped the various CFG into dot format and
   and graphed them for fun.

This part of work are very interesting. It will be very helpful if these CFG
information are kept even after verification pass finished, or if the storage
overhead is a concern, made into reusable functions.

I plan to implement similar graph dump in bpftool, i.e. be able to dump eBPF
CFG into .dot graph and color the graph according to some simple static 
these exactly need such CFG information.


Reply via email to