High Loop Carried Dependency Bound - why?

First, there is a recurrence on several arrays.  Consider validMin.  On every iteration of the outer loop, you reset validMin to &validMin0[x], but also increment validMin in the inner loop.  The pattern of accesses for validMin0 is 0 1 2 3, 1 2 3 4, 2 3 4 5, etc.  Perhaps you meant to initialize validMin to &validMin0[x*4] in the outer loop?

Secondly, restrict only takes effect for the lifetime of the variable.  As you have it, it says nothing about the relationship between these variables and the same variables on the next iteration of the outer loop.  Consider moving the declaration of the variables outside the outer for loop as follows:

short* restrict leftMin;
short* restrict leftMinIdx;
short* restrict rightMin; 
short* restrict rightMinIdx;
short* restrict validMin; 
short* restrict validMinIdx;

int x;
for(x=0; x < 4; x++) {
    leftMin = &min0_0[x];
    leftMinIdx = &minIdx0_0[x];
    rightMin = &min0_1[x]; 
    rightMinIdx = &minIdx0_1[x];
    validMin = &validMin0[x]; 
    validMinIdx = &validMin0Idx[x];

Hi Archaelogist,

Actually the code is iterating in two dimensions - one dimension in the outer loop ("x") and another one in the inner loop ("y" only 0-3).

Thanks to your suggestions of moving the definition of the pointers out of the loop, the "loop carried dependency bound" went down to 20 - and the compiler was able to find a schedule within 21 cycles. ts a descent improvement of 20%, thanks a lot.
I decided against writing this function in linear assembly as its memory bound anyway.

What I don't understand is, why is there any  "loop carried dependency bound" at all - the inner loop is unrolled, so according to the output the optimizer is pipelining the outer loop. However, all a loop iteration does, is reading and writing some non-dependant memory locations, there is not a single variable passed to the next iteration, as all pointers are reset at the beginning.
It would be really great for me to understand the optimizer in this case, so I would able to understand whats going on behind the scenes and write better code next time.

Thx

Heinrich Schwarz said:

Actually the code is iterating in two dimensions - one dimension in the outer loop ("x") and another one in the inner loop ("y" only 0-3).

Are yStep and valStep guaranteed to be multiples of 4?

The loop carried dependency bound comes from the if statement. There is a path through the if statement such that the pointer leftMin gets incremented, and another path such that it does not get incremented. The if control expression reads the value of leftMin. Thus, the next iteration of the loop can't start until we know whether or not leftMin got incremented in the previous iteration. The same is true of rightMin. No amount of unrolling will help.

Are yStep and valStep guaranteed to be multiples of 4?

Thx