Ivan Godard [2021-06-28 09:44:47] wrote:
> On 6/28/2021 7:21 AM, Stefan Monnier wrote:
>>>> One pretty simple solution to this kind of problem that has been used in
>>>> the past is to start a timer/counter each time an instruction starts.
>>>> If the count exceeds some large number, generate an exception.
>>> That is a good idea to include, but I am a little stumped at the moment
>>> about implementation.
>> As a compiler/proglang guy, the one thing that stumps me instead here is
>> "why?".
>> Why would you want, or when/where would you need something like an
>> "exec" opcode? It seems to me like a "solution" in search of a problem.
>> Stefan
> An exec is a very cheap special-case function call for very short functions.

What makes it so "very cheap"er than a function call using normal
instructions and why/when would I need it?

Stefan

"robf...@gmail.com" <robfi680@gmail.com> writes:
>On Monday, June 28, 2021 at 11:14:07 AM UTC-4, Thomas Koenig wrote:
>> Stefan Monnier <mon...@iro.umontreal.ca> schrieb:
>> >>>One pretty simple solution to this kind of problem that has been used =
>in=20
>> >>>the past is to start a timer/counter each time an instruction starts.=
>=20
>> >>>If the count exceeds some large number, generate an exception.=20
>> >> That is a good idea to include, but I am a little stumped at the momen=
>t=20
>> >> about implementation.=20
>> >=20
>> > As a compiler/proglang guy, the one thing that stumps me instead here i=
>s "why?".=20
>> > Why would you want, or when/where would you need something like an=20
>> > "exec" opcode? It seems to me like a "solution" in search of a problem.
>> I have even missed what this exec opcode should do, to be frank.=20
>>=20
>> Would it be like the UNIX exec() system call, or something else?
>
>EXEC executes an instruction contained in a register. It would allow passin=
>g the instruction around in a program. The great benefit of EXEC is that it=
> allows functionality of a routine to be altered without resorting to self-=
>modified code. I missed this kind of thing when programming a graphics libr=
>ary. I ended up using self modifying code for performance reasons. EXEC cou=
>ld have been used to implement the raster-ops for instance. It could also b=
>e used in text processing software. It is far faster to use an EXEC instruc=
>tion than the switch statement it typically replaces. It does have some ben=
>efit, but it is also costly to implement.
>I have had EXEC like functionality available on one machine in the form of =
>specialized code buffers. Code could be executed out of a buffer in a singl=
>e clock cycle.

Forth has a word EXECUTE that executes an arbitrary word (not just
colon definitions (functions/procedures in other languages)) whose
token is passed to EXECUTE on the stack. In the dynamically executed
instructions in <http://www.complang.tuwien.ac.at/forth/peep/>, about
0.5% of the executed primitives are EXECUTE; 96% of the EXECUTEd words
are colon definitions, followed by variables (1.4%).

In a threaded-code implementation, EXECUTE works by leaving the
threaded-code instruction pointer alone, but jumping to the native
code that executes the word; as soon as it is done, the next word is
executed, which is the one after the EXECUTE. This is very much like
the exec opcode (compare the threaded code to the macrocode and the
native code to the microcode of a microcoded CPU).

In a native-code implementation, this does not work, because there is
only one program counter in play. So native-code implementations
implement all words such that they can be CALLed, and EXECUTE performs
an indirect call. The call saves the program counter, and at the end
the word returns and execution continues with the next word after the
EXECUTE.

What Forth native-code implementations do may also be a good approach
for doing whatever one wants to do with an exec instruction. It is
probably faster than a half-hearted implementation of exec.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

On 6/28/2021 9:58 AM, Stefan Monnier wrote:
> Ivan Godard [2021-06-28 09:44:47] wrote:
>> On 6/28/2021 7:21 AM, Stefan Monnier wrote:
>>>>> One pretty simple solution to this kind of problem that has been used in
>>>>> the past is to start a timer/counter each time an instruction starts.
>>>>> If the count exceeds some large number, generate an exception.
>>>> That is a good idea to include, but I am a little stumped at the moment
>>>> about implementation.
>>> As a compiler/proglang guy, the one thing that stumps me instead here is
>>> "why?".
>>> Why would you want, or when/where would you need something like an
>>> "exec" opcode? It seems to me like a "solution" in search of a problem.
>>> Stefan
>> An exec is a very cheap special-case function call for very short functions.
>
> What makes it so "very cheap"er than a function call using normal
> instructions

It reduces the "overhead" of the function call by half. One instruction
(the EXC) versus two (the Call and the Return).

> and why/when would I need it?

You never "need" it, as there are other, albeit more costly, ways to
accomplish the same thing, but it is sometimes useful.

--
- Stephen Fuld
(e-mail address disguised to prevent spam)

>> What makes it so "very cheap"er than a function call using normal
>> instructions
> It reduces the "overhead" of the function call by half. One instruction
> (the EXC) versus two (the Call and the Return).

I don't think you can count it quite this way except maybe for
naive implementations, since "jump&link" and "ret" are typically both
"performed" by the branch prediction (and then later actually executed,
admittedly, but this should usually use an otherwise unused execution
unit so it's quite cheap).

Also those gains can easily be dwarfed by the potential difficulty to
keep the fetch unit fed when encountering an EXEC (i.e adjusting the
branch prediction to do something useful).

>> and why/when would I need it?
> You never "need" it, as there are other, albeit more costly, ways to
> accomplish the same thing, but it is sometimes useful.

The question is what are real cases where the presumably lower cost
can/could be used to get a measurably higher performance than using the
usual implementation&optimization strategies?

Stefan

On Monday, June 28, 2021 at 7:31:13 PM UTC-5, Stefan Monnier wrote:
> >> What makes it so "very cheap"er than a function call using normal
> >> instructions
> > It reduces the "overhead" of the function call by half. One instruction
> > (the EXC) versus two (the Call and the Return).
> I don't think you can count it quite this way except maybe for
> naive implementations, since "jump&link" and "ret" are typically both
> "performed" by the branch prediction (and then later actually executed,
> admittedly, but this should usually use an otherwise unused execution
> unit so it's quite cheap).
>
> Also those gains can easily be dwarfed by the potential difficulty to
> keep the fetch unit fed when encountering an EXEC (i.e adjusting the
> branch prediction to do something useful).
> >> and why/when would I need it?
> > You never "need" it, as there are other, albeit more costly, ways to
> > accomplish the same thing, but it is sometimes useful.
<
> The question is what are real cases where the presumably lower cost
> can/could be used to get a measurably higher performance than using the
> usual implementation&optimization strategies?
<
What High Level Languages allow one to pass code to a subroutine that
is not wrapped up in a subroutine ?
>
>
> Stefan

On Monday, June 28, 2021 at 8:40:39 PM UTC-4, MitchAlsup wrote:
> On Monday, June 28, 2021 at 7:31:13 PM UTC-5, Stefan Monnier wrote:
> > >> What makes it so "very cheap"er than a function call using normal
> > >> instructions
> > > It reduces the "overhead" of the function call by half. One instruction
> > > (the EXC) versus two (the Call and the Return).
> > I don't think you can count it quite this way except maybe for
> > naive implementations, since "jump&link" and "ret" are typically both
> > "performed" by the branch prediction (and then later actually executed,
> > admittedly, but this should usually use an otherwise unused execution
> > unit so it's quite cheap).
> >
> > Also those gains can easily be dwarfed by the potential difficulty to
> > keep the fetch unit fed when encountering an EXEC (i.e adjusting the
> > branch prediction to do something useful).
> > >> and why/when would I need it?
> > > You never "need" it, as there are other, albeit more costly, ways to
> > > accomplish the same thing, but it is sometimes useful.
> <
> > The question is what are real cases where the presumably lower cost
> > can/could be used to get a measurably higher performance than using the
> > usual implementation&optimization strategies?
> <
> What High Level Languages allow one to pass code to a subroutine that
> is not wrapped up in a subroutine ?
> >
> >
> > Stefan

Suppose there is a text search driven by user input. The first time in the user wants to find all letters < ‘a’ so a set less than ‘a’ instruction is passed in a register to the text search function. The next time in the user want to search for letters greater than ‘g’. So a greater than ‘g’ instruction is passed in a register to the text search function. In the text search function all it does is ‘exec Rn’ where Rn is the register containing the instruction. Without an exec instruction either self modifying code (JIT) must be used to get the same performance or a switch statement with an option set by the user passed in. The switch statement because it is branches is several times slower than exec. It may not make a difference in many programs, but sometimes if the code is called millions of times for instance drawing graphics on-screen it can make a difference.

EXEC is a challenge to implement in a classic pipelined processor, but in a processor using an out-of-order instruction queue it is a bit easier to do.. EXEC does not really affect the branch logic. It is not actually doing a fast subroutine call / return. It is just populating the instruction register field with a value from a register, so there is a double decode. To get the double decode in a classic pipelined processor the easiest approach may be to perform a hidden branch back to the same instruction after feeding a pipeline IR register with the value from a register.
After the first decode it is treated as an ordinary instruction which may or may not be a branch instruction. There are ways to avoid the double decode, but it increases the size of the execute logic.

On Monday, June 28, 2021 at 11:18:07 PM UTC-4, robf...@gmail.com wrote:
> On Monday, June 28, 2021 at 8:40:39 PM UTC-4, MitchAlsup wrote:
> > On Monday, June 28, 2021 at 7:31:13 PM UTC-5, Stefan Monnier wrote:
> > > >> What makes it so "very cheap"er than a function call using normal
> > > >> instructions
> > > > It reduces the "overhead" of the function call by half. One instruction
> > > > (the EXC) versus two (the Call and the Return).
> > > I don't think you can count it quite this way except maybe for
> > > naive implementations, since "jump&link" and "ret" are typically both
> > > "performed" by the branch prediction (and then later actually executed,
> > > admittedly, but this should usually use an otherwise unused execution
> > > unit so it's quite cheap).
> > >
> > > Also those gains can easily be dwarfed by the potential difficulty to
> > > keep the fetch unit fed when encountering an EXEC (i.e adjusting the
> > > branch prediction to do something useful).
> > > >> and why/when would I need it?
> > > > You never "need" it, as there are other, albeit more costly, ways to
> > > > accomplish the same thing, but it is sometimes useful.
> > <
> > > The question is what are real cases where the presumably lower cost
> > > can/could be used to get a measurably higher performance than using the
> > > usual implementation&optimization strategies?
> > <
> > What High Level Languages allow one to pass code to a subroutine that
> > is not wrapped up in a subroutine ?
> > >
> > >
> > > Stefan
> Suppose there is a text search driven by user input. The first time in the user wants to find all letters < ‘a’ so a set less than ‘a’ instruction is passed in a register to the text search function. The next time in the user want to search for letters greater than ‘g’. So a greater than ‘g’ instruction is passed in a register to the text search function. In the text search function all it does is ‘exec Rn’ where Rn is the register containing the instruction. Without an exec instruction either self modifying code (JIT) must be used to get the same performance or a switch statement with an option set by the user passed in. The switch statement because it is branches is several times slower than exec. It may not make a difference in many programs, but sometimes if the code is called millions of times for instance drawing graphics on-screen it can make a difference.
>
> EXEC is a challenge to implement in a classic pipelined processor, but in a processor using an out-of-order instruction queue it is a bit easier to do. EXEC does not really affect the branch logic. It is not actually doing a fast subroutine call / return. It is just populating the instruction register field with a value from a register, so there is a double decode. To get the double decode in a classic pipelined processor the easiest approach may be to perform a hidden branch back to the same instruction after feeding a pipeline IR register with the value from a register.
> After the first decode it is treated as an ordinary instruction which may or may not be a branch instruction. There are ways to avoid the double decode, but it increases the size of the execute logic.

One issue with EXEC is code readability. It makes code potentially difficult to understand. If a series of exec statements is written was is the code doing?

> Suppose there is a text search driven by user input. The first time in the
> user wants to find all letters < ‘a’ so a set less than ‘a’ instruction is
> passed in a register to the text search function.

And in which application is such a search performance critical enough
that the application doesn't generate a DFA or something similar?

> the instruction. Without an exec instruction either self modifying code
> (JIT) must be used to get the same performance or a switch statement with an
> option set by the user passed in.

AFAIK for text search, it's pretty easy to setup a table-driven function
that works efficiently enough, with very predictable branches.
What applications do you have in mind where that approach is not fast enough?

> The switch statement because it is branches is several times slower
> than exec.

I think this presumes quite pessimistic performance of the branch
prediction of the switch and unrealistically good performance of the
branch prediction of the EXEC.

> It may not make a difference in many programs, but sometimes if the
> code is called millions of times for instance drawing graphics
> on-screen it can make a difference.

If it's called that many times, even a slow JIT-generation
(e.g. calling a plain old compiler) will pay for itself and can then
outperform your EXEC, e.g. by inlining code into the loop.

> EXEC is a challenge to implement in a classic pipelined processor, but in
> a processor using an out-of-order instruction queue it is a bit easier to
> do. EXEC does not really affect the branch logic.

How can it not? At the time we fetch the EXEC instruction we don't know
yet what will be the content of the register when that instruction will
be executed (there are probably a few hundred instructions in flight
already several of which will likely affect that register's content),
yet we already need to decide what will be the next instruction to push
into the pipeline.

Just as for branches, you need to *predict* the code that will be
executed next, the only difference is that it's not at an address.
I guess if you use a BTB that holds the actual code at the target rather
than the address of the target, then EXEC is no worse than an indirect
branch but it's probably not noticeably faster either.

> It is just populating the instruction register field with a value from
> a register, so there is a double decode.

The double decode is the least of your problems, I think.

Stefan

robf...@gmail.com wrote:
>
> EXEC is a challenge to implement in a classic pipelined processor, but in a processor using an out-of-order instruction queue it is a bit easier to do.. EXEC does not really affect the branch logic. It is not actually doing a fast subroutine call / return. It is just populating the instruction register field with a value from a register, so there is a double decode. To get the double decode in a classic pipelined processor the easiest approach may be to perform a hidden branch back to the same instruction after feeding a pipeline IR register with the value from a register.
> After the first decode it is treated as an ordinary instruction which may or may not be a branch instruction. There are ways to avoid the double decode, but it increases the size of the execute logic.

Decode has to have a way to stall when it encounters things like "JMP reg"
and it does not know what reg value is. Decode passes the jmp uOp along,
sets a DecodeStall flag, which signals back to fetch, and stops looking
at the instruction buffer. However the Fetch unit may
continue to use the fetch_PC to fill the prefetch buffers.
Note that the fetch_PC is pointing to the next instruction after JMP.

The same decode-stalls-fetch mechanism can be used for single-step,
where Decode emits a single uOp is marked as single-step and stalls itself.
When the uOp reaches Retire, it sees it is marked as single step
and resets the DecodeStall flag.

That same stall mechanism can be used for EXEC. Decode sees EXEC and
passes its uOp along and stalls itself. Eventually EXEC reaches
register read, gets the instruction value, and the execute unit
writes back the value into the instruction buffer.
The instruction buffer write also sets a buffer flag "IsExec".

The instruction buffer and IsExec flag feed into Decode.
If the instruction is EXEC and the IsExec flag is set,
then it is an EXEC to an EXEC instruction so it
triggers an illegal instruction trap.
Otherwise it decodes the instruction as normal.
In any case it resets the IsExec and DecodeStall flags.

Resetting the DecodeStall flag enables fetch to pass the next
sequential instruction in the instruction buffer.

If there is a mispredicted branch then the pipeline gets flushed
and the DecodeStall and IsExec flags are reset.

Stefan Monnier <monnier@iro.umontreal.ca> schrieb:

> The question is what are real cases where the presumably lower cost
> can/could be used to get a measurably higher performance than using the
> usual implementation&optimization strategies?

If you did not know the integral of cos(), you could pass cos()
to an integration routine if you had it as a machine instruction
as on My 66000.

However, the need to numerically integrate cos() should be
pretty small.

On 2021-06-29, Stefan Monnier wrote:
>>> and why/when would I need it?
>> You never "need" it, as there are other, albeit more costly, ways to
>> accomplish the same thing, but it is sometimes useful.
>
> The question is what are real cases where the presumably lower cost
> can/could be used to get a measurably higher performance than using the
> usual implementation&optimization strategies?

In my experience the better option for some of the use cases that I see
mentioned (e.g. making adaptations of a highly optimized core routine)
is to use JIT. For instance, see LLVMpipe [1] in Mesa that generates
optimized software rasterization code on-the-fly.

/Marcus

[1] https://docs.mesa3d.org/drivers/llvmpipe.html

> In my experience the better option for some of the use cases that I see
> mentioned (e.g. making adaptations of a highly optimized core routine)
> is to use JIT. For instance, see LLVMpipe [1] in Mesa that generates
> optimized software rasterization code on-the-fly.
>
> /Marcus
There is compute time overhead with JIT. With EXEC it is just a loading a register with a value.

Torturing the topic a little bit.

The fast way of supporting EXEC increases the size of the core by about 15%, just for the one instruction; requiring the IR to act like another register and be part of the bypass network. The slow way of supporting EXEC does not increase the size of the core significantly, but may take EXEC a couple of more cycles to execute which pretty much negates its usefulness. The slow way is to have EXEC execute like any other instruction placing the operand on the result bus, then copy the result to the IR, reset several flags, and wait for it to decode and execute again. The work-around for having special logic to detect an EXEC of an EXEC is the watchdog timer on the queue.
Found another feature of EXEC that is interesting. Potentially wider instructions can be used because the value is coming from a register which is 64-bits wide. So, 64-bit instructions could be used with EXEC. It may be one way to execute an instruction requiring four read source ports for instance – too wide for the regular format. Having an instruction in a register means one can also perform calculations on it. For instance incrementing the register fields. If there are a lot of registers to save / restored an EXEC instruction in a loop could do the trick. I will not mention my other favorite instruction ATNI - add to next instruction.

I had the core treating EXEC as if it were an ordinary ALU op, not a branch.. Predicted as if sequential instructions follow with ensuing consequences if it turns out to be a flow control op. That would make it horrendously slow if it turns out to be a branch, but why would one EXEC a branch anyway?

Robert

Stefan Monnier wrote:
>
>> It is just populating the instruction register field with a value from
>> a register, so there is a double decode.
>
> The double decode is the least of your problems, I think.

Especially since that's the instructions' raison d'etre.

The performance cost is the pipeline stall between
"EXEC reg" decode and when the register value is available
to forward back to Decode input instruction buffer.

If a branch predictor can predict that this 32-bit PC address
is next after that instruction PC, then a similar mechanism
could predict the contents of the "EXEC reg" register value
and provide it early to the Decoder.
However as with "JMP reg" the predicted register value
must later be checked against the actual register value,
with a mis-match triggering a mispredict rollback.

Since EXEC is intended to execute instructions that could
not have been predicted in advance, it is unlikely that an
EXEC predictor would be much help.
If something was intended for high performance,
you probably wouldn't be doing EXEC's in the first place.

MitchAlsup <MitchAlsup@aol.com> writes:
>What High Level Languages allow one to pass code to a subroutine that
>is not wrapped up in a subroutine ?

Forth.

But that's the wrong question. Architectures have a number of
features that are not directly reflected in high-level languages,
e.g., the carry flag (and Intel has added the ADX extension because
the existing carry flag was not enough).

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

On Tuesday, June 29, 2021 at 9:58:54 AM UTC-4, Anton Ertl wrote:
> MitchAlsup <Mitch...@aol.com> writes:
> >What High Level Languages allow one to pass code to a subroutine that
> >is not wrapped up in a subroutine ?
> Forth.
>
> But that's the wrong question. Architectures have a number of
> features that are not directly reflected in high-level languages,
> e.g., the carry flag (and Intel has added the ADX extension because
> the existing carry flag was not enough).
> - anton
> --
> 'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
> Mitch Alsup, <c17fcd89-f024-40e7...@googlegroups.com>

I believe also IIRC the Clipper DBASE3/4 compiler also allows code to pass to a subroutine.

Appreciating that EXEC is not high-performance instruction I am still tempted to include it, as the way it is implemented is not high cost and I have transistors to burn. XOR is not a very useful instruction either, but many machines include it. EXEC may allow 64-bit instructions to execute in a kludgy manner.
Since EXEC uses a 2R instruction format it could conditionally execute based on the value in a second register. Could allow predicated execution of any instruction. Getting a vector exec turns out not to have additional cost. It may be an idea to have a vector exec abort instruction. Vector, execute is interesting because it could be made dependent on a mask register setting. Different combinations of instructions could be executed based on the mask value.

"robf...@gmail.com" <robfi680@gmail.com> writes:
>Suppose there is a text search driven by user input. The first time in the =
>user wants to find all letters < =E2=80=98a=E2=80=99 so a set less than =E2=
>=80=98a=E2=80=99 instruction is passed in a register to the text search fun=
>ction. The next time in the user want to search for letters greater than =
>=E2=80=98g=E2=80=99. So a greater than =E2=80=98g=E2=80=99 instruction is p=
>assed in a register to the text search function. In the text search functio=
>n all it does is =E2=80=98exec Rn=E2=80=99 where Rn is the register contain=
>ing the instruction. Without an exec instruction either self modifying code=
> (JIT) must be used to get the same performance or a switch statement with =
>an option set by the user passed in.

The classic approach is to pass the address of a subroutine; that
could contain

slt r1,r1,r2
ret

or

slt r1,r2,r1
ret

>The switch statement because it is bra=
>nches is several times slower than exec.

The branches are predicted and may cost very little. But the indirect
call tends to cost even less.

>EXEC is a challenge to implement in a classic pipelined processor, but in a=
> processor using an out-of-order instruction queue it is a bit easier to do=
>.

On a OoO CPU it is a lot harder. You need to feed data from the
execution unit back into the front end. It introduces arbitrary
source and destination registers, so on front ends with a register
renamer the front end cannot proceed past the exec until the data is
here. I expect that the value-passing style of OoO engine also has
its difficulties with inserting arbitrary register reads and writes,
and possibly memory reads and writes somewhere in the middle of the
OoO part of the engine.

I think the fastest way to implement exec on both kinds of OoO CPUs is
like what we do for branches (the other place where we need to feed
back from the OoO part to the front end): have a predictor, and check
at commit whether the prediction was correct. If it was not, throw
away everything after the exec, change the predicted instruction, and
start again from the exec.

But does it pay to have exec and yet another predictor, or is it
better to invest the effort in faster indirect call and return (e.g.,
a larger indirect branch predictor)?

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

"robf...@gmail.com" <robfi680@gmail.com> writes:
>That would make it horrendously sl=
>ow if it turns out to be a branch, but why would one EXEC a branch anyway?

You want to pass code that consists of more instructions than you can
pass directly to EXEC, so you pass a call to the instruction sequence
(96% of the uses of EXECUTE in Forth).

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

> Decode has to have a way to stall when it encounters things like "JMP reg"
> and it does not know what reg value is.

No, AFAIK it doesn't.
Instead it uses a BTB to predict the destination of the jump, otherwise
such indirect jumps would be much too slow.

Stefan

> There is compute time overhead with JIT.

But if it's executed enough times, this overhead is lost in the noise.
And if it's not executed enough times, then it's usually not
performance-critical.

Also most of the "overhead" of JIT is usually in the time to generate
the code (and that time would be the same for EXEC), rather than in the
synchronization with the I$/fetch/decode.

Stefan

>>That would make it horrendously sl=
>>ow if it turns out to be a branch, but why would one EXEC a branch anyway?
> You want to pass code that consists of more instructions than you can
> pass directly to EXEC, so you pass a call to the instruction sequence
> (96% of the uses of EXECUTE in Forth).

That's just an indirect function call (i.e. "JAL reg"), no need for an
EXEC instruction in the CPU for that.

Stefan

Stefan Monnier wrote:
>> Decode has to have a way to stall when it encounters things like "JMP reg"
>> and it does not know what reg value is.
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

> No, AFAIK it doesn't.
> Instead it uses a BTB to predict the destination of the jump, otherwise
> such indirect jumps would be much too slow.
>
>
> Stefan

The predictor MAY supply such a value, which MAY be correct.
However the design must deal with the possibility that the predictor
responds with "no hit", or "hit" but provides the wrong value.
Hit with the correct value is just gravy.

On Monday, June 28, 2021 at 10:18:07 PM UTC-5, robf...@gmail.com wrote:
> On Monday, June 28, 2021 at 8:40:39 PM UTC-4, MitchAlsup wrote:
> > On Monday, June 28, 2021 at 7:31:13 PM UTC-5, Stefan Monnier wrote:
> > > >> What makes it so "very cheap"er than a function call using normal
> > > >> instructions
> > > > It reduces the "overhead" of the function call by half. One instruction
> > > > (the EXC) versus two (the Call and the Return).
> > > I don't think you can count it quite this way except maybe for
> > > naive implementations, since "jump&link" and "ret" are typically both
> > > "performed" by the branch prediction (and then later actually executed,
> > > admittedly, but this should usually use an otherwise unused execution
> > > unit so it's quite cheap).
> > >
> > > Also those gains can easily be dwarfed by the potential difficulty to
> > > keep the fetch unit fed when encountering an EXEC (i.e adjusting the
> > > branch prediction to do something useful).
> > > >> and why/when would I need it?
> > > > You never "need" it, as there are other, albeit more costly, ways to
> > > > accomplish the same thing, but it is sometimes useful.
> > <
> > > The question is what are real cases where the presumably lower cost
> > > can/could be used to get a measurably higher performance than using the
> > > usual implementation&optimization strategies?
> > <
> > What High Level Languages allow one to pass code to a subroutine that
> > is not wrapped up in a subroutine ?
> > >
> > >
> > > Stefan
> Suppose there is a text search driven by user input. The first time in the user wants to find all letters < ‘a’ so a set less than ‘a’ instruction is passed in a register to the text search function. The next time in the user want to search for letters greater than ‘g’. So a greater than ‘g’ instruction is passed in a register to the text search function.
<
Now imagine the case where the caller passes the "clear all registers" instruction..............
<
>In the text search function all it does is ‘exec Rn’ where Rn is the register containing the instruction. Without an exec instruction either self modifying code (JIT) must be used to get the same performance or a switch statement with an option set by the user passed in. The switch statement because it is branches is several times slower than exec. It may not make a difference in many programs, but sometimes if the code is called millions of times for instance drawing graphics on-screen it can make a difference.
>
> EXEC is a challenge to implement in a classic pipelined processor, but in a processor using an out-of-order instruction queue it is a bit easier to do.
<
In OoO it is even HARDER to do. imagine that the instruction to be fetched takes a data cache miss
whose address is dependent on a integer DIVIDE instruction. You don't have the instruction for 50-70 cycles, so you basically sit there issuing nothing until the instruction to EXC shows up.
<
>EXEC does not really affect the branch logic. It is not actually doing a fast subroutine call / return. It is just populating the instruction register field with a value from a register, so there is a double decode. To get the double decode in a classic pipelined processor the easiest approach may be to perform a hidden branch back to the same instruction after feeding a pipeline IR register with the value from a register.
> After the first decode it is treated as an ordinary instruction which may or may not be a branch instruction. There are ways to avoid the double decode, but it increases the size of the execute logic.

On Tuesday, June 29, 2021 at 9:20:11 AM UTC-5, robf...@gmail.com wrote:
> On Tuesday, June 29, 2021 at 9:58:54 AM UTC-4, Anton Ertl wrote:
> > MitchAlsup <Mitch...@aol.com> writes:
> > >What High Level Languages allow one to pass code to a subroutine that
> > >is not wrapped up in a subroutine ?
> > Forth.
> >
> > But that's the wrong question. Architectures have a number of
> > features that are not directly reflected in high-level languages,
> > e.g., the carry flag (and Intel has added the ADX extension because
> > the existing carry flag was not enough).
> > - anton
> > --
> > 'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
> > Mitch Alsup, <c17fcd89-f024-40e7...@googlegroups.com>
> I believe also IIRC the Clipper DBASE3/4 compiler also allows code to pass to a subroutine.
>
> Appreciating that EXEC is not high-performance instruction I am still tempted to include it, as the way it is implemented is not high cost and I have transistors to burn. XOR is not a very useful instruction either,
<
On the contrary, it is very useful, and exceedingly inexpensive to implement.
<
if( state & SOME_STATE )
state ^= SOME_STATE | SOME_NEXT_STATE;
<
>but many machines include it. EXEC may allow 64-bit instructions to execute in a kludgy manner.
<
What is the semantic if you wanted to EXEC a register and the instruction needed 96-bits,
128-bits, or 160-bits ??
<
> Since EXEC uses a 2R instruction format it could conditionally execute based on the value in a second register. Could allow predicated execution of any instruction.
<
There are much better and safer means to predicate an instruction--which your ISA should
already have.
<
>Getting a vector exec turns out not to have additional cost. It may be an idea to have a vector exec abort instruction. Vector, execute is interesting because it could be made dependent on a mask register setting. Different combinations of instructions could be executed based on the mask value.

Stefan Monnier <monnier@iro.umontreal.ca> writes:
>>>That would make it horrendously sl=
>>>ow if it turns out to be a branch, but why would one EXEC a branch anyway?
>> You want to pass code that consists of more instructions than you can
>> pass directly to EXEC, so you pass a call to the instruction sequence
>> (96% of the uses of EXECUTE in Forth).
>
>That's just an indirect function call (i.e. "JAL reg"), no need for an
>EXEC instruction in the CPU for that.

If you only want to do indirect calls, yes. If you also want to be
able to execute other instructions, you need EXEC. Or you need to
store these other instructions in memory followed by a return (and the
usual cache synchronization dance).

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

I do not seem to be able to follow the example. Why cannot other instructions decode and execute during that time? It is just a load operation taking place to load the instruction. Things would proceed as per a normal load. It may be many more cycles / instructions before the instruction EXEC is executed. Once EXEC is decoded / issued it is just a matter of waiting for register values.

>What is the semantic if you wanted to EXEC a register and the instruction needed 96-bits,
>128-bits, or 160-bits ??
Instructions are limited to 36-bits in this case. I think using more registers to contain instruction modifiers will work.

I think it is execute of the one particular instruction that must stall, not decode. On my machine other instructions can be decoded or execute. This is relied on to hide the decode time in many cases.
If the registers are valid before the EXEC is processed, then it will be fast. Hmm, it just occurred to me that I put a four-cycle lockout in the execute scheduler to prevent it selecting the same queue slot until there was time to mark the instruction as out. So, EXEC would take five or more cycles to execute. Of course, it is mostly hidden time.

It is very few LOC to implement EXEC. The biggest piece is probably the mux on the IR. I am waiting to see how much it impacts design size, but synth keeps crashing on me.
I think all that needs to be done is:
if (robo.exec) begin
rob[robo.rid].ir <= robo.res.val[35:0]; // comes from register arg A
rob[robo.rid].dec <= FALSE;
rob[robo.rid].out <= FALSE;
rob[robo.rid].cmt <= FALSE;
rob[robo.rid].cmt2 <= FALSE;
rob[robo.rid].vcmt <= FALSE;
end