Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1996-05-15
2002-04-30
Millin, Vincent (Department: 2165)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S152000, C714S037000, C714S038110
Reexamination Certificate
active
06381739
ABSTRACT:
CROSS REFERENCE TO RELATED APPLICATION
This application is related to our copending patent application entitled METHOD AND APPARATUS FOR ANALYZING CONTROL FLOW, filed of even date herewith and assigned to the assignee hereof.
This application is related to our copending patent application entitled METHOD AND APPARATUS FOR SEQUENCING COMPUTER INSTRUCTION EXECUTION IN A DATA PROCESSING SYSTEM, filed of even date herewith and assigned to the assignee hereof.
FIELD OF THE INVENTION
This invention generally relates to compiler and profiler technology for microprocessors and specifically relates to sequencing instructions for optimal data processor execution.
BACKGROUND OF THE INVENTION
FIG. 1
illustrates a control flow graph for a computer program. In the control flow graph of
FIG. 1
, there are ten computer instructions or ten segments of code (referred to also as basic blocks of computer code) represented as nodes “a”-“j” in a directed graph. The ten nodes of
FIG. 1
are labeled “a” through “j” and correspond to ten different basic blocks of computer code. In the control flow graph of
FIG. 1
, the computer instruction(s) in basic block a are executed first in time in the execution path of the computer program. Since basic block “a” is the endpoint of a feedback path or looping path from basic block “j” back to basic block “a”, basic block a may contain, for example, a while loop instruction, a for loop instruction, a repeat instruction, a do loop, or a like looping structure or basic block “j” can contain a branch instruction which has a destination address of the beginning of basic block “a”.
After the basic block “a” is executed, sequential execution results in basic block “b” being executed following every execution of basic block “a” as illustrated in the control flow graph of FIG.
1
. Execution flow will split in one of two directions after basic block “b” is executed depending upon a software condition. Therefore, basic block “b” contains either an if-then-else instruction, or a like flow construct which involves branching down one of two distinct and different execution flow paths. If one condition or set of constraints is detected in the basic block “b”, basic block c is executed. If another condition or set of constraints are determined to exist in basic block “b”, then the basic block d is executed. In either case, one of “c” or “d” is executed at a time after “b” is executed as illustrated in FIG.
1
. Both basic blocks “c” and “d” converge back to basic block “e” in a manner similar to an if-then-else flow control. In other words, after executing one of either “c” or “d”, the code contained in basic block “e” will be executed.
From basic block “e” or node “e” of the directed graph of
FIG. 1
, execution flow continues so that basic block “f” is executed. The basic blocks “f”, “g”, “h” and “i” of
FIG. 1
are of a construct very similar to basic blocks “b”, “c”, “d” and “e” discussed above, and therefore these two sets of basic blocks are executed in a similar or identical execution flow manner. Once the basic block “j”, which is a loop termination point as discussed above, determines that no more loops need to be made through the nodes of
FIG. 1
, then the execution flow of the computer program exists the construct of
FIG. 1
via the exit path from node “j”.
The execution flow of the computer program illustrated in
FIG. 1
can be analyzed to determine efficient rearrangement of computer basic blocks in memory so that software executes in an efficient manner. In order to do so,
FIG. 2
illustrates that an execution tracing routine is performed to collect data from the execution of the computer program graphically illustrated in FIG.
1
. This trace process creates a trace data file in memory. The trace data file illustrated in
FIG. 2
records the time-sequential execution flow of the computer program graphically illustrated as basic blocks of code in FIG.
1
. The trace data stores block execution order in a time sequential manner. Spaces (“ ”) are used in
FIG. 2
to separate different executed passes of the loop a-j from each other.
Therefore, in order to create the trace file in
FIG. 2
, an empty trace data file is first created and execution of the basic blocks a-j begins. The time sequential order of the basic blocks executed in a first loop through basic blocks a through “j” is {abcefgij}. Therefore, in a first loop, recorded in a left-hand side of
FIG. 2
, the {b-c} path is taken in FIG.
1
and the {f-g} path is taken in
FIG. 1
resulting in the blocks {abcefgij} being executed in a time sequential order. The basic block “j” directs the execution flow back to basic block “a”, and the second loop sequence in
FIG. 2
is {abcefgij}. Therefore, the same instruction sequence {abcefgij} executed twice in a row, one right after another, a time sequential manner via the loop from block “j” to block a. This time sequential execution flow is continually recorded for a period of time and stored in the trace data file for further analysis at a subsequent time.
A computer is then able to graphically model the computer software as illustrated in
FIG. 3
by analyzing the trace data of FIG.
2
. It is important to note that when first executing the computer program containing blocks a-j to generate the trace data file in
FIG. 2
, the computer has no idea of the execution flow of the software as illustrated in FIG.
1
. The trace file of
FIG. 2
is analyzed to obtain the execution flow structure of
FIG. 3
which also contains the same information contained in FIG.
1
.
The directed graph of
FIG. 3
is constructed by scanning the trace data in
FIG. 2
from left to right and analyzing pairs of basic blocks that are adjacent each other in time. Initially, no data structure is present when the algorithm begins (
FIG. 3
is blank in a starting state). The algorithm then takes the first pair of basic blocks in
FIG. 2
, which is the pair ab. In
FIG. 3
, a node “a” is created, a node “b” is created and an edge “ab” from node “a” to node “b” is created with a weight or count of 1. In a second access to the data of
FIG. 2
, the pair “bc” is next analyzed. Since the node “b” has been previously created in
FIG. 3
, the computer simply creates a node “c” and an edge “bc” from “b” to “c” with a weight of 1. This interconnection and/or creation of nodes and edges and the incrementing of weights of the edges between nodes as further pairs of nodes are encountered continues for the entire data segment illustrated in
FIG. 2
to result in the completed data structure illustrated in FIG.
3
. As illustrated in
FIG. 3
, the basic block b follows basic block a nine times in
FIG. 2
whereas basic block c follows basic block b only five times in
FIG. 2
as evident from the weights on the edges “ab” connecting nodes “a” and “b” and the edge bc connecting nodes “b” and “c” illustrated in FIG.
3
.
Once the data structure of
FIG. 3
is created from the trace file of
FIG. 2
, a method illustrated in the flowchart of
FIG. 4
can be performed to analyze the data structure of
FIG. 3
to determine an efficient manner of ordering basic blocks in memory so that cache performance may be improved and pipeline flushing may be minimized resulting in improved processor performance. The efficient output order of basic blocks (the output file resulting from the method of
FIG. 4
) is illustrated in FIG.
5
. In order to discuss
FIG. 4
of the prior art restructuring method, it is important to refer to
FIG. 5
, which is the output of the method of FIG.
4
.
Initially, the method of
FIG. 4
begins via an initialization step
100
which prepares for the formation of a sequence chain or reordered basic blocks of instructions. In step
102
, the node in
FIG. 3
that has not been so far selected with the highest exiting path/edge value is selected. In
FIG. 3
, the nodes “a”, “e”, and “i” are tied in numerical value for the highest path value where this path/edge value is 9 in FIG.
3
. Nine is the greatest edge value in FIG.
3
Breternitz, Jr. Mauricio
Smith Roger A.
Gariazzo Joanna P.
Millin Vincent
Motorola Inc.
Nguyen Cuong H.
LandOfFree
Method and apparatus for hierarchical restructuring of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for hierarchical restructuring of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for hierarchical restructuring of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2869565