Re: Backward branches

> Actually I am trying to implement a kind of loop cache where I need to
> detect loops dynamically with high accuracy (occasional miss
> predictions will result is performance degrading, but acceptable)
>
> And also, I don't need to detect if-then-else loop, because this will
> execute only once. What I need to detect is "while loop", "for loop"
> etc. As I said earlier, I can ignore exception, as it would happen
> less frequently.
>
> So, from what I understood from your reply, it should work (leaving
> the exception) without any compiler assistance. Is it correct?


What you are trying to do is simple, though not easy.


Many things have been tried before in the past. As Torben said many
hardware branch predictors will initially assume that a backward
branch is taken. This is because they are most commonly loops.


Compilers reorder blocks, but they rarely add backward jumps that
aren't likely to be taken, this is because they know that hardware
assumes they are taken. (Though some do.)


After the branch predictor has made it's first judgement it will make
it's second judgement based on the accuracy of the first. Also, some
predictors have special features to minimize the mispredicts
encountered at the end of loops. Read some articles on branch
prediction.


As for detecting "while loop" and "for loop", to the compiler backend
such things don't exist, there are simply loops. There is no
difference between them anyway.


for (n = 0; n < 10; n++)
{
    .. Block
}


==


n = 0;
while (n < 10)
{
    .. Block
    n++
}


Conversely


while (condition)
{
    .. Block
}


==


for (;condition;)
{
    .. Block
}


In some compiler backends all loops are turned into "for" loops, in
others all are turned into "while" loops.

Return to the comp.compilers page.
Search the comp.compilers archives again.