Profile-based optimizing postprocessors for data references

Claim 2

A computer implemented process for directing a computer system having at least a processor, memory, and user controls, to optimize a program at the object code level, said program having memory references, comprising the steps of: instrumenting each of said memory references to create an instrumented program by: setting a pointer to an address; scanning said program to detect one of said memory references; replacing said memory reference with a branch to said pointer; generating instrumentation code at said pointer; generating said memory reference; and repeating said above steps until all of said memory references have been instrumented; executing said instrumented program to capture effective address trace data for each of said memory references; analyzing access patterns of said effective address trace data; in response to said analyzing step, reordering said memory references to create an optimized program.

Claim 3

The process according to claim 1 wherein said step of generating instrumentation code comprises the steps of: saving contents of at least one register; loading an address for a trace buffer into said memory; storing an effective address of said memory reference into said trace buffer; incrementing said address of said trace buffer; and restoring said contents of said at least one register.

Claim 4

The process according to claim 1 wherein said analyzing step comprises the step of: generating a directed flow graph from said effective address trace data to indicate access patterns of said effective address trace data.

Claim 5

The process according to claim 3 wherein said analyzing step further comprises the steps of: from said directed flow graph, generating a reorder list, said reorder list comprising said effective address trace data positioned in sequential order from the most frequent to the least frequent number of executions; and generating a new effective address for each of said effective address trace data.

Claim 6

The process according to claim 4 wherein said memory references comprise a store or load instruction.

Claim 7

The process according to claim 4 wherein said reordering step comprises the steps of: scanning said program for one of said memory references; determining if said memory reference is static; in response to said memory reference being static, determining an effective address for said memory reference; searching said reorder list for said effective address; and in response to finding said effective address in said reorder list, changing said effective address of said memory reference to said new effective address.

Claim 8

A computer system having at least a processor, memory, and user controls, to optimize a program at the object code level, said program having memory references, comprising: a processor; memory; means for controlling said processor to instrument each of said memory references to create an instrumented program including: means for setting a pointer to an address; means for scanning said program to detect at least one of said memory references; means for replacing said memory reference with a branch to said pointer; means for generating instrumentation code at said pointer; and means for generating said memory reference; means for controlling said processor to execute said instrumented program to capture effective address trace data for each of said memory references; means for controlling said processor to analyze access patterns of said effective address trace data; and in response to analyzing said access patterns, means for controlling said processor to reorder said memory references to create an optimized program.

Claim 9

A computer system having at least a processor, memory, and user controls, to optimize a program at the object code level, said program having memory references, comprising: a processor; memory; means for controlling said processor to instrument each of said memory references to create an instrumented program including: means for setting a pointer to an address; means for scanning said program to detect at least one of said memory references; means for replacing said memory reference with a branch to said pointer; means for generating instrumentation code at said pointer; and means for generating said memory reference; means for controlling said processor to execute said instrumented program to capture effective address trace data for each of said memory references; means for controlling said processor to analyze access patterns of said effective address trace data; and in response to analyzing said access patterns, means for controlling said processor to reorder said memory references to create an optimized program.

Claim 10

The system according to claim 7 wherein said means for generating instrumentation code comprises: means for saving contents of at least one register; means for loading an address for a trace buffer into said memory; means for storing an effective address of said memory reference into said trace buffer; means for incrementing said address of said trace buffer; and means for restoring said contents of said at least one register.

Claim 11

The system according to claim 7 wherein said means for analyzing comprises: means for generating a directed flow graph from said effective address trace data to indicate access patterns of said effective address trace data.

Claim 12

The system according to claim 9 wherein said means for analyzing further comprises: from said directed flow graph, means for generating a reorder list, said reorder list comprising said effective address trace data positioned in sequential order from the most frequent to the least frequent number of execution; and means for generating a new effective address for each of said effective address trace data.

Claim 13

The system according to claim 10 wherein said memory references comprise a store or load instruction.

Claim 14

The system according to claim 10 wherein said means for reordering comprises: means for scanning said program for one of said memory references; means for determining if said memory reference is static; in response to said memory reference being static, means for determining an effective address for said memory reference; means for searching said reorder list for said effective address; and in response to finding said effective address in said reorder list, means for changing said effective address of said memory reference to said new effective address.