grammar example\_grammar;

integer : 'alpha' | 'bravo'
```This example grammar uses all ANTLR version 4-parser constructs the generic, multi-objective superoptimizer supports. The following images express the grammar as a syntax (or railroad) diagram[\[4\]](#_ftn4).

Statement

 ![fig1.1](/img/images/fig1-1.png)

Integer

 ![fig1.2](/img/images/fig1-2.png)

Fig. 1. Example grammar expressed in a syntax diagram

The superoptimizer generates the Cartesian product of potential integer values, substituting these values into the respective “integer” rule references. The following table shows all 16 possible programs generated by the superoptimizer that could be expressed by the example grammar.

Table I. Programs generated by the superoptimizer using the example grammar

alpha=alpha+alpha

alpha=bravo+alpha

bravo=alpha+alpha

bravo=bravo+alpha

alpha=alpha+bravo

alpha=bravo+bravo

bravo=alpha+bravo

bravo=bravo+bravo

alpha=alpha-alpha

alpha=bravo-alpha

bravo=alpha-alpha

bravo=bravo-alpha

alpha=alpha-bravo

alpha=bravo-bravo

bravo=alpha-bravo

bravo=bravo-bravo

### Test Execution

The generic, multi-objective superoptimizer sends the programs generated by the _ProgramBuilder_ package to the _TestRunner_ package. The _TestRunner_ package splits the set of generated programs across the instances defined by the end-user. On a per-program basis, the TestRunner package inserts a program into a FreeMarker template and executes an external process. An exemplar use-case involves the populated FreeMarker template becoming compliable or interpretable source code being compiled, interpreted and run by the external process (typically a script).

The external process needs to return either “true” or “false” to the superoptimizer, indicating whether the generated program’s output matched the source program’s output. Optional text, such as the number of test failures encountered can be appended to the output for further analysis. Successful programs: that is programs that return “true” are returned to the superoptimizer.

### Scenario Execution

The _ScenarioRunner_ package performs the non-functional analysis of successful programs. The scenario execution works in an identical way to the _TestRunner_ package with the exception that the _ScenarioRunner_ package can receive any text output from an external process. For example, in the case study the scenario calculates the program size and average program execution time, returning this data as two integers separated by a colon. This design facilitates the multi-objective optimization aspect of the superoptimizer as the _ScenarioRunner_ allows multiple metrics to be calculated on generated programs that pass the tests executed by the _TestRunner_.

### Output

The generic, multi-objective superoptimizer generates the following output:

— A list of all programs generated by the ProgramBuilder package.

— The results from the tests performed on all generated programs.

— The results from the scenarios performed on all generated programs that passed the previous tests.

— A system log generated by the log4j package.

Similarities and differences with past superoptimizers
------------------------------------------------------

Granlund and Kenner’s GNU Superoptimizer is well cited and regarded \[Bansal & Aiken 2006, p. 402; Crick et al. 2006, p. 272; Joshi et al. 2002, p. 2; Sayle 2008, p. 110\] especially for its contributions to the GNU C compiler, following Massalin’s definition of optimal programs having the shortest sequence \[Granlund & Kenner 1992, p. 345\] However, the generic, multi-objective superoptimizer provides a framework for alternate metrics for measuring code beyond code length or performance.

Joshi et al’s superoptimizer source programs are expressed in C language \[Joshi et al. 2002, p. 5\], and their Denali-2 uses a proprietary language \[Joshi et al. 2006, pp. 970-976\] to generate optimal code that “minimal number of instructions”, and postulate an alternate metric of “ number of extra registers” \[Joshi et al. 2006, p. 969\]. Brain et al’s TOAST tool follows a similar approach to the Denali approach \[Brain et al. 2006, p. 273\], only assessing program performance.

Bansal and Aiken focus on developing peephole superoptimizers specifically for the x86 architecture processors \[Bansal & Aiken 2006, p. 395\], whereas the generic, multi-objective superoptimizer can be used for superoptimizing any programming language that can be expressed with a context-free grammar.

Unlike Schkufza et al’s use of “a Markov Chain Monte Carlo sampler” to improve superoptimizer performance, the generic, multi-objective superoptimizer allows a developer to improve performance by excluding possible operations from the space of all possible programs. However the generic, multi-objective superoptimizer capitalizes on Schkufza et al’s observations by excluding possible operations sacrifices completeness for superoptimizer performance.

Sayle takes a unique approach to optimizing multiway selection code through known constructs and superoptimization: using a Paerto frontier for assessing multiway selection code for performance and code size \[Sayle 2008, p. 111\]. The generic, multi-objective superoptimizer attempts to allow any metric to be considered for measuring non-functional attributes of generated programs, which builds on Sayle’s definition of an objective function “that is used to assess the merit of each \[program\]” \[Sayle 2008, p. 110\]: optimizing code size involves assessing program size in bytes, optimizing performance involves measuring the amount of time required to execute the program.

Development Process
-------------------

The generic, multi-objective superoptimizer was developed on Mac OSX Yosemite and Windows 8.1 from 29 November 2014 to 23 February 2015. The history of the software development process is available on the project’s GitHub page[\[5\]](#_ftn5).

5.   Case Study
===============

Introduction
------------

The following case study involves using the generic, multi-objective superoptimizer to optimize a program written for the Lego NXT Mindstorms robot. The author configured the Lego NXT Mindstorms robot in its vehicular, “Tribot” configuration \[Lego 2006\] with the Lego-provided firmware and installed a sample program.

![fig2](/img/images/fig2.png)

Fig. 2. Tribot Program Source Code.

The sample program in Figure 2 drives the robot around an oval racing track on the Mindstorms Test Pad 8527, turning upon detecting a black line. The robot completes the manoeuvre at slower speeds, but if the robot’s speed exceeds 66% of its maximum speed the robot fails to complete its manoeuvre and leaves the racetrack. The author rewrote the program for in Java for the LeJOS 0.0.7 firmware (an extract is shown in Code Listing 2) and the Lego NXT Mindstorms robot exhibited the same behaviour[\[6\]](#_ftn6), as shown in the series of still video images in Figure 3. This issue does not appear in subsequent versions of the LeJOS firmware.

Code Listing 2. Extract of the Tribot program rewritten for the Java-based LeJOS framework

```
while ( !Button.LEFT.isPressed() ) {

  displayMainInformation( appName, lightSensor, reading, checkValue );

  if ( reading > ((lightSensor.getHigh() + lightSensor.getLow()) / 2 )) {

    Motor.C.forward();

    Motor.B.forward();

  }

}
```Fig. 3. Lego NXT Mindstorms Robot failing to follow a line at 66% maximum speed.

\[gallery ids="260,262,257,259,258,261,264,263" type="rectangular"\]

A video of this demonstration is available on the author’s Vimeo channel[\[7\]](#_ftn7).

This implies that there are inefficiencies in the Lego-provided firmware and the LeJOS 0.0.7 firmware resulting in the robot being unable to complete the “line following routine” and complete the turn if its speed exceeds 66% of the maximum speed.

This case study will provide a practical demonstration of the use of the generic, multi-objective superoptimizer in optimizing the “line following program” through a laboratory experiment.

Experiment Plan
---------------

The aim of the case study is to test the following hypothesis:

Hypothesis 1. There exists a program, expressed in the Java-based LeJOS framework that performs the “line following program” faster than the existing program.

### Equipment Used

— The Lego NXT Mindstorms robot in its “tribot” configuration with non-rechargeable alkaline batteries.

— A MacBook Pro (15-inch, Mid 2012 edition) 2.6 GHz Intel Core i7 processor with 16GB memory running Windows 8.1 (64-bit) and Java (both 32-bit and 64-bit editions) with the latest service packs and updates installed. The MacBook Pro requires the LeJOS 0.0.7 framework and Lego NXT Mindstorms 64-bit drivers to be installed[\[8\]](#_ftn8).

— The generic, multi-objective superoptimizer installed on the MacBook Pro[\[9\]](#_ftn9).

— A USB 2.0 A-to-B cable connecting the Lego NXT Mindstorms robot to the MacBook Pro.

— An air-conditioned office environment.

The configuration of the experiment environment is shown below.

![fig4.png](/img/images/fig4.png)

Fig. 4. Experiment configuration and environment.

### Method

The experiment would validate the hypothesis by conducting a test and multiple scenarios with the generic, multi-objective superoptimizer. The tests would assess whether programs generated by the grammar in Appendix A pass a series of unit tests executed by the Lego NXT Mindstorms robot running the LeJOS 0.0.7 firmware.

The scenarios would involve measuring the following attributes of valid programs:

— The program’s average computation time in milliseconds from a 1000 samples,

— The compiled, binary file size of the compiled program (specifically, the “.nxj” object code that is deployed on the Lego NXT Mindstorms robot: not the “.class” file created by the Java compiler), and

— The program length, expressed in lines of code. This measure considers “if-then”, “if-then-else”, “do-while”, “while-do” and unary “?” constructs as well as any statement that ends with a semicolon as a line of code.

The optimal program would be the program with (in the following order):

— The shortest average computation time,

— The smallest compiled binary file size, and

— The shortest program length.

The previously mentioned GitHub release contains the test and scenario scripts as well as other relevant templates and scripts.

### Assumptions

Independence between programs executing is assumed, specifically that the following factors do not impact on the results obtained such as wear-and-tear and changes in battery life due to the continuous use of the sensors and motors. During the experiment battery life did not reduce below 50%, there was no physical damage observed on the robot or accessories and there was no consistent trend observed in measurements (such as a continually increasing computation time due to a lack of power), therefore these factors did not have an impact on the results obtained.

It is also assumed that any other optimization processes (such as peephole optimization) performed by the compiler are consistently applied during the compilation process. This assumption means that the independent variable (the set of programs generated by the superoptimizer based on the grammar provided) is the only factor being changed, making the dependent variables (average computation time, compiled binary file size and program length) altered by the independent variable.

Given that the grammar defined in Appendix A is not the complete Java grammar including the LeJOS framework, a globally optimal solution may not be obtained from this experiment. This assumption is valid as the objective of the experiment is not to find the optimal program but to find a program that solves the technical issue.

Finally, it is assumed that the following issues did not affect the quality of the results obtained.

Issues Encountered
------------------

### Lego NXT Mindstorms Robot Test and Scenario Execution Time

Executing tests and scenarios on the Lego NXT Mindstorms robot involved the following process, as implemented in the respective scripts:

— The generated program is substituted into the FreeMarker template.

— The LeJOS compiler (nxjc.bat) is called, creating a Java “.class” file.

— The LeJOS linker (nxj.bat) is called, creating a “.nxj” compiled binary file.

— The LeJOS uploading program (nxjupload.bat) is called, uploading the “.nxj” file onto the Lego NXT Mindstorms robot and running the file.

— The LeJOS remote console (nxjconsole.bat) is called, opening a USB-based connection to the Lego NXT Mindstorms allowing for data (such as the number of failures encountered during the tests or average computation time) to be transferred from the robot to the computer.

This process took approximately 5 seconds due to a delay being required for the Lego NXT Mindstorms to install the downloaded binary file, start the test or scenario application and initiate a “server” for the computer to connect to. If the LeJOS remote console tried to connect to the Lego NXT Mindstorms robot before the server was ready the connection fails and a “false positive” error occurs.

However, the superoptimizer generated 21,440,680 programs[\[10\]](#_ftn10) requiring up to 41 months to complete.

Therefore, the author developed a simple LeJOS simulator[\[11\]](#_ftn11): this simulator used the lejos.\* packages in the LeJOS 0.0.7 build but removed all functions that communicated to the Lego NXT Mindstorms robot. This simulator did not offer any emulation of the robot or its environment but did provide a functionally equivalent environment to run tests against. While tests required approximately 1.5 seconds, a software-only simulator meant that the task could be parallelized between the eight available logical cores, reducing the time to conduct the tests to 46 days.

The author deviated from the original experiment by introducing a two-step equivalence test: generated programs would be tested on the simulator and programs that pass the tests run in the simulator would be tested on the Lego NXT Mindstorms robot. This allowed the author to capitalize on the performance of the testing but eliminate the potential for Type 2 error (that is, a program passes the tests on the simulator but fails to pass tests on the Lego NXT Mindstorms robot). Type 1 error (that is, a program that would pass tests on the Lego NXT Mindstorms but does not pass the tests on the simulator) was considered acceptable, as a mathematically optimal solution was not expected.

### Infinite Loop Detection Failure

A defect was detected on 17 March 2015, where in the generic, multi-objective superoptimizer, which prevented detecting infinite loops in generated programs. For example, programs such as the following program continue indefinitely and the Apache Commons Exec framework’s watchdog timer would never halt the test.

Code Listing 3. Example program that failed to halt due to an infinite loop

```
while ( reading != lightSensor.getHigh() )  { lightSensor.setFloodlight( false ); }
```This issue was resolved by the following two fixes:

— Programs that followed the halted programs and contained “while” or “do- while” loops were skipped.

— A new feature allowing the generic, multi-objective superoptimizer to restart the superoptimizer test or scenario at a particular program (on a per-process basis if parallelization was enabled) was added.

The experiment was restarted on 4 April 2015 with the new version of the superoptimizer from program number 1,181,392 of 1,340,042 on a per-logical process basis[\[12\]](#_ftn12). Omitting programs was chosen as a conservative approach to resolving this issue, but this was accepted, as global optimal solutions were not expected for this experiment.

### Lego NXT Mindstorms Robot Reliability

The previously mentioned “compile-build-upload” process for installing compiled programs based on the generated programs failed several times, resulting in a Java exception being reported by the LeJOS firmware running on the Lego NXT Mindstorms robot.

This occurred during running tests and scenarios, requiring a new feature being added to the superoptimizer to run either tests, scenarios or both tests and scenarios: depending on whether the experiment failed during a test or scenario[\[13\]](#_ftn13).

The only intervention that was required was resetting the superoptimizer and the Lego NXT Mindstorms robot to resume the experiment after a failure occurred.

### Discontinuous Superoptimizer Operation

The generic, multi-objective superoptimizer was originally developed in mind that an experiment would be conducted in a single, continuous session. However the multiple issues encountered meant that the final output created by the superoptimizer did not contain the complete experiment results.  This issue has no impact on the quality of the experiment or results: results were obtained by searching the log files generated for test and scenario results.

Results
-------

Excluding the time required to detect and resolve the aforementioned issues, the case study took 28 days to execute. Out of the 21,440,680 programs generated, 910 programs passed the tests on both the simulator and the Lego NXT Mindstorms robot. The following scatter plots show the overall distribution of results, organized by the scenario’s respective metrics.

![fig5](/img/images/fig5.png)

Fig. 5. Average Computation Time versus Program ID Scatter Plot

![fig6](/img/images/fig6.png)

Fig. 6. Program Length versus Program ID Scatter Plot

![fig7](/img/images/fig7.png)

Fig. 7. Program Size versus Program ID Scatter Plot

The outlier program in Figure 5 and 6 is shown below.

Code Listing 4. Optimal program obtained from superoptimizer experiment

```
Motor.C.setPower( ( ( reading > checkValue ) ? DEFINED\_POWER : 2 ) );
```On average, the program in Code Listing 4 performed 300ms faster than other generated programs and was the shortest program, by program length.

When the program was substituted for the ported code on the Lego NXT Mindstorms robot in Code Listing 2[\[14\]](#_ftn14) the Lego NXT Mindstorms robot in its Tribot configuration was able to complete its manoeuvre as shown below.

\[gallery ids="290,286,291,293,288,287,289,292" type="rectangular"\]

Fig. 8. Lego NXT Mindstorms Robot successfully turning at 66% maximum speed

A video of this demonstration is available on the author’s Vimeo channel[\[15\]](#_ftn15).

6.   Discussion
===============

Improve Lego NXT Mindstorms performance by reducing hardware instructions
-------------------------------------------------------------------------

An often-taught rule in embedded software development is to reduce the number of functions that require access to hardware (such as the functions on the Lego NXT Mindstorms robot that detect light observed by the light sensor or control the motor's speed). A direct correlation (P-value: 0.000355 and 4.76×10\-12) was observed between the number of times functions requiring the “C” motor and the light sensor were invoked and the average program execution time. Paradoxically, the number of times functions requiring the “B” motor was inversely correlated  (P-value: 1.19×10\-47) to the average execution time. Unfortunately there was insufficient time to investigate this anomaly.

Tests should combine software emulation with hardware simulation
----------------------------------------------------------------

The process for equivalence testing used to resolve one of the experimental issues was inspired by Bansal and Aiken’s two-step equivalence test, where an initial execution test for “fingerprinting” is used to quickly scan the space of potential programs using a unit-testing methodology \[Bansal & Aiken 2006, p. 399\]. This process of testing the space of generated programs for equivalence in a synthetic environment and then using the physical system for detailed analysis greatly reduced the time to conduct experiments and did not reduce the quality of the results obtained, assuming Type 1 and Type 2 errors are sufficiently managed.

Machine independent superoptimizer potential
--------------------------------------------

The simple grammar defined in Appendix A generated programs between 2 and 5 lines of code: these programs are of similar length to the programs in Massalin’s paper. A limiting factor on the number of programs the superoptimizer can generate is the amount of memory available to the superoptimizer: this is because the superoptimizer stores all generated programs in memory. For instance, all 21,440,680 programs generated with the grammar required all 16 Gb memory available during the case study. Therefore, there is a direct correlation between the grammar complexity, superoptimizer memory and the program length. If an end-user had a large amount of memory available with a small grammar (such as those offered on microcontrollers with a reduced instruction set) then longer programs could be generated by the superoptimizer.

Superoptimization should increase learning about the experimentation environment rather than just find optimal programs
-----------------------------------------------------------------------------------------------------------------------

The author takes a different philosophical view to existing superoptimizer research: the focus should be on understanding why the “best” program was discovered, not just limited to finding the “best” program according to the end user’s metric. In particular, why using different statements in a programming language can perform the same function but improve a non-functional (such as code size or performance) metric.

The author believes this provides more value to developers, as one needs to manually check superoptimizer output to ensure correctness \[Granlund & Kenner 1992, p. 351\] as superoptimizers exploit “side-effects of the hardware architecture in unexpected ways” \[Hume 2013, p. 9\] and developers need to be aware of the impact of these side effects raised by Joshi et al \[Joshi et al. 2002, p. 2\]. For example, the superoptimizer functions could introduce security vulnerabilities through direct memory manipulation instead of using secure functions offered by the programming language. In addition, the end user needs to be aware that any optimization may be specific to their particular physical or technical environment and may not be generalizable to all contexts, especially where the metrics are sensitive to environment such as heat dissipation and energy consumption.

7.   Future Research Directions
===============================

The generic, multi-objective superoptimizer can be improved in the following ways:

— Refactor the superoptimizer to include the two-step equivalence testing process.

— Given the superoptimizer was developed in Java using its parallelization framework the first, software-only equivalence test can be distributed using a distributed framework such as Apache Spark or Apache Hadoop. This could be deployed on a cloud-based provider such as Amazon Web Services to reduce the time required to search for programs.

— Increase the compatibility the ANTLR grammar parsing to include more ANTLR grammar constructs.

— Implement the more sophisticated program generation and testing methodologies from the literature review.

— Improve the output to be more resilient to failure such as exporting intermediate results if a failure during the experiment occurs and resuming experiments without significant user intervention.

— Perform the Pareto multi-objective optimization within the tool or export the results into more formats beyond comma-separated values or system logs.

Finally, more experimentation could be conducted on alternate processors, environments and programming languages measuring alternate metrics such as energy consumption or heat dissipation.

8\.   Conclusion
================

The generic, multi-objective superoptimizer was successfully developed. The Lego NXT Mindstorms case study was conducted, successfully proving the hypothesis and finding that superoptimization can be used in a modern context. Further development of the superoptimizer is recommended to capitalize on contemporary improvements to the superoptimization processes. Continued research into alternate metrics such as energy consumption and heat dissipation is also recommended to discover new superoptimizer applications in contemporary embedded software development.

DISCLOSURE STATEMENT
====================

The author privately funded and resourced this research project. The author has no commercial relationship with any of the products or trademarks referenced in this article.

ACKNOWLEDGMENTS
===============

 

Trademarks mentioned in this article are the respective owners of Amazon, the Apache Software Foundation, Apple, GitHub, Lego, Microsoft, Oracle and Wolfram Research.

APPENDIX A – LeJOS Java Syntax

```
statement

Expressions
```

```
![figA.02](/img/images/figa-02.png)
```

```
expression
```

```
 ![figA.03](/img/images/figa-03.png)
```

```
motor

Expressions
```

```
 ![figA.05](/img/images/figa-05.png)
```

```
lightSensor
```

```
 ![figA.06](/img/images/figa-06.png)
```

```
lightSensor

ReturningAn

Operations
```

```
![figA.08](/img/images/figa-08.png)
```

```
motor
```

```
 ![figA.09](/img/images/figa-09.png)
```

```
basicMotor

Operations
```

```
 ![figA.11](/img/images/figa-11.png)
```

```
functionsReturningAnInteger

Operator
```

```
 ![figA.12](/img/images/figa-12.png)
```

```
logical

Operations
```

```
 ![figA.15](/img/images/figa-15.png)
```

```
booleanValue
```

```
 ![figA.17.png](/img/images/figa-17.png)
```

```
integerValue
```

```
![figA.16](/img/images/figa-16.png)
```

```
variable
```

```
![figA.19](/img/images/figa-19.png)
```

```
arithmetic

 ![figA.21](/img/images/figa-21.png)