llvm dev - Apr 2005 - [LLVMdev] "Refactoring" Basic Blocks into a new function

On Apr 19, 2005, at 22:10, Evan Jones wrote:
> I just found the Interval class, and it looks like it could help me 
> out here. I want to locate the Interval that begins with the call to 
> the "magic" begin(), and ends with the call to the
"magic" end(), if
> it exists. If there is no such valid interval, then I want to detect 
> that and return an error. Can I make this happen by using the 
> IntervalPartition pass? It looks like LLVM has some functionality that 
> I could use *some where.* I just can't quite figure out how to make 
> use of it.
Ah ha! I figured out the succ_begin() and pred_begin() functions. This 
looks like it *might* be a better way to do things. At the very least, 
I can verify that I have located the chunk of code between begin() and 
end() correctly:

1. All predecessors must be in the interval, except for the initial 
block, which must have a single predecessor: the block that used to 
contain the begin() call.
2. All successors must be in the interval, except for the last block, 
which must have a single successor: the block that was created when 
splitting the block with the end() call.

However, since I am creating the Interval manually, it is possible that 
one of these errors occurs because the blocks are returned out of order 
by the Function::begin() iterator. However, since I only need to worry 
about handling code that is produced by llvm-gcc, I'm not going to 
worry about it.


On to issue #2.

Evan Jones

On Apr 19, 2005, at 8:39 PM, Evan Jones wrote:
> I have two very specific questions about LLVM, but first let me give 
> you the general overview of what I am trying to achieve. I have some 
> section of a function that I want to replace with a function call to a 
> brand new function. For example, I want to take the following 
> function:
>
> function foo:
> 	code A
> <--- CUT
> 	code B
> <--- CUT
> 	code C
>
> and (approximately) convert it into:
>
> function foo:
> 	code A
> 	call label
> 	code C
>
> function label:
> 	code B
>
> I think I have a pretty good idea of how to do this (BasicBlock::split 
> really helps!), but I have a few specific questions:

Evan,

Have you looked at ExtractCodeRegion() and its siblings in 
include/llvm/Transform/Utils/FunctionUtils.h?  It seems to be what you 
need.

--Vikram
http://www.cs.uiuc.edu/~vadve
http://llvm.cs.uiuc.edu/

On Tue, 19 Apr 2005, Vikram Adve wrote:
> Evan,
>
> Have you looked at ExtractCodeRegion() and its siblings in 
> include/llvm/Transform/Utils/FunctionUtils.h?  It seems to be what you
need.
Vikram is exactly right.  The functions in that header can extract an 
arbitrary single entry multiple exit set of basic blocks into a new 
function, and takes care of all of the updating needed for live ins and 
live outs of the code.  If you want to extract something that doesn't 
start/end on a basic block boundary, use of BB::splitBasicBlock would be 
appropriate.

I'm glad LLVM is working out for you!! :)

-Chris

-- 
http://nondot.org/sabre/
http://llvm.cs.uiuc.edu/

On Apr 19, 2005, at 23:17, Vikram Adve wrote:
> Have you looked at ExtractCodeRegion() and its siblings in 
> include/llvm/Transform/Utils/FunctionUtils.h?  It seems to be what you 
> need.
This is brilliant. In fact, it is nearly *exactly* what I need.


On Apr 19, 2005, at 23:59, Chris Lattner wrote:
> An Interval (and an Interval partition) is a concept with a lot of 
> compiler theory behind it.  If you google for control flow analysis 
> and interval you should find info on it.  That said, I don't think it 
> is what you're looking for...
You are right: it's not. As you may be able to tell, compilers are 
*not* my research area, although I do think they are very interesting.


On Apr 20, 2005, at 0:03, Chris Lattner wrote:
> The order of BasicBlock's in an LLVM Function match the order that 
> they are printed.  If you iterate over them, you are guaranteed to get 
> this order.  Note that if you're looking at the output of the C 
> front-end, they could be permuted arbitrarily w.r.t. the source order, 
> due to various optimizations.  That said, if you have begin/end 
> markers in the same basic block, they should stay within the same 
> basic block most of the time (enough for it to not matter).
Yuck. This is what I was afraid of. I do *not* necessarily have 
begin/end markers in the same basic block. In fact, it would be quite 
unusual that they would be in the same basic block. There are likely to 
be intervening conditionals or loops.  From this comment, it seems to 
me that I need to collect my vector of BasicBlocks in a "smarter" 
fashion by actually tracing the control flow from the "begin" marker 
through to the "end" marker. Am I right about this?
> This is trickier.  In particular, if you have code like this:
[snip]
> Then you need to arrange to pass the value of "a" into the new 
> function and get the value of "x" back out of it.  This is
exactly the
> sort of details that ExtractCodeRegion takes care of for you. :)``
Right, this is what I was going to hack on myself. I'm glad I don't 
have to! Like I said, I've been able to implement a surprising amount 
of functionality very easily using LLVM. It's just an issue of figuring 
out what APIs to use.

Browsing through the implementation, I see that it will not work for 
any code that calls alloca or vastart. It seems to me this is not a 
fundamental limitation, but is a limitation of the current 
implementation. Am I right about that? I doubt it will be an issue for 
me anyway.

Evan Jones