Blocking of nested loops having feedback or feedforward indexes

A system comprising:

• a random access memory to hold a computer program, wherein the computer program includes a nested loop, the nested system having a first program loop and a second program loop, the first program loop being within the second program loop, the first program loop being indexed over a contiguous one-dimensional iteration space, the first program loop having a constant index shift;
• a cache memory to hold values from a memory, the values including values for a two-dimensional iteration space for the nested loop;
• and
• a processing unit to evaluate the computer program and to generate a modified form of the nested loop, the modified form including an outer loop around the nested loop and generating a plurality of blocks over the two-dimensional iteration space for the nested loop.

A machine-readable medium having stored thereon data representing sequences of instructions that, when executed by a processor, cause the processor to perform operations comprising:

• receiving a computer program for compiling, the computer program including an outer loop and a plurality of inner loops, the inner loops being within the outer loop, the inner loops being indexed over a contiguous one-dimensional iteration space, an inner loop of the plurality of inner loops having an index that is shifted;
• compiling the computer program, the compilation of the computer program including:
• adding an additional loop around the outer loop, and
• dividing the values of a two-dimensional iteration space for the outer loop and inner loops into a plurality of shapes, the added loop running iterations of the values for each shape in sequence.