Scalar evolution

By scalar evolution, we mean how the value of a scalar changes in a program with the execution of code. We look at a particular scalar value and see how it is getting derived, what all other elements it is dependent on, whether this is known at compile time or not, and what all operations are being performed. We need to look into a block of code rather than looking into individual instructions. A scalar value is build up from two elements, a variable and an operation of constant step. The variable element that builds up this scalar value is unknown at compile time and its value can be known at run time only. The other element is the constant part. These elements themselves may be recursively broken into other elements such as a constant, an unknown value or an arithmetic operation.

The main idea here is to look at complete scalar value containing the unknown part at compile time and see how this value will evolve during execution and try to use this for optimization. One...