US 10,503,634 B1Granted

Semantic comparison of computer compiler traces

AssigneeMicrosoft Technology Licensing, LLC

InventorsXiang Li, Ivan Nevraev, David McCarthy Peixotto, Marcelo Lopez Ruiz

Life of this patent

Estimating the term…

Loading patent…

Abstract

Techniques are described for semantically comparing machine code traces generated by compilers that compile computer software code. For example, a trace of machine code generated by a compiler can be obtained. The trace can be transformed into a set of expressions in a uniform expression format (e.g., by performing translation of the trace instructions into corresponding expressions and/or by performing other transformations). The set of expressions in the uniform expression format can be compared to other sets of expressions in the uniform expression format (e.g., other sets of expressions created from traces of machine code from other compilers). Results of the comparison can comprise indications of whether the sets of expressions match.

Claims16

Dependent claims

A computing device comprising:

a processing unit;
and
memory;
the computing device configured, via computer-executable instructions, to perform operations for semantically comparing machine code traces, the operations comprising:
receiving a first trace of machine code generated by a first compiler, wherein the first trace comprises a plurality of executed instructions, and wherein the first trace of machine code is generated by executing the machine code on the or another computing device to obtain the first trace comprising the plurality of executed instructions;
transforming the first trace into a first set of expressions in a uniform expression format that have the same semantic meaning as the first trace, comprising:
for each of the plurality of executed instructions of the first trace, translating the executed instruction into an expression of the executed instruction in the uniform expression format;
merging multiple instances of one or more expression types into corresponding single instances of the one or more expression types in the uniform expression format;
and
sorting input operands of the merged single instances of the one or more expression types into a uniform order;
receiving a second trace of machine code generated by a second compiler, wherein the second trace comprises a plurality of executed instructions, and wherein the second trace of machine code is generated by executing the machine code on the or another computing device to obtain the second trace comprising the plurality of executed instructions;
transforming the second trace into a second set of expressions in the uniform expression format that have the same semantic meaning as the second trace, comprising:
for each of the plurality of executed instructions of the second trace, translating the executed instruction into an expression of the executed instruction in the uniform expression format;
merging multiple instances of one or more expression types into corresponding single instances of the one or more expression types in the uniform expression format;
and
sorting input operands of the merged single instances of the one or more expression types into the uniform order;
comparing the first set of expressions in the uniform expression format to the second set of expressions in the uniform expression format;
and
outputting a result of the comparison comprising an indication of whether the first set of expressions in the uniform expression format matches the second set of expressions in the uniform expression format.

16 more elements

A method, implemented by a computing device, for semantically comparing machine code traces, the method comprising:

receiving a first trace of machine code generated by a first compiler;
transforming the first trace of machine code generated by the first compiler into a first set of expressions in a uniform expression format that have the same semantic meaning as the first trace of machine code, wherein the first trace comprises a plurality of executed instructions, and wherein the first trace of machine code is generated by executing the machine code on the or another computing device to obtain the first trace comprising the plurality of executed instructions, the transforming comprising:
for each of the plurality of executed instructions of the first trace, translating the executed instruction into an expression of the executed instruction in the uniform expression format;
merging multiple expression instances, having the same expression type, into a single instance of the expression in the uniform expression format;
and
sorting input operands of the merged single instance of the expression into a uniform order;
receiving a second trace of machine code generated by a second compiler;
transforming the second trace of machine code generated by the second compiler into a second set of expressions in a uniform expression format that have the same semantic meaning as the second trace of machine code, wherein the second trace comprises a plurality of executed instructions, and wherein the second trace of machine code is generated by executing the machine code on the or another computing device to obtain the second trace comprising the plurality of executed instructions, the transforming comprising:
for each of the plurality of executed instructions of the second trace, translating the executed instruction into an expression of the executed instruction in the uniform expression format;
merging multiple expression instances, having the same expression type, into a single instance of the expression in the uniform expression format;
and
sorting input operands of the merged single instance of the expression into a uniform order;
comparing the first set of expressions in the uniform expression format to the second set of expressions in the uniform expression format;
and
outputting a result of the comparison comprising an indication of whether the first set of expressions in the uniform expression format matches the second set of expressions in the uniform expression format.

12 more elements

A computer-readable storage medium storing computer-executable instructions for execution on a computing device to perform operations for semantically comparing machine code traces, the operations comprising:

receiving a first trace of machine code generated by a first compiler, wherein the first trace comprises a plurality of executed instructions, and wherein the first trace of machine code is generated by executing the machine code on the or another computing device to obtain the first trace comprising the plurality of executed instructions;
transforming the first trace into a first set of expressions in a uniform expression format that have the same semantic meaning as the first trace, comprising:
for each of the plurality of executed instructions of the first trace, translating the executed instruction into an expression of the executed instruction in the uniform expression format;
merging multiple instances of one or more expression types into corresponding single instances of the one or more expression types in the uniform expression format;
and
sorting input operands of the merged single instances of the one or more expression types into a uniform order;
receiving a second trace of machine code generated by a second compiler, wherein the second trace comprises a plurality of executed instructions, and wherein the second trace of machine code is generated by executing the machine code on the or another computing device to obtain the second trace comprising the plurality of executed instructions;
transforming the second trace into a second set of expressions in the uniform expression format that have the same semantic meaning as the second trace, comprising:
for each of the plurality of executed instructions of the second trace, translating the executed instruction into an expression of the executed instruction in the uniform expression format;
merging multiple instances of one or more expression types into corresponding single instances of the one or more expression types in the uniform expression format;
and
sorting input operands of the merged single instances of the one or more expression types into the uniform order;
comparing the first set of expressions in the uniform expression format to the second set of expressions in the uniform expression format;
and
outputting an indication of whether the first set of expressions in the uniform expression format matches the second set of expressions in the uniform expression format.

12 more elements

Dependencies are inferred from the claim text.