What I did in one case was to make sure that the part of the C code that did most of the work was completely independent of the code that interfaces with Perl, so that it could be compiled and profiled separately as a standalone C program. YMMV.
Comment on Re: Profiling the C side of an Inline::C module
That's a good idea, but I think it would be hard in this case. The code includes a lot of calls to Perl functions (sv_catpvn, for example) and the relative performance of those calls is important.