Call-graphs

Dizz

Hi all - me again! :P - I'm looking for a piece of kit (library, application) that will read in a number of C source files and given an arbitary entry point (method/function) the software will create an in-memory call-graph starting at the given entry point and will allow me to emit code based on the call-graph. Any suggestions?

Cheers

Dizz

flav0rflav

Run time? Various debugger interfaces will give you the info. Windows has a dll for debugging help that'll do it.

Just from the source files? Well for a start it won't be possible if there are function pointers involved. But that's usually a small number of cases. A number of source code editor's create just such databases of code symbols, and can be scripted. I use Source Insight, from Source Dynamics. There are also various unix tools that'll do it too. ctags will start you in the right direction. Do a search for software engineering tools, specifically source code reverse engineering or reverse documentation or call tree generators, there are a number out there, I'm just too much of a bastard to do the search for you.

Also some compilers/linkers can have the ability to output such info, as they use it for optimisation.

Dizz

Hmmm - I've a feeling those tools don't offer what I'm looking for... I've been looking at SUIF and at the modifying the IR of gcc. What I need to do is with the generated call graph is to specialise the call graph with respect to the library and in doing so reducing the library size. ctags, Source Insight etc seem (tho I've only quickly looked at them... I'll study them later) more introspective than anything.

Dizz

BTW: The stuff is at compile-time so yep there may be problems with function pointers - fun fun!:rolleyes:

flav0rflav

Hmm, sounds interesting, but I don't quite follow what you mean. Do you want to change the call graph to reduce it's use of the library functions. Or do you want to change the library based on the call graph? OR, based on the call graph, make different choices of library functions?

Uh, I've probably muddied the waters further.

Dizz

Nope the waters are perhaps more clear! What I want to do is to change the library based on the call graph. Libraries tend to encapsulate functionality for the general case and unfortunately applications of the specific case using the library have to suffer the library's genericity ie code bloat. So what I want to do is to strip all but the required functionality out of the library and residualise the library.

Now what is begining to dawn on me - correct or not - is whether or not I could use a partial evaluator for this task, but I've a suspicion that it ain't the tool for the job.

Dizz

Tenshot

I may have missed the point, but wouldn't it be simpler to instead just factor all the functions into separate source files (one per function), and then let the linker worry about which files (i.e. functions) need to be pulled in for a particular library use?

Global variables make it a bit trickier, but just dump them all into a single file on their own - a well designed library will hopefully not have too many.

(Later...) Okay, maybe I did miss the point - you want to figure out at compile time what parts of the library a particular caller is going to end up requiring, and essentially compile out the other parts? E.g. if a caller to printf was only using %s and %f, you wouldn't bother compiling the code to handle %d?

Strikes me as horrendously difficult to solve in the general case!

ecksor

The first thing that comes to mind when looking for a call graph for C is to check out cflow, which doesn't do what you want straight off, but does produce a call graph. I don't know how suitable it is for code emission.

Partial evaluation might be an efficiency gain, but what you're describing also sounds like it could be program slicing (I can't think of an example where this would be practically useful for what you describe though). I think you should define exactly what you mean by 'efficiency' (speed, size, memory usage, ?) and 'bloat'.

Is this supposed to be able to understand binary libraries?

Dizz

Tenshot:
Yea your fist idea regarding function per file would be sweet only I'm afraid that it wouldn't take into account the more dynamic things in a system such as function pointers.
As to the second part, the fuctionality you talk of there is the type a partial evaluator you give you ie you know that part of the funtion parameters are static so just account for the dynamic aspect (/me explains PE ina hand waving way )
Yea what I need to do is sounding kinda difficult to do but hey there'd be no challenge then!

ecksor:
Yea I've looked at cflow, me reckons not quite the tool in itself, tho if the source is freely available it could be nicely hackable
Oooo program slicing... gotta look that up and get back about it.
With regards to efficency, I'm looking at speed and size (both disk and in memory) so that's them all! Lets just say the target area is embedded systems so in this area both efficency in both size and speed are important.

Dizz

E&OE

PS: Sorry for the delay in replying