# US 10,503,634 B1 · Semantic comparison of computer compiler traces > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,503,634 B1 - Document ID: US10503634B1 - Status: Granted - Kind: B1 - Application number: 15/989,973 - Filed: 2018-05-25 - Published: 2019-11-28 - Granted: 2019-12-10 - Earliest claimed: 2018-05-25 - Assignees: Microsoft Technology Licensing, LLC - Applicants: Microsoft Technology Licensing, LLC - Inventors: Xiang Li; Ivan Nevraev; David McCarthy Peixotto; Marcelo Lopez Ruiz - Web page: https://patentgrep.com/patent/US10503634B1 ## CPC - G06F 8/436: {Semantic checking} - G06F 11/3692: {for test results analysis} - G06F 8/40: Transformation of program code - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## 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. ## Claims ### Claim 1 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. ### Claim 2 (depends on 1) The computing device of claim 1 wherein translating the executed instruction into an expression of the executed instruction in the uniform expression format comprises: translating a single multiply and add (MAD) executed instruction into an expression in the uniform expression format that uses both a multiply (MUL) instruction and an add (ADD) instruction. ### Claim 3 (depends on 1) The computing device of claim 1 wherein translating the executed instruction into an expression of the executed instruction in the uniform expression format comprises: translating a single subtract (SUB) executed instruction into an expression in the uniform expression format that uses both an add (ADD) instruction and a multiply (MUL) instruction. ### Claim 4 (depends on 1) The computing device of claim 1 wherein 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 comprises merging multiple instances of multiply (MUL) expressions or multiple instances of add (ADD) expressions. ### Claim 5 (depends on 1) The computing device of claim 1 wherein 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 comprises: identifying multiple multiply (MUL) expression instances; creating a single MUL expression instance in the uniform expression format from the identified multiple MUL expression instances. ### Claim 6 (depends on 1) The computing device of claim 1 wherein sorting input operands of the merged single instances of the one or more expression types into the uniform order comprises: sorting input operands for merged multiply (MUL) expressions; and sorting input operands for merged add (ADD) expressions. ### Claim 7 (depends on 1) The computing device of claim 1 wherein the uniform expression format uses a tree structure for representing the transformed first and second traces. ### Claim 8 (depends on 1) The computing device of claim 1 wherein the result of the comparison comprises a sequence of text instructions of the first set of expressions in the uniform expression format and a corresponding sequence of text instructions of the second set of expressions in the uniform expression format. ### Claim 9 (depends on 1) The computing device of claim 1 wherein the first compiler is a compiler being tested and wherein the second compiler is a reference compiler. ### Claim 10 (depends on 1) The computing device of claim 1 wherein transforming the first trace into the first set of expressions in the uniform expression format further comprises performing one or more optimizations of the expressions in the uniform expression format, and wherein transforming the second trace into the second set of expressions in the uniform expression format further comprises performing one or more optimizations of the expressions in the uniform expression format. ### Claim 11 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. ### Claim 12 (depends on 11) The method of claim 11 wherein translating the executed instruction into an expression of the executed instruction in the uniform expression format comprises: translating a single multiply and add (MAD) executed instruction into an expression in the uniform expression format that uses both a multiply (MUL) instruction and an add (ADD) instruction. ### Claim 13 (depends on 11) The method of claim 11 wherein merging multiple expression instances comprises merging multiple instances of multiply (MUL) expressions or multiple instances of add (ADD) expressions. ### Claim 14 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. ### Claim 15 (depends on 14) The computer-readable storage medium of claim 14 wherein 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 comprises merging multiple instances of mul (multiply) expressions or multiple instances of add expressions. ### Claim 16 (depends on 14) The computer-readable storage medium of claim 14 wherein translating the executed instruction into an expression of the executed instruction in the uniform expression format comprises: translating a single multiply and add (MAD) executed instruction into an expression in the uniform expression format that uses both a multiply (MUL) instruction and an add (ADD) instruction.