4 ms·

> Returning to an alternate address shouldn’t be significantly more expensive than returning to the default address, so this has to be cheap. Modern CPUs add c

> Returning to an alternate address shouldn’t be significantly more expensive than returning to the default address, so this has to be cheap. Modern CPUs add complications to arguments like this. Branches stall the execution pipeline, so branch prediction was invented to keep the pipeline flowing. Return instructions are perfectly predicted, which makes them literally free. At the very least, any alternate return scheme has to pay for a full misprediction. That can be expensive.

tsimionescu 2y ago
This doesn't really make sense. The branch predictor relies on a history of previous executions of that branch, or on explicit hints, to decide if a branch will be taken or not. Based on this prediction, the speculative execution hardware then sees the jump (return/panic) and loads the code from that address into the icache. There is 0 difference between `if (condition) jump $panic_recover_address` and `if (condition) jump $function_return_address` in terms of how easy or hard it is to predict or speculatively load based on the prediction.
- codeflo 2y ago
  On x86, ret and call are explicit instructions. Ret always predicts the address of the last call, which is (usually) 100% accurate. Your example of `if (condition) jump $panic_recover_address` contains two branches, either of which can be mispredicted.
  - tsimionescu 2y ago
    No, an unconditional jump to a fixed address can't be mispredicted.
    - codeflo 2y ago
      How can a reusable function have a fixed return address?
      - eptcyka 2y ago
        Because of the stack? It is not fixed, but once you a function is called, the CPU must know where it was called from.
      - tsimionescu 2y ago
        This is a good point that I hadn't considered - these are indirect jumps, and the return instruction has special handling from the processor to compute the address specifically, which a jump to a recover address can't have.
    - bjackman 2y ago
      Yes it can, prediction begins before decode. In general, literally any instruction can be mispredicted, even if it isn't a branch at all, even if there isn't even a instruction there (on x86 where instructions are variable length).
      - ithkuil 2y ago
        For the uninitiated, branch prediction roughly works like this: The CPU fetches instructions from memory well ahead of actually decoding what the instructions are. In case of variable length instruction sets such as x86 that also means the cpu has no ability to "peek ahead" in the instruction stream to find out if there is a branch. But don't despair, there is a trick: Each instruction (obviously) has an address. So if you had an associative memory (think of it as a hash map) that stored a pair of (address of a branch; target address) then you can consult this memory while you're fetching instructions to feed to the decoder stage of the pipeline. When the address of the next instruction you're about to fetch is found in that associative memory you get the address of where the rest of the instruction stream lives. I.e. instead of fetching the next word sequentially you continue fetching from whatever address was found by the lookup. Now, when you actually end up executing the instructions it may turn out that the target address suggested by that lookup memory was wrong. In that case you just flush the pipeline and start fetching again from the actual target (and you update the branch predictor associative memory). This basic model works for conditional branches, unconditional and indirect branches too but in practice there are more tricks. Some indirect jumps like returns exploit the natural call/ret pairing as described elsewhere in this thread. Conditional branch entries may contain an extra bit taken/not-taken etc. But the main idea is more or less this. To "mispredict" an unconditional jump for example all it takes is to modify the code so that the instruction points to a different target. If the branch predictor target address still points to the old target, that address will be prefetchec and a stall will be caused. No big deal in practice.
        hu3 2y ago
        Your explanation is amazing. Thanks How would this happen in practice? > To "mispredict" an unconditional jump for example all it takes is to modify the code so that the instruction points to a different target. Perhaps a jump to a pointer that changed value? Or maybe JIT code that was optimized during runtime?
    - CoastalCoder 2y ago
      > No, an unconditional jump to a fixed address can't be mispredicted. Is that even true if an interrupt triggers after the return instruction prediction?
  - Joker_vD 2y ago
    Sine Intel processors have shadow (call-)stack to ensure control-flow integrity, I imagine they use it to predict the return address as well.
    - gpderetta 2y ago
      Intel (and most CPUs really) have had a "shadow" call stack for ret+call prediction (the Return Stack Buffer) decades before they had the control-flow integrity shadow stack. It is possible that the two stacks are now unified, but I'm not 100% sure. The RSB has 10 or so entries and it is in the critical path, while the integrity stack might be larger and have less strict performance characteristics, so they might be separate objects.
- gpderetta 2y ago
  returns, conditional jumps and indirect jumps have each fairly different prediction profiles. In particular paired call+ret are predicted perfectly at least until the dedicated internal stack doesn't overflow; indirect jumps are, as a general rule, less predictable than conditional jumps as more state (the jump target) need to stored.
- jnordwick 2y ago
  I thought the Branch Target Predictor on x64 was global, not local, and it has to kick in before decode so even direct branches can be mispredicted. Branch prediction is 2 parts - the conditional predictor and the target predictor. The conditional predictor is actually per 64 byte instruction block (so if you have a few branches consecutively they share branch predictor entries and can step on each other. the target predictor uses a global history and needs to happen very early to keep the front end fed.
  - ozgrakkurt 2y ago
    Predicting the branch predictor is extremely difficult because it is complex afaik, it is best to test. All of the interaction between a million caches, predictor, instruction parallelism, different cpus, different code etc. feels like it is impossible to reason about it
- beng-nl 2y ago
  Not that you’re wrong, but Returns aren’t predicted using the branch predictor, but with the RSB (return stack buffer) which stores the return addresses of the current call stack. The x86 optimization manual (starting quite a few years ago) explicitly mentions calls and rets should match for best performance.
- amluto 2y ago
  It may well be possible to do an alternate return, skipping a frame, that is, itself, very reliably predicted correctly. But it still looks like: CALL jump-without-RET and the calls and the rets don’t line up. This defeats the return prediction on the next return.
- IshKebab 2y ago
  Modern CPUs have a "return address stack" which basically mirrors the real stack and allows them to perfectly predict returns (for normal code anyway). First explanation I found on Google. Haven't read it: https://one2bla.me/cs6290/lesson4/return-address-stack.html https://one2bla.me/cs6290/lesson4/return-address-stack.html
meindnoch 2y ago
>Return instructions are perfectly predicted As long as you don't overwrite the return address on the stack.
kaba0 2y ago
But in the given context, returning a Return type will almost by necessity involve a conditional at the caller site, so for an apples to apples comparison that should be compared, not a linear return and nothing else.

tsimionescu 2y ago

This doesn't really make sense. The branch predictor relies on a history of previous executions of that branch, or on explicit hints, to decide if a branch will be taken or not. Based on this prediction, the speculative execution hardware then sees the jump (return/panic) and loads the code from that address into the icache. There is 0 difference between `if (condition) jump $panic_recover_address` and `if (condition) jump $function_return_address` in terms of how easy or hard it is to predict or speculatively load based on the prediction.

codeflo 2y ago
On x86, ret and call are explicit instructions. Ret always predicts the address of the last call, which is (usually) 100% accurate. Your example of `if (condition) jump $panic_recover_address` contains two branches, either of which can be mispredicted.
- tsimionescu 2y ago
  No, an unconditional jump to a fixed address can't be mispredicted.
  - codeflo 2y ago
    How can a reusable function have a fixed return address?
    - eptcyka 2y ago
      Because of the stack? It is not fixed, but once you a function is called, the CPU must know where it was called from.
    - tsimionescu 2y ago
      This is a good point that I hadn't considered - these are indirect jumps, and the return instruction has special handling from the processor to compute the address specifically, which a jump to a recover address can't have.
  - bjackman 2y ago
    Yes it can, prediction begins before decode. In general, literally any instruction can be mispredicted, even if it isn't a branch at all, even if there isn't even a instruction there (on x86 where instructions are variable length).
    - ithkuil 2y ago
      For the uninitiated, branch prediction roughly works like this: The CPU fetches instructions from memory well ahead of actually decoding what the instructions are. In case of variable length instruction sets such as x86 that also means the cpu has no ability to "peek ahead" in the instruction stream to find out if there is a branch. But don't despair, there is a trick: Each instruction (obviously) has an address. So if you had an associative memory (think of it as a hash map) that stored a pair of (address of a branch; target address) then you can consult this memory while you're fetching instructions to feed to the decoder stage of the pipeline. When the address of the next instruction you're about to fetch is found in that associative memory you get the address of where the rest of the instruction stream lives. I.e. instead of fetching the next word sequentially you continue fetching from whatever address was found by the lookup. Now, when you actually end up executing the instructions it may turn out that the target address suggested by that lookup memory was wrong. In that case you just flush the pipeline and start fetching again from the actual target (and you update the branch predictor associative memory). This basic model works for conditional branches, unconditional and indirect branches too but in practice there are more tricks. Some indirect jumps like returns exploit the natural call/ret pairing as described elsewhere in this thread. Conditional branch entries may contain an extra bit taken/not-taken etc. But the main idea is more or less this. To "mispredict" an unconditional jump for example all it takes is to modify the code so that the instruction points to a different target. If the branch predictor target address still points to the old target, that address will be prefetchec and a stall will be caused. No big deal in practice.
      - hu3 2y ago
        Your explanation is amazing. Thanks How would this happen in practice? > To "mispredict" an unconditional jump for example all it takes is to modify the code so that the instruction points to a different target. Perhaps a jump to a pointer that changed value? Or maybe JIT code that was optimized during runtime?
  - CoastalCoder 2y ago
    > No, an unconditional jump to a fixed address can't be mispredicted. Is that even true if an interrupt triggers after the return instruction prediction?
- Joker_vD 2y ago
  Sine Intel processors have shadow (call-)stack to ensure control-flow integrity, I imagine they use it to predict the return address as well.
  - gpderetta 2y ago
    Intel (and most CPUs really) have had a "shadow" call stack for ret+call prediction (the Return Stack Buffer) decades before they had the control-flow integrity shadow stack. It is possible that the two stacks are now unified, but I'm not 100% sure. The RSB has 10 or so entries and it is in the critical path, while the integrity stack might be larger and have less strict performance characteristics, so they might be separate objects.
gpderetta 2y ago
returns, conditional jumps and indirect jumps have each fairly different prediction profiles. In particular paired call+ret are predicted perfectly at least until the dedicated internal stack doesn't overflow; indirect jumps are, as a general rule, less predictable than conditional jumps as more state (the jump target) need to stored.
jnordwick 2y ago
I thought the Branch Target Predictor on x64 was global, not local, and it has to kick in before decode so even direct branches can be mispredicted. Branch prediction is 2 parts - the conditional predictor and the target predictor. The conditional predictor is actually per 64 byte instruction block (so if you have a few branches consecutively they share branch predictor entries and can step on each other. the target predictor uses a global history and needs to happen very early to keep the front end fed.
- ozgrakkurt 2y ago
  Predicting the branch predictor is extremely difficult because it is complex afaik, it is best to test. All of the interaction between a million caches, predictor, instruction parallelism, different cpus, different code etc. feels like it is impossible to reason about it
beng-nl 2y ago
Not that you’re wrong, but Returns aren’t predicted using the branch predictor, but with the RSB (return stack buffer) which stores the return addresses of the current call stack. The x86 optimization manual (starting quite a few years ago) explicitly mentions calls and rets should match for best performance.
amluto 2y ago
It may well be possible to do an alternate return, skipping a frame, that is, itself, very reliably predicted correctly. But it still looks like: CALL jump-without-RET and the calls and the rets don’t line up. This defeats the return prediction on the next return.
IshKebab 2y ago
Modern CPUs have a "return address stack" which basically mirrors the real stack and allows them to perfectly predict returns (for normal code anyway). First explanation I found on Google. Haven't read it: https://one2bla.me/cs6290/lesson4/return-address-stack.html https://one2bla.me/cs6290/lesson4/return-address-stack.html

meindnoch 2y ago

>Return instructions are perfectly predicted As long as you don't overwrite the return address on the stack.

kaba0 2y ago

But in the given context, returning a Return type will almost by necessity involve a conditional at the caller site, so for an apples to apples comparison that should be compared, not a linear return and nothing else.