Devel::NYTProf has worked wonders for me in similar situations - especially if you include the nytprofhtml program, which makes a browsable, annotated html document for all the code usage, including summary lists of all code called, how many times etc..., which will give you the dependancies you need.

Although as Joost says this obviously depends on the tests being up to scratch!