Path: utzoo!mnetor!uunet!husc6!bbn!rochester!PT.CS.CMU.EDU!K.GP.CS.CMU.EDU!lindsay
From: lindsay@K.GP.CS.CMU.EDU (Donald Lindsay)
Newsgroups: comp.arch
Subject: Re: taken -vs- untaken branches
Message-ID: <588@PT.CS.CMU.EDU>
Date: 5 Jan 88 17:33:50 GMT
References: <496@cresswell.quintus.UUCP> <638@l.cc.purdue.edu> <20339@amdahl.amdahl.com>
Sender: netnews@PT.CS.CMU.EDU
Organization: Carnegie-Mellon University, CS/RI
Lines: 20

In article <20339@amdahl.amdahl.com> chuck@amdahl.amdahl.com (Charles Simmons) writes:
>One method of allowing a compiler to automagically guess whether
>a branch will usually be taken or not, would be for the compiler
>to estimate the number of legal values that one side of the expression
>can take on, and the number of legal values that the other side of
>the expression can take on.  These two estimates can then be used
>to estimate how often the expression will be TRUE.

The best heuristics use high-level context.  For example, a loop construct
is liable go around again. An IF-part is more likely to be executed than an
ELSE part. CASE TRUE is more likely than CASE FALSE.

Compilers should allow the source program to give hints. With that, it's
easy to build tools that measure running programs, and then feed the
results back into the source. The CRISP machine is well suited to this,
since its conditional branch instruction contains a hint bit.


-- 
	Don		lindsay@k.gp.cs.cmu.edu    CMU Computer Science