Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!usc!wuarchive!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!emory!gatech!mcnc!rti!dg-rtp!bigben!bigben!philip
From: philip@beeblebrox.dle.dg.com (Philip Gladstone)
Newsgroups: comp.arch
Subject: Re: speculative execution
Message-ID: <PHILIP.90Oct11102731@beeblebrox.dle.dg.com>
Date: 11 Oct 90 14:27:31 GMT
References: <1990Oct9.212103.363@rice.edu> <12905@encore.Encore.COM>
	<1990Oct10.164353.21070@rice.edu>
Sender: usenet@dle.dg.com (Net News)
Organization: Data General, Development Lab Europe
Lines: 54
In-Reply-To: preston@titan.rice.edu's message of 10 Oct 90 16:43:53 GMT

In article <1990Oct10.164353.21070@rice.edu> preston@titan.rice.edu (Preston Briggs) writes:
[stuff deleted]
>   We can however, hoist the initial pipeline stages (perhaps overlapping
>   them with earlier pipeline compuations).
>
>           int-1, pfmul.ss f3,f4,f0     <--- These floats hoisted from
>           int-2, pfmul.ss f0,f0,f0     <--- from the if
>           int-3, pfmul.ss f0,f0,f0
>           if (something) {
>               pfmul.ss f0,f0,f5
>           }
>           fst.l	f5,somewhere
>
>   The true path get much shorter.
>   No increase in the path length of the false path.
>   And no extra register required.

It seems to me that it is very difficult to spot when this is legal or not.
It is assumed in this example that none of the hoisted instructions
will cause any problems if they are executed when the programmer did
not intend them to be executed. Consider the case of overflow! I must
confess to knowing little or nothing about the i860, but similar
examples exist for the 88100 (which I do understand). Consider the
following code fragment:

            if (i > 0)
            {
                volatile_global = b / i;
            }

On the 88000 at least, divides are very slow (36 cycles) and there is
a great temptation to move them back up the instruction stream so as
to get greater parallelism. In this case, the divide could blow up (if
i was equal to 0) when the source would not have blown up.

This whole problem arises from the fact that most instructions have an
implicit conditional branch (interrupt) as part of their
specification. You can only (reliably) hoist instructions that cannot
trap -- unless you can perform major flow analysis to check that the
trap conditions never arise (such as adding two shorts in long
registers with an overflow causing instruction).

Removing the implicit trapping action of these instructions would be a
way out of this problem, but you would have to introduce some sort of
'trap on previous overflow' instruction. Even then you would have to
take great care that you only detected the right overflows.

Enough of this
---
--
Philip Gladstone                        philip@dle.dg.com
Development Lab Europe                  C=gb/AD=gold 400/PR=dgc/O=dle
Data General, Cambridge                   /SN=gladstone/GN=philip
England.  +44 223-67600