[llvm-dev] Testing utility for building and updating CFG

Tobias Grosser via llvm-dev llvm-dev at lists.llvm.org
Wed Jun 28 02:01:59 PDT 2017

On Wed, Jun 28, 2017, at 12:31 AM, Jakub (Kuba) Kuderski via llvm-dev
> Hi folks,
> I’m working on adding an API for incremental updates to DominatorTree and
> I
> noticed that there isn’t a simple way to quickly build and update CFG
> (just
> for testing) -- one has to either build CFG programmatically, or write IR
> by hand and manually map pointers to basic blocks. The downside is that
> it
> tends to be pretty verbose and not easy to update (e.g. adding a new edge
> often involves changing the type of terminator instruction).

Hi Jakub,

I really like the idea of automating the testing and to even prepare for
extensive fussing.

> My idea is to create a simple format for building arbitrary CFG’s and new
> utilities for updating it.
> It can look something like this:
> b ModuleName FunctionName // Build module ‘ModuleName’ with a single
>                          // function ‘FunctionName’.
> a entry if                // Add new basic blocks (entry and if) and
>                          // connect them with an edge.
> a if if.then              // Add new basic block (if.then) and create
>                          // an edge from if to if.then
> a if if.else
> a if.then foo
> a if.else foo
> a bar                     // Add a new block bar, but don’t create
>                          // any edges.
> e                         // Finish constructing initial CFG
> i foo bar                 // Insert and edge from foo to bar.
> d if if.then              // Delete the edge from if to if.then.
> i if bar                  // Insert an edge from if to bar.
> Under the hood, the utility would build IR with just switch instructions.
> Then you could assign it to a string and use in a unit test:
> CFGBuilder B(MyString);
> Function *F = B.getFunction();
> while (!B.finished()) {
>    Update U = B.applyNextUpdate(); // B changes the CFG.
> // U stores type of update (insertion/deletion) and a pair of BB’s
> // (From and To).
>    doSomethingWithTheUpdate(U);
> }
> Other CFG passes (e.g. LoopInfo, NewGVN) could also use it for testing.
> It
> would be also possible to hook it up to a fuzzer at some point in the
> future.
> What do you think about having such a utility in llvm?

I like the idea and if it helps to have extensive unit tests in LLVM,
that's great. I am slightly worried about a new DSL (which always has a
maintenance cost). However, this seems well contained and simple, so I
would expect it to remain unchanged and up-to-date for a while.

Some thoughts (which I mentioned earlier).

# lit compatibility and maybe even opt compatability

I believe that LLVM lit tests are the easiest tests to write and debug.
If there is a chance we can write such unit tests as lit tests,
I would really appreciate this. It might even make sense to allow these
update-sets to be read through an opt pass, such that
dominators, loop passes, ... can be tested as part of the pass pipeline.

; RUN: opt -dom -verify-dom -cfg-updater -cfg-updater-file %s < %s
; CFG: i entry, if
; CFG: i if if.then
; CFG: i if if.else
; CFG: i if.then a
; CFG: i if.else a
; CFG: d entry a
def void @entry() {
   br label %a


# Which terminators do you return for bbs without a successor. Are these
automatically return blocks or can these also be unreachable?

Most of the above comments are mostly to provide you with more ideas. I
generally like the approach. As you are the one using it most at the
moment, you likely know best where to put emphasis on.


> ~Kuba
> -- 
> Jakub Kuderski
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

More information about the llvm-dev mailing list