llvm dev - Nov 2003 - [LLVMdev] Basic Block Chaining

Newbie Question .. (sorry if its redundant/silly) ..

As I've started to develop Stacker, I  had assumed that simply adding
BasicBlocks to a function in sequence would imply that there is an
implicit unconditional branch from the end of one basic block to the
start of the next block. Based on the assertion checks that I get when I
tried this, I assume that it is required to place a terminating
instruction at the end of every basic block even if that should simply
be a branch to the start of the next block. Is this indeed the case?

If it is, it would be "user friendly" to simply supply the branch
instruction.  That is, provide a method on Function that appends a
BasicBlock to the end of the block list. If the existing final basic
block doesn't have a terminating instruction, simply add one that points
to the block being appended.  Is this the RightThing(tm) or are there
good reasons this can't or shouldn't be done?  

The method I'm thinking of is something like:


Function::chainBasicBlock( BasicBlock* bb )
{
    BasicBlock& previous = this->back();
    TerminatorInst* terminator = previous.getTerminator();
    if ( ! terminator )
    {
        BranchInst* branch = new BranchInst(bb);
        previous.push_back( branch );
    }
    BranchList.push_back( bb );
}

Reid
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20031120/caf0f79e/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 189 bytes
Desc: This is a digitally signed message part
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20031120/caf0f79e/attachment.sig>

This seems hard to use safely.  First, it implies that the last 
inserted BB will be at the end of the list.  Second, and more serious, 
it has very different behavior if the last BB does or  does not have a 
terminator, which does not seem to be a desirable thing (this could be 
fixed by making this function illegal, i.e., asserting out, if the last 
BB does have a terminator).

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

On Nov 20, 2003, at 2:39 AM, Reid Spencer wrote:
> Newbie Question .. (sorry if its redundant/silly) ..
>
> As I've started to develop Stacker, I  had assumed that simply adding 
> BasicBlocks to a function in sequence would imply that there is an 
> implicit unconditional branch from the end of one basic block to the 
> start of the next block. Based on the assertion checks that I get when 
> I tried this, I assume that it is required to place a terminating 
> instruction at the end of every basic block even if that should simply 
> be a branch to the start of the next block. Is this indeed the case?
>
> If it is, it would be "user friendly" to simply supply the branch
> instruction.  That is, provide a method on Function that appends a 
> BasicBlock to the end of the block list. If the existing final basic 
> block doesn't have a terminating instruction, simply add one that 
> points to the block being appended.  Is this the RightThing(tm) or are 
> there good reasons this can't or shouldn't be done? 
>
> The method I'm thinking of is something like:
>
>
> Function::chainBasicBlock( BasicBlock* bb )
> {
>     BasicBlock& previous = this->back();
>     TerminatorInst* terminator = previous.getTerminator();
>     if ( ! terminator )
>     {
>         BranchInst* branch = new BranchInst(bb);
>         previous.push_back( branch );
>     }
>     BranchList.push_back( bb );
> }
>
> Reid
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: text/enriched
Size: 1837 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20031120/bade0f49/attachment.bin>

On Thu, 20 Nov 2003, Reid Spencer wrote:
> Newbie Question .. (sorry if its redundant/silly) ..
No worries, this is good stuff to have archived on the list!
> As I've started to develop Stacker, I  had assumed that simply adding
> BasicBlocks to a function in sequence would imply that there is an
> implicit unconditional branch from the end of one basic block to the
> start of the next block. Based on the assertion checks that I get when I
> tried this, I assume that it is required to place a terminating
> instruction at the end of every basic block even if that should simply
> be a branch to the start of the next block. Is this indeed the case?
Yup, every basic block must end with a terminator.  The terminators are
what build the implicit CFG in LLVM (ie, the presence of terminators
makes pred_iterator & succ_iterator work on basic blocks).
> If it is, it would be "user friendly" to simply supply the branch
> instruction.  That is, provide a method on Function that appends a
> BasicBlock to the end of the block list. If the existing final basic
> block doesn't have a terminating instruction, simply add one that
points
> to the block being appended.  Is this the RightThing(tm) or are there
> good reasons this can't or shouldn't be done?
I agree with Vikram that this would be hard to implement in a generally
useful way.  Besides that, you can always do something like this to add a
new basic block, assuming the last basic block in the function is
unterminated:

---

// Get the last basic block in the function, presumably you already have
// this cached somewhere.
BasicBlock *CurrentEnd = &F->back();

// Create the new basic block, adding the Function parameter causes it to
// be automatically inserted at the end of the function.
BasicBlock *New = new BasicBlock("label", F);

// Create a new branch instruction, jumping to the 'New' block.  Specify
// where in the LLVM program to insert it, in this case, at the end of the
// CurrentEnd block.
new BranchInst(New, CurrentEnd.end());

---

This is basically the strategy used to generate code by the C front-end as
well: there is always an unterminated block at the end of the function
which we are emitting statements into.  When a control flow instruction is
encountered, like an 'if', we emit the conditional branch, create a new
basic block to emit into, recursively generate the body, then emit the
else/fallthrough blocks.

-Chris

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

> // Create a new branch instruction, jumping to the 'New' block. 
Specify
> // where in the LLVM program to insert it, in this case, at the end of the
> // CurrentEnd block.
> new BranchInst(New, CurrentEnd.end());
Actually, I just realized that this won't work.  This will attempt to
dereference the end iterator, which will cause an assertion to fire.
Instead, use the (just now checked in) constructor that takes an 'insert
at end' block:

new BranchInst(New, 0, 0, CurrentEnd);

The 0's are to indicate that an unconditional branch should be made, not a
conditional branch.

I added some documentation for all of the return and branch ctors
available here:
http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20031117/009698.html

-Chris

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