SYSTEM FOR DYNAMIC PROGRAM PROFILING
A system and method for efficient whole program profiling of software applications. A computing system comprises a dynamic binary instrumentation (DBI) tool coupled to a virtual machine configured to translate and execute binary code of a software application. The binary code is augmented with instrumentation and analysis code during translation and execution. Characterization information of each basic block is stored as each basic block is executed. A dynamic binary analysis (DBA) tool inspects this information to identify hierarchical layers of cycles within the application that describe the dynamic behavior of the application. A sequence of basic blocks may describe paths, a sequence of paths may describe a stratum, and a sequence of strata may describe a stratum layer. Statistics of these layers and hot paths may be determined and stored. This data storage yields a whole program profile comprising program phase changes that accurately describes the dynamic behavior of the application.
1 . A method for program profiling, the method comprising:
executing program code of a program;
instrumenting said program code during said execution to identify a sequence of basic blocks in dynamic program order;
storing characterization information corresponding to each identified basic block during said execution;
identifying one or more repeated paths during said execution, wherein a path comprises a sequence of basic blocks, wherein each basic block is unique within a corresponding path; and
producing a program profile based upon said execution, wherein said program profile identifies the one or more repeated paths.
2 . The method as recited in claim 1 , further comprising identifying one or more repeated strata during said execution, wherein a stratum comprises a sequence of repeated paths, wherein each repeated path is unique within a corresponding stratum, and wherein said program profile identifies said one or more repeated strata.
3 . The method as recited in claim 2 , further comprising identifying one or more stratum layers during said execution, wherein a stratum layer comprises a sequence of repeated stratum, wherein each repeated stratum is unique within a corresponding stratum layer, and wherein said program profile identifies said one or more stratum layers.
4 . The method as recited in claim 1 , further comprising associating a weight value to each basic block, wherein the weight value corresponds to one or more of the following within the corresponding basic block: a total number of instructions, a number of a certain type of instruction within the corresponding basic block, a total number of clock cycles required for an execution of the basic block, and a total number of cache misses.
5 . The method as recited in claim 4 , further comprising generating a hot value for each path, wherein said generation comprises summing the weight values for each corresponding basic block to produce a sum and multiplying the sum by a number of dynamic occurrences of the path.
6 . The method as recited in claim 4 , wherein the stored characterization information comprises one or more of the following: an address of the first instruction of the basic block, the weight value, and disassembly of the instructions.
7 . The method as recited in claim 3 , further comprising compressing one or more of the following prior to storing: each path, each stratum, each repeated stratum, and each stratum layer.
8 . The method as recited in claim 1 , wherein said execution is performed without use of a simulator.
9 . A computing system comprising:
one or more processors comprising one or more processor cores;
a memory coupled to the one or more processors, wherein the memory stores a program comprising program code;
wherein a processor of the one or more processors is configured to execute program instructions which when executed are operable to:
instrument said program code during execution to identify a sequence of basic blocks in dynamic program order;
store characterization information corresponding to each identified basic block during said execution;
identify one or more repeated paths during said execution, wherein a path comprises a sequence of basic blocks, wherein each basic block is unique within a corresponding path; and
produce a program profile based upon said execution, wherein said program profile identifies the one or more repeated paths.
10 . The computing system as recited in claim 9 , wherein a processor of the one or more processors is configured to execute program instructions which when executed are operable to identify one or more repeated strata during said execution, wherein a stratum comprises a sequence of repeated paths, wherein each repeated path is unique within a corresponding stratum, and wherein said program profile identifies said one or more repeated strata.
11 . The computing system as recited in claim 10 , wherein a processor of the one or more processors is configured to execute program instructions which when executed are operable to identify one or more stratum layers during said execution, wherein a stratum layer comprises a sequence of repeated stratum, each repeated stratum is unique within a corresponding stratum layer, and wherein said program profile identifies said one or more stratum layers.
12 . The computing system as recited in claim 9 , wherein a processor of the one or more processors is configured to execute program instructions which when executed are operable to associate a weight value to each basic block, wherein the weight value corresponds to one or more of the following within the corresponding basic block: a total number of instructions, a number of a certain type of instruction within the corresponding basic block, a total number of clock cycles required for an execution of the basic block, and a total number of cache misses.
13 . The computing system as recited in claim 12 , wherein a processor of the one or more processors is configured to execute program instructions which when executed are operable to generate a hot value for each path, wherein said generation comprises summing the weight values for each corresponding basic block to produce a sum and multiplying the sum by a number of dynamic occurrences of the path.
14 . The computing system as recited in claim 12 , wherein the stored characterization information comprises one or more of the following: an address of the first instruction of the basic block, the weight value, and disassembly of the instructions.
15 . The computing system as recited in claim 11 , wherein a processor of the one or more processors is configured to execute program instructions which when executed are operable to store compressed versions of one or more of the following: each path, each stratum, each repeated stratum, and each stratum layer.
16 . The computing system as recited in claim 9 , wherein said execution does not utilize a simulator.
17 . A computer readable storage medium storing program instructions, wherein the program instructions are executable to:
instrument said program code during execution to identify a sequence of basic blocks in dynamic program order;
store characterization information corresponding to each identified basic block during said execution;
identify one or more repeated paths during said execution, wherein a path comprises a sequence of basic blocks, wherein each basic block is unique within a corresponding path; and
produce a program profile based upon said execution, wherein said program profile identifies the one or more repeated paths.
18 . The storage medium as recited in claim 17 , wherein the program instructions are further executable to identify one or more repeated strata during said execution, wherein a stratum comprises a sequence of repeated paths, wherein each repeated path is unique within a corresponding stratum, and wherein said program profile identifies said one or more repeated strata.
19 . The storage medium as recited in claim 18 , wherein the program instructions are further executable to identify one or more stratum layers during said execution, wherein a stratum layer comprises a sequence of repeated stratum, wherein each repeated stratum is unique within a corresponding stratum layer, and wherein said program profile identifies said one or more stratum layers.
20 . The storage medium as recited in claim 17 , wherein the program instructions are further executable to generate a hot value for each path, wherein said generation comprises summing a weight values for each corresponding basic block to produce a sum and multiplying the sum by a number of dynamic occurrences of the path.