Prev: begginer question
Next: Parallel execution of carry dependent instructions ?
From: Skybuck Flying on 6 May 2008 19:36
What is a branch ?

Classic sense like a tree:

if (True) then <- node/evaluation/condition.
/\
/ \
/ \
/ \
/ \
/ \
True Branch False Branch (does not exist)

Since there is only one branch.

The manual says:

"It assumes the branch is not taken".

Now you say this is backwards, if so then I say:

Manual needs to be fixed/clearified.

Anyway, Wikipedia to the rescue:

"
Branch (Computer Science):

A branch (or jump on some computer architectures, such as the PDP-8 and
Intel x86) is a point in a computer program where the flow of control is
altered. The term branch is usually used when referring to a program written
in machine code or assembly language; in a high-level programming language,
branches usually take the form of conditional statements, subroutine calls
or GOTO statements. An instruction that causes a branch, a branch
instruction, can be taken or not taken: if a branch is not taken, the flow
of control is unchanged and the next instruction to be executed is the
instruction immediately following the current instruction in memory; if
taken, the next instruction to be executed is an instruction at some other
place in memory. There are two usual forms of branch instruction: a
conditional branch that can be either taken or not taken, depending on a
condition such as a CPU flag, and an unconditional branch which is always
taken.
"

Ok now I understand a little bit but it's difficult for me as high level
language programmer to understand what the processor will do, because the
high level language might implement branches differently etc but ok.

So one must look at the assembler level:

compare blablablablabla
jump condition to somewhere else

next instructions
next instructions

somewhere else

other instructions
other instructions.

Jump = taken
Not Jump = not taken.

So the processor assumes it can simply skip over the jump statements etc and
executes the next instructions.

Now back to my code example:

// Condition 1
026B08AA 803C2400 cmp byte ptr [esp],$00
026B08AE 0F8496000000 jz $026b094a

// Condition 1 Code

026B08B4 8B481C mov ecx,[eax+$1c]
....


This translates to:

Compare/Look at condition at some memory location.
Jump if condition is zero.
Continue if condition is not zero

So it would seem the condition code is indeed executed the first time.

Then the manual says it assumes the branch is taken until not taken.

Which is a flip flop from previous situation...

This is probably to have a 50% chance of predicting it ok if branch tables
full and such problems.

The manual doesn't say what happens when the branch prediction table gets
full... ?

I guess some will be thrown out... so maybe then it repeat the above logic
again.

Oh well, I guess conditions are still better than using a function/procedure
pointer... because that involves a return address...

And the processor only has very little space for the return stack.

So using branches probably much better idea ;)

Bye,
Skybuck.


From: Skybuck Flying on 6 May 2008 15:10
Hmm,

I just came across this little piece of information from the amd
optimization guide:

"
A.6 Branch-Prediction Table
The AMD Athlon 64 and AMD Opteron processors assume that a branch is not
taken until it is taken
once. Then it is assumed that the branch is taken, until it is not taken.
Thereafter, the branch
prediction table is used.
The fetch logic accesses the branch prediction table in parallel with the L1
instruction cache. The
information stored in the branch prediction table is used to predict the
direction of branch
instructions. When instruction cache lines are evicted to the L2 cache,
branch selectors and predecode
information are also stored in the L2 cache.
The AMD Athlon 64 and AMD Opteron processors employ combinations of a branch
target address
buffer (BTB), a global history bimodal counter (GHBC) table, and a return
address stack (RAS) to
predict and accelerate branches. Predicted-taken branches incur only a
single-cycle delay to redirect
the instruction fetcher to the target instruction. In the event of a
misprediction, the minimum penalty
is 10 cycles.
The BTB is a 2048-entry table that caches in each entry the predicted target
address of a branch. The
16384-entry GHBC table contains 2-bit saturating counters used to predict
whether a conditional
branch is taken. The GHBC table is indexed using the outcome (taken or not
taken) of the last eight
conditional branches and 4 bits of the branch address. The GHBC table allows
the processors to
predict branch patterns of up to eight branches.
In addition, the processors implement a 12-entry return address stack to
predict return addresses from
a near or far call. As calls are fetched, the next rIP is pushed onto the
return stack. Subsequent returns
pop a predicted return address off the top of the stack.
"

First of all it seems to have a pretty large branch table.

Second of all..

From the first few lines it seems it assumes branch is not taken.

So I think this means:

if True then
begin
// processor will think this won't be executed at the first time.
end;

Then later when processor comes across it again, it knows it was taken.

So then it assumes it will be taken again.

So this means the if statements will be mis-predicted the first time.

And then it should be good predictable all other times.

As long as it fits in the 2k or so.

Bye,
Skybuck ;) :)


From: MitchAlsup on 6 May 2008 18:17
On May 6, 1:10 pm, "Skybuck Flying" <BloodySh...(a)hotmail.com> wrote:
> So I think this means:
>
> if True then
> begin
>     // processor will think this won't be executed at the first time.
> end;

You got that one backwards. The

if( TRUE )
{
// this code will always be executed
}

So the branch associated with the if statement will never be taken.

But ANY reasonable compiler will remove the branch.
 | 
Pages: 1
Prev: begginer question
Next: Parallel execution of carry dependent instructions ?