|Backward branches email@example.com (2003-12-14)|
|Re: Backward branches firstname.lastname@example.org (2003-12-20)|
|Re: Backward branches email@example.com (2003-12-21)|
|Re: Backward branches firstname.lastname@example.org (2004-01-02)|
|Re: Backward branches email@example.com (2004-01-09)|
|Re: Backward branches firstname.lastname@example.org (Jens Troeger) (2004-01-12)|
|Re: Backward branches Robert.Thorpe@antenova.com (Robert Thorpe) (2004-01-16)|
|From:||"Robert Thorpe" <Robert.Thorpe@antenova.com>|
|Date:||16 Jan 2004 22:23:34 -0500|
|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
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++)
n = 0;
while (n < 10)
In some compiler backends all loops are turned into "for" loops, in
others all are turned into "while" loops.
Return to the
Search the comp.compilers archives again.