This program reads a trace and tries to build loop nests that reproduce the input data. Details of the algorithm can be found in "Prediction and Trace Compression of Data Access Addresses through Nested Loop Recognition", by Alain Ketterlin and Philippe Clauss, at CGO'2008.
Please direct all questions and remarks to:
Licensing information can be found in the LICENSE file that comes with the source distribution.
Feel free to contact any of the authors if you have any question or need some specific feature. Also, if you do any serious thing with this code, please let us know by sending a short description of what you did.
The latest version of NLR is available from https://icps.u-strasbg.fr/nlr/ (current version is nlr-0.7.tar.gz).
To build the executable (named nlr), just type make. There should be no warning, no error. You need a C99 compliant compiler. I've tried this on various Linux distributions, with no problem. If you have trouble compiling nlr, or get warnings or errors, please send me (Alain) the compiler's output (and problematic lines of code if you changed the source). The code is probably Unix-specific, you're on your own if you try to compile this on another system.
The details of the algorithm can be found in the CGO paper mentioned earlier. The tool has a (slightly outdated) man-page, visible with:
man ./nlr.1Invoking "./nlr -h" also gives a summary of command line options.
NLR tries to find loops producing the given trace. For instance, given input:
1
2
3
4NLR will produce the following loop:
for i0 = 0 to 3
val 0x1 + 1*i0The algorithm has a parameter indicating the maximal length of a loop body (in terms of loops and values). The "-k" option assigns a value different from the default 1. For instance, with input:
a 1
b 2
a 3
b 4
a 5
b 6a call to "./nlr -k 2" (or any larger value) will produce:
for i0 = 0 to 2
val a , 0x1 + 2*i0
val b , 0x2 + 2*i0whereas "./nlr -k 1" (or "./nlr" with no option) will output (a stylized version of) the input trace.
It is customary to use a relatively large value for first experiments ("-k 100" or so), but higher values have a strong effect on run-time with inputs displaying no or little linear regularity.
Since it was initially used to process traces of memory addresses, NLR prints affine functions with an hexadecimal constant and decimal factors of loop indices. Using "-a none" prints every number in decimal ("-a all" prints all numbers in hexadecimal).
Another useful option is "-g" whose argument is a bitset: value 1 requests a progress counter to be printed, value 2 prints timing and volume information at the end of the run.
NLR is not really set up to be used as a library. If you have such a requirement, please contact the authors for help. (Or start with the nlr.c file's main function, which is a thin wrapper around the algorithm itself.)
If you do this, be advised that the code uses global data at several places (for efficiency purposes), which probably makes it hard to use as-is in a multithreaded setting.
Also, the software is currently full of dead-code, hacks etc. For any usage other than running it on some traces and look at the output please contact me, as I have various other versions that may help you more than this one.