Re: Loop dependency analysis for C programs

Paul Anderson <notme@nowhere.com>
1 Dec 2006 09:19:34 -0500

          From comp.compilers

Related articles
Loop dependency analysis for C programs renjith.varma@gmail.com (renjith.varma@gmail.com) (2006-11-29)
Re: Loop dependency analysis for C programs DrDiettrich1@aol.com (Hans-Peter Diettrich) (2006-11-29)
Re: Loop dependency analysis for C programs renjith.varma@gmail.com (renjith.varma@gmail.com) (2006-11-30)
Re: Loop dependency analysis for C programs dima@rts.ua (Dmitry Marienko) (2006-12-01)
Re: Loop dependency analysis for C programs Sid.Touati@inria.fr (Sid Touati) (2006-12-01)
Re: Loop dependency analysis for C programs notme@nowhere.com (Paul Anderson) (2006-12-01)
Re: Loop dependency analysis for C programs neal.wang@gmail.com (neal) (2006-12-01)
Re: Loop dependency analysis for C programs robert.hundt@gmail.com (Robert H) (2006-12-03)
| List of all articles for this month |

From: Paul Anderson <notme@nowhere.com>
Newsgroups: comp.compilers
Date: 1 Dec 2006 09:19:34 -0500
Organization: Compilers Central
References: 06-11-11806-11-128 06-11-134
Keywords: analysis
Posted-Date: 01 Dec 2006 09:19:34 EST

Renjith:


>>>I am planning to do loop dependency analysis for C programs. Could you
>>>tell me the best way to get the loop structure?
>>
>>You want to create an "control flow graph" (CFG).
>>
>>DoDi
>
>
> But how can CFG help in loop dependency analysis. I want to find out
> whether the iterations of a particular loop are paralleizable. For this
> i need to get the loop index variable and anyother variables depending
> on that.
>
> I got one parser named 'ELSA'. It has the option to write the AST into
> an XML file. I think i can use some xml parser to get an AST data
> structure from that. But is there any other tool that provides an AST
> that can be directly used in my program?


You should check out our product CodeSurfer. For a C/C++ program it
produces a variety of representations:


        ASTs, both unnormalized and normalized
        CFGs, one for each procedure with each node associated
                with a normalized AST fragment
        The call graph, and the strongly-connected components thereof
        Basic blocks
        SSA form
        GMOD/GREF, the set of non-local variables modified/used
                directly or transitively for each procedure
        Control dependence
        Data dependence
        Summary edges
        The points-to graph, based on Andersen's context and
                flow-insensitive algorithm, but with extensions
                that yield some context sensitivity.


These representations are all cross-associated, and there is a
coordinate system that allows a user to get back to the source
text.


There are built-in queries on these representations, including
slicing and chopping. The Path Inspector extension provides
model checking on the interprocedural control flow graph, with
the property to be checked specified as a state machine.
Counter examples are shown as paths through the program.


These analyses are interprocedural and whole program. Computing
some of them can be very expensive, so you can turn off those
that you don't need.


Scheme is used as a scripting language, giving access to all
of the above representations.


See http://www.grammatech.com


If you are an educator you can sign up for our academic program,
which lets you use CodeSurfer free of charge.


We don't compute loop-carried dependence edges or anti-dependence
edges, but you can code those up fairly easily.


I hope this helps,


Paul Anderson
GrammaTech, Inc.


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.