Linus Torvalds (torvalds@linux-foundation.org) on 8/16/09 wrote:
---------------------------


>The reason predication needs truly unpredictable cases is
>that when branch prediction works (and it does work
>a lot of the time - it's just not perfect), then a good
>prediction is much more effective than doing both
>sides and choosing one of them dynamically.
>
>Why? Part of it is avoiding the unnecessary work of the
>side that isn't taken, but part of it is also that a
>predicted branch actually removes a data dependency
>entirely, so the dependency chain is literally shorter.
>

Just to nit pick a bit but what you are saying is a consequence of the manner in which predication/branches are used. After all logically a predicated instruction is merely a tidy form of a conditional. However, a short conditional wouldn't be a very useful feature so predication actually functions as a hint to the processor not to guess at the outcome of the conditional but instead fold the conditional into the data dependencies.

>Of course, the downside of branch prediction is the extra
>work when it doesn't work. But on the whole that is a lot
>smaller than the downsides of predications.

Seems to me the real problem with predication is that it doesn't cleanly map onto the content we might wish to communicate to the CPU. It seems to me there are three different notions that predication is blurring together.

1) A hint to the hardware that this conditional is poorly predicted.

2) A way to indicate to the hardware that any dependencies on the branch taken pass through a particular location(s).

For example if we replace a conditional with a predicated mov BX, AX then we've communicated to the hardware that only those instructions with a data dependency on BX (well the result of this mov) have a dependency on the conditional. Anything else we can push through without worrying about the direction taken.

3) An representation of the conditional avoiding any rollbacks in case of misprediction, i.e., both paths cohere with each other.

4) The guarantee that both paths of the conditional are actually taken.

----

4 is just stupid and 1-3 should be divided up to avoid unnecessary waste.

The poor prediction is something that can apply in situations predication is poorly suited and should be indicated by a simple flag.

2-3 should be handled by a different construct that explicitly allows the compiler to indicate the registers/memory locations whose values depend on the branch taken (and we care about).

As I suggested elsewhere there should be a pair of instructions CSPLIT/PHI with semantics as follows:

CSPLIT alt_addr, join_addr
conditionally executes either the instructions between the current location and alt_addr or those between alt_addr and join_addr and then picks up at join_addr.

PHI reg/mem
executed in sequence at join_addr specifies that the reg/mem location should have the value assigned along the correct branch, e.g., if one side of the branch sets EAX=0 and the other EAX=1 then PHI EAX sets it to 0 iff that was the branch taken.

Any other memory/register will have a value as if one or both of the branches executed and need not cohere with each other.

---

Now the hardware can fold the prediction into a data dependency on it's own if it wants. If the branch is predicted to go one way then loads possibly overwritten can be pushed up to the front of the branch and the instructions along the guessed branch actually retired. If later we are discovered to be in error only those instructions with a data dependency on the PHI operand must be rolled back and the correct side of the branch followed.

If this turns out to be a tough branch to predict then the hardware can simply execute both (renamed) paths in parallel from the get go.



>
>(But you can find cases where one or the other is clearly
>better - I'm not saying that predication is bad. I'm just
>saying that it's less useful than you'd think, and it does
>not remove that many branches).
>
>Linus


Seems to me that removing branches is besides the point. The issue is in removing the high mispredict penalty. It seems to me that by explicitly identifying the branch dependent data we gain the best of both worlds.