One embodiment of the present invention provides a system that facilitates configuring selected methods for instrument-based profiling at run-time. The system first identifies a root method in a target application, wherein only methods that are reachable from the root method during execution of the target application are to be instrumented. The system then instruments the root method. Next, while subsequently executing a given instrumented method, the system determines if the given instrumented method is about to be executed for the first time. If so, the system instruments any methods that are called by the given instrumented method, are loaded, and have not been instrumented before.