How does an optimizing compiler react to a program with nested loops?

Question

Say you have a bunch of nested loops.

public void testMethod() {
    for(int i = 0; i<1203; i++){
                //some computation
        for(int k=2; k<123; k++){
                        //some computation
            for(int j=2; j<12312; j++){
                                //some computation
                for(int l=2; l<123123; l++){
                                        //some computation
                    for(int p=2; p<12312; p++){
                            //some computation
                    }
                }
            }
        }
    }

}

When the above code reaches the stage where the compiler will try to optimize it (I believe it's when the intermediate language needs to converted to machine code?), what will the compiler try to do? Is there any significant optimization that will take place?

I understand that the optimizer will break up the loops by means of loop fission. But this is only per loop isn't it? What I mean with my question is will it take any action exclusively based on seeing the nested loops? Or will it just optimize the loops one by one?

If the Java VM complicates the explanation then please just assume that it's C or C++ code.

Answer 1

An optimising compiler generally works on the basis that the innermost loop is the only one worth the effort. The strategies for optimising loops include unrolling, vectorisation, hoisting (calculations out of the loop), and so on. It may also change the code if it can determine that the loop will terminate early, or not at all. None of these are specific to nested loops.

The only optimisations I know of that are specific to nested loops are these.

1. Loop exchange/inversion. for(x...){for(y...){...}} can be inverted into for(y...){for(x...){...}} if the compiler can determine that it is (a) equivalent (b) faster or (c) can be made faster.
2. Vectorisation applied to the inner loop may be extended to vectorise multiple loops, depending on the instruction set available.
3. If the inner loop can be unrolled or vectorised or deleted then the next loop becomes the inner loop, and is subject to the same optimisations.
4. If an expression can be hoisted out of an inner loop, it can perhaps be hoisted further.

It's not easy to know which compilers currently implement which if any of these. I know that Fortran compilers were very early implementers of aggressive vectorisation on machines like Cyber and Cray, but I'm not in touch with that now. You would now look at compilers targeting GPUs.