explanation.txt

-+1 ------->Explanation for output.tc<------------

STOKE uses random search to explore the extremely high-dimensional space of all possible program transformations. For a way to give a backbone to the Stoke Search methods we need to generate a set of test-cases. One of the them is Random Generation and Backtracking. I selected this since it was good head start for someone who is looking to generate their own cases for the algorithm.

The one in the attachment 'output.tc' has generated a similar testcase. The nehalem system ( core i7) has 16 registers from %rax to %r15. The following argument 'testcase' will put random values in registers, and then try to fill in dereferenced memory locations with random values. The function popcntm() gives the number of 1s when set to search the space. The .s program which I have used uses this function. Just that it gives a mangled name to it as _z6popcnt to avoid it's name collision.

To know the current status of the processor in an intel make, the processors have some flags for eg. https://www.shsu.edu/~csc_tjm/fall2005/cs272/flags.html. & http://www.c-jump.com/CIS77/ASM/Instructions/I77_0070_eflags_bits.htm. The further flag names such as vm and ac and vif concern with the second link since they do not fall in the category for the flags but qualify as eflags.

The Intel makes (Sandybridge - i5; Haswell - i3 ) make use of AVX (Advanced Vector Extension) instruction set and the registers (YMM0 to YMM15) represent the condition of the registers just before execution of the test. The new make (Nehalem - i7) however, uses the MMX instruction set. The technical data of registers that concerns these systems is generally packed in file format (technical Data) and so the weird extension (output.tc).

Finally the last set of result in output.tc gives a set of valid and invalid contents of flag on stack and heap. Bytes will be segregated in valid and invalid. This brings me to the Final Configuration of the Stoke project as explained below.

When STOKE finishes generating the search from the testcases provided it generates a low-cost verified version of the same program. The generated function _Z6popcntm.s which is stored in bins directory is a compiled version of the main.cc and main2.cc programs pushed on Github. To go in-depth, the popcnt function is the function which is used in main.cc and main2.cc programs. It is a built-in function which is used for counting the population of the number of bits. This function was created because it gave a way for optimising the programs for eg. Replacing serial-shifting operation. This is used in operations where large amount of memory is used, to sort the contents and to get a lookup table of the population count. Link : (https://en.wikichip.org/wiki/population_count)

This program is compiled via g++ and gets stored in a mangled name _Z6popcntm. When _Z6popcntm function is passed as a testcase, i.e after the testcase arg., when we implement (stoke synthesis), we have input target as _Z6popcntm.s, the generated testcases as --testcases and the output in the desired location via -o <path/to/output>.

When the project discovers a low-cost verified rewrite code it will take its output and log under, Progress Update and consequently the statistics table. The replace.conf file can be used for patching the result in the original binary. One more thing to cross verify, the execution time, i.e runtime measurement stats are also several magnitudes lesser than the previous found run-times. Command: time ./a.out 1000000 (the last figure is the number of iterations which can be kept constant for comparison