llvm dev - Mar 2010 - [LLVMdev] Why is BasicBlock's copy constructor private?

On 03/26/10 01:04, Trevor Harmon wrote:
> Hi,
>
> LLVM provides basic graph traversal for its CFGs, but I need
> additional operations, such as iterating over the edges. I thought I
> would solve this problem using the Boost graph library. It should be
> relatively simple to walk an LLVM CFG and add the BasicBlock objects
> to a Boost graph declared as:
Hi Trevor,

I am not 100% sure why you should not copy a BasicBlock, however I 
believe two times the same BasicBlock does not make any sense in a CFG. 
There would be inconsistencies as e.g if a BB A is the successor of B 
there are two equal basic blocks A and A' after copying A, but only one 
(A) can be the real successor. The other one (A') is not referenced, but 
still references B as the predecessor of A'.
So for me the reason is that BasicBlocks are not independent and can 
just be copied. They are connected to their environment and cannot be 
exactly the same. Even the statements in the basicblock always have to 
be different, as every register in LLVM can only be written once per 
function.


To copy a BasicBlock in LLVM you should probably create a new one and 
copy the statements into the new BasicBlock. This obviously does not 
work for boost.

Some basic functionality for graph traversal is already in LLVM (as you 
mentioned) like iterating over edges, children or doing stuff like 
depthfirstsearch or post order search.
What kind of graph algorithm would you like to execute that is not 
available in LLVM?

Tobi

On Mar 25, 2010, at 5:40 PM, Tobias Grosser wrote:
> Some basic functionality for graph traversal is already in LLVM (as  
> you
> mentioned) like iterating over edges, children or doing stuff like
> depthfirstsearch or post order search.
> What kind of graph algorithm would you like to execute that is not
> available in LLVM?
Well, iterating over the edges was one of the first things I'd wanted  
to do. But I spent hours reading the source code and couldn't figure  
out how. AFAICT there are no actual "edge" objects that can be  
iterated over.

The edges also need to have IDs assigned to them so that, for example,  
if Basic Block "A" has a successor "B", the outgoing edge of
A will
have the same ID as the incoming edge of B.

But it wasn't just this functionality I needed from Boost. The sample  
code and documentation would also be a big help, as I was having  
trouble figuring out LLVM's graph functionality just from its source  
code. That's why I'm trying to convert LLVM's CFG into a Boost
graph.

Trevor