Method and apparatus for compiling code based on a dependency tree

Patent metadata

Field	Value
Publication number	US-9823911-B2
Application number	US-201514590164-A
Country	US
Kind code	B2
Filing date	Jan 6, 2015
Priority date	Jan 31, 2014
Publication date	Nov 21, 2017
Grant date	Nov 21, 2017

Abstract

A compiling apparatus generates a dependency tree representing dependency relations among a plurality of instructions included in first code. The compiling apparatus detects, from the dependency tree, a partial tree including a first instruction, a second instruction, and a third instruction that depends on the operation results of the first and second instructions, and rewrites the instructions corresponding to the partial tree to a set of instructions including a plurality of complex instructions each of which causes a processor to perform a complex operation including a plurality of operations. The compiling apparatus generates second code on the basis of the dependency tree and the set of instructions.

First claim

What is claimed is:

1. A non-transitory computer-readable medium storing therein a compiling program that causes a computer to execute a process comprising:
generating a dependency tree representing dependency relations among a plurality of instructions included in first code;
detecting a first partial tree from the dependency tree, the first partial tree including a first instruction, a second instruction, and a third instruction, the third instruction depending on operation results of the first instruction and the second instruction;
updating the dependency tree by replacing the first partial tree with a second partial tree, wherein the replacing includes converting the first, second and third instructions included in the first partial tree into a plurality of complex instructions under a conversion rule that is determined according to operation types of the first, second and third instructions, the plurality of complex instructions each causing a processor to perform a complex operation that includes a plurality of operations; and
generating second code based on the updated dependency tree;
wherein generating second code includes comparing the updated dependency tree including the complex instructions with another dependency tree including complex instructions, and converting some or all of the plurality of instructions into parallel instructions, the parallel instructions each causing the processor to perform two or more complex instructions in parallel.

2. The non-transitory computer-readable medium according to claim 1 , wherein the process further includes, before detecting the first partial tree, detecting a set of instructions from the dependency tree and deforming the set of instructions into the first partial tree, the set of instructions including the first instruction, a fourth instruction, and a fifth instruction and satisfying prescribed conditions, the fourth instruction depending on an operation result of the first instruction, the fifth instruction depending on an operation result of the fourth instruction.

3. A compiling method comprising:
generating, by a processor, a dependency tree representing dependency relations among a plurality of instructions included in first code;
detecting, by the processor, a first partial tree from the dependency tree, and rewriting instructions corresponding to the partial tree to a set of instructions, the instructions corresponding to the first partial tree including a first instruction, a second instruction, and a third instruction, the third instruction depending on operation results of the first instruction and the second instruction;
updating, by the processor, the dependency tree by replacing the first partial tree with a second partial tree, wherein the replacing includes converting the first, second and third instructions included in the first partial tree into a plurality of complex instructions under a conversion rule that is determined according to operation types of the first, second and third instructions, the set of instructions including a the plurality of complex instructions each causing the processor or another processor to perform a complex operation that includes a plurality of operations; and
generating, by the processor, second code based on the updated dependency tree and the set of instructions;
wherein generating second code includes comparing the updated dependency tree including the complex instructions with another dependency tree including complex instructions, and converting some or all of the plurality of instructions into parallel instructions, the parallel instructions each causing the processor to perform two or more complex instructions in parallel.

4. A compiling apparatus comprising:
a memory configured to store first code and second code generated by converting the first code; and
a processor configured to perform a process including:
generating a dependency tree representing dependency relations among a plurality of instructions included in the first code;
detecting a first partial tree from the dependency tree, and rewriting instructions corresponding to the partial tree to a set of instructions, the instructions corresponding to the first partial tree including a first instruction, a second instruction, and a third instruction, the third instruction depending on operation results of the first instruction and the second instruction;
updating the dependency tree by replacing the first partial tree with a second partial tree, wherein the replacing includes converting the first, second and third instructions included in the first partial three into a plurality of complex instructions under a conversion rule that is determined according to operation types of the first, second and third instructions, the set of instructions including a the plurality of complex instructions each causing a processor to perform a complex operation that includes a plurality of operations; and
generating the second code based on the updated dependency tree and the set of instructions;
wherein generating second code includes comparing the updated dependency tree including the complex instructions with another dependency tree including complex instructions, and converting some or all of the plurality of instructions into parallel instructions, the parallel instructions each causing the processor to perform two or more complex instructions in parallel.

Assignees

• Fujitsu Ltd

Inventors

• Chiba Shuichi

Classifications

• G06F8/453 Primary

  Data distribution · CPC title

• G06F9/30145

  Instruction analysis, e.g. decoding, instruction word fields · CPC title

• G06F8/40

  Transformation of program code · CPC title

• G06F8/433 Primary

  Dependency analysis; Data or control flow analysis · CPC title

• G06F8/456

  Parallelism detection · CPC title