Indirect branches are typically divided into single-target branches (at least within a local execution context sufficient to provide accurate prediction and multiple-target branches. The predictor for the former is best indexed by a hash of the address of branch instruction, while for the multiple-target branches including some history information for the predictor index is desirable.

This is similar to the problem of indexing a TLB for multiple page sizes and so might be addressed by André Seznec's overlaid skewed associativity (my term — Seznec did not provide a name distinguishing from separate bank skewed associativity) technique ("Concurrent Support of Multiple Page Sizes On a Skewed Associative TLB", 2003). This would have the same advantage of sharing capacity among branch types. (In principle, direct branches might also be included as a special case of single-target branches.)

By preferring a more specific prediction, a common case target with one or more specific exceptions might be accurately predicted.

This is not fundamentally different from using separate target predictors except that the capacity is shared (at the cost of conflicts) — very analogous to the difference between André Seznec's TLB and using per-page-size TLBs. Using hash-rehash/multiple probes is another alternative for capacity sharing; multiple probes could also be applied with overlaid skewed associativity. A later probe could use later available information; while one bit of later arriving information might be used by doubling the read width and selecting, the cost of that technique increases exponentially.

If the storage has non-uniform access latency, there may be optimization opportunities in the indexing functions and their mappings to different-latency locations, perhaps exploiting different timings of information availability or accuracy/criticality of prediction. (Non-uniform latency encourages more complex placement, migration, and replacement choices.)

On Saturday, June 26, 2021 at 1:26:31 PM UTC-5, Paul A. Clayton wrote:
> Indirect branches are typically divided into single-target branches (at least within a local execution context sufficient to provide accurate prediction and multiple-target branches. The predictor for the former is best indexed by a hash of the address of branch instruction, while for the multiple-target branches including some history information for the predictor index is desirable.
<
There are five cases: Switches, Returns, Method calls, Tabulated Calls, and Longjump.
<
Switches tend to be unpredictable much of the time.
Returns are easily highly predictable
Method calls tend to use few methods more than others
Tabulated calls tend to be indexed tables of entry points
And longjump is a category all by itself.
<
If your ISA is supporting indirect branches within a subroutine, you are likely to remain
"on your own" as far as branch prediction is concerned.
<
Dense Switches, Method Calls, and Tabulated Calls are directly supported in My 66000 ISA
and do not use Indirect Jump or Indirect Call.
<
Returns are best supported by a call-return stack predictor that can self repair when
a mispredicted branch leads to a return which must then be undone when the branch
is recovered (so the return when it does happen returns to the proper place..)
>
Switches are decomposed into dense areas and loose areas. Loose areas are
performed by a series of compares and branches, while dense areas are performed
by indexing through a table of branch target addresses. The Loose areas are adequately
supported by normal branch prediction, while the dense areas have in the past been
supported by the generalized indirect predictors.
<
A Tabulated Call is where a field of (say) an instruction is used to index a table of
worker functions that perform the required semantic of the (say) instruction. The
index into the table is the bit pattern of the field. Should there not be a defined
semantic for a particular bit pattern, the call is performed to the undefined handler.
<
A method call is similar to a tabulated call except the compiler is in charge of the
indexing of the table and of its contents.
>
> This is similar to the problem of indexing a TLB for multiple page sizes and so might be addressed by André Seznec's overlaid skewed associativity (my term — Seznec did not provide a name distinguishing from separate bank skewed associativity) technique ("Concurrent Support of Multiple Page Sizes On a Skewed Associative TLB", 2003). This would have the same advantage of sharing capacity among branch types. (In principle, direct branches might also be included as a special case of single-target branches.)
>
> By preferring a more specific prediction, a common case target with one or more specific exceptions might be accurately predicted.
<
I would say that by filtering out Method Calls, from Tabularized calls, from "indirect"
calls and jumps one improves the predictability of the well organized means from the
less well organized means.
>
> This is not fundamentally different from using separate target predictors except that the capacity is shared (at the cost of conflicts) — very analogous to the difference between André Seznec's TLB and using per-page-size TLBs. Using hash-rehash/multiple probes is another alternative for capacity sharing; multiple probes could also be applied with overlaid skewed associativity. A later probe could use later available information; while one bit of later arriving information might be used by doubling the read width and selecting, the cost of that technique increases exponentially.
>
> If the storage has non-uniform access latency, there may be optimization opportunities in the indexing functions and their mappings to different-latency locations, perhaps exploiting different timings of information availability or accuracy/criticality of prediction. (Non-uniform latency encourages more complex placement, migration, and replacement choices.)

Adding::

On Saturday, June 26, 2021 at 2:31:36 PM UTC-5, MitchAlsup wrote:
> On Saturday, June 26, 2021 at 1:26:31 PM UTC-5, Paul A. Clayton wrote:
> > Indirect branches are typically divided into single-target branches (at least within a local execution context sufficient to provide accurate prediction and multiple-target branches. The predictor for the former is best indexed by a hash of the address of branch instruction, while for the multiple-target branches including some history information for the predictor index is desirable.
> <
> There are five cases: Switches, Returns, Method calls, Tabulated Calls, and Longjump.
> <
> Switches tend to be unpredictable much of the time.
> Returns are easily highly predictable
> Method calls tend to use few methods more than others
> Tabulated calls tend to be indexed tables of entry points
> And longjump is a category all by itself.
> <
> If your ISA is supporting indirect branches within a subroutine, you are likely to remain
> "on your own" as far as branch prediction is concerned.
> <
> Dense Switches, Method Calls, and Tabulated Calls are directly supported in My 66000 ISA
> and do not use Indirect Jump or Indirect Call.
> <
> Returns are best supported by a call-return stack predictor that can self repair when
> a mispredicted branch leads to a return which must then be undone when the branch
> is recovered (so the return when it does happen returns to the proper place.)
> >
> Switches are decomposed into dense areas and loose areas. Loose areas are
> performed by a series of compares and branches, while dense areas are performed
> by indexing through a table of branch target addresses. The Loose areas are adequately
> supported by normal branch prediction, while the dense areas have in the past been
> supported by the generalized indirect predictors.
> <
> A Tabulated Call is where a field of (say) an instruction is used to index a table of
> worker functions that perform the required semantic of the (say) instruction. The
> index into the table is the bit pattern of the field. Should there not be a defined
> semantic for a particular bit pattern, the call is performed to the undefined handler.
> <
> A method call is similar to a tabulated call except the compiler is in charge of the
> indexing of the table and of its contents.
> >
> > This is similar to the problem of indexing a TLB for multiple page sizes and so might be addressed by André Seznec's overlaid skewed associativity (my term — Seznec did not provide a name distinguishing from separate bank skewed associativity) technique ("Concurrent Support of Multiple Page Sizes On a Skewed Associative TLB", 2003). This would have the same advantage of sharing capacity among branch types. (In principle, direct branches might also be included as a special case of single-target branches.)
<
I think the problem is more fundamental, let us postulate that you have a simulator for a processor.
This processor has an instruction set, and the instruction set has a few formats. One way to decode
this ISA is to take the major OpCode and index a table of format subroutines. These format subroutines
look at another (format specific) field and index another table of subroutines. There will be heavy use
of the first table, with the Major OpCode touching most of the (valid) decode indexes ever hundred
simulated instructions. The other format subroutines are used less often (on average) but with even
more sporadic use.
<
This puts the predictor in limbo--unless it can somehow guess the actual instruction stream being
processed. Thus, low prediction accuracy is expected. Lower than typical Switch prediction accuracy
while processing a parser done in YACC.
<
> >
> > By preferring a more specific prediction, a common case target with one or more specific exceptions might be accurately predicted.
> <
> I would say that by filtering out Method Calls, from Tabularized calls, from "indirect"
> calls and jumps one improves the predictability of the well organized means from the
> less well organized means.
> >
> > This is not fundamentally different from using separate target predictors except that the capacity is shared (at the cost of conflicts) — very analogous to the difference between André Seznec's TLB and using per-page-size TLBs. Using hash-rehash/multiple probes is another alternative for capacity sharing; multiple probes could also be applied with overlaid skewed associativity. A later probe could use later available information; while one bit of later arriving information might be used by doubling the read width and selecting, the cost of that technique increases exponentially.
> >
> > If the storage has non-uniform access latency, there may be optimization opportunities in the indexing functions and their mappings to different-latency locations, perhaps exploiting different timings of information availability or accuracy/criticality of prediction. (Non-uniform latency encourages more complex placement, migration, and replacement choices.)

MitchAlsup wrote:
> I think the problem is more fundamental, let us postulate that you have a simulator for a processor.
> This processor has an instruction set, and the instruction set has a few formats. One way to decode
> this ISA is to take the major OpCode and index a table of format subroutines. These format subroutines
> look at another (format specific) field and index another table of subroutines. There will be heavy use
> of the first table, with the Major OpCode touching most of the (valid) decode indexes ever hundred
> simulated instructions. The other format subroutines are used less often (on average) but with even
> more sporadic use.
> <
> This puts the predictor in limbo--unless it can somehow guess the actual instruction stream being
> processed. Thus, low prediction accuracy is expected. Lower than typical Switch prediction accuracy
> while processing a parser done in YACC.

This is why I always try to see if it makes sense to convert those code
switches to data switches, i.e. the first opcode table is used to lookup
the fields needed for the second level, which can then proceed at once.

This sometimes means that the second-level entry have to say "Whoa, that
was too far, backtrack now", but if these fixups are rare enough, it
might still be faster.

In the extreme case there are no exceptions, so everything just becomes
a long data-dependent graph with no (code) branching.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

MitchAlsup wrote:
> On Saturday, June 26, 2021 at 2:31:36 PM UTC-5, MitchAlsup wrote:
>> <
>> A Tabulated Call is where a field of (say) an instruction is used to index a table of
>> worker functions that perform the required semantic of the (say) instruction. The
>> index into the table is the bit pattern of the field. Should there not be a defined
>> semantic for a particular bit pattern, the call is performed to the undefined handler.
>> <
> I think the problem is more fundamental, let us postulate that you have a simulator for a processor.
> This processor has an instruction set, and the instruction set has a few formats. One way to decode
> this ISA is to take the major OpCode and index a table of format subroutines. These format subroutines
> look at another (format specific) field and index another table of subroutines. There will be heavy use
> of the first table, with the Major OpCode touching most of the (valid) decode indexes ever hundred
> simulated instructions. The other format subroutines are used less often (on average) but with even
> more sporadic use.
> <

By the way, this is how I believe the VAX 780 decoder worked.
Microcode can perform N-way branches and calls by jamming a value
into the low order bits of the uPC (micro-op program counter).

The root instruction sequence reads the first instruction byte.
The opcode byte is looked up in a table (a PLA) to get a uPC destination
address, which is then called (an N-way call).
That routine has a sequence of uOp calls to fetch operands.
The operand fetch routine reads the address mode byte, looks it up in
a table, and does an N-way call, to a routine to fetch the operand data.

The instruction sequence itself may not need to be different for
different operations as the opcode lookup can provide bits that
are routed directly to the ALU to control its operation.
All the instruction sequence has to do it tell the ALU to
"do the thing that the opcode bits say".

So a few microcode sequences can handle most of the simple arithmetic
and logic instructions, using N-way calls to handle the operands.

On Sunday, June 27, 2021 at 11:04:04 AM UTC-5, EricP wrote:
> MitchAlsup wrote:
> > On Saturday, June 26, 2021 at 2:31:36 PM UTC-5, MitchAlsup wrote:
> >> <
> >> A Tabulated Call is where a field of (say) an instruction is used to index a table of
> >> worker functions that perform the required semantic of the (say) instruction. The
> >> index into the table is the bit pattern of the field. Should there not be a defined
> >> semantic for a particular bit pattern, the call is performed to the undefined handler.
> >> <
> > I think the problem is more fundamental, let us postulate that you have a simulator for a processor.
> > This processor has an instruction set, and the instruction set has a few formats. One way to decode
> > this ISA is to take the major OpCode and index a table of format subroutines. These format subroutines
> > look at another (format specific) field and index another table of subroutines. There will be heavy use
> > of the first table, with the Major OpCode touching most of the (valid) decode indexes ever hundred
> > simulated instructions. The other format subroutines are used less often (on average) but with even
> > more sporadic use.
> > <
> By the way, this is how I believe the VAX 780 decoder worked.
<
So did PDP-11..........
<
> Microcode can perform N-way branches and calls by jamming a value
> into the low order bits of the uPC (micro-op program counter).
<
And this works because each microcode "word" contains its successor
address in µCode. So, you branch to an indexed entry point, do what was
specified there, and then end up in separate places as if the call was to
separate entry points
>
> The root instruction sequence reads the first instruction byte.
> The opcode byte is looked up in a table (a PLA) to get a uPC destination
> address, which is then called (an N-way call).
<
For the PDP-11, they got the instruction word and did a 8-way call to
address mode[0], then an 8-way call to address mode[1],...
<
For VAX, they did a 256-way call for the OpCode decode, the a series
of 16-way calls for each address mode.
<
> That routine has a sequence of uOp calls to fetch operands.
> The operand fetch routine reads the address mode byte, looks it up in
> a table, and does an N-way call, to a routine to fetch the operand data.
<
Where N=8 for PDP-11 and N=16 for VAX.
>
> The instruction sequence itself may not need to be different for
> different operations as the opcode lookup can provide bits that
> are routed directly to the ALU to control its operation.
> All the instruction sequence has to do it tell the ALU to
> "do the thing that the opcode bits say".
>
> So a few microcode sequences can handle most of the simple arithmetic
> and logic instructions, using N-way calls to handle the operands.
<
Which is why Maurice Wilkes was so keen of µCode.

MitchAlsup wrote:
> On Sunday, June 27, 2021 at 11:04:04 AM UTC-5, EricP wrote:
>>
>> So a few microcode sequences can handle most of the simple arithmetic
>> and logic instructions, using N-way calls to handle the operands.
> <
> Which is why Maurice Wilkes was so keen of µCode.

Ah... Sir Maurice Wilkes invented micro-programming in 1951.

The best way to design an automatic calculating machine, 1951
http://www.cs.princeton.edu/courses/archive/fall09/cos375/BestWay.pdf

EricP <ThatWouldBeTelling@thevillage.com> schrieb:
> MitchAlsup wrote:
>> On Sunday, June 27, 2021 at 11:04:04 AM UTC-5, EricP wrote:
>>>
>>> So a few microcode sequences can handle most of the simple arithmetic
>>> and logic instructions, using N-way calls to handle the operands.
>> <
>> Which is why Maurice Wilkes was so keen of µCode.
>
> Ah... Sir Maurice Wilkes invented micro-programming in 1951.

So he's to blame for shenanigans like Intel deciding that your
machine is too fast, and doing something about it?

https://travisdowns.github.io/blog/2021/06/17/rip-zero-opt.html

I love that headline... "Your CPU May Have Slowed Down on Wednesday".

On Sunday, June 27, 2021 at 2:14:23 PM UTC-5, Thomas Koenig wrote:
> EricP <ThatWould...@thevillage.com> schrieb:
> > MitchAlsup wrote:
> >> On Sunday, June 27, 2021 at 11:04:04 AM UTC-5, EricP wrote:
> >>>
> >>> So a few microcode sequences can handle most of the simple arithmetic
> >>> and logic instructions, using N-way calls to handle the operands.
> >> <
> >> Which is why Maurice Wilkes was so keen of µCode.
> >
> > Ah... Sir Maurice Wilkes invented micro-programming in 1951.
> So he's to blame for shenanigans like Intel deciding that your
> machine is too fast, and doing something about it?
>
> https://travisdowns.github.io/blog/2021/06/17/rip-zero-opt.html
>
> I love that headline... "Your CPU May Have Slowed Down on Wednesday".
<
One of the things that makes µCode so (ahem) useful is that one can add
a few "words" to the side of the µCode store and be able to alter the sequencer
and sequences after power on.
<
One can use this to patch µCode and avoid catastrophes or to create
catastrophes. Apparently Intel tries to do both.................

On Saturday, June 26, 2021 at 3:31:36 PM UTC-4, MitchAlsup wrote:
> On Saturday, June 26, 2021 at 1:26:31 PM UTC-5, Paul A. Clayton wrote:
>> Indirect branches are typically divided into single-target branches (at least
>> within a local execution context sufficient to provide accurate prediction
>> and multiple-target branches. The predictor for the former is best indexed
>> by a hash of the address of branch instruction, while for the multiple-target
>> branches including some history information for the predictor index is
>> desirable.
[snip interesting analysis]

> I would say that by filtering out Method Calls, from Tabularized calls, from "indirect"
> calls and jumps one improves the predictability of the well organized means from the
> less well organized means.

I think there may have been a miscommunication. The idea is not to
force all predictions to use the same indexing information (i.e., different
types of jumps would use different information), but to merge the
*storage*. As far as I know, the current best _practice_ is to use an
ordinary BTB for single-target instructions and a separate table indexed
with history information for the multiple-target instructions. My (minor)
idea is to merge these using Andé Seznec's overlaid skewed associativity
mechanism. (As I understand current practice, the indirect predictors do
not even use variable length (and variable selection) history despite TAGE
direction predictors doing so. I suspect this is, in part, because having
dedicated storage for different indexings can result in low utilization of
some storage. With overlaying, capacity is shared at the cost of sharing
some indexing information to guarantee lack of bank conflicts — infrequent
bank conflicts might be managed by reprobing, presumably with biasing
of probing priority.)

On Monday, June 28, 2021 at 10:19:06 AM UTC-5, Paul A. Clayton wrote:
> On Saturday, June 26, 2021 at 3:31:36 PM UTC-4, MitchAlsup wrote:
> > On Saturday, June 26, 2021 at 1:26:31 PM UTC-5, Paul A. Clayton wrote:
> >> Indirect branches are typically divided into single-target branches (at least
> >> within a local execution context sufficient to provide accurate prediction
> >> and multiple-target branches. The predictor for the former is best indexed
> >> by a hash of the address of branch instruction, while for the multiple-target
> >> branches including some history information for the predictor index is
> >> desirable.
> [snip interesting analysis]
> > I would say that by filtering out Method Calls, from Tabularized calls, from "indirect"
> > calls and jumps one improves the predictability of the well organized means from the
> > less well organized means.
<
> I think there may have been a miscommunication. The idea is not to
> force all predictions to use the same indexing information (i.e., different
> types of jumps would use different information), but to merge the
> *storage*.
<
Perhaps I did not get to my point:: if you can identify more different kinds
of "branching" it is more likely that each one has an optimal predictor than
all of then having a common optimal predictor.
<
> As far as I know, the current best _practice_ is to use an
> ordinary BTB for single-target instructions and a separate table indexed
> with history information for the multiple-target instructions. My (minor)
> idea is to merge these using Andé Seznec's overlaid skewed associativity
> mechanism. (As I understand current practice, the indirect predictors do
> not even use variable length (and variable selection) history despite TAGE
> direction predictors doing so. I suspect this is, in part, because having
> dedicated storage for different indexings can result in low utilization of
> some storage. With overlaying, capacity is shared at the cost of sharing
> some indexing information to guarantee lack of bank conflicts — infrequent
> bank conflicts might be managed by reprobing, presumably with biasing
> of probing priority.)

On 27/06/21 7:31 am, MitchAlsup wrote:

> There are five cases: Switches, Returns, Method calls, Tabulated Calls, and Longjump.
> <
> Switches tend to be unpredictable much of the time.
> Returns are easily highly predictable
> Method calls tend to use few methods more than others
> Tabulated calls tend to be indexed tables of entry points
> And longjump is a category all by itself.

Ummm, so no love for Call Return Tables?, wouldn't they go some way to
reducing the number of conditional instructions spent checking for error
return codes and having otherwise unneeded instructions situated right
after the original call.

On 6/28/2021 10:45 PM, Andy wrote:
> On 27/06/21 7:31 am, MitchAlsup wrote:
>
>> There are five cases: Switches, Returns, Method calls, Tabulated
>> Calls, and Longjump.
>> <
>> Switches tend to be unpredictable much of the time.
>> Returns are easily highly predictable
>> Method calls tend to use few methods more than others
>> Tabulated calls tend to be indexed tables of entry points
>> And longjump is a category all by itself.
>
> Ummm, so no love for Call Return Tables?, wouldn't they go some way to
> reducing the number of conditional instructions spent checking for error
> return codes and having otherwise unneeded instructions situated right
> after the original call.
>

A dedicated call-return table probably only really makes sense for
something like x86, which loads the return address from memory at the
same time as branching to it.

If you use a link register, or return via some other special register
(such as treating R1 as a secondary link register), then all one needs
to do is check is that this register hasn't been modified within the
pipeline, and if so use the value held in this register as the predicted
branch target.

In this case, typically one can reload the LR or "Secondary LR" several
cycles before its associated RTS or JMP. If one reloads the link
register before the others in a function epilog, then (typically) the
reloaded register will have left the pipeline before the CPU reaches the
return instruction.

Meanwhile, switch faces a problem that typically one calculates the
switch target immediately before branching to it. If one could somehow
do something like:
Calculate where the "switch()" will go;
Put some prior unrelated logic here;
Do the branch to the switch target.

Then "switch()" could potentially also be made predictable.

For small switch one might instead use linear probing or binary
subdivision or similar, in which case it is predictable if the
individual branches are predictable.

Say (number of case labels):
1-3: Linear Probe
4-11: Binary Subdivide
12-511 (and sufficiently dense): Branch Table
Else: Binary Subdivide (1)

*1: Binary subdivide happens until either it reaches the conditions for
a branch-table, or the number of targets is small enough that it falls
back to a linear probe.

....

On Monday, June 28, 2021 at 12:13:14 PM UTC-4, MitchAlsup wrote:
> On Monday, June 28, 2021 at 10:19:06 AM UTC-5, Paul A. Clayton wrote:
[snip]
>> I think there may have been a miscommunication. The idea
>> is not to force all predictions to use the same indexing
>> information (i.e., different types of jumps would use
>> different information), but to merge the *storage*.
>
> Perhaps I did not get to my point:: if you can identify
> more different kinds of "branching" it is more likely that
> each one has an optimal predictor than all of then having
> a common optimal predictor.

I tend to agree, though I feel the targets of direct,
single-target jumps and returns should be cached/memoized
rather than predicted. For returns, this introduces extra
tagging overhead and forces mispeculation fix-up to apply to
the cache. For direct jumps, this adds some tagging overhead
to the degree that the target cache has broader coverage
than the instruction cache (and any outer shared cache which
can compress instruction data by eliding targets cached in
the specialized target caches — just accepting redudant
storage may be easier, avoiding coherent retention of data
[dropping a target address would only be a performance
problem (and potential side channel) since the absence would
be recognized and the data would be in main memory).

(Such also implies predecoding to extract/calculate targets.
The variable storage requirements further adds complexity.)

Storing targets on the instruction side for jump-based
switch statements would allow the predictor to only store
an index into the instruction-side jump table rather than
an offset. It might also be possible to microarchitecturally
bypass proximate storage for rarely taken targets/offsets.
(Architecturally, if a collection of targets is known at
compile-time to be rarely taken, the standard cold code
optimization could be used.)

For C++-like virtual calls, if one does not have code
generation (or fix-up) across compilation units, one could
not use an inline table. Such would also presumably increase
the size of an executable text because each method will have
multiple call sites. (Direct calls have the same issue, of
course, and few suggest requiring tables so that an offset
is replaced with a smaller index.)

(I like the idea of link-time code generation, but such is
more complex and slower. Caching of compilation information
and invalidation at finer granularity than object file would
presumably reduce compile times, but such does not seem to
be commonly implemented and would add further complexity.)

If your statement, Mitch, was that one should not focus on
incremental improvements in this area but look closer at the
root of the problem, I can understand the connection with
my post, which merely incrementally (possibly) improved
common practice. Since it addressed common practice and
seemed kind of neat (and added a use for overlaid skewed
associativity: https://cs.stackexchange.com/q/108720/4577 )
I wanted to share it.

Control flow target encoding and placement does not seem to
be a solved problem. One would prefer to extract targets
that are rarely taken from the instruction fetch stream, but
retreiving even cool targets all the way from main memory
might cost more than is saved by extraction from the
instruction stream. (One intermediate between inline and
completely independent [especially data-side] target
retreival would be an offset into a local aligned storage
area. E.g., every 1 MiB code region might be enabled to
index storage directly below that region.)

With respect to setjump/longjump, such seems to be similar
to setting up an exception target and then taking an
exception. Caching such a target would not seem especially
difficult (though being per-thread — I think — when other
exception targets are typically(?) per 'process' would
increase tagging overhead). As with exceptions, I suspect
there is some way that threading support would integrate
with this, but as a non-programmer I am fairly clueless
about how such features are used.

On Monday, June 28, 2021 at 10:45:41 PM UTC-5, Bitter blue pill wrote:
> On 27/06/21 7:31 am, MitchAlsup wrote:
>
> > There are five cases: Switches, Returns, Method calls, Tabulated Calls, and Longjump.
> > <
> > Switches tend to be unpredictable much of the time.
> > Returns are easily highly predictable
> > Method calls tend to use few methods more than others
> > Tabulated calls tend to be indexed tables of entry points
> > And longjump is a category all by itself.
<
> Ummm, so no love for Call Return Tables?, wouldn't they go some way to
> reducing the number of conditional instructions spent checking for error
> return codes and having otherwise unneeded instructions situated right
> after the original call.
<
I am not sure I understand your 3 word phrase--can you give an example ?
<
I have seen a lot of code that does stuff like::
<
if( function( arg1, arg1, arg3 ) == SUCCESS )
if( next_function( arg4, arg5 ) == SUCCESS )
return SUCCESS;
return FAILURE;
<
And I would expect the code at the return point have a CMP-BC or BC0
depending if SUCCESS was == 0 or not.

On Tuesday, June 29, 2021 at 11:04:03 AM UTC-5, BGB wrote:
> On 6/28/2021 10:45 PM, Andy wrote:
> > On 27/06/21 7:31 am, MitchAlsup wrote:
> >
> >> There are five cases: Switches, Returns, Method calls, Tabulated
> >> Calls, and Longjump.
> >> <
> >> Switches tend to be unpredictable much of the time.
> >> Returns are easily highly predictable
> >> Method calls tend to use few methods more than others
> >> Tabulated calls tend to be indexed tables of entry points
> >> And longjump is a category all by itself.
> >
> > Ummm, so no love for Call Return Tables?, wouldn't they go some way to
> > reducing the number of conditional instructions spent checking for error
> > return codes and having otherwise unneeded instructions situated right
> > after the original call.
> >
> A dedicated call-return table probably only really makes sense for
> something like x86, which loads the return address from memory at the
> same time as branching to it.
>
> If you use a link register, or return via some other special register
> (such as treating R1 as a secondary link register), then all one needs
> to do is check is that this register hasn't been modified within the
> pipeline, and if so use the value held in this register as the predicted
> branch target.
>
> In this case, typically one can reload the LR or "Secondary LR" several
> cycles before its associated RTS or JMP. If one reloads the link
> register before the others in a function epilog, then (typically) the
> reloaded register will have left the pipeline before the CPU reaches the
> return instruction.
>
>
> Meanwhile, switch faces a problem that typically one calculates the
> switch target immediately before branching to it. If one could somehow
> do something like:
> Calculate where the "switch()" will go;
> Put some prior unrelated logic here;
> Do the branch to the switch target.
>
> Then "switch()" could potentially also be made predictable.
>
> For small switch one might instead use linear probing or binary
> subdivision or similar, in which case it is predictable if the
> individual branches are predictable.
>
> Say (number of case labels):
> 1-3: Linear Probe
> 4-11: Binary Subdivide
> 12-511 (and sufficiently dense): Branch Table
<
My 66000 ISA directly supports tabularized dense switch regions. The
instruction checks the (now zero relative) index, and fetches an offset
to the switch case label, checks the index for being in bounds, and
transfers control to the case label or the default label (depending).
This is efficient enough to cover the dense 4-11 case, too.
<
> Else: Binary Subdivide (1)
>
> *1: Binary subdivide happens until either it reaches the conditions for
> a branch-table, or the number of targets is small enough that it falls
> back to a linear probe.
>
> ...

On Tuesday, June 29, 2021 at 11:15:39 AM UTC-5, Paul A. Clayton wrote:
> On Monday, June 28, 2021 at 12:13:14 PM UTC-4, MitchAlsup wrote:
> > On Monday, June 28, 2021 at 10:19:06 AM UTC-5, Paul A. Clayton wrote:
> [snip]
> >> I think there may have been a miscommunication. The idea
> >> is not to force all predictions to use the same indexing
> >> information (i.e., different types of jumps would use
> >> different information), but to merge the *storage*.
> >
> > Perhaps I did not get to my point:: if you can identify
> > more different kinds of "branching" it is more likely that
> > each one has an optimal predictor than all of then having
> > a common optimal predictor.
> I tend to agree, though I feel the targets of direct,
> single-target jumps and returns should be cached/memoized
> rather than predicted. For returns, this introduces extra
> tagging overhead and forces mispeculation fix-up to apply to
> the cache.
<
Which is why call/ret is generally done with a predictor operating
much like a cache--so it can be un-done and un-un-done when
necessary.
<
But I don't think one should mingle the call return stack with the
conditional branch predictor. Nor should the indirect predictor
be integrated. The way switches and method calls are supported
in My 66000 ISA means these need no predictors, just fast or wide
ICache access.
<
> For direct jumps, this adds some tagging overhead
> to the degree that the target cache has broader coverage
> than the instruction cache (and any outer shared cache which
> can compress instruction data by eliding targets cached in
> the specialized target caches — just accepting redudant
> storage may be easier, avoiding coherent retention of data
> [dropping a target address would only be a performance
> problem (and potential side channel) since the absence would
> be recognized and the data would be in main memory).
>
> (Such also implies predecoding to extract/calculate targets.
> The variable storage requirements further adds complexity.)
>
> Storing targets on the instruction side for jump-based
> switch statements would allow the predictor to only store
> an index into the instruction-side jump table rather than
> an offset. It might also be possible to microarchitecturally
> bypass proximate storage for rarely taken targets/offsets.
> (Architecturally, if a collection of targets is known at
> compile-time to be rarely taken, the standard cold code
> optimization could be used.)
>
> For C++-like virtual calls, if one does not have code
> generation (or fix-up) across compilation units, one could
> not use an inline table. Such would also presumably increase
> the size of an executable text because each method will have
> multiple call sites. (Direct calls have the same issue, of
> course, and few suggest requiring tables so that an offset
> is replaced with a smaller index.)
>
> (I like the idea of link-time code generation, but such is
> more complex and slower. Caching of compilation information
> and invalidation at finer granularity than object file would
> presumably reduce compile times, but such does not seem to
> be commonly implemented and would add further complexity.)
>
> If your statement, Mitch, was that one should not focus on
> incremental improvements in this area but look closer at the
> root of the problem, I can understand the connection with
> my post, which merely incrementally (possibly) improved
> common practice. Since it addressed common practice and
> seemed kind of neat (and added a use for overlaid skewed
> associativity: https://cs.stackexchange.com/q/108720/4577 )
> I wanted to share it.
>
> Control flow target encoding and placement does not seem to
> be a solved problem. One would prefer to extract targets
> that are rarely taken from the instruction fetch stream, but
> retreiving even cool targets all the way from main memory
> might cost more than is saved by extraction from the
> instruction stream. (One intermediate between inline and
> completely independent [especially data-side] target
> retreival would be an offset into a local aligned storage
> area. E.g., every 1 MiB code region might be enabled to
> index storage directly below that region.)
>
> With respect to setjump/longjump, such seems to be similar
> to setting up an exception target and then taking an
> exception. Caching such a target would not seem especially
> difficult (though being per-thread — I think — when other
> exception targets are typically(?) per 'process' would
> increase tagging overhead).
<
The issue with longjump() is that you need to call destructors as
the stack is walked backwards in C++.
<
>As with exceptions, I suspect
> there is some way that threading support would integrate
> with this, but as a non-programmer I am fairly clueless
> about how such features are used.

BGB <cr88192@gmail.com> writes:
>If you use a link register, or return via some other special register
>(such as treating R1 as a secondary link register), then all one needs
>to do is check is that this register hasn't been modified within the
>pipeline, and if so use the value held in this register as the predicted
>branch target.

McKinley and the PowerPC 970 predicted indirect jumps that way. If
the target arrives a short time before the call, this causes a
misprediction; IIRC it cost 6 cycles on McKinley (which did not have a
particularly deep pipeline).

On a modern high-performance CPU, you want to be able to call a short
routine, fetch the instructions from there, and fetch the instructions
from after the call a cycle later. Modern AMD64 implementations
achieve that (thanks to a very streamlined predictor including a
return stack), but with the approach you are suggesting it would not
be possible; keeping the return address in a register helps only so
far.

>In this case, typically one can reload the LR or "Secondary LR" several
>cycles before its associated RTS or JMP.

On a wide processor, you often cannot, see below.

>If one reloads the link
>register before the others in a function epilog, then (typically) the
>reloaded register will have left the pipeline before the CPU reaches the
>return instruction.

You certainly cannot if you do the load in a function epilog (rather
than immediately after the last call). The load has 3-5 cycles of
latency for use by some execution unit, and even in short pipelines
several additional cycles for use in instruction fetching; let's say
you have a short pipeline and only 6 cycles latency from executing a
load to instruction fetch that uses its result; and you have a
moderately wide machine at 4 instructions fetched and decoded per
cycle; then you need to put the load 24 cycles before the return
instructions.

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

On 6/29/2021 9:01 AM, BGB wrote:
> On 6/28/2021 10:45 PM, Andy wrote:
>> On 27/06/21 7:31 am, MitchAlsup wrote:
>>
>>> There are five cases: Switches, Returns, Method calls, Tabulated
>>> Calls, and Longjump.
>>> <
>>> Switches tend to be unpredictable much of the time.
>>> Returns are easily highly predictable
>>> Method calls tend to use few methods more than others
>>> Tabulated calls tend to be indexed tables of entry points
>>> And longjump is a category all by itself.
>>
>> Ummm, so no love for Call Return Tables?, wouldn't they go some way to
>> reducing the number of conditional instructions spent checking for
>> error return codes and having otherwise unneeded instructions situated
>> right after the original call.
>>
>
> A dedicated call-return table probably only really makes sense for
> something like x86, which loads the return address from memory at the
> same time as branching to it.
>
> If you use a link register, or return via some other special register
> (such as treating R1 as a secondary link register), then all one needs
> to do is check is that this register hasn't been modified within the
> pipeline, and if so use the value held in this register as the predicted
> branch target.
>
> In this case, typically one can reload the LR or "Secondary LR" several
> cycles before its associated RTS or JMP. If one reloads the link
> register before the others in a function epilog, then (typically) the
> reloaded register will have left the pipeline before the CPU reaches the
> return instruction.
>
>
> Meanwhile, switch faces a problem that typically one calculates the
> switch target immediately before branching to it. If one could somehow
> do something like:
>   Calculate where the "switch()" will go;
>   Put some prior unrelated logic here;
>   Do the branch to the switch target.
>
> Then "switch()" could potentially also be made predictable.

You can do exactly that: figure index; index-load from a table in
memory; do other stuff; indirect branch. Of course, that puts the table
in dmem, which Mitch doesn't like, or requires a load instruction from imem.

> For small switch one might instead use linear probing or binary
> subdivision or similar, in which case it is predictable if the
> individual branches are predictable.
>
> Say (number of case labels):
>   1-3: Linear Probe
>   4-11: Binary Subdivide
>   12-511 (and sufficiently dense): Branch Table
>   Else: Binary Subdivide (1)
>
> *1: Binary subdivide happens until either it reaches the conditions for
> a branch-table, or the number of targets is small enough that it falls
> back to a linear probe.
>
> ...

What matters is the distribution of indices, not the number of targets.
Think a typical lexer: you want to isolate all alphas with one compare,
not a four way binary to a particular alpha, because all the alphas go
to a single label. Once you do that, normal ifconversion will get rid of
half the internal branches of the decision tree..

On Tuesday, June 29, 2021 at 12:53:14 PM UTC-5, Anton Ertl wrote:
> BGB <cr8...@gmail.com> writes:
> >If you use a link register, or return via some other special register
> >(such as treating R1 as a secondary link register), then all one needs
> >to do is check is that this register hasn't been modified within the
> >pipeline, and if so use the value held in this register as the predicted
> >branch target.
> McKinley and the PowerPC 970 predicted indirect jumps that way. If
> the target arrives a short time before the call, this causes a
> misprediction; IIRC it cost 6 cycles on McKinley (which did not have a
> particularly deep pipeline).
>
> On a modern high-performance CPU, you want to be able to call a short
> routine, fetch the instructions from there, and fetch the instructions
> from after the call a cycle later. Modern AMD64 implementations
> achieve that (thanks to a very streamlined predictor including a
> return stack), but with the approach you are suggesting it would not
> be possible; keeping the return address in a register helps only so
> far.
> >In this case, typically one can reload the LR or "Secondary LR" several
> >cycles before its associated RTS or JMP.
> On a wide processor, you often cannot, see below.
> >If one reloads the link
> >register before the others in a function epilog, then (typically) the
> >reloaded register will have left the pipeline before the CPU reaches the
> >return instruction.
<
> You certainly cannot if you do the load in a function epilog (rather
> than immediately after the last call). The load has 3-5 cycles of
> latency for use by some execution unit, and even in short pipelines
> several additional cycles for use in instruction fetching; let's say
> you have a short pipeline and only 6 cycles latency from executing a
> load to instruction fetch that uses its result; and you have a
> moderately wide machine at 4 instructions fetched and decoded per
> cycle; then you need to put the load 24 cycles before the return
> instructions.
<
In My 66000, EXIT fetches the return address first then fetches the instructions
at the return point, before reloading the saved registers. So the instructions
are entering the pipeline when the preserved registers have their proper values.
>
> - anton
> --
> 'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
> Mitch Alsup, <c17fcd89-f024-40e7...@googlegroups.com>

On Tuesday, June 29, 2021 at 2:27:46 PM UTC-5, Ivan Godard wrote:
> On 6/29/2021 9:01 AM, BGB wrote:
> > On 6/28/2021 10:45 PM, Andy wrote:
> >> On 27/06/21 7:31 am, MitchAlsup wrote:
> >>
> >>> There are five cases: Switches, Returns, Method calls, Tabulated
> >>> Calls, and Longjump.
> >>> <
> >>> Switches tend to be unpredictable much of the time.
> >>> Returns are easily highly predictable
> >>> Method calls tend to use few methods more than others
> >>> Tabulated calls tend to be indexed tables of entry points
> >>> And longjump is a category all by itself.
> >>
> >> Ummm, so no love for Call Return Tables?, wouldn't they go some way to
> >> reducing the number of conditional instructions spent checking for
> >> error return codes and having otherwise unneeded instructions situated
> >> right after the original call.
> >>
> >
> > A dedicated call-return table probably only really makes sense for
> > something like x86, which loads the return address from memory at the
> > same time as branching to it.
> >
> > If you use a link register, or return via some other special register
> > (such as treating R1 as a secondary link register), then all one needs
> > to do is check is that this register hasn't been modified within the
> > pipeline, and if so use the value held in this register as the predicted
> > branch target.
> >
> > In this case, typically one can reload the LR or "Secondary LR" several
> > cycles before its associated RTS or JMP. If one reloads the link
> > register before the others in a function epilog, then (typically) the
> > reloaded register will have left the pipeline before the CPU reaches the
> > return instruction.
> >
> >
> > Meanwhile, switch faces a problem that typically one calculates the
> > switch target immediately before branching to it. If one could somehow
> > do something like:
> > Calculate where the "switch()" will go;
> > Put some prior unrelated logic here;
> > Do the branch to the switch target.
> >
> > Then "switch()" could potentially also be made predictable.
> You can do exactly that: figure index; index-load from a table in
> memory; do other stuff; indirect branch. Of course, that puts the table
> in dmem, which Mitch doesn't like, or requires a load instruction from imem.
<
Switch is common enough that it should be performed in an instruction
(the multiway branch) I added limit checking to this due to how it
"worked out" in my ISA.
<
Also note: the tables in my switches remain program relative, so you fetch
from ICache and then add this to the IP for the target address. This saves
table size as the majority of all tables fit in 16-bit offsets, retains program
relativity.
<
> > For small switch one might instead use linear probing or binary
> > subdivision or similar, in which case it is predictable if the
> > individual branches are predictable.
> >
> > Say (number of case labels):
> > 1-3: Linear Probe
> > 4-11: Binary Subdivide
> > 12-511 (and sufficiently dense): Branch Table
> > Else: Binary Subdivide (1)
> >
> > *1: Binary subdivide happens until either it reaches the conditions for
> > a branch-table, or the number of targets is small enough that it falls
> > back to a linear probe.
> >
> > ...
> What matters is the distribution of indices, not the number of targets.
> Think a typical lexer: you want to isolate all alphas with one compare,
> not a four way binary to a particular alpha, because all the alphas go
> to a single label. Once you do that, normal ifconversion will get rid of
> half the internal branches of the decision tree..
<
In any event, any HW is going to be able to sort through the situation
faster than any string of SW instructions.

On 6/29/2021 1:33 PM, MitchAlsup wrote:
> On Tuesday, June 29, 2021 at 2:27:46 PM UTC-5, Ivan Godard wrote:
>> On 6/29/2021 9:01 AM, BGB wrote:
>>> On 6/28/2021 10:45 PM, Andy wrote:
>>>> On 27/06/21 7:31 am, MitchAlsup wrote:
>>>>
>>>>> There are five cases: Switches, Returns, Method calls, Tabulated
>>>>> Calls, and Longjump.
>>>>> <
>>>>> Switches tend to be unpredictable much of the time.
>>>>> Returns are easily highly predictable
>>>>> Method calls tend to use few methods more than others
>>>>> Tabulated calls tend to be indexed tables of entry points
>>>>> And longjump is a category all by itself.
>>>>
>>>> Ummm, so no love for Call Return Tables?, wouldn't they go some way to
>>>> reducing the number of conditional instructions spent checking for
>>>> error return codes and having otherwise unneeded instructions situated
>>>> right after the original call.
>>>>
>>>
>>> A dedicated call-return table probably only really makes sense for
>>> something like x86, which loads the return address from memory at the
>>> same time as branching to it.
>>>
>>> If you use a link register, or return via some other special register
>>> (such as treating R1 as a secondary link register), then all one needs
>>> to do is check is that this register hasn't been modified within the
>>> pipeline, and if so use the value held in this register as the predicted
>>> branch target.
>>>
>>> In this case, typically one can reload the LR or "Secondary LR" several
>>> cycles before its associated RTS or JMP. If one reloads the link
>>> register before the others in a function epilog, then (typically) the
>>> reloaded register will have left the pipeline before the CPU reaches the
>>> return instruction.
>>>
>>>
>>> Meanwhile, switch faces a problem that typically one calculates the
>>> switch target immediately before branching to it. If one could somehow
>>> do something like:
>>> Calculate where the "switch()" will go;
>>> Put some prior unrelated logic here;
>>> Do the branch to the switch target.
>>>
>>> Then "switch()" could potentially also be made predictable.
>> You can do exactly that: figure index; index-load from a table in
>> memory; do other stuff; indirect branch. Of course, that puts the table
>> in dmem, which Mitch doesn't like, or requires a load instruction from imem.
> <
> Switch is common enough that it should be performed in an instruction
> (the multiway branch) I added limit checking to this due to how it
> "worked out" in my ISA.
> <
> Also note: the tables in my switches remain program relative, so you fetch
> from ICache and then add this to the IP for the target address. This saves
> table size as the majority of all tables fit in 16-bit offsets, retains program
> relativity.
> <
>>> For small switch one might instead use linear probing or binary
>>> subdivision or similar, in which case it is predictable if the
>>> individual branches are predictable.
>>>
>>> Say (number of case labels):
>>> 1-3: Linear Probe
>>> 4-11: Binary Subdivide
>>> 12-511 (and sufficiently dense): Branch Table
>>> Else: Binary Subdivide (1)
>>>
>>> *1: Binary subdivide happens until either it reaches the conditions for
>>> a branch-table, or the number of targets is small enough that it falls
>>> back to a linear probe.
>>>
>>> ...
>> What matters is the distribution of indices, not the number of targets.
>> Think a typical lexer: you want to isolate all alphas with one compare,
>> not a four way binary to a particular alpha, because all the alphas go
>> to a single label. Once you do that, normal ifconversion will get rid of
>> half the internal branches of the decision tree..
> <
> In any event, any HW is going to be able to sort through the situation
> faster than any string of SW instructions.
>

Arguable.

Label density matters for the tables too:
switch (<32 bit>) {
<cases: 11111, 22222, 33333, 44444, 55555, 66666, 77777, 88888, 99999>

Do you really want 100k labels in your table, or a 3-deep compare tree?

Out of curiosity, what happens when you throw that at Brian's compiler?

> Switch is common enough that it should be performed in an instruction
> (the multiway branch) I added limit checking to this due to how it
> "worked out" in my ISA.

BTW, what kind of prediction structure do you foresee for your "multiway
branch" instructions? Do you foresee predicting the index (and then
looking up the corresponding target address in the table), so similar to
a taken/nottaken predictor but just returning more than one bit, or do
you foresee something more like a BTB (i.e. predict the actual target
address of the branch)?

Stefan

> Switch is common enough that it should be performed in an instruction
> (the multiway branch) I added limit checking to this due to how it
> "worked out" in my ISA.

BTW, what kind of prediction structure do you foresee for your "multiway
branch" instructions? Do you foresee predicting the index (and then
looking up the corresponding target address in the table), so similar to
a taken/nottaken predictor but just returning more than one bit, or do
you foresee something more like a BTB (i.e. predict the actual target
address of the branch)?

Stefan

On 6/29/2021 12:27 PM, Ivan Godard wrote:
> On 6/29/2021 9:01 AM, BGB wrote:
>> On 6/28/2021 10:45 PM, Andy wrote:
>>> On 27/06/21 7:31 am, MitchAlsup wrote:
>>>
>>>> There are five cases: Switches, Returns, Method calls, Tabulated
>>>> Calls, and Longjump.
>>>> <
>>>> Switches tend to be unpredictable much of the time.
>>>> Returns are easily highly predictable
>>>> Method calls tend to use few methods more than others
>>>> Tabulated calls tend to be indexed tables of entry points
>>>> And longjump is a category all by itself.
>>>
>>> Ummm, so no love for Call Return Tables?, wouldn't they go some way
>>> to reducing the number of conditional instructions spent checking for
>>> error return codes and having otherwise unneeded instructions
>>> situated right after the original call.
>>>
>>
>> A dedicated call-return table probably only really makes sense for
>> something like x86, which loads the return address from memory at the
>> same time as branching to it.
>>
>> If you use a link register, or return via some other special register
>> (such as treating R1 as a secondary link register), then all one needs
>> to do is check is that this register hasn't been modified within the
>> pipeline, and if so use the value held in this register as the
>> predicted branch target.
>>
>> In this case, typically one can reload the LR or "Secondary LR"
>> several cycles before its associated RTS or JMP. If one reloads the
>> link register before the others in a function epilog, then (typically)
>> the reloaded register will have left the pipeline before the CPU
>> reaches the return instruction.
>>
>>
>> Meanwhile, switch faces a problem that typically one calculates the
>> switch target immediately before branching to it. If one could somehow
>> do something like:
>>    Calculate where the "switch()" will go;
>>    Put some prior unrelated logic here;
>>    Do the branch to the switch target.
>>
>> Then "switch()" could potentially also be made predictable.
>
> You can do exactly that: figure index; index-load from a table in
> memory; do other stuff; indirect branch. Of course, that puts the table
> in dmem, which Mitch doesn't like, or requires a load instruction from
> imem.
>
>> For small switch one might instead use linear probing or binary
>> subdivision or similar, in which case it is predictable if the
>> individual branches are predictable.
>>
>> Say (number of case labels):
>>    1-3: Linear Probe
>>    4-11: Binary Subdivide
>>    12-511 (and sufficiently dense): Branch Table
>>    Else: Binary Subdivide (1)
>>
>> *1: Binary subdivide happens until either it reaches the conditions
>> for a branch-table, or the number of targets is small enough that it
>> falls back to a linear probe.
>>
>> ...
>
> What matters is the distribution of indices, not the number of targets.
> Think a typical lexer: you want to isolate all alphas with one compare,
> not a four way binary to a particular alpha, because all the alphas go
> to a single label. Once you do that, normal ifconversion will get rid of
> half the internal branches of the decision tree..

I am not a compiler guy, so forgive my ignorance. What would a compiler
do in such a situation? Would it first test for something like if char
>= "a" and <= "z", etc.?

Just thinking about how I might do it, I think I would have a 256 byte
array, indexed by the character value, with each entry having an
indicator value, say 1 for lower case letters, 2 for upper case letters,
3 for numbers, 4 for white space characters, etc. Looking up the value
shouldn't be costly as most of the table with shortly be in D-cache.
Then use the indicator value to index a jump or call table (which I
guess is fairly predictable as most characters are lower case letters.

But what do I know? :-(

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