Path: utzoo!mnetor!uunet!husc6!bloom-beacon!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, Fortran FREQUENCY declaration
Message-ID: <645@l.cc.purdue.edu>
Date: 7 Jan 88 11:11:46 GMT
References: <496@cresswell.quintus.UUCP> <638@l.cc.purdue.edu> <836@ima.ISC.COM>
Organization: Purdue University Statistics Department
Lines: 37
Summary: A misconclusion based on the peculiarities of a single machine

In article <836@ima.ISC.COM>, johnl@ima.ISC.COM (John R. Levine) writes:
> In article <18251@bu-cs.BU.EDU> hen@bucsd.bu.edu (Wm. H. Henneman) writes:
> >As I recall, the original FORTRAN (for the IBM 704) had a FREQUENCY
> >statement which allowed the programmer to give hints about the
> >probability of branches being taken.  It was used by the compiler for
> >index register optimization.  

> >[Why did it disappear in later versions?]
  
> The FREQUENCY statement disappeared for two reasons, as far as I can tell.
> The first is that it didn't improve the code much; changing the order of
> the "branch if greater" vs. the "branch if less" instructions after a test
> made little difference on the non-overlapped, non-pipelined 7094.  .....

> But enough of this, it's a far cry from hardware architecture.  The lesson
> here seems to be that the compiler should make its branch predictions
> automatically based on the code or perhaps iteratively based on information
> gathered from profiling a previously compiled version.

It is a property of the 70x(x) series, and most of the computers of that time,
that a branch was almost costless, and the time required to save and restore
all registers was approximately that of a single multiplication.  In fact, on
some computers transfer (even conditional) was the fastest operation, and
memory access next.  Since then, arithmetic operations have, relative to 
access, speeded up, branches have slowed, and the number of registers has
greatly increased.  On many machines, a transfer can cost 15-100 instruction
times.  On many which attempt to look ahead, even an untaken transfer can
cost 8 instructions.  Thus it is important that the programmer (algorithm
designer) be able to tell the compiler which way things are going, and for
the hardware to be able to charge ahead when there is a possibility of a
rare branch.


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