To quote the POWER9 User Manual:

# The POWER9 core normally ignores any software that attempts to
# override the dynamic branch prediction by setting the “a” bit
# in the BO field. This is done because historically programmers
# and compilers have made poor choices for setting the “a” bit,
# which limited the performance of codes where the hardware can
# do a superior job of predicting the branches.

Having read this: Are branching hints actually useful today?

I could see some use in a "almost never used" hint for branches
for fatal error messages, maybe.

> Having read this: Are branching hints actually useful today?

I had the impression that since the CPU needs to predict the address of
the next fetch during the current fetch, there just isn't much room for
using these branching hints: they'd presumably be most useful when the
branch is not yet in the branch prediction table, but in that case we
also don't yet have the branch instruction itself to look at its bits.

Stefan

On Saturday, May 22, 2021 at 5:28:51 PM UTC-5, Thomas Koenig wrote:
> To quote the POWER9 User Manual:
>
> # The POWER9 core normally ignores any software that attempts to
> # override the dynamic branch prediction by setting the “a” bit
> # in the BO field. This is done because historically programmers
> # and compilers have made poor choices for setting the “a” bit,
> # which limited the performance of codes where the hardware can
> # do a superior job of predicting the branches.
>
> Having read this: Are branching hints actually useful today?
<
Branch hints might (MIGHT) have been useful when predictors were
in the 90% accuracy range. Hints are a regrettable waste of entropy
with predictors in the 98% range.
>
> I could see some use in a "almost never used" hint for branches
> for fatal error messages, maybe.
<
Over in the unpredictable branch category, predication and conditional
move have made hints even less valuable than they originally were.
<
Predictors are very accurate on the use-once branches one finds around
initialization codes.

On 5/22/2021 3:28 PM, Thomas Koenig wrote:
> To quote the POWER9 User Manual:
>
> # The POWER9 core normally ignores any software that attempts to
> # override the dynamic branch prediction by setting the “a” bit
> # in the BO field. This is done because historically programmers
> # and compilers have made poor choices for setting the “a” bit,
> # which limited the performance of codes where the hardware can
> # do a superior job of predicting the branches.
>
> Having read this: Are branching hints actually useful today?
>
> I could see some use in a "almost never used" hint for branches
> for fatal error messages, maybe.
>

Hints are not useful, but the same logic that generates hints can be
used to swap the sense of conditional branches so that the expected case
is the not-taken one, i.e. fall through. This doesn't buy you anything
in latency over a good predictor, but does buy you denser code working
sets and hence reduced I$ contention and bandwidth demand.

On Saturday, May 22, 2021 at 7:27:03 PM UTC-5, Ivan Godard wrote:
> On 5/22/2021 3:28 PM, Thomas Koenig wrote:
> > To quote the POWER9 User Manual:
> >
> > # The POWER9 core normally ignores any software that attempts to
> > # override the dynamic branch prediction by setting the “a” bit
> > # in the BO field. This is done because historically programmers
> > # and compilers have made poor choices for setting the “a” bit,
> > # which limited the performance of codes where the hardware can
> > # do a superior job of predicting the branches.
> >
> > Having read this: Are branching hints actually useful today?
> >
> > I could see some use in a "almost never used" hint for branches
> > for fatal error messages, maybe.
> >
> Hints are not useful, but the same logic that generates hints can be
> used to swap the sense of conditional branches so that the expected case
> is the not-taken one, i.e. fall through. This doesn't buy you anything
> in latency over a good predictor, but does buy you denser code working
> sets and hence reduced I$ contention and bandwidth demand.
<
The packetizer does this automagically. Packets are built in the "observed" direction.

On Saturday, May 22, 2021 at 9:30:18 PM UTC-5, MitchAlsup wrote:
> On Saturday, May 22, 2021 at 7:27:03 PM UTC-5, Ivan Godard wrote:
> > On 5/22/2021 3:28 PM, Thomas Koenig wrote:
> > > To quote the POWER9 User Manual:
> > >
> > > # The POWER9 core normally ignores any software that attempts to
> > > # override the dynamic branch prediction by setting the “a” bit
> > > # in the BO field. This is done because historically programmers
> > > # and compilers have made poor choices for setting the “a” bit,
> > > # which limited the performance of codes where the hardware can
> > > # do a superior job of predicting the branches.
> > >
> > > Having read this: Are branching hints actually useful today?
> > >
> > > I could see some use in a "almost never used" hint for branches
> > > for fatal error messages, maybe.
> > >
> > Hints are not useful, but the same logic that generates hints can be
> > used to swap the sense of conditional branches so that the expected case
> > is the not-taken one, i.e. fall through. This doesn't buy you anything
> > in latency over a good predictor, but does buy you denser code working
> > sets and hence reduced I$ contention and bandwidth demand.
> <
> The packetizer does this automagically. Packets are built in the "observed" direction.
<
Not only in the as observed direction, but the branch to get there has zero
cost !

On 5/22/2021 5:28 PM, Thomas Koenig wrote:
> To quote the POWER9 User Manual:
>
> # The POWER9 core normally ignores any software that attempts to
> # override the dynamic branch prediction by setting the “a” bit
> # in the BO field. This is done because historically programmers
> # and compilers have made poor choices for setting the “a” bit,
> # which limited the performance of codes where the hardware can
> # do a superior job of predicting the branches.
>
> Having read this: Are branching hints actually useful today?
>
> I could see some use in a "almost never used" hint for branches
> for fatal error messages, maybe.
>

Scenario 1:
Core is too cheap to do branch prediction:
Branch hints are useless.
Core only does a fixed prediction with no context:
Maybe relevant.
Core does branch prediction, has context:
This is useless.

Predictable branches:
A hardware branch predictor can predict them fairly easily, this is useless.

Unpredictable branches:
Can't be predicted either way, this is useless.

So, general leaning:
Branch direction hints are "kinda useless"...

Nevermind if my ISA has a few encodings which could potentially be
interpreted this way, in my defense, these encodings arrived as a
historical accident (predicated ops were added on after branches already
existed, so some redundant encodings appeared, ...).

It is likely I might reclaim some of this space eventually and use it
for something else (maybe more space for PrWEX ops?...).

As noted, some encodings technically exist (for Disp20 branches), but I
don't really consider them "valid":
BSR?T / BSR?F (1);
BT?T / BT?F / BF?T / BF?F;
WEX encoded branch ops (2).

*1: These operations "actually work", but predicated subroutine calls
aren't really an operation which "makes sense". So, fall into a sort of
"invalid de-facto because the operation itself is kinda absurd" category.

*2: Previously, these had been reclaimed as the original form of the
"jumbo" encoding, but then I reorganized some stuff and came up with a
"slightly less awful" encoding for Jumbo ops (at the expense of the
original Op48 space), but this leaves this as ambiguous.

Op48: Could re-add with new encodings, but isn't likely to be useful
enough to offset its cost if re-added.

More PrWEX? Is possible, but these isn't currently anything meaningful
to put there. The parts of the ISA which can't be encoded via PrWEX
either are not valid within the current ISA semantics (eg: Load/Store
with Displacement), or would not be able to fit into the encoding space
(Imm16 ops).

Some of these cases will either trigger an invalid opcode exception, or
trigger behaviors which are effectively undefined.

Then there are also encodings which are semantically redundant:
BT / BRA?T, BF / BRA?F
Where I could change this, but there is not currently any way to
eliminate this redundancy without breaking binary compatibility with
existing code, so "I may be stuck with them".

Well, and then there are the Jumbo-Branch encodings, which are "also
invalid", but would at this point most likely be used as part of an Op64
space (while there is now a "BRA/BSR Abs48" encoding, it doesn't count
here, because it is elsewhere in the encoding space; similar also goes
for "BRA Disp33s").

And, ironically enough, neither "BT Abs48" or "BRA?T Abs48" can be
encoded, but can't currently think up a whole lot of use cases where one
"really needs" a conditional branch to an absolute address.

....

Granted, it seems like it is almost inevitable that an ISA will be
"ugly" or "inefficient" in one area or another...
It is seemingly more just sorta shuffling stuff around to try to get
something "tolerable".
.... And eventually, the ISA either rams into some impassable wall, or it
turns into something resembling x86 ...

On 5/22/2021 9:50 PM, BGB wrote:
> On 5/22/2021 5:28 PM, Thomas Koenig wrote:
>> To quote the POWER9 User Manual:
>>
>> # The POWER9 core normally ignores any software that attempts to
>> # override the dynamic branch prediction by setting the “a” bit
>> # in the BO field. This is done because historically programmers
>> # and compilers have made poor choices for setting the “a” bit,
>> # which limited the performance of codes where the hardware can
>> # do a superior job of predicting the branches.
>>
>> Having read this: Are branching hints actually useful today?
>>
>> I could see some use in a "almost never used" hint for branches
>> for fatal error messages, maybe.
>>
>
> Scenario 1:
>   Core is too cheap to do branch prediction:
>     Branch hints are useless.
>   Core only does a fixed prediction with no context:
>     Maybe relevant.
>   Core does branch prediction, has context:
>     This is useless.
>
> Predictable branches:
> A hardware branch predictor can predict them fairly easily, this is
> useless.
>
> Unpredictable branches:
> Can't be predicted either way, this is useless.
>
> So, general leaning:
> Branch direction hints are "kinda useless"...
>
>
>
>
> Nevermind if my ISA has a few encodings which could potentially be
> interpreted this way, in my defense, these encodings arrived as a
> historical accident (predicated ops were added on after branches already
> existed, so some redundant encodings appeared, ...).
>
> It is likely I might reclaim some of this space eventually and use it
> for something else (maybe more space for PrWEX ops?...).
>
> As noted, some encodings technically exist (for Disp20 branches), but I
> don't really consider them "valid":
>   BSR?T / BSR?F (1);
>   BT?T / BT?F / BF?T / BF?F;
>   WEX encoded branch ops (2).
>
> *1: These operations "actually work", but predicated subroutine calls
> aren't really an operation which "makes sense". So, fall into a sort of
> "invalid de-facto because the operation itself is kinda absurd" category.

Predicated calls are common in if-converted code. Of course, if you are
doing hardware bundle creation as in Mitch's then you don't need static
predication of any form.

On 5/23/2021 1:24 AM, Ivan Godard wrote:
> On 5/22/2021 9:50 PM, BGB wrote:
>> On 5/22/2021 5:28 PM, Thomas Koenig wrote:
>>> To quote the POWER9 User Manual:
>>>
>>> # The POWER9 core normally ignores any software that attempts to
>>> # override the dynamic branch prediction by setting the “a” bit
>>> # in the BO field. This is done because historically programmers
>>> # and compilers have made poor choices for setting the “a” bit,
>>> # which limited the performance of codes where the hardware can
>>> # do a superior job of predicting the branches.
>>>
>>> Having read this: Are branching hints actually useful today?
>>>
>>> I could see some use in a "almost never used" hint for branches
>>> for fatal error messages, maybe.
>>>
>>
>> Scenario 1:
>>    Core is too cheap to do branch prediction:
>>      Branch hints are useless.
>>    Core only does a fixed prediction with no context:
>>      Maybe relevant.
>>    Core does branch prediction, has context:
>>      This is useless.
>>
>> Predictable branches:
>> A hardware branch predictor can predict them fairly easily, this is
>> useless.
>>
>> Unpredictable branches:
>> Can't be predicted either way, this is useless.
>>
>> So, general leaning:
>> Branch direction hints are "kinda useless"...
>>
>>
>>
>>
>> Nevermind if my ISA has a few encodings which could potentially be
>> interpreted this way, in my defense, these encodings arrived as a
>> historical accident (predicated ops were added on after branches
>> already existed, so some redundant encodings appeared, ...).
>>
>> It is likely I might reclaim some of this space eventually and use it
>> for something else (maybe more space for PrWEX ops?...).
>>
>> As noted, some encodings technically exist (for Disp20 branches), but
>> I don't really consider them "valid":
>>    BSR?T / BSR?F (1);
>>    BT?T / BT?F / BF?T / BF?F;
>>    WEX encoded branch ops (2).
>>
>> *1: These operations "actually work", but predicated subroutine calls
>> aren't really an operation which "makes sense". So, fall into a sort
>> of "invalid de-facto because the operation itself is kinda absurd"
>> category.
>
> Predicated calls are common in if-converted code. Of course, if you are
> doing hardware bundle creation as in Mitch's then you don't need static
> predication of any form.
>

Bundle creation in my case is explicit and handled by the compiler (or
ASM programmer).

But, I am only dealing with predication for simple branches, eg:
if(x>0)
x--;
Or:
if(x>0)
z=x-5;
else
z=x+13;
....

But, not for anything much more than a few instructions, or anything
involving a function call, ..., since presumably in this case a branch
is cheaper (and the core isn't really wide nor has enough registers to
really justify any IA-64 style modular scheduling trickery, ...).

Also, the state of SR.T would not be preserved across a function call,
so any logic following the function's return could not be predicated.

On 5/23/2021 1:33 AM, BGB wrote:
> On 5/23/2021 1:24 AM, Ivan Godard wrote:
>> On 5/22/2021 9:50 PM, BGB wrote:
>>> On 5/22/2021 5:28 PM, Thomas Koenig wrote:
>>>> To quote the POWER9 User Manual:
>>>>
>>>> # The POWER9 core normally ignores any software that attempts to
>>>> # override the dynamic branch prediction by setting the “a” bit
>>>> # in the BO field. This is done because historically programmers
>>>> # and compilers have made poor choices for setting the “a” bit,
>>>> # which limited the performance of codes where the hardware can
>>>> # do a superior job of predicting the branches.
>>>>
>>>> Having read this: Are branching hints actually useful today?
>>>>
>>>> I could see some use in a "almost never used" hint for branches
>>>> for fatal error messages, maybe.
>>>>
>>>
>>> Scenario 1:
>>>    Core is too cheap to do branch prediction:
>>>      Branch hints are useless.
>>>    Core only does a fixed prediction with no context:
>>>      Maybe relevant.
>>>    Core does branch prediction, has context:
>>>      This is useless.
>>>
>>> Predictable branches:
>>> A hardware branch predictor can predict them fairly easily, this is
>>> useless.
>>>
>>> Unpredictable branches:
>>> Can't be predicted either way, this is useless.
>>>
>>> So, general leaning:
>>> Branch direction hints are "kinda useless"...
>>>
>>>
>>>
>>>
>>> Nevermind if my ISA has a few encodings which could potentially be
>>> interpreted this way, in my defense, these encodings arrived as a
>>> historical accident (predicated ops were added on after branches
>>> already existed, so some redundant encodings appeared, ...).
>>>
>>> It is likely I might reclaim some of this space eventually and use it
>>> for something else (maybe more space for PrWEX ops?...).
>>>
>>> As noted, some encodings technically exist (for Disp20 branches), but
>>> I don't really consider them "valid":
>>>    BSR?T / BSR?F (1);
>>>    BT?T / BT?F / BF?T / BF?F;
>>>    WEX encoded branch ops (2).
>>>
>>> *1: These operations "actually work", but predicated subroutine calls
>>> aren't really an operation which "makes sense". So, fall into a sort
>>> of "invalid de-facto because the operation itself is kinda absurd"
>>> category.
>>
>> Predicated calls are common in if-converted code. Of course, if you
>> are doing hardware bundle creation as in Mitch's then you don't need
>> static predication of any form.
>>
>
> Bundle creation in my case is explicit and handled by the compiler (or
> ASM programmer).
>
>
> But, I am only dealing with predication for simple branches, eg:
>   if(x>0)
>     x--;
> Or:
>   if(x>0)
>     z=x-5;
>   else
>     z=x+13;
> ...
>

consider:
if(x>0)
z=x-5;
else
z=foo(x);
if you have exceptions under control, this can become:
t1=x-5;t2=(x>0)?nil:foo(x);
z=x>0?t1:t2;
the architectural challenge is how to implement "t2=(x>0)?nil:foo(x);",
i.e. predicated calls.

> But, not for anything much more than a few instructions, or anything
> involving a function call, ..., since presumably in this case a branch
> is cheaper (and the core isn't really wide nor has enough registers to
> really justify any IA-64 style modular scheduling trickery, ...).

That's a problem with any if-conversions or other speculative
scheduling: you have to have enough FUs to get useful parallelism.
There's a sweet spot in speculative width: too narrow and you lose the
benefit; too wide and the power and area cost more than the overhead of OOO

> Also, the state of SR.T would not be preserved across a function call,
> so any logic following the function's return could not be predicated.

This can be architected around; ours is not the only possible way to do it.

Thomas Koenig wrote:
> To quote the POWER9 User Manual:
>
> # The POWER9 core normally ignores any software that attempts to
> # override the dynamic branch prediction by setting the “a” bit
> # in the BO field. This is done because historically programmers
> # and compilers have made poor choices for setting the “a” bit,
> # which limited the performance of codes where the hardware can
> # do a superior job of predicting the branches.
>
> Having read this: Are branching hints actually useful today?
>
> I could see some use in a "almost never used" hint for branches
> for fatal error messages, maybe.

I think gcc already have an option to annotate branches that are very
unlikely to be taken, if that could be encoded as a hint to the cpu it
could totally bypass the BTB and thereby saving branch buffer space.

In order to retrofit it to existing architectures it would however
probably need to be as a separate hint opcode, previously defined as a
NOP, so making the code slower (at least by the time needed to decode
that NOP) on all previous cpu versions.

Terje

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

Thomas Koenig wrote:
> To quote the POWER9 User Manual:
>
> # The POWER9 core normally ignores any software that attempts to
> # override the dynamic branch prediction by setting the “a” bit
> # in the BO field. This is done because historically programmers
> # and compilers have made poor choices for setting the “a” bit,
> # which limited the performance of codes where the hardware can
> # do a superior job of predicting the branches.
>
> Having read this: Are branching hints actually useful today?
>
> I could see some use in a "almost never used" hint for branches
> for fatal error messages, maybe.

There is a case for a "predict never" hint where it doesn't matter
what this conditional branch did the last million times it executed,
always predict not-taken.

In a spinlock which normally test the lock condition with
a load before attempting the atomic sequence,
you never want to speculatively execute into the atomic sequence.
At a minimum it could cause ping-pong'ing the cache lines.

With Hardware Transactional Memory HTM reading a memory location
even speculatively might abort another's processors active transaction,
you don't want to even touch data memory without explicit permission,
not even prefetching any load or store addresses.

If you don't have a hint to explicitly block speculation at the
branch then the design would have to use more complicated and
probably error prone dynamic logic to "deduce" what to do.

Without an explicit "predict never" hint, in the case of HTM
this looked to me like that speculation might have to shut off
while a transaction was in progress because there is no way
to deduce which loads are guarded by a particular condition.
At a minimum, in an HTM it looked like no loads performed while
any prior branch was unresolved, not even prefetched into cache
(or maybe that's a good thing, I don't know).

Predict-never can also be used for rarely executed error handling code.

Predict-always is the complementary case for branching around
rarely executed error handling code that one wants inline,
and it doesn't matter what it did the last million times it executed.

EricP <ThatWouldBeTelling@thevillage.com> schrieb:

[stuff on locks snipped]
> Thomas Koenig wrote:

>> I could see some use in a "almost never used" hint for branches
>> for fatal error messages, maybe.
>
> There is a case for a "predict never" hint where it doesn't matter
> what this conditional branch did the last million times it executed,
> always predict not-taken.
>
> In a spinlock which normally test the lock condition with
> a load before attempting the atomic sequence,
> you never want to speculatively execute into the atomic sequence.
> At a minimum it could cause ping-pong'ing the cache lines.

[HTM snipped]

> Predict-never can also be used for rarely executed error handling code.

> Predict-always is the complementary case for branching around
> rarely executed error handling code that one wants inline,
> and it doesn't matter what it did the last million times it executed.

Compilers already split functions into "hot" and "cold" parts
for better cache locality. Code that the programmer assures the
compiler will very rarely be taken is already put into the cold
section.

So, I take it from your article that a "Never predict this branch
to be taken" bit could be a reasonable thing to include in an ISA.

Thomas Koenig wrote:
> EricP <ThatWouldBeTelling@thevillage.com> schrieb:
>
> [stuff on locks snipped]
>> Thomas Koenig wrote:
>
>>> I could see some use in a "almost never used" hint for branches
>>> for fatal error messages, maybe.
>> There is a case for a "predict never" hint where it doesn't matter
>> what this conditional branch did the last million times it executed,
>> always predict not-taken.
>>
>> In a spinlock which normally test the lock condition with
>> a load before attempting the atomic sequence,
>> you never want to speculatively execute into the atomic sequence.
>> At a minimum it could cause ping-pong'ing the cache lines.
>
> [HTM snipped]
>
>> Predict-never can also be used for rarely executed error handling code.
>
>> Predict-always is the complementary case for branching around
>> rarely executed error handling code that one wants inline,
>> and it doesn't matter what it did the last million times it executed.
>
> Compilers already split functions into "hot" and "cold" parts
> for better cache locality. Code that the programmer assures the
> compiler will very rarely be taken is already put into the cold
> section.

Yes, the case for a "predict-always" is weaker but there are times
when I want the error handler to sit right beside the error detector
so that the program counter indicates where the error occurred.

Also, symmetry is its' own reward (entropy considerations be dammed!).

> So, I take it from your article that a "Never predict this branch
> to be taken" bit could be a reasonable thing to include in an ISA.

I think so, or at least it makes a case for discussion.

This also crosses into Spectre territory. Spectre-safe code generation
could put the cold error handling code inline, and use a predict-never
hint to branch around error handler to the hot code.
It doesn't use the branch predictor so it can't be mis-trained.

But note that the use cases I gave for "predict-never" were both
using the hints to achieve a kind of branch-fence effect to block
speculation while a branch condition was unresolved.

Alternatively (left field thought here) maybe a branch-fence instruction
specifically designed to do that job would be more generally useful.
(Not sure what that means... just thinking out loud.)

On Sunday, May 23, 2021 at 5:26:22 AM UTC-5, Ivan Godard wrote:
> On 5/23/2021 1:33 AM, BGB wrote:
> > On 5/23/2021 1:24 AM, Ivan Godard wrote:

> > Bundle creation in my case is explicit and handled by the compiler (or
> > ASM programmer).
> >
> >
> > But, I am only dealing with predication for simple branches, eg:
> > if(x>0)
> > x--;
> > Or:
> > if(x>0)
> > z=x-5;
> > else
> > z=x+13;
> > ...
PLT0 Rx,{1,1}
ADD Rz,Rx,#-1
....
PLT0 Rx,{2,10}
ADD Rz,Rx,#-5
ADD Rz,Rx,#13
> >
> consider:
> if(x>0)
> z=x-5;
> else
> z=foo(x);
<
PLT0 Rx,{4,1000}
ADD Rz,Rx,#-1
MOV R1,Rx
CALL foo
MOV Rz,R1
<
> if you have exceptions under control, this can become:
> t1=x-5;t2=(x>0)?nil:foo(x);
> z=x>0?t1:t2;
> the architectural challenge is how to implement "t2=(x>0)?nil:foo(x);",
> i.e. predicated calls.
<
You also have to predicate the argument setup and the result delivery.
<
> > But, not for anything much more than a few instructions, or anything
> > involving a function call, ..., since presumably in this case a branch
> > is cheaper (and the core isn't really wide nor has enough registers to
> > really justify any IA-64 style modular scheduling trickery, ...).
> That's a problem with any if-conversions or other speculative
> scheduling: you have to have enough FUs to get useful parallelism.
> There's a sweet spot in speculative width: too narrow and you lose the
> benefit; too wide and the power and area cost more than the overhead of OOO
<
The majority of the benefit has already accrued when you can predicate
as far as you FETCH width. SO if you FETCH 4-wide, you get the majority
of the benefit by predication at least 4 instructions. More than 2× this
distance and you should be using branches to avoid tracking instructions
that don't execute.
<
> > Also, the state of SR.T would not be preserved across a function call,
> > so any logic following the function's return could not be predicated.
> This can be architected around; ours is not the only possible way to do it.
<
If SR.T is in a preserved register, you just use PRED again after return.

On Sunday, May 23, 2021 at 5:56:00 AM UTC-5, Terje Mathisen wrote:
> Thomas Koenig wrote:

> I think gcc already have an option to annotate branches that are very
> unlikely to be taken, if that could be encoded as a hint to the cpu it
> could totally bypass the BTB and thereby saving branch buffer space.
<
The fact that GCC can so annotate, does not increase the viability of
such annotations !
<
This thread is about whether the annotations are useful, and at what
scale they might be useful.
>
> In order to retrofit it to existing architectures it would however
> probably need to be as a separate hint opcode, previously defined as a
> NOP, so making the code slower (at least by the time needed to decode
> that NOP) on all previous cpu versions.
>
> Terje
>
> --
> - <Terje.Mathisen at tmsw.no>
> "almost all programming can be viewed as an exercise in caching"

On Sunday, May 23, 2021 at 8:54:03 AM UTC-5, EricP wrote:

> There is a case for a "predict never" hint where it doesn't matter
> what this conditional branch did the last million times it executed,
> always predict not-taken.
>
> In a spinlock which normally test the lock condition with
> a load before attempting the atomic sequence,
> you never want to speculatively execute into the atomic sequence.
> At a minimum it could cause ping-pong'ing the cache lines.
<
Yes, the classical test-and-test-and-set. But this only decreases
bus traffic from BigO(n^3) to BigO(N^2). There are ways to
decrease bus traffic to BigO( N+3 )
>
> With Hardware Transactional Memory HTM reading a memory location
> even speculatively might abort another's processors active transaction,
> you don't want to even touch data memory without explicit permission,
> not even prefetching any load or store addresses.
<
This is one of the things WRONG about HTM.
<
in My 66000 there is a Exotic Synchronization Method (ESM) which is not
an HTM but can be used to create HTMs. In ESM, if the ATOMIC event has
reached a critical juncture (i.e., can complete) the CPUs reaching those
points gain the ability to NAK interference, allowing these CPUs to complete
the ATOMIC event, and making the interferers run slower!
>
> If you don't have a hint to explicitly block speculation at the
> branch then the design would have to use more complicated and
> probably error prone dynamic logic to "deduce" what to do.
<
You do not want Naked memory refs to be used to setup or complete
ATOMIC events. You need to "mark" their participation in the event
so the machine knows that such an event is going on from the out-
set.
>
> Without an explicit "predict never" hint, in the case of HTM
> this looked to me like that speculation might have to shut off
> while a transaction was in progress because there is no way
> to deduce which loads are guarded by a particular condition.
> At a minimum, in an HTM it looked like no loads performed while
> any prior branch was unresolved, not even prefetched into cache
> (or maybe that's a good thing, I don't know).
<
Should an ATOMIC event fail, the compiler needs to know that all
of the participating memory references are not viable containers
of data! And not ever use those units of stale data. The only use
that should be allowed is to print the values that failed.
>
> Predict-never can also be used for rarely executed error handling code.
>
> Predict-always is the complementary case for branching around
> rarely executed error handling code that one wants inline,
> and it doesn't matter what it did the last million times it executed.

>> I think gcc already have an option to annotate branches that are very
>> unlikely to be taken, if that could be encoded as a hint to the cpu it
>> could totally bypass the BTB and thereby saving branch buffer space.
> The fact that GCC can so annotate, does not increase the viability of
> such annotations !

Such annotations in the source code are most useful in order to improve
the generated code, not to add hints to branch instructions (I don't
know if GCC ever uses them to add hints to branch instructions, but
I know it uses them to guess which code is expected to be hot/cold).

Stefan

MitchAlsup wrote:
> On Sunday, May 23, 2021 at 5:56:00 AM UTC-5, Terje Mathisen wrote:
>> Thomas Koenig wrote:
>
>> I think gcc already have an option to annotate branches that are very
>> unlikely to be taken, if that could be encoded as a hint to the cpu it
>> could totally bypass the BTB and thereby saving branch buffer space.
> <
> The fact that GCC can so annotate, does not increase the viability of
> such annotations !
> <
> This thread is about whether the annotations are useful, and at what
> scale they might be useful.

We seem to once again be in violent agreement:

I generally don't like hint instructions, simply because I have seen far
too many instances where they hindered and _very_ few where they
actually helped.

See alos what I wrote below:
>>
>> In order to retrofit it to existing architectures it would however
>> probably need to be as a separate hint opcode, previously defined as a
>> NOP, so making the code slower (at least by the time needed to decode
>> that NOP) on all previous cpu versions.

Terje

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

On 5/23/2021 5:26 AM, Ivan Godard wrote:
> On 5/23/2021 1:33 AM, BGB wrote:
>> On 5/23/2021 1:24 AM, Ivan Godard wrote:
>>> On 5/22/2021 9:50 PM, BGB wrote:
>>>> On 5/22/2021 5:28 PM, Thomas Koenig wrote:
>>>>> To quote the POWER9 User Manual:
>>>>>
>>>>> # The POWER9 core normally ignores any software that attempts to
>>>>> # override the dynamic branch prediction by setting the “a” bit
>>>>> # in the BO field. This is done because historically programmers
>>>>> # and compilers have made poor choices for setting the “a” bit,
>>>>> # which limited the performance of codes where the hardware can
>>>>> # do a superior job of predicting the branches.
>>>>>
>>>>> Having read this: Are branching hints actually useful today?
>>>>>
>>>>> I could see some use in a "almost never used" hint for branches
>>>>> for fatal error messages, maybe.
>>>>>
>>>>
>>>> Scenario 1:
>>>>    Core is too cheap to do branch prediction:
>>>>      Branch hints are useless.
>>>>    Core only does a fixed prediction with no context:
>>>>      Maybe relevant.
>>>>    Core does branch prediction, has context:
>>>>      This is useless.
>>>>
>>>> Predictable branches:
>>>> A hardware branch predictor can predict them fairly easily, this is
>>>> useless.
>>>>
>>>> Unpredictable branches:
>>>> Can't be predicted either way, this is useless.
>>>>
>>>> So, general leaning:
>>>> Branch direction hints are "kinda useless"...
>>>>
>>>>
>>>>
>>>>
>>>> Nevermind if my ISA has a few encodings which could potentially be
>>>> interpreted this way, in my defense, these encodings arrived as a
>>>> historical accident (predicated ops were added on after branches
>>>> already existed, so some redundant encodings appeared, ...).
>>>>
>>>> It is likely I might reclaim some of this space eventually and use
>>>> it for something else (maybe more space for PrWEX ops?...).
>>>>
>>>> As noted, some encodings technically exist (for Disp20 branches),
>>>> but I don't really consider them "valid":
>>>>    BSR?T / BSR?F (1);
>>>>    BT?T / BT?F / BF?T / BF?F;
>>>>    WEX encoded branch ops (2).
>>>>
>>>> *1: These operations "actually work", but predicated subroutine
>>>> calls aren't really an operation which "makes sense". So, fall into
>>>> a sort of "invalid de-facto because the operation itself is kinda
>>>> absurd" category.
>>>
>>> Predicated calls are common in if-converted code. Of course, if you
>>> are doing hardware bundle creation as in Mitch's then you don't need
>>> static predication of any form.
>>>
>>
>> Bundle creation in my case is explicit and handled by the compiler (or
>> ASM programmer).
>>
>>
>> But, I am only dealing with predication for simple branches, eg:
>>    if(x>0)
>>      x--;
>> Or:
>>    if(x>0)
>>      z=x-5;
>>    else
>>      z=x+13;
>> ...
>>
>
> consider:
>     if(x>0)
>       z=x-5;
>     else
>       z=foo(x);
> if you have exceptions under control, this can become:
>     t1=x-5;t2=(x>0)?nil:foo(x);
>     z=x>0?t1:t2;
> the architectural challenge is how to implement "t2=(x>0)?nil:foo(x);",
> i.e. predicated calls.
>

This case could be done as-is with some register-use trickery, though
unclear how useful it would be in general.

>> But, not for anything much more than a few instructions, or anything
>> involving a function call, ..., since presumably in this case a branch
>> is cheaper (and the core isn't really wide nor has enough registers to
>> really justify any IA-64 style modular scheduling trickery, ...).
>
> That's a problem with any if-conversions or other speculative
> scheduling: you have to have enough FUs to get useful parallelism.
> There's a sweet spot in speculative width: too narrow and you lose the
> benefit; too wide and the power and area cost more than the overhead of OOO
>

Yeah. In my own uses, what I was able to leverage in hand-written ASM
seems to imply an optimal width of ~ 2 or 3. Any wider, and I run out of
stuff that could be run in parallel, or run out of registers to put
stuff in. Some modular-loop scheduling was done manually in a few cases,
but is a rarity, and only sometimes pays off.

My C compiler still falls well short of this though...

It looks to me like making use of a 4 or 5 wide core would effectively
require a rather different approach:
multiple predication registers
with ops being able to select a src/dst predicate
bigger register file
...

At this point, it would start to look more like an Itanium.

Though, something kinda like Itanium, but with say 64 GPRs and 4 or 8
predicate registers, and variable-length bundles, could make some sense
(goal being to still use 32-bit instruction words and still have a
"plausible" code density).

One possibility for predication is that ops are predicated by default,
just one of the predicate flags is hard-wired (to allow for "always
execute" ops), then ops fall into a mode:
00 Scalar/End-Of-Bundle, Execute True
01 Scalar/End-Of-Bundle, Execute False
10 Wide, Execute True
11 Wide, Execute False
With a predicate register (Source):
00: Hard wired as True
01: Predicate 1
10: Predicate 2
11: Predicate 3

Other ops would have 3 registers (18 bits), or 2 registers (12 bits).
Compare ops could have a 2-bit predicate-destination field.

It is possible that 01:00 (Never Execute) could be used to encode a
Jumbo Prefix or similar (or, maybe a few unconditional large-immed
instructions or similar).

>> Also, the state of SR.T would not be preserved across a function call,
>> so any logic following the function's return could not be predicated.
>
> This can be architected around; ours is not the only possible way to do it.

Yeah. Most likely option would be a callee-save register containing
predicates or similar. As opposed to a single predicate flag which is
treated as a scratch value (and only ISRs need to bother with preserving
it).

On Sunday, May 23, 2021 at 12:15:04 PM UTC-5, robf...@gmail.com wrote:
> Speaking of the usefulness of branch hints for prediction I have to agree
> that they are not that useful. As a gag though I added the ability to supply
> branch predictor hints in ‘if’ statements that also allowed the branch
> predictor to be selected. How useful is it to be able to select the branch
> predictor to use (assuming multiple predictors are present)?
> The only case I can think of is maybe power savings.
<
I might note that Virtual Vector Method loops do not use the branch predictor
but are executed in advance of the loop iteration to effectively perform as if
the branch took zero cycles when the loop terminates (and zero cycles when
the loop continues.)
<
This improves the prediction accuracy of the "rest of the branches".
<
PREDication also does not use the branch predictor getting the HW setup
to execute either then-clause or else-clause. This also improves the prediction
accuracy of the "rest of the branches".

On 5/23/2021 8:56 AM, MitchAlsup wrote:
> On Sunday, May 23, 2021 at 5:26:22 AM UTC-5, Ivan Godard wrote:
>> On 5/23/2021 1:33 AM, BGB wrote:
>>> On 5/23/2021 1:24 AM, Ivan Godard wrote:
>
>>> Bundle creation in my case is explicit and handled by the compiler (or
>>> ASM programmer).
>>>
>>>
>>> But, I am only dealing with predication for simple branches, eg:
>>> if(x>0)
>>> x--;
>>> Or:
>>> if(x>0)
>>> z=x-5;
>>> else
>>> z=x+13;
>>> ...
> PLT0 Rx,{1,1}
> ADD Rz,Rx,#-1
> ...
> PLT0 Rx,{2,10}
> ADD Rz,Rx,#-5
> ADD Rz,Rx,#13
>>>
>> consider:
>> if(x>0)
>> z=x-5;
>> else
>> z=foo(x);
> <
> PLT0 Rx,{4,1000}
> ADD Rz,Rx,#-1
> MOV R1,Rx
> CALL foo
> MOV Rz,R1
> <
>> if you have exceptions under control, this can become:
>> t1=x-5;t2=(x>0)?nil:foo(x);
>> z=x>0?t1:t2;
>> the architectural challenge is how to implement "t2=(x>0)?nil:foo(x);",
>> i.e. predicated calls.
> <
> You also have to predicate the argument setup and the result delivery.

No, unless the argument setup is potentially excepting; another example
that predication must keep exceptions under control, or you get a
predication explosion and wind up with an ARM. Once you have Mill's NaR
bits or equivalent the only ops that get predicated are control flow
(including call and return) and store.

As for call result: whether a not-taken predicate clears or leaves alone
the result reg is a matter for architectural design; either can work.

>>> But, not for anything much more than a few instructions, or anything
>>> involving a function call, ..., since presumably in this case a branch
>>> is cheaper (and the core isn't really wide nor has enough registers to
>>> really justify any IA-64 style modular scheduling trickery, ...).
>> That's a problem with any if-conversions or other speculative
>> scheduling: you have to have enough FUs to get useful parallelism.
>> There's a sweet spot in speculative width: too narrow and you lose the
>> benefit; too wide and the power and area cost more than the overhead of OOO
> <
> The majority of the benefit has already accrued when you can predicate
> as far as you FETCH width. SO if you FETCH 4-wide, you get the majority
> of the benefit by predication at least 4 instructions. More than 2× this
> distance and you should be using branches to avoid tracking instructions
> that don't execute.

That assumes that consecutive instructuins all predicate the same way,
which works when you have hardware dynamic OOO, and doesn't when you
have static scheduling with interleaving from multiple paths.

There really doesn't seem to be any middle ground: either you work out
all the implications of static scheduling and wind up with a Mill, or
you work out all those of OOO and wind up with a MY66.

> <
>>> Also, the state of SR.T would not be preserved across a function call,
>>> so any logic following the function's return could not be predicated.
>> This can be architected around; ours is not the only possible way to do it.
> <
> If SR.T is in a preserved register, you just use PRED again after return.
>

On 5/23/2021 11:13 AM, BGB wrote:
> On 5/23/2021 5:26 AM, Ivan Godard wrote:
>> On 5/23/2021 1:33 AM, BGB wrote:
>>> On 5/23/2021 1:24 AM, Ivan Godard wrote:
>>>> On 5/22/2021 9:50 PM, BGB wrote:
>>>>> On 5/22/2021 5:28 PM, Thomas Koenig wrote:
>>>>>> To quote the POWER9 User Manual:
>>>>>>
>>>>>> # The POWER9 core normally ignores any software that attempts to
>>>>>> # override the dynamic branch prediction by setting the “a” bit
>>>>>> # in the BO field. This is done because historically programmers
>>>>>> # and compilers have made poor choices for setting the “a” bit,
>>>>>> # which limited the performance of codes where the hardware can
>>>>>> # do a superior job of predicting the branches.
>>>>>>
>>>>>> Having read this: Are branching hints actually useful today?
>>>>>>
>>>>>> I could see some use in a "almost never used" hint for branches
>>>>>> for fatal error messages, maybe.
>>>>>>
>>>>>
>>>>> Scenario 1:
>>>>>    Core is too cheap to do branch prediction:
>>>>>      Branch hints are useless.
>>>>>    Core only does a fixed prediction with no context:
>>>>>      Maybe relevant.
>>>>>    Core does branch prediction, has context:
>>>>>      This is useless.
>>>>>
>>>>> Predictable branches:
>>>>> A hardware branch predictor can predict them fairly easily, this is
>>>>> useless.
>>>>>
>>>>> Unpredictable branches:
>>>>> Can't be predicted either way, this is useless.
>>>>>
>>>>> So, general leaning:
>>>>> Branch direction hints are "kinda useless"...
>>>>>
>>>>>
>>>>>
>>>>>
>>>>> Nevermind if my ISA has a few encodings which could potentially be
>>>>> interpreted this way, in my defense, these encodings arrived as a
>>>>> historical accident (predicated ops were added on after branches
>>>>> already existed, so some redundant encodings appeared, ...).
>>>>>
>>>>> It is likely I might reclaim some of this space eventually and use
>>>>> it for something else (maybe more space for PrWEX ops?...).
>>>>>
>>>>> As noted, some encodings technically exist (for Disp20 branches),
>>>>> but I don't really consider them "valid":
>>>>>    BSR?T / BSR?F (1);
>>>>>    BT?T / BT?F / BF?T / BF?F;
>>>>>    WEX encoded branch ops (2).
>>>>>
>>>>> *1: These operations "actually work", but predicated subroutine
>>>>> calls aren't really an operation which "makes sense". So, fall into
>>>>> a sort of "invalid de-facto because the operation itself is kinda
>>>>> absurd" category.
>>>>
>>>> Predicated calls are common in if-converted code. Of course, if you
>>>> are doing hardware bundle creation as in Mitch's then you don't need
>>>> static predication of any form.
>>>>
>>>
>>> Bundle creation in my case is explicit and handled by the compiler
>>> (or ASM programmer).
>>>
>>>
>>> But, I am only dealing with predication for simple branches, eg:
>>>    if(x>0)
>>>      x--;
>>> Or:
>>>    if(x>0)
>>>      z=x-5;
>>>    else
>>>      z=x+13;
>>> ...
>>>
>>
>> consider:
>>      if(x>0)
>>        z=x-5;
>>      else
>>        z=foo(x);
>> if you have exceptions under control, this can become:
>>      t1=x-5;t2=(x>0)?nil:foo(x);
>>      z=x>0?t1:t2;
>> the architectural challenge is how to implement
>> "t2=(x>0)?nil:foo(x);", i.e. predicated calls.
>>
>
> This case could be done as-is with some register-use trickery, though
> unclear how useful it would be in general.
>
>
>>> But, not for anything much more than a few instructions, or anything
>>> involving a function call, ..., since presumably in this case a
>>> branch is cheaper (and the core isn't really wide nor has enough
>>> registers to really justify any IA-64 style modular scheduling
>>> trickery, ...).
>>
>> That's a problem with any if-conversions or other speculative
>> scheduling: you have to have enough FUs to get useful parallelism.
>> There's a sweet spot in speculative width: too narrow and you lose the
>> benefit; too wide and the power and area cost more than the overhead
>> of OOO
>>
>
> Yeah. In my own uses, what I was able to leverage in hand-written ASM
> seems to imply an optimal width of ~ 2 or 3. Any wider, and I run out of
> stuff that could be run in parallel, or run out of registers to put
> stuff in. Some modular-loop scheduling was done manually in a few cases,
> but is a rarity, and only sometimes pays off.
>
>
> My C compiler still falls well short of this though...
>
>
> It looks to me like making use of a 4 or 5 wide core would effectively
> require a rather different approach:
>   multiple predication registers
>    with ops being able to select a src/dst predicate
>   bigger register file
>   ...
>
> At this point, it would start to look more like an Itanium.
>
> Though, something kinda like Itanium, but with say 64 GPRs and 4 or 8
> predicate registers, and variable-length bundles, could make some sense
> (goal being to still use 32-bit instruction words and still have a
> "plausible" code density).
>
> One possibility for predication is that ops are predicated by default,
> just one of the predicate flags is hard-wired (to allow for "always
> execute" ops), then ops fall into a mode:
>   00 Scalar/End-Of-Bundle, Execute True
>   01 Scalar/End-Of-Bundle, Execute False
>   10 Wide, Execute True
>   11 Wide, Execute False
> With a predicate register (Source):
>   00: Hard wired as True
>   01: Predicate 1
>   10: Predicate 2
>   11: Predicate 3
>
> Other ops would have 3 registers (18 bits), or 2 registers (12 bits).
> Compare ops could have a 2-bit predicate-destination field.
>
> It is possible that 01:00 (Never Execute) could be used to encode a
> Jumbo Prefix or similar (or, maybe a few unconditional large-immed
> instructions or similar).

Having predication for most ops is just entropy clutter and a waste of
power: it costs more to *not* do an ADD than to do it, so always do it,
and junk the predicates. You need predicates for ops that might do a
hard throw, or that change persistent state like store and control flow;
nowhere else.

>>> Also, the state of SR.T would not be preserved across a function
>>> call, so any logic following the function's return could not be
>>> predicated.
>>
>> This can be architected around; ours is not the only possible way to
>> do it.
>
>
> Yeah. Most likely option would be a callee-save register containing
> predicates or similar. As opposed to a single predicate flag which is
> treated as a scratch value (and only ISRs need to bother with preserving
> it).
>

On 5/23/2021 6:53 AM, EricP wrote:
> Thomas Koenig wrote:
>> To quote the POWER9 User Manual:
>>
>> # The POWER9 core normally ignores any software that attempts to
>> # override the dynamic branch prediction by setting the “a” bit
>> # in the BO field. This is done because historically programmers
>> # and compilers have made poor choices for setting the “a” bit,
>> # which limited the performance of codes where the hardware can
>> # do a superior job of predicting the branches.
>>
>> Having read this: Are branching hints actually useful today?
>>
>> I could see some use in a "almost never used" hint for branches
>> for fatal error messages, maybe.
>
> There is a case for a "predict never" hint where it doesn't matter
> what this conditional branch did the last million times it executed,
> always predict not-taken.
>
> In a spinlock which normally test the lock condition with
> a load before attempting the atomic sequence,
> you never want to speculatively execute into the atomic sequence.
> At a minimum it could cause ping-pong'ing the cache lines.
>
> With Hardware Transactional Memory HTM reading a memory location
> even speculatively might abort another's processors active transaction,
> you don't want to even touch data memory without explicit permission,
> not even prefetching any load or store addresses.
>
> If you don't have a hint to explicitly block speculation at the
> branch then the design would have to use more complicated and
> probably error prone dynamic logic to "deduce" what to do.
>
> Without an explicit "predict never" hint, in the case of HTM
> this looked to me like that speculation might have to shut off
> while a transaction was in progress because there is no way
> to deduce which loads are guarded by a particular condition.
> At a minimum, in an HTM it looked like no loads performed while
> any prior branch was unresolved, not even prefetched into cache
> (or maybe that's a good thing, I don't know).
>
> Predict-never can also be used for rarely executed error handling code.
>
> Predict-always is the complementary case for branching around
> rarely executed error handling code that one wants inline,
> and it doesn't matter what it did the last million times it executed.
>
>

Your HTM breaks on a load? Why? We break only on a colliding store.

Perhaps your HTM's intra-transaction state is visible from outside?

On 5/23/2021 9:07 AM, MitchAlsup wrote:
> On Sunday, May 23, 2021 at 8:54:03 AM UTC-5, EricP wrote:
>
>> There is a case for a "predict never" hint where it doesn't matter
>> what this conditional branch did the last million times it executed,
>> always predict not-taken.
>>
>> In a spinlock which normally test the lock condition with
>> a load before attempting the atomic sequence,
>> you never want to speculatively execute into the atomic sequence.
>> At a minimum it could cause ping-pong'ing the cache lines.
> <
> Yes, the classical test-and-test-and-set. But this only decreases
> bus traffic from BigO(n^3) to BigO(N^2). There are ways to
> decrease bus traffic to BigO( N+3 )
>>
>> With Hardware Transactional Memory HTM reading a memory location
>> even speculatively might abort another's processors active transaction,
>> you don't want to even touch data memory without explicit permission,
>> not even prefetching any load or store addresses.
> <
> This is one of the things WRONG about HTM.
> <
> in My 66000 there is a Exotic Synchronization Method (ESM) which is not
> an HTM but can be used to create HTMs. In ESM, if the ATOMIC event has
> reached a critical juncture (i.e., can complete) the CPUs reaching those
> points gain the ability to NAK interference, allowing these CPUs to complete
> the ATOMIC event, and making the interferers run slower!
>>
>> If you don't have a hint to explicitly block speculation at the
>> branch then the design would have to use more complicated and
>> probably error prone dynamic logic to "deduce" what to do.
> <
> You do not want Naked memory refs to be used to setup or complete
> ATOMIC events. You need to "mark" their participation in the event
> so the machine knows that such an event is going on from the out-
> set.

This also permits you to have intra-transaction stores that are not part
of the transaction, say for logging and debugging, where you don't lock
the log memory.

>> Without an explicit "predict never" hint, in the case of HTM
>> this looked to me like that speculation might have to shut off
>> while a transaction was in progress because there is no way
>> to deduce which loads are guarded by a particular condition.
>> At a minimum, in an HTM it looked like no loads performed while
>> any prior branch was unresolved, not even prefetched into cache
>> (or maybe that's a good thing, I don't know).
> <
> Should an ATOMIC event fail, the compiler needs to know that all
> of the participating memory references are not viable containers
> of data! And not ever use those units of stale data. The only use
> that should be allowed is to print the values that failed.
>>
>> Predict-never can also be used for rarely executed error handling code.
>>
>> Predict-always is the complementary case for branching around
>> rarely executed error handling code that one wants inline,
>> and it doesn't matter what it did the last million times it executed.