One embodiment of the present invention provides a system that dynamically configures selected methods for instrument-based profiling at run-time. The system operates by identifying a root method in a target application, wherein methods that are reachable from the root method during execution of the target application are to be instrumented. Upon loading of a new method during execution of the target application, the system identifies methods in the target application that become reachable from the root method through the new method. The system then instruments methods that are reachable, loaded and have not been instrumented before.