Path: utzoo!mnetor!uunet!husc6!hao!gatech!purdue!i.cc.purdue.edu!j.cc.purdue.edu!k.cc.purdue.edu!l.cc.purdue.edu!cik
From: cik@l.cc.purdue.edu (Herman Rubin)
Newsgroups: comp.arch
Subject: Re: taken -vs- untaken branches
Message-ID: <638@l.cc.purdue.edu>
Date: 1 Jan 88 11:18:56 GMT
References: <496@cresswell.quintus.UUCP>
Organization: Purdue University Statistics Department
Lines: 31
Summary: The programmer should tell the computer

In article <496@cresswell.quintus.UUCP>, ok@quintus.UUCP (Richard A. O'Keefe) writes:
> I thought that taken branches were always more costly than untaken
> branches, so that one should try to arrange branches so that the
> not-taken case was the commonest.  There were some messages in this
> group a while back which seems to suggest that in some newer RISCs
> this was no longer the case.

On some machines, taken branches are faster; on others, not taken are.
It may depend on the amount of displacement involved.  The programmer
(or the algorithm designer) usually knows which is more likely.  As
it frequently matters, I suggest that there be a way to tell the compiler
which, and also that the architecture should use a bit in the branch
instruction to tell the machine which.

>     - compiler-assigned fixed branch prediction bits
>     - guessing that backward branches will be taken and forward ones won't

How can the compiler know?  In many of the if - then -else situations I have
encountered, the if - then is rare; in others the else is rare.  If it is 
just if -then with a drop through if the condition does not hold, usually
the drop through is the common condition _in my experience_.  Most compilers
will make the drop through as a forward branch, as that gives the shortest
code.  If there is a cost for taken branches, the conditional code should be
shunted off, possibly to a remote location.  This may involve transfers to
locations outside the current block, which is frowned on by most compilers.
This should not be treated as a conditional subroutine call, as the setup
for a subroutine is likely to exceed the branch penalty.
-- 
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907
Phone: (317)494-6054
hrubin@l.cc.purdue.edu (ARPA or UUCP) or hrubin@purccvm.bitnet