Re: Re: eliminating array bounds checking overhead

Patryk Zadarnowski <>
1 May 2000 13:17:41 -0400

          From comp.compilers

Related articles
Re: eliminating array bounds checking overhead (Sandeep Dutta) (2000-04-29)
Re: Re: eliminating array bounds checking overhead (Patryk Zadarnowski) (2000-05-01)
Branch prediction (was: eliminating array bounds checking overhead) (Patryk Zadarnowski) (2000-05-04)
Re: Branch prediction (was: eliminating array bounds checking overhead (2000-05-08)
Re: Branch prediction (was: eliminating array bounds checking overhead (David Gregg) (2000-05-12)
| List of all articles for this month |

From: Patryk Zadarnowski <>
Newsgroups: comp.compilers
Date: 1 May 2000 13:17:41 -0400
Organization: Compilers Central
References: 00-04-216
Keywords: architecture, performance, comment

> > As for the hardware side I guess that most modern architectures have
> > something like BOUND on Intel.
> Speaking of Hardware solutions, architectures like PowerPC and MIPS
> allow static brach predictions (although MIPS is doing away with this
> feature in their next generation ).

A clarification on the topic of MIPS branch-likely instructions:

This is actually a very common misconception about the branch-likely
MIPS instructions. While R10k might have dynamic branch prediction,
MIPS in general doesn't have any support for static branch prediction,
for the simple reason that R4k CPUs don't prefetch instructions. On
R4k CPUs, a branch always results in a pipeline slip(3 cycles on R4000
and R4400, 2 cycles on most others) of which one cycle can be salvaged
as the branch delay slot.

On R4K CPUs, the branch-likely instructions merely nullify the
instruction in the branch delay slot if the branch is not taken (in
which case the branch delay slot is lost and you haven't gained
anything.) These instructions exist only to make it easier to populate
the branch delay slots in loops. Specifically, there are no branch-
unlikely instructions in MIPS, and at most one instruction is ever
executed after the branch before the pipeline starts slipping.

This is very different from true branch hints which tell the CPU to
continue prefetching instructions from the target address, and
possibly speculatively execute them. Such hints exist on SPARC v9
(single predict taken/not taken bit), Alpha (page offset of the target
PC), POWER, PowerPC (single bit), PA-RISC and IA-64 (predict static
taken/not taken, dynamic taken/not taken, prefetch none/few/many cache
lines and allocate/deallocate branch logic resources.) Did I miss any?

IA-64, in a true Intel fashion, (and most other EPIC/VLIW ISAs) has a
very sophisticated static predictor which goes beyond predicting
branches, but that's a topic for another email. ;)


Patryk Zadarnowski University of New South Wales
<> School of Computer Science and Engineering
[I was under the impression that guessing that backward branches are
taken and forward branches aren't does surprisingly well. -John]

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.