[RFC] Consistent branches support in LLVM

IR & Optimizations
1

Hello everyone,
I would like to propose __builtin_consistent, MD_consistent metadata, MIFlag::Consistent flag and additional argument to removeBranch,insertBranch methods to support consistent branches.

Motivation

AArch64 2021 extensions introduced hinted conditional branches (FEAT_HBC)

BC.<cond> <label>

instructions.
The hint indicates that that branch is very consistent in its behaviour and very likely to always go in the same direction.

Proposal

To support generation of such consistent branches new builtin __builtin_consistent was added:

  if (__builtin_consistent(x > 0)) {
    foo();
  }

It is used to specify that branches or switches having expression from it as condition are consistent.

The builtin set consistent metadata MD_consistent to instructions accordingly, which is taken into account and inherited by control flow optimizations. For this purpose consistent flag as argument was added to removeBranch and insertBranch target methods. Consistency also inherited to machine instructions level MIFlag::Consistent and on AArch64 target with FEAT_HBC for consistent branches BC.cond instructions are generated.

Pull request

2

Naive question: Don’t we already have likely/unlikely annotations for this kind of thing?

1 Like
3

I guess likely/unlikely specifies which way the branch will go, while consistent only seems to state that it goes the same way most of the time.

1 Like
4

I think the intent of the new builtin is a way to say “the branch will go one way or the other, but I don’t know which.” But, IMO, I’m not sure I really see the use of this as a frontend feature.

It seems to me that we should just use the existing branch_weights data that comes from __builtin_expect/__builtin_expect_with_probability to decide to emit a consistent-branch instruction in the backend, rather than introducing a new __builtin_consistent operation, even though the latter does, in theory, express something slightly different.

1 Like
5

In general, you can’t replace all usage of this with __builtin_expect. For example, suppose you’re doing runtime CPU detection to choose one path or another. The branch is predictable in the sense that it always goes the same way, but it doesn’t make sense to say one path is more likely.

I guess we can use __builtin_expect as a hint for consistent branches, though; if you’re using __builtin_expect, probably the branch consistently branches towards the likely side, so we could use the “consistent” branch in the generated assembly. And probably that does cover most realistic uses.

It might be worth considering whether any optimizations could benefit from “consistent” markings; certain optimizations, like heuristics for flattening ccontrol flow, care whether the branch is predictable, not which way it goes goes any specific way.

1 Like
6

As a counterpoint: in the linux kernel, they have a “static branch” mechanism, used for such CPU-detection cases. This mechanism arranges to patch the instruction stream at boot time (and potentially at runtime, in some use-cases), to either have an unconditional branch or a nop. No conditional branch is ever used, so no condition needs to be evaluated at runtime. This is the epitome of a “consistent branch”! Yet, interestingly, the abstraction provided consists of a pair of APIs: static_branch_likely and static_branch_unlikely. There is no API for “I cannot guess which direction is more likely to be consistently taken”!

7

my main input is: for an embedded/bare metal application it is hard to know the behavior of the branch with high accuracy, and so if we get it wrong it may hurt the performance of the application. so most of the time we may not use this builtin if it were available to us.

1 Like