Patent ID: 12197310

DETAILED DESCRIPTION

In order to address the challenges discussed above, a computing device is provided.FIG.1shows an example embodiment of a computing device10, which may include a volatile storage device12, a non-volatile storage device14, and/or a processor16. The volatile storage device12and the non-volatile storage device14may each include memory addresses configured to store data. The processor16may be configured to run a compiler30configured to receive source code20and convert the source code20into assembly code38. Conversion of source code20into assembly code38when the source code20includes at least one compound conditional22is described herein with reference to the systems and methods shown in the figures of the present disclosure.

The example source code20ofFIG.1is shown in further detail with reference toFIG.2. As shown inFIGS.1and2, the example source code20includes a compound conditional22in the form of an “if” statement. The source code20received by the compiler30may include at least one compound conditional22. The compound conditional22may include a plurality of conditions24, each of which may have a Boolean value (true or false). For each condition24of the plurality of conditions24, the source code20may include a respective code block26including one or more instructions28to evaluate the condition24. When the one or more instructions28are evaluated, the code block26may return a Boolean value for the condition24. In some embodiments, each code block26may be a basic block within which no branches occur. Alternatively, at least one code block26may include a plurality of basic blocks.

The compound conditional22may return a Boolean value based on the Boolean values of the plurality of conditions24. As shown inFIG.2, the source code20may further include a first branch code block42including one or more first branch evaluation instructions44configured to be executed when the plurality of conditions24are true. In the embodiment ofFIG.2, the compound conditional22includes a logical operator40, shown here as an AND (&&) logical operator. However, in other embodiments, the compound conditional22may be expressed using another logical operator40, such as OR, XOR, or NAND. The Boolean value of the compound conditional may be evaluated by applying the logical operator40to the plurality of conditions24. The source code20may further include a second branch code block46including one or more second branch evaluation instructions48configured to be executed when at least one condition24of the plurality of conditions24is false. As shown inFIG.2, the second branch code block46may be an “else” branch of an “if” statement.

Although the compound conditional22ofFIGS.1and2is shown with two conditions24, other numbers of conditions24are also contemplated. In some embodiments, the compound conditional22may include three or more conditions24. In such embodiments, the compound conditional22may further include two or more logical operators40that may be applied to the conditions24to evaluate the compound conditional22.

In addition to the compound conditional22, the first branch code block42, and the second branch code block46, the source code20may include other code blocks, as indicated by the ellipses shown before the compound conditional22and after the second branch code block46inFIG.2.

Returning toFIG.1, the compound conditional22may be sent to the compiler30. The compiler30may be configured to determine a plurality of orderings32of the plurality of conditions24included in the compound conditional22. In some embodiments, the compiler30may determine each possible ordering32of the plurality of conditions24. In other embodiments, the compiler30may determine only a subset of all possible orderings32of the conditions24.

As a corollary of Rice's theorem, there does not exist an algorithm that can always determine, for any compound conditional22, which condition24has the lowest computational cost. However, a condition24that is likely to have the lowest computational cost may be identified using heuristic techniques. Such heuristic techniques may be based on syntactic properties of the one or more instructions28included in the respective code blocks26of each of the conditions24.

For each ordering32of the plurality of orderings32of the conditions24, the processor16may be further configured to determine that the ordering32satisfies one or more legality constraints34. A legality constraint34is defined here as a constraint based on one or more syntactic properties of one or more conditions24with a particular ordering32such that when the one or more conditions24do not satisfy the legality constraint34, the processor16is configured to prevent the compiler30from outputting assembly code38with that ordering32. Thus, by determining which orderings32satisfy the one or more legality constraints34, the processor16may prevent errors in the assembly code38that may result from reordering the conditions24. Example legality constraints34are discussed below with reference toFIG.2.

In embodiments in which the source code20includes a first branch code block42including one or more first branch evaluation instructions44configured to be executed when the plurality of conditions24are true and a second branch code block46including one or more second branch evaluation instructions48configured to be executed when at least one condition24of the plurality of conditions24is false, the one or more legality constraints34include a constraint34that the source code20includes one first branch code block42and one second branch code block46. When the above legality constraint34is satisfied, the source code20does not include more than one first branch code block42and/or more than one second branch code block46. Additionally or alternatively, the one or more legality constraints34may include a constraint that the respective code block26of each condition24includes an instruction28to proceed to a common target code block, shown inFIG.2as the first branch code block42. Thus, the compiler30may prevent a change in the ordering32of the plurality of conditions24from affecting what code block is executed following evaluation of the compound conditional22.

In some embodiments, as shown inFIG.3, the source code20may include a portion50following a last code block26of the respective code blocks26of the plurality of conditions24and preceding the common target code block. For example, when the compound conditional22is included in a “while” loop, as shown inFIG.3, the portion50of the source code20may be at least one code block including one or more instructions to increment a variable. Other functions of the portion50of the source code20are also contemplated. In such embodiments, the one or more legality constraints34may include a constraint that the portion50of the source code20following a last code block26of the respective code blocks26of the plurality of conditions24and preceding the common target code block has one entry point and one exit point. In such embodiments, the entry point may be an instruction in the portion50of the source code20where the processor16may begin to execute the portion50of the source code20. Similarly, the exit point may be an instruction at which the processor16stops executing the portion50of the source code20.

In some embodiments, the one or more legality constraints34may include a constraint that no instruction28calls an undefined variable. Two example scenarios in which an instruction28may call an undefined variable are discussed below. In one example, the undefined variable may be an untracked memory address. When an instruction28to dereference the untracked memory address occurs prior to an instruction28to track the untracked memory address, an undefined variable error may occur. In a second example, an undefined variable error may occur when an instruction28uses a variable prior to another instruction28that defines the variable.

In some embodiments, the one or more legality constraints34may include a constraint that no code block26includes an instruction28that is a division or remainder operation where the divisor could have a value of zero. By checking this legality constraint34, the processor16may prevent division-by-zero errors resulting from reordering the conditions24.

When no candidate reorderings included in the plurality of orderings32satisfy each legality constraint34checked by the processor16, the compiler30may output a warning message52, as shown inFIG.1. The warning message52may include, in some embodiments, an indication that the compound conditional22could not be reordered to have a computationally cheaper ordering32. The warning message52may include an indication of a location (e.g. a line number) in the source code20at which the compound conditional22occurs. In some embodiments, the compiler30may not output the assembly code38when the compiler30outputs the warning message52.

For each ordering32of the plurality of orderings32that satisfy the one or more legality constraints34, the processor16may be further configured to determine a respective estimated computational cost36for that ordering32. The respective estimated computational costs36of the orderings36may be determined based on predetermined static values assigned to the one or more instructions28included in each code block26. Thus, estimated computational costs36of the orderings32may be determined without having to collect data related to historical computational costs of similar instructions.

Determination of the estimated computational cost36according to one example embodiment is shown in further detail with reference toFIG.4. As shown inFIG.4, to determine the estimated computational cost36of a code block26included in a condition24when the plurality of conditions24have a particular ordering32, the processor16may refer to an estimated computational cost table60for each instruction28included in the code block26, which contains predetermined static values for each type of instruction in the code block. Thus, the estimated computational cost table60may include, for one or more type of operation62, an estimated cost score64associated with that operation62. The types of operations62may include, for example, addition, subtraction, comparison, negation, division, remainder, AND, OR, XOR, minimum, maximum, load, store, and/or one or more other operations62. Each type of operation62listed in the estimated computational cost table may have an estimated cost score64, as shown in the second column of the estimated computational cost table60inFIG.4. In some embodiments, each operation may have an estimated integer cost and an estimated floating-point cost. The estimated integer cost may be the estimated cost score64of the operation62when performed using integer computation, and the estimated floating-point cost may be the estimated cost score64of the operation62when performed using floating point computation.

The processor16may be configured to determine a respective estimated cost score64for each instruction28included in the code block26, typically by reference to the table discussed above. In addition, the processor16may determine the respective estimated cost score64of each instruction28for each code block26in this manner when the plurality of conditions24have the ordering32. Thus, the processor16may be configured to assign an estimated cost score64to each instruction28included in the ordering32. Based on the respective estimated cost scores64of each instruction28, the processor16may determine an estimated computational cost36of the ordering. For example, the estimated computational cost36of the ordering32may be determined by summing the respective estimated cost scores64assigned to each instruction28. Alternatively, the estimated computational cost36may be determined using some other formula. For example, a weighting factor may be applied to at least one estimated cost score64.

In some embodiments, the processor16may determine an estimated computational cost36only for each ordering32than satisfies the one or more legality constraints34. In other embodiments, the processor16may determine the estimated computational cost36of each ordering32before checking whether that ordering32satisfies the one or more legality constraints34. In such embodiments, the processor16may be configured to discard any ordering32with an estimated computational cost36that exceeds a predetermined threshold. This estimated computational cost filtering may occur before checking for satisfaction of the one or more legality constraints34.

The processor16may be further configured to determine an ordering32that has a lowest estimated computational cost36of the plurality of orderings32that satisfy the one or more legality constraints34. The processor16may then reorder the plurality of conditions24to have the ordering32with the lowest estimated computational cost36of the plurality of orderings32that satisfy the one or more legality constraints34. If the ordering with the lowest estimated computational cost36is the original ordering32of the plurality of conditions24, the processor16may be configured to maintain the original ordering32. If two or more orderings32are tied for the lowest estimated computational cost36, the processor16may select one ordering32of the two or more orderings32and reorder the plurality of conditions24to have the selected ordering32, or, if the original ordering32is included in the two or more orderings32, maintain the original ordering32.

In embodiments in which the estimated computational costs36of the respective orderings32are determined prior to checking whether the orderings32satisfy the one or more legality constraints34, the processor16may be configured to sort the one or more orderings32by estimated computational cost36. The processor16may then determine whether each ordering32satisfies one or more legality constraints34in order of ascending estimated computational cost36among the plurality of orderings32. The processor16may check the orderings32for satisfaction of the one or more legality constraints34thusly until an ordering32with a lowest estimated computational cost36that satisfies the one or more legality constraints34is determined. The processor16may be further configured to reorder the plurality of conditions24to have the ordering32with the lowest estimated computational cost36that satisfies the one or more legality constraints34. Checking estimated computational costs36of the orderings32before checking legality constraints34may be advantageous, for example, when differences in estimated computational costs36among the orderings32are expected to be large, and/or when the estimated computational cost36of an ordering32can be determined more quickly than whether the ordering32satisfies the one or more legality constraints34.

FIG.5shows a flowchart of a method100performed by a processor of a computing device, according to one example embodiment. The computing device may be the computing device10ofFIG.1. At step102, the method may include receiving source code at a compiler. The source code may include at least one compound conditional having a plurality of conditions. In some embodiments, the compound conditional may include three or more conditions. The compound conditional may include two or more Boolean-valued conditions and one or more logical operators, such as AND, OR, XOR, and/or NAND. The compound conditional may further include, for each condition of the plurality of conditions, a respective code block including one or more instructions to evaluate the condition. In some embodiments, each code block may be a basic block. In other embodiments, at least one code block may include a plurality of basic blocks.

At step104, the method100may further include, for each ordering of a plurality of orderings of the plurality of conditions, determining that the ordering satisfies one or more legality constraints. A legality constraint is a constraint based on one or more syntactic properties of one or more conditions with a particular ordering such that when the one or more conditions do not satisfy the legality constraint, outputting of assembly code with that ordering is inhibited. As one example, the one or more legality constraints may include a constraint that the respective code block of each condition includes an instruction to proceed to a common target code block. Thus, unwanted branching that depends upon the ordering of the conditions may be prevented.

As another example, the one or more legality constraints may include a constraint that a portion of the source code following a last code block of the respective code blocks of the plurality of conditions and preceding the common target code block has one entry point and one exit point. This legality constraint may prevent the processor from skipping instructions before the entry point or after the exit point due to unwanted entry to and/or exit from the portion of the source code following the last code block and preceding the common target code block.

As another example, the one or more legality constraints include a constraint that no instruction calls an undefined variable. When a variable is defined in a first condition and subsequently called in a second condition in the original ordering of the conditions, a call to an undefined variable may occur when the second condition is moved to be before the first condition. The above legality constraint may be checked in order to determine that such a reordering is not performed.

As another example, the one or more legality constraints may include a constraint that that no code block includes an instruction that is a division or remainder operation where the divisor could have a value of zero.

In some embodiments, the source code may further include a first branch code block including one or more first branch evaluation instructions configured to be executed when the plurality of conditions are true. The source code may further include a second branch code block including one or more second branch evaluation instructions configured to be executed when at least one condition of the plurality of conditions is false. For example, when the compound conditional is included in an “if” statement, the second branch code block may be an “else” branch of the “if” statement. In such embodiments, the one or more legality constraints may include a constraint that the source code includes one first branch code block and one second branch code block, rather than a plurality of first branch code blocks and/or second branch code blocks.

At step106, the method100may further include for each ordering of the plurality of orderings that satisfy the one or more legality constraints, determining a respective estimated computational cost for that ordering. In some embodiments, determining the respective estimated computational cost for each ordering may include, at step108, assigning an estimated cost score to each instruction included in the ordering. The estimated cost scores may be determined, for example, by reading an estimated cost score associated with an operation indicated by the instruction from an estimated computational cost table. In some embodiments, a weighting factor may be applied to the estimated cost scores of one or more instructions. At step110, the estimated computational cost of the ordering may then be determined, for example, by summing the respective estimated cost scores assigned to each instruction. In some embodiments, one or more other operations may additionally or alternatively be performed on the estimated cost scores in order to determine the estimated computational cost of the ordering.

At step112, the method100may further include reordering the plurality of conditions to have an ordering that has a lowest estimated computational cost of the plurality of orderings that satisfy the one or more legality constraints. When the original ordering of the plurality of conditions satisfies the one or more legality constraints and has the lowest estimated computational cost, the method100may instead include maintaining the original ordering.

Although, in the systems and methods described above, the at least one compound conditional that is reordered includes two conditions, embodiments in which more than two conditions are reordered are also contemplated. For example, a compound conditional may have the form “if (a∥b) && (c∥d).” In such an example, the blocks “(a∥b)” and “(c∥d)” may be reordered such that the compound conditional becomes “if (c∥d) && (a∥b).” Alternatively, the conditions a, b, c, and d may be reordered such that the compound conditional becomes, in one example, “if (b∥a) && (d∥c).” In embodiments in which more than two conditions are evaluated, one or more conditions may have respective code blocks that include a plurality of basic blocks.

Compound conditional reordering as described above may be generalized to include reordering of code blocks that are not included a compound conditional, as shown with reference to the example code provided below. In the example, the code blocks included in the following C++ code may be reordered:

struct s1 {int c;int b;struct s2 *substr;};void shouldDo1(struct s1 *ptr, int pred, int bound) {for (int i = 0; i< bound; i++) {int var = ptr[i].substr−>a;// block 1; ends with conditional jumpto block 3if (var % 2) {var = var*2;// block 2; jumps to block 4}else {// block 3var = var + 7;}if (var && pred) {// block 4 compares var and jumps toblockptr[i].b++;// block 5 compares pred and jumps}// block 6 computes ptr[i].b++ andreturnselse {ptr[i].b = i;// block 7 computes ptr[i].b = i andreturns}}}

In the example code shown above, computing “var” is more expensive than computing “pred.” Thus, the example code may be made less computationally expensive to execute by reordering the code blocks in the following order: block 5, block 1, block 2, block 3, block 4, block 6, block 7. The systems and methods of legality constraint checking and computational cost estimation may be applied to determine an ordering of the code blocks that satisfies one or more legality constraints and has a lowest estimated computational cost.

To accomplish this, a computing device may be provided which is configured to execute the following method. Initially, source code including a plurality of code blocks may be received at a compiler. The source code may have an initial ordering, which is one of a plurality of possible orderings. That is, the initial ordering may be reorderered into one of a plurality of candidate reorderings. For each ordering of the plurality of orderings of the plurality of code blocks, the computing device may be configured to determine that the ordering satisfies one or more legality constraints, similar to the legality constraints discussed above. For each ordering of the plurality of orderings that satisfy the one or more legality constraints, the computing device may be configured to determine a respective estimated computational cost for that ordering, and reorder the plurality of code blocks to have an ordering that has a lowest estimated computational cost of the plurality of orderings that satisfy the one or more legality constraints. The estimated computational cost may be determined using methods similar to those described above.

Using the systems and methods described above, a computing device may determine which of a plurality of compound conditionals is the most likely to require the fewest computational resources while satisfying syntactic legality constraints. With this approach, the wasteful processing of prior systems can be avoided, which previously resulted when a complicated conditional was unnecessarily evaluated before a simple conditional which fails a test evaluation. Thus, the systems and methods described above may allow compiled code to be executed more efficiently than code compiled using previously existing methods.

In some embodiments, the methods and processes described herein may be tied to a computing system of one or more computing devices. In particular, such methods and processes may be implemented as a computer-application program or service, an application-programming interface (API), a library, and/or other computer-program product.

FIG.6schematically shows a non-limiting embodiment of a computing system200that can enact one or more of the methods and processes described above. Computing system200is shown in simplified form. Computing system200may, for example, embody the computing device10ofFIG.1, or may instead embody some other computing system. Computing system200may take the form of one or more personal computers, server computers, tablet computers, home-entertainment computers, network computing devices, gaming devices, mobile computing devices, mobile communication devices (e.g., smart phone), and/or other computing devices, and wearable computing devices such as smart wristwatches and head mounted augmented/virtual reality devices.

Computing system200includes a logic processor202, volatile memory204, and a non-volatile storage device206. Computing system200may optionally include a display subsystem208, input subsystem210, communication subsystem212, and/or other components not shown inFIG.6.

Logic processor202includes one or more physical devices configured to execute instructions. For example, the logic processor may be configured to execute instructions that are part of one or more applications, programs, routines, libraries, objects, components, data structures, or other logical constructs. Such instructions may be implemented to perform a task, implement a data type, transform the state of one or more components, achieve a technical effect, or otherwise arrive at a desired result.

The logic processor202may include one or more physical processors (hardware) configured to execute software instructions. Additionally or alternatively, the logic processor202may include one or more hardware logic circuits or firmware devices configured to execute hardware-implemented logic or firmware instructions. Processors of the logic processor202may be single-core or multi-core, and the instructions executed thereon may be configured for sequential, parallel, and/or distributed processing. Individual components of the logic processor202optionally may be distributed among two or more separate devices, which may be remotely located and/or configured for coordinated processing. Aspects of the logic processor may be virtualized and executed by remotely accessible, networked computing devices configured in a cloud-computing configuration. In such a case, these virtualized aspects may be run on different physical logic processors of various different machines.

Volatile memory204may include physical devices that include random access memory. Volatile memory204is typically utilized by logic processor202to temporarily store information during processing of software instructions. It will be appreciated that volatile memory204typically does not continue to store instructions when power is cut to the volatile memory204.

Non-volatile storage device206includes one or more physical devices configured to hold instructions executable by the logic processors to implement the methods and processes described herein. When such methods and processes are implemented, the state of non-volatile storage device206may be transformed—e.g., to hold different data.

Non-volatile storage device206may include physical devices that are removable and/or built-in. Non-volatile storage device206may include optical memory (e.g., CD, DVD, HD-DVD, Blu-Ray Disc, etc.), semiconductor memory (e.g., ROM, EPROM, EEPROM, FLASH memory, etc.), and/or magnetic memory (e.g., hard-disk drive, floppy-disk drive, tape drive, MRAM, etc.), or other mass storage device technology. Non-volatile storage device206may include nonvolatile, dynamic, static, read/write, read-only, sequential-access, location-addressable, file-addressable, and/or content-addressable devices. It will be appreciated that non-volatile storage device206is configured to hold instructions even when power is cut to the non-volatile storage device206.

Aspects of logic processor202, volatile memory204, and non-volatile storage device206may be integrated together into one or more hardware-logic components. Such hardware-logic components may include field-programmable gate arrays (FPGAs), program- and application-specific integrated circuits (PASIC/ASICs), program- and application-specific standard products (PSSP/ASSPs), system-on-a-chip (SOC), and complex programmable logic devices (CPLDs), for example.

The term “program” may be used to describe an aspect of computing system200implemented to perform a particular function. In some cases, a program may be instantiated via logic processor202executing instructions held by non-volatile storage device206, using portions of volatile memory204. It will be understood that different programs may be instantiated from the same application, service, code block, object, library, routine, API, function, etc. Likewise, the same program may be instantiated by different applications, services, code blocks, objects, routines, APIs, functions, etc. The term “program” encompasses individual or groups of executable files, data files, libraries, drivers, scripts, database records, etc.

When included, display subsystem208may be used to present a visual representation of data held by non-volatile storage device206. As the herein described methods and processes change the data held by the non-volatile storage device206, and thus transform the state of the non-volatile storage device206, the state of display subsystem208may likewise be transformed to visually represent changes in the underlying data. Display subsystem208may include one or more display devices utilizing virtually any type of technology. Such display devices may be combined with logic processor202, volatile memory204, and/or non-volatile storage device206in a shared enclosure, or such display devices may be peripheral display devices.

When included, input subsystem210may comprise or interface with one or more user-input devices such as a keyboard, mouse, touch screen, or game controller. In some embodiments, the input subsystem210may comprise or interface with selected natural user input (NUI) componentry. Such componentry may be integrated or peripheral, and the transduction and/or processing of input actions may be handled on- or off-board. Example NUI componentry may include a microphone for speech and/or voice recognition; an infrared, color, stereoscopic, and/or depth camera for machine vision and/or gesture recognition; a head tracker, eye tracker, accelerometer, and/or gyroscope for motion detection, gaze detection, and/or intent recognition; as well as electric-field sensing componentry for assessing brain activity; and/or any other suitable sensor.

When included, communication subsystem212may be configured to communicatively couple computing system200with one or more other computing devices. Communication subsystem212may include wired and/or wireless communication devices compatible with one or more different communication protocols. As non-limiting examples, the communication subsystem212may be configured for communication via a wireless telephone network, or a wired or wireless local- or wide-area network. In some embodiments, the communication subsystem212may allow computing system200to send and/or receive messages to and/or from other devices via a network such as the Internet.

According to one aspect of the present disclosure, a computing device is provided, including a processor configured to receive source code at a compiler. The source code may include at least one compound conditional having a plurality of conditions, and, for each condition of the plurality of conditions, a respective code block including one or more instructions to evaluate the condition. For each ordering of a plurality of orderings of the plurality of conditions, the processor may be further configured to determine that the ordering satisfies one or more legality constraints. For each ordering of the plurality of orderings that satisfy the one or more legality constraints, the processor may be further configured to determine a respective estimated computational cost for that ordering. The processor may be further configured to reorder the plurality of conditions to have an ordering that has a lowest estimated computational cost of the plurality of orderings that satisfy the one or more legality constraints.

According to this aspect, the source code may further include a first branch code block including one or more first branch evaluation instructions configured to be executed when the plurality of conditions are true. The source code may further include a second branch code block including one or more second branch evaluation instructions configured to be executed when at least one condition of the plurality of conditions is false.

According to this aspect, the one or more legality constraints may include a constraint that the source code includes one first branch code block and one second branch code block.

According to this aspect, the one or more legality constraints may include a constraint that the respective code block of each condition includes an instruction to proceed to a common target code block.

According to this aspect, the one or more legality constraints may include a constraint that a portion of the source code following a last code block of the respective code blocks of the plurality of conditions and preceding the common target code block has one entry point and one exit point.

According to this aspect, the one or more legality constraints may include a constraint that no instruction calls an undefined variable.

According to this aspect, each code block may be a basic block.

According to this aspect, at least one code block may include a plurality of basic blocks.

According to this aspect, the processor may be configured to determine the respective estimated computational cost for each ordering at least in part by assigning an estimated cost score to each instruction included in the ordering and summing the respective estimated cost scores assigned to each instruction.

According to another aspect of the present disclosure, a method performed by a processor of a computing device is provided. The method may include receiving source code at a compiler. The source code may include at least one compound conditional having a plurality of conditions, and, for each condition of the plurality of conditions, a respective code block including one or more instructions to evaluate the condition. For each ordering of a plurality of orderings of the plurality of conditions, the method may further include determining that the ordering satisfies one or more legality constraints. For each ordering of the plurality of orderings that satisfy the one or more legality constraints, the method may further include determining a respective estimated computational cost for that ordering. The method may further include reordering the plurality of conditions to have an ordering that has a lowest estimated computational cost of the plurality of orderings that satisfy the one or more legality constraints.

According to this aspect, the source code may further include a first branch code block including one or more first branch evaluation instructions configured to be executed when the plurality of conditions are true. The source code may further include a second branch code block including one or more second branch evaluation instructions configured to be executed when at least one condition of the plurality of conditions is false.

According to this aspect, the one or more legality constraints may include a constraint that the source code includes one first branch code block and one second branch code block.

According to this aspect, the one or more legality constraints may include a constraint that a portion of the source code following a last code block of the respective code blocks of the plurality of conditions and preceding the common target code block has one entry point and one exit point.

According to this aspect, the one or more legality constraints may include a constraint that no instruction calls an undefined variable.

According to this aspect, each code block may be a basic block.

According to this aspect, determining the respective estimated computational cost for each ordering may include assigning an estimated cost score to each instruction included in the ordering and summing the respective estimated cost scores assigned to each instruction.

According to another aspect of the present disclosure, a computing device is provided, including a processor configured to receive source code at a compiler. The source code may include a plurality of code blocks. For each ordering of a plurality of orderings of the plurality of code blocks, the processor may be further configured to determine that the ordering satisfies one or more legality constraints. For each ordering of the plurality of orderings that satisfy the one or more legality constraints, the processor may be further configured to determine a respective estimated computational cost for that ordering. The processor may be further configured to reorder the plurality of code blocks to have an ordering that has a lowest estimated computational cost of the plurality of orderings that satisfy the one or more legality constraints.

It will be understood that the configurations and/or approaches described herein are exemplary in nature, and that these specific embodiments or examples are not to be considered in a limiting sense, because numerous variations are possible. The specific routines or methods described herein may represent one or more of any number of processing strategies. As such, various acts illustrated and/or described may be performed in the sequence illustrated and/or described, in other sequences, in parallel, or omitted. Likewise, the order of the above-described processes may be changed.

The subject matter of the present disclosure includes all novel and non-obvious combinations and sub-combinations of the various processes, systems and configurations, and other features, functions, acts, and/or properties disclosed herein, as well as any and all equivalents thereof.