How to use LLVM to generate a call graph?

Question

I'm looking into generating a call-graph for the linux kernel that would include function pointers (see my previous question Static call graph generation for the Linux kernel for more information). I've been told LLVM should be suitable for this purpose, however I was unable to find the relevant information on llvm.org

Any help, including pointers to relevant documentation, would be appreciated.

Solution

First, you have to compile your kernel into LLVM IR (instead of native object files). Then, using llvm-ld, combine all the IR object files into a single large module. It could be quite a tricky thing to do, you'll have to modify the makefiles heavily, but I believe it is doable.

Now you can do your analysis. A simple call graph can be generated using the opt tool with -dot-callgraph pass. It is unlikely to handle function pointers, so you may want to modify it.

Tracking all the possible data flow paths that would carry your function pointers is quite a challenge, and in general case it is impossible to do (if there are any pointer to integer casts, if pointers are stored in complicated data structures, etc.). For a majority of specific cases you can try to implement a global abstract interpretation to approximate all the possible data flow paths for your pointers. It would not be accurate, of course, but then you'll get at least a conservative approximation.

Comments

[Ira Baxter]

You really don't want to produce a dot callgraph for 8 million lines of code. It would cover a tennis cour, if dot could draw it, which it can't. Other than that, this is a great echo of the answer to the other question note by OP :-} with special emphasis on what fun function pointers are.

[SK-logic]

@IraBaxter, certainly you don't want to display a dot callgraph for anything bigger than "hello, world!". But you may want to use that .dot file for your further analysis. I normally parse .dot files and store them into a database.

[addalbx]

Thanks for pointing out the opt tool. Yes, Ira, I'm not looking into generating a graphical representation of the call graph. Having it in any parsable format is OK, which the dot format qualifies for. Concerning function pointers, I have been told that LLVM should be able to do some of that points-to analysis for function pointers. I am not looking into implementing this myself, clearly.

[user]

llvm-ld is deprecated, use llvm-link or gold plugin instead.