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

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:

1. To mark the section of code to be cut out, I'm using "magic" 
function calls (begin() and end()). In order to locate these calls, I 
am currently iterating over the basic blocks in a function using the 
iterator. Is it possible that I could get the blocks "out of order" 
with respect to the control flow? For example, if I have this code:

blockA
if ( blockB ) {
	blockC
} else {
	blockD
}
blockE

I expect to get the blocks in alphabetical order. I can see that it is 
possible that LLVM could give them to me in an arbitrary order. If so, 
it will complicate how I need to locate the basic blocks that compose 
"code B" in my example above.


2. I am going to need to pass dependencies for the "code B" block into
the new function. I'm hoping that it work if I just create the 
arguments with the same name and type as the dependencies, then use 
"setParent" to transfer the basic blocks to the new function. However,
after staring at the "instruction" object a little bit, I am starting 
to think that I may need to actually modify each individual instruction 
to point to the arguments. Can anyone straighten me out here?


By the way, I have to say that I am *very* impressed with LLVM's 
documentation and organization. I have been able to get an amazing 
amount of functionality working *very* quickly. This is a really useful 
tool for manipulating code.

Evan Jones

On Apr 19, 2005, at 21:39, Evan Jones wrote:
> 1. To mark the section of code to be cut out, I'm using
"magic"
> function calls (begin() and end()). In order to locate these calls, I 
> am currently iterating over the basic blocks in a function using the 
> iterator. Is it possible that I could get the blocks "out of
order"
> with respect to the control flow?
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.

Thanks,

Evan Jones

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 Tue, 19 Apr 2005, Evan Jones wrote:
> On Apr 19, 2005, at 21:39, Evan Jones wrote:
>> 1. To mark the section of code to be cut out, I'm using
"magic" function
>> calls (begin() and end()). In order to locate these calls, I am
currently
>> iterating over the basic blocks in a function using the iterator. Is it
>> possible that I could get the blocks "out of order" with
respect to the
>> control flow?
>
> 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.
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...

-Chris

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

On Tue, 19 Apr 2005, 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:
> I think I have a pretty good idea of how to do this (BasicBlock::split
really
> helps!), but I have a few specific questions:
ok
> 1. To mark the section of code to be cut out, I'm using
"magic" function
> calls (begin() and end()). In order to locate these calls, I am currently 
> iterating over the basic blocks in a function using the iterator. Is it 
> possible that I could get the blocks "out of order" with respect
to the
> control flow? For example, if I have this code:
>
> blockA
> if ( blockB ) {
> 	blockC
> } else {
> 	blockD
> }
> blockE
>
> I expect to get the blocks in alphabetical order. I can see that it is 
> possible that LLVM could give them to me in an arbitrary order. If so, it 
> will complicate how I need to locate the basic blocks that compose
"code B"
> in my example above.
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).
> 2. I am going to need to pass dependencies for the "code B" block
into the
> new function. I'm hoping that it work if I just create the arguments
with the
> same name and type as the dependencies, then use "setParent" to
transfer the
This is trickier.  In particular, if you have code like this:

   ...
   a = ...
   ---cut---
   X = add a, 1
   ---cut---
   C = add X, b

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. :)
> By the way, I have to say that I am *very* impressed with LLVM's 
> documentation and organization. I have been able to get an amazing amount
of
> functionality working *very* quickly. This is a really useful tool for 
> manipulating code.
Great! :)

-Chris

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