Optimization apparatus for removing hazards by arranging instruction order

An optimization apparatus for removing hazards from a program by rearranging instructions for each program segment, wherein each program segment does not include any jump instruction nor any jump target label, comprising:

• a Directed Acyclic Graph (hereinafter DAG) generating means for generating a plurality of DAGs for each program segment, each DAG showing a relationship between instructions by a parent-to-child relation wherein the parent instructions define resources and the child instructions refer to the resources;
• a hazard marking means for marking hazard-including combinations of a parent instruction and a child instruction in the DAGs as a hazard;
• a rearranging means for rearranging the instructions for each program segment so that instructions are inserted between the instructions of each marked combination, wherein the inserted instructions do not destroy values stored in resources used by the instructions of the marked combination;
• a first priority assigning means for assigning a first priority to a top instruction of a DAG whose descendant instructions include a hazard, and assigning a second priority to a top instruction of a DAG whose descendant instructions do not include a hazard, wherein the first priority is higher than the second priority, and wherein descendant instructions of a top instruction are instructions in the DAG which are traced from the top instruction through parent-to-child relations directly or indirectly;
• and
• wherein the rearranging means comprises:
• an extracting means for extracting a selected top instruction from the DAGs;
• an instruction storage means for storing the extracted instructions serially in order of extraction;
• a destructive instruction detecting means for detecting, as a destructive instruction, a top instruction of a DAG that destroys a value stored in a resource to be referred to later by other instructions in program segments;
• a marked instruction detecting means for detecting a top instruction of a DAG whose parent instruction is a last instruction in the instruction storage means, and which makes up a marked combination with the parent instruction;
• a second priority assigning means for assigning a third priority to the instruction detected by the marked instruction detecting means, wherein the third priority is lower than the second priority;
• an extraction prohibiting means for prohibiting the extracting means from extracting the destructive instruction;
• and
• an instruction selecting means for selecting a top instruction of a DAG which has highest priority and which is not an instruction prohibited by the extraction prohibiting means from being extracted by the extracting means, wherein the extracting means extracts the selected top instruction, and the rearranging means repeats operations of the extracting means through the instruction selecting means until a last instruction of a program segment is extracted, and wherein the optimization apparatus obtains rearranged instructions for the program segment from the instruction storage means.

An optimization apparatus for removing hazards from a program by rearranging instructions for each program segment, wherein each program segment does not include any jump instructions nor any jump target label, comprising:

• a Directed Acyclic Graph (hereinafter DAG) generating means for generating a plurality of DAGs for each program segment, each DAG showing a relationship between instructions by a parent-to-child relation wherein the parent instructions define resources and the child instructions refer to the resources;
• a hazard marking means for marking hazard-including combinations of a parent instruction and a child instruction in the DAGs as a hazard;
• a rearranging means for rearranging the instructions for each program segment so that instructions are inserted between the instructions of each marked combination, wherein the inserted instructions do not destroy values stored in resources used by the instructions of the marked combination;
• and
• a priority assigning means for assigning a higher priority to a top instruction of a DAG whose descendant instructions include a hazard, and assigning a lower priority to a top instruction of a DAG whose descendant instructions do not include a hazard, wherein descendant instructions of a top instruction are instructions in the DAG which are traced from the top instruction through parent-to-child relations directly or indirectly;
• and
• wherein the rearranging means comprises:
• an extracting means for extracting a selected top instruction from the DAGs;
• an instruction storage means for storing the extracted instructions serially in order of extraction;
• a destructive instruction detecting means for detecting, as a destructive instruction, a top instruction of a DAG that destroys a value stored in a resource to be referred to later by another instruction in program segments;
• a marked instruction detecting means for detecting a top instruction of a DAG whose parent instruction is a last instruction in the instruction storage means, and which makes up a marked combination with the parent instruction;
• an extraction prohibiting means for prohibiting the extracting means from extracting the destructive instruction and the instruction detected by the marked instruction detecting means;
• and
• an instruction selecting means for selecting a top instruction of a DAG which has highest priority and which is not prohibited by the extraction prohibiting means, wherein the extracting means extracts the selected top instruction, and the rearranging means repeats operations of the extracting means through the instruction selecting means until a last instruction of a program segment is extracted, and wherein the optimization apparatus obtains rearranged instructions for the program segment from the instruction storage means.

An optimization apparatus for removing hazards from a program by rearranging instructions for each program segment, wherein each program segment does not include any jump instruction nor any jump target label, comprising:

• a Directed Acyclic Graph (hereinafter DAG) generating means for generating a plurality of DAGs for each program segment, each DAG showing a relationship between instructions by parent-to-child relation wherein the parent instructions define resources and the child instructions refer to the resources;
• a hazard marking means for marking hazard-including combinations of a parent instruction and a child instruction in the DAGs as a hazard;
• a rearranging means for rearranging the instructions for each program segment so that instructions are inserted between the instructions of each marked combination, wherein the inserted instructions do not destroy values stored in resources used by the instructions of the marked combination;
• and
• a priority assigning means for assigning a higher priority to a top instruction of a DAG whose descendant instructions, include a hazard, and assigning a lower priority to a top instruction of a DAG whose descendant instructions do not include a hazard, wherein descendant instructions of a top instruction are instructions in the DAG which are traced from the top instruction through parent-to-child relations directly or indirectly;
• and
• wherein the rearranging means comprises:
• an extracting means for extracting a selected top instruction from the DAGs;
• an instruction storage means for storing the extracted instructions serially in order of extraction;
• a destructive instruction detecting means for detecting, as a destructive instruction, a top instruction of a DAG that destroys a value stored in a resource to be referred to later by another instruction in program segments;
• a marked instruction detecting means for detecting a top instruction of a DAG whose parent instruction is a last instruction in the instruction storage means, and which makes up a marked combination with the parent instruction;
• a first resource selecting means for selecting resources which are not used in a data-flow section if the destructive instruction detecting means detects a destructive instruction, wherein the data-flow section ranges from the destructive instruction to a last instruction in the DAG that refers to the resource whose value is destroyed by the destructive instruction, wherein when the resource is defined again halfway, the data-flow section extends to a last reference of data of the re-defined resource;
• a first identifying means for identifying types of the resources selected by the first resource selecting means;
• a second identifying means for identifying types of instructions which either define or refer to the resources and a type of the destructive instruction;
• a second resource selecting means for selecting replacement-candidate resources from the resources selected by the first resource selecting means by making each combination of types of an instruction and a resource, comparing the combination with combination patterns stored in a processor, and excluding resources in combinations that do not match the combination patterns;
• a resource replacing means for replacing a resource defined by the destructive instruction by any of the replacement-candidate resources for each instruction with the resource in the data-flow section;
• an extraction prohibiting means for prohibiting the extracting means from extracting the instruction detected by the marked instruction detecting means and the destructive instruction whose resources have not been replaced by other resources by the resource replacing means;
• and
• an instruction selecting means for selecting a top instruction of a DAG which has highest priority and which is not prohibited by the extraction prohibiting means, wherein the extracting means extracts the selected top instruction, and the rearranging means repeats operations of the extracting means through the instruction selecting means until a last instruction of a program segment is extracted, and wherein the optimization apparatus obtains rearranged instructions for the program segment from the instruction storage means.

An optimization apparatus for removing hazards from a program by rearranging instructions for each program segment, wherein each program segment does not include any jump instruction nor any jump target label, comprising:

• a Directed Acyclic Graph (hereinafter DAG) generating means for generating a plurality of DAGs for each program segment, each DAG showing a relationship between instructions by a parent-to-child relation wherein the parent instructions define resources and the child instructions refer to the resources;
• a hazard marking means for marking hazard-including combinations of a parent instruction and a child instruction in the DAGs as a hazard;
• a rearranging means for rearranging the instructions for each program segment so that instructions are inserted between the instructions of each marked combination, wherein the inserted instructions do not destroy values stored in resources used by the instructions of the marked combination;
• and
• a priority assigning means for assigning a higher priority to a top instruction of a DAG whose descendant instructions include a hazard, and assigning a lower priority to a top instruction of a DAG whose descendant instructions do not include a hazard, wherein descendant instructions of a top instruction are instructions in the DAG which are traced from the top instruction through parent-to-child relations directly or indirectly;
• and
• wherein the rearranging means comprises:
• an extracting means for extracting a selected top instruction from the DAGs;
• an instruction storage means for storing the extracted instructions serially in order of extraction;
• a destructive instruction detecting means for detecting, as a destructive instruction, a top instruction of a DAG that destroys a value stored in a resource to be referred to later by another instruction in program segments;
• a marked instruction detecting means for detecting a top instruction of a DAG whose parent instruction is a last instruction in the instruction storage means, and which makes up a marked combination with the parent instruction;
• a first resource selecting means for, if the destructive instruction detecting means detects a destructive instruction, selecting resources which are not used in a DAG whose top instruction is the destructive instruction;
• a first identifying means for identifying types of the resources selected by the first resource selecting means;
• a second identifying means for identifying types of instructions which either define or refer to the resources and a type of the destructive instruction;
• a second resource selecting means for selecting replacement-candidate resources from the resources selected by the first resource selecting means by making each combination of types of an instruction and a resource, comparing the combination with combination patterns stored in a processor, and excluding resources in combinations that do not match the combination patterns;
• a resource replacing means for replacing a resource defined by the destructive instruction by any of the replacement-candidate resources for each instruction with the resource in the data-flow section;
• an extraction prohibiting means for prohibiting the extracting means from extracting the instruction detected by the marked instruction detecting means and the destructive instruction whose resources have not been replaced by other resources by the resource replacing means;
• and
• an instruction selecting means for selecting a top instruction of a DAG which has highest priority and which is not prohibited by the extraction prohibiting means, wherein the extracting means extracts the selected top instruction, and the rearranging means repeats operations of the extracting means through the instruction selecting means until a last instruction of a program segment is extracted, and wherein the optimization apparatus obtains rearranged instructions for the program segment from the instruction storage means.

An optimization apparatus for removing delays in pipeline processing by rearranging instructions for each program segment, wherein the delays occur since a resource defined by a load instruction is referred to by any of an Arithmetic Logic Unit (hereinafter ALU) operation and an address operation both of which succeed to the load instruction, and wherein each program segment does not include any jump instruction nor any jump target label, comprising:

• a Directed Acyclic Graph (hereinafter DAG) generating means for generating a plurality of DAGs for each program segment, each DAG showing a relationship between instructions by a parent-to-child relation wherein the parent instructions define resources and the child instructions refer to the resources;
• a hazard marking means for marking an instruction sequence in which a resource defined by a load instruction is referred to by any of an ALU operation and an address operation both of which succeed to the load instruction;
• a rearranging means for rearranging the instructions for each program segment so that instructions are inserted between the instructions of each marked instruction sequence, wherein the inserted instructions do not destroy values stored in resources used by the instructions of the marked instruction sequence;
• a priority assigning means for assigning a higher priority to a top instruction of each DAG whose descendant instructions include a hazard, and assigning a lower priority to a top instruction of each DAG whose descendant instructions do not include a hazard, wherein descendant instructions of a top instruction are instructions in the DAG which are traced from the top instruction through parent-to-child relations directly or indirectly;
• and
• wherein the rearranging means comprises:
• an extracting means for extracting a selected top instruction from the DAGs;
• an instruction storage means for storing the extracted instructions serially in order of extraction;
• a destructive instruction detecting means for detecting, as a destructive instruction, a top instruction of a DAG that destroys a value stored in a resource to be referred to later by another instruction in program segments;
• a marked instruction detecting means for detecting a top instruction of a DAG whose parent instruction is a last instruction in the instruction storage means, and which makes up a marked combination with the parent instruction;
• an extraction prohibiting means for prohibiting the extracting means from extracting the destructive instruction and the instruction detected by the marked instruction detecting means;
• and
• an instruction selecting means for selecting a top instruction of a DAG which has highest priority and which is not prohibited by the extraction prohibiting means, wherein the extracting means extracts the selected top instruction, and the rearranging means repeats operations of the extracting means through the instruction selecting means until a last instruction of a program segment is extracted, and wherein the optimization apparatus obtains rearranged instructions for the program segment from the instruction storage means.