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

[Tobias Grosser via llvm-dev]

On Wed, Jun 28, 2017, at 12:31 AM, Jakub (Kuba) Kuderski via llvm-dev
wrote:
> 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() {
entry:
   br label %a

a:
  return
}
---------------------------------

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

Best,
Tobias

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