[LLVMdev] CFG using LLVM

[John Criswell]

Hersh.S. Iyer wrote:
> I used successors to find the basic blocks that can be visited and 
> those that cannot be reached.
> My pass just prints out those blocks which can be reached. The problem 
> is that I want to include
> this in my compiler code rather than as a separate .cpp file which 
> will perform the pass when I use 'opt'.
> I have seen that there is something called a PassManager class. Will 
> this help me any way ?
> Basically, I want to run this pass on the functions and generate the 
> optimized .ll file.
> Right now, the .ll file is generated without optimizations. Also, is 
> there a way that I can make
> LLVM generate unreachable basic blocks ? I need to test my pass and 
> not able to find suitable examples.
Yes, you can create a PassManager object and use it to run any number of 
LLVM analysis and transform passes from your own C++ program (there are 
hooks for C and other languages, too).  For examples on how to use it, 
you can look at the source code of opt (found in the LLVM distribution), 
pa (found in the poolalloc distribution), or sc (found in the SAFECode 
distribution that I sent email to llvmdev about last Friday).

As for your second question, I do not know how to convince LLVM to 
generate code for basic blocks that it has determined are unreachable.  
I suppose the easiest thing to do would be to make the unreachable basic 
blocks appear reachable so that they don't get eliminated.  To do that, 
you would do the following:

1) Add a global constant variable that is assigned the value of zero.
2) Add a volatile load to the entry basic block.
3) Change the terminator instruction of the entry basic block so that it 
is a switch instruction that switches on the result of the volatile 
load.  The 0 tag will cause it to branch to its original destination.  
Other tags will cause it to branch to the unreachable basic blocks.

The basic blocks will still be unreachable, but because the load is 
volatile, LLVM won't optimize it away, and therefore, LLVM won't be able 
to tell that those blocks are unreachable.

-- John T.

>
> Regards,
> Hersh
>
> On Sat, Nov 14, 2009 at 2:53 PM, John Criswell <criswell at uiuc.edu 
> <mailto:criswell at uiuc.edu>> wrote:
>
>     Hersh.S. Iyer wrote:
>
>         Hi John,
>
>         Thanks for the reply.
>         I read the document and was able to write simple passes too.
>         I used members of CFG.H to find the successor and predecessor
>         of the blocks.
>         So this way I get to know which blocks are reachable and which
>         are not.
>         All this said and done, if a block is not reachable, can I
>         delete it?
>
>     In general, yes, I believe you can delete it, unless you want to
>     optimize programs that utilize undefined behavior (e.g., a program
>     that manufactures function pointers).
>
>     There are more aggressive algorithms that perform constant
>     propagation along with dead code elimination; this can reveal
>     basic blocks that are reachable through conditional branches but
>     for which the condition can be proven constant if dead code is
>     ignored.
>
>         The function pass goes over each function in the .ll code and
>         finds basic blocks in them. So
>         all I need to do is to create a new .ll file which is same as
>         the old one except that the dead
>         blocks are gone.
>         The inbuilt passes won't work as I need to write my own pass.
>
>     Why do you need to write your own pass?  Passes can be executed
>     one after another, so if you pass needs to do something else
>     besides remove dead basic blocks, you run the dead code
>     elimination pass first and then your pass after it.
>
>     -- John T.
>
>         Your help is appreciated.
>
>         Thanks,
>         Hersh
>
>         On Sat, Nov 14, 2009 at 10:14 AM, John Criswell
>         <criswell at uiuc.edu <mailto:criswell at uiuc.edu>
>         <mailto:criswell at uiuc.edu <mailto:criswell at uiuc.edu>>> wrote:
>
>            Hersh.S. Iyer wrote:
>
>                Hi,
>
>                I am a new user of LLVM. I am using it as the IR for a
>                compiler for a subset of LUA.
>                I have the .ll file ready and it executes fine when
>         passed to
>                the llvm interpreter.
>
>            Welcome!
>
>
>                Now, I wish to perform a few optimizations to the code
>                starting with dead code elimination.
>                For this I would need the CFG. I am very new to all of this
>                stuff. Please help me out guys.
>                The way I want to proceed is to start at the top of the CFG
>                and then find out the blocks
>                reachable from here. At the end, if any basic block remains
>                unreachable, then I would
>                classify it as dead code.
>
>            LLVM already has at least two dead-code elimination passes
>         (-dce
>            and -adce); I believe it also has a pass to remove dead basic
>            blocks.  These can be run using the opt tool and can be
>            incorporated into any tool that you're building.  They're
>            documented at http://llvm.org/docs/Passes.html.  Is there a
>         reason
>            these won't work for your purpose?
>
>            If you do need to write your own pass, you'll notice that
>         the CFG
>            of a function is explicit in the IR: each basic block ends
>         with a
>            terminator instruction which explicitly lists the successor
>         basic
>            blocks to which control flow can move.  Assuming that you
>         write a
>            function pass (which is given a Function & reference as input),
>            you can find the entry basic block by using the getEntryBlock()
>            method and then follow the CFG by finding the basic block's
>            terminator instruction (using the getTerminator() method)
>         and then
>            finding the successors listed in the terminator instruction
>         (using
>            the getSuccessor() method).
>
>            You'll find doxygen (http://llvm.org/doxygen/hierarchy.html)
>            invaluable in looking up what methods each class has and how to
>            use them.
>
>            Have you read the Programmer's Manual and the "How to Write an
>            LLVM Pass" document?
>
>            -- John T.
>
>
>                I read a few things about llvm passes and felt this
>         could be
>                made a pass. Please let me
>                know what's the right and fastest way to do this.
>
>                Regards,
>                Hersh
>
>
>
>
>
>         -- 
>         HSIyer
>
>
>
>
>
> -- 
> HSIyer