We will look now at instruction scheduling in the compiler.
No that this is different from what happens in a Tomasulo type scheduler,
where the hardware is trying to reorder instructions,
in a different way than they were arranged by the compiler.
Now the compiler will actually try to do a similar thing. Here's a sequence of
instructions that can happen. We load, a value from the address in R1 into R2.
We add R0 to that. We store the result back into that memory location.
We next move the memory address four places forward, so
that we are looking at the next for example, element in our array in memory. And
then, we compare the pointer to some sort of end of array pointer, and
if they're not equal, we jump back to the loop. So these are five instructions,
out of which a single iteration of a loop is composed of. So let's say that we
have a very simple processor, that can only look at the very next instruction.
So it's not really trying to have reservation stations and execute out of order.
In that case, what might happen is. There would be this load. And let's say,
it takes two cycles to actually get the value into this register from the cache.
That means that the next cycle, the processor cannot do this ADD,
it has to stall, because the result in R2 is not available yet.
In the next cycle, it will be adding R0 to the value in R2. Let's say now,
that the ADD takes a few cycles. Let's say, three. So only here,
can we store. The next instruction, doesn't depend on the store. So
let's say we can do it in the next cycle. But then, this ADD again, takes three
cycle, let's say. So we have two Stalls, before we can do this branch. So
let's say that the compiler is trying to help the processor do better than this.
If we still have the same processor. But we wanted to execute these
instructions faster than one, two, three, four, five, six, seven, eight, nine,
ten cycles per iteration. How can we do that? Well what the compiler will try to
do is, it knows that after this load we cannot do this ADD until,
two cycles later, so it's going to try to find something that can be here.
So, we need something that doesn't depend on the load and can be done here.
Now, we can see that the ADD does depend on the load, so it cannot go here.
The Stall, needs the result of the ADD so it cannot more here.
But the ADD actually can go here because the ADD doesn't depend on
the R1 value here. So, the compiler is going to try to move this ADDI here. So
we want a schedule in which the ADDI is here, because this processor can do only
one instruction at a time, in the order in which they're placed in the program.
That would mean, moving this ADD here in the program. Let's see how that,
would be done. So conceptually, we want this ADD here.
Note however, that while the load gets the same value of R1 that it did before,
the Stall now gets R1 that has already been incremented by 4. So
we have moved this ADD, because this R1 is now, larger than it should be.
We have to fix the offset here so that, it loads from R1 minus 4.
When we remove this ADD, the branch still sees the correct value of R1
because it needs to see the incremented value and
the new program looks like this. The black stuff is the stuff that has moved or
changed. And the, blue stuff is what has remained exactly the same as before.
Now let's see what happens to our schedule. Now we have a load.
And, instead of the ADD here being the next instruction so
we had to Stall, the next instruction is this ADD. This ADD,
can proceed in parallel with the load. It doesn't depend on the, R2. So we
can actually do this ADD here. So, instead of a Stall, we can now do our ADDI.
This eliminates one of the Stalls. The Add here, doesn't depend on this ADD,
so it can still stay where it is. Now, in order to get to the Stall instruction,
we still have to do the two Stalls because the ADD here takes two cycles of
stalling before we can use the result. So, this Stall needs to stay here.
But at this point, we have already done this ADDI. It's moved here. Of course,
the Stall now need to be modified this way. So this instruction is now
like this. The ADD now goes away. So we have just removed one cycle here.
Next, when can we do this branch? Well the ADD has happened here.
We cannot use R1 until one, two, the third cycle from there.
So pretty much at any point after here, the branch actually is safe to go,
as far R1 is concerned. Note that here we have to stall because of this. So
we have just eliminated, two more cycles here. And now we can do our branch. So
pretty much, we had plenty of Stalls then. Now we have only two Stalls and
the rest of the loop body is scheduled. So, pretty much, the idea of instruction
scheduling is to find instructions that can be done in place of stalls.
And thus, avoid having too many stalls in the processor schedule.