[LLVMdev] Reversing a function's CFG?

[Justin M. LaPre]

On Mar 23, 2011, at 12:24 PM, Joshua Warner wrote:

> Hi Justin,
> 
> I take the fact that nobody has replied as a sign that nobody really understands what you are asking.

Most likely.  I was trying not to write a ten page e-mail to the list but quite possibly simplified too much.  I'll try to elaborate a little more:

In large-scale parallel simulations, sometimes you process an event speculatively.  If it turns out you should not have processed that event (and such situations can be detected by our system), you need to undo all of the changes you made in your event handler.  Most approaches use some form of state-saving.  We opt for an approach coined by my advisor (Chris Carothers, actually) called "reverse computation."  The reverse function is basically the inverse of the forward event handler e.g. if in the forward event handler you increment a variable, the reverse handler would need to decrement it.  That's an extremely simple case.  A more complicated case: if you have an "if" in your forward handler, you must augment it with a bitfield to remember which path you took so the reverse handler can find its way back.  So we're basically saving our control state as opposed to our data state as the control state is often significantly smaller.  I like to think of it as a trail of breadcrumbs.  Using different approaches we can handle loops, ifs, switches, etc. by following our "breadcrumbs" back.

> I was wondering if there was a quick way to reverse a function's CFG and, in turn, all basic blocks within it.  Assuming all variables are globals, is there a quick way to generate a function's reversal?  I highly doubt such functionality exists but I figured it was worth asking.  I'm trying to develop an "undo function" generator pass that would be able to restore system state (without state-saving) after determining an error occurred.  This is documented in, "Efficient Optimistic Parallel Simulations using Reverse Computation" by Carothers et al.[1]
>  
> 
> I'm unaware of an easy way to "reverse the CFG" - but even if there was, I don't think that would solve your problem.  First, you will only be able to generate "undo" functions for a small subset of all possible functions - specifically, invertible functions.  Second, my intuition is that computing an inverse function will be significantly more involved than just reversing the CFG.

Reversing the CFG is just a piece of the puzzle.  To generate our reverse handler, I thought a good place to start would be the reverse CFG.  Specifically, I need to:

1. instrument the forward handler control path
2. emit the reverse handler given the forward handler (which I believe can be achieved by the following)
2a. create the reverse CFG
2b. for each basic block in (2a), invert the instructions

Unfortunately, not all functions are invertible as you said.  In those cases, we may opt to fall back on state-saving or use some heuristics to try and bypass state-saving (memory operations can be expensive on some of the machines we run simulations on).

Assuming the above steps go off without a hitch (which is a big assumption), we should have our reverse event handler generated for us.

I do have some questions: is there any way to differentiate IR I inserted while instrumenting the forward path from IR that was there before?  I don't want to invert my instrumentation instructions.  Also, due to this problem, I've been attempting to write a Module pass as opposed to a Function pass because I couldn't differentiate between the two.

> Could you be a little more specific about the problem you are dealing with?  How do Carothers et al. do the inversion?

Carothers did it all by hand! :)  In the paper he talks about automating it.  As I have taken a few compiler courses, apparently I'm the compiler guy in our HPC group.

Anyway, thanks for the response.  If I was unclear in any way, please ask questions!

-Justin


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110323/c9906f2f/attachment.html>