Re: Backward branches

"Robert Thorpe" <Robert.Thorpe@antenova.com>
16 Jan 2004 22:23:34 -0500

          From comp.compilers

Related articles
Backward branches kugan@ieee.org (2003-12-14)
Re: Backward branches torbenm@diku.dk (2003-12-20)
Re: Backward branches haberg@matematik.su.se (2003-12-21)
Re: Backward branches kugan@ieee.org (2004-01-02)
Re: Backward branches vbdis@aol.com (2004-01-09)
Re: Backward branches j.troeger@qut.edu.au (Jens Troeger) (2004-01-12)
Re: Backward branches Robert.Thorpe@antenova.com (Robert Thorpe) (2004-01-16)
| List of all articles for this month |

From: "Robert Thorpe" <Robert.Thorpe@antenova.com>
Newsgroups: comp.compilers
Date: 16 Jan 2004 22:23:34 -0500
Organization: Compilers Central
References: 04-01-020
Keywords: architecture, optimize
Posted-Date: 16 Jan 2004 22:23:34 EST

> 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.


Post a followup to this message

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