[WIP] Support MustControl conditional control attribute

[melver]

Summary

[ WIP, only high-level comments for now ]

Introduce a new attribute, 'MustControl'/'mustcontrol', which denotes that a
conditional control statement must result in true control-flow and not
be optimized away. The attribute otherwise has no semantic relevance.

However, the existence of a true branch is of relevance when branch
execution has side-effects on machine state that the programmer is
interested in, for example in OS kernels.

The Linux kernel, for one, relies on the existence of true conditional
branches for the enforcement of memory orders, per Linux-kernel memory
consistency model (LKMM) [1]. With the 'mustcontrol' attribute, Clang
would provide a primitive required for the Linux kernel to ensure a true
branch is emitted without resorting to inline assembly (which often
results in poor codegen). The primitive is simple and low-level enough,
that the compiler can remain blissfully unaware of the LKMM and leave
the semantics of Linux's memory model to the kernel community.

[1] https://lkml.kernel.org/r/[e-mail]

[lebedev.ri]

This is missing langref changes, and a RFC to llvm-dev.
I'm rather skeptical of this.

[melver]

In D103958#2807811, @lebedev.ri wrote:

This is missing langref changes, and a RFC to llvm-dev.

We're not there yet, but will send something. Having real code helped me understand what out the myriad of options that were discussed were actually reasonable to implement. (Perhaps I should have uploaded WIP code elsewhere, sorry about that.)

I'm rather skeptical of this.

We're trying to solve a serious problem, and the Linux kernel is an important usecase. We'd be very glad to hear constructive criticism, the LKML thread is still ongoing: https://lore.kernel.org/linux-arch/[e-mail]/

Thank you.

[jdoerfert]

WIP here is fine, would help to include a test that shows/explains what problem is actually solved though. I don't understand form this patch alone.

[nickdesaulniers]

The first talk from https://www.youtube.com/watch?v=FFjV9f_Ub9o (https://github.com/ClangBuiltLinux/plumbers-2020-slides/blob/master/LPC_2020_--_Dependency_ordering.pdf) might be helpful to link to at some point from the commit message, for a little additional context.

[jdoerfert]

In D103958#2808767, @nickdesaulniers wrote:

The first talk from https://www.youtube.com/watch?v=FFjV9f_Ub9o (https://github.com/ClangBuiltLinux/plumbers-2020-slides/blob/master/LPC_2020_--_Dependency_ordering.pdf) might be helpful to link to at some point from the commit message, for a little additional context.

I read the slides and I'm not sure how this connects. I'll wait for the LangRef and/or IR example :)

[efriedma]

I don't like using metadata like this. Dropping metadata should generally preserve the semantics of the code.

without resorting to inline assembly (which often results in poor codegen).

Could you give an example of the resulting assembly with mustcontrol vs. this patch?

[efriedma]

In D103958#2808861, @efriedma wrote:

without resorting to inline assembly (which often results in poor codegen).

Could you give an example of the resulting assembly with mustcontrol vs. this patch?

Err, I mean, the resulting assembly using the inline asm version, vs. an equivalent construct using mustcontrol.

[melver]

In D103958#2808861, @efriedma wrote:

I don't like using metadata like this. Dropping metadata should generally preserve the semantics of the code.

Anything better for this without introducing new instructions? Would an argument be reasonable?

without resorting to inline assembly (which often results in poor codegen).

Could you give an example of the resulting assembly with mustcontrol vs. this patch?

For one of the pathological cases:

int x, y, z;                                                                                                                                                                                                                                                 
                                                                                                                                                                                                                                                               
int main(int argc, char *argv[]) {                                                                                                                                                                                                                           
    z = 42;                                                                                                                                                                                                                                                    
                                                                                                                                                                                                                                                               
  volatile_if (READ_ONCE(x)) {                                                                                                                                                                                                                               
      WRITE_ONCE(y, z);                                                                                                                                                                                                                                        
    } else {                                                                                                                                                                                                                                                   
      WRITE_ONCE(y, z);                                                                                                                                                                                                                                        
    }                                                                                                                                                                                                                                                          
                                                                                                                                                                                                                                                               
    return 0;                                                                                                                                                                                                                                                  
}

Doing nothing:

define dso_local i32 @main(i32 %argc, i8** nocapture readnone %argv) local_unnamed_addr #0 {
entry:
  store i32 42, i32* @z, align 4, !tbaa !3
  %0 = load volatile i32, i32* @x, align 4, !tbaa !3
  store volatile i32 42, i32* @y, align 4, !tbaa !3
  ret i32 0
}

No branch here.

Their latest proposal using compiler barriers (and not asmgoto):

define dso_local i32 @main(i32 %0, i8** nocapture readnone %1) local_unnamed_addr #0 {
  store i32 42, i32* @z, align 4, !tbaa !2
  %3 = load volatile i32, i32* @x, align 4, !tbaa !2
  %4 = icmp eq i32 %3, 0
  br i1 %4, label %7, label %5

5:                                                ; preds = %2
  tail call void asm sideeffect "", "i,~{memory},~{dirflag},~{fpsr},~{flags}"(i32 0) #1, !srcloc !6                            
  %6 = load i32, i32* @z, align 4, !tbaa !2
  br label %7

7:                                                ; preds = %2, %5
  %8 = phi i32 [ %6, %5 ], [ 42, %2 ]
  store volatile i32 %8, i32* @y, align 4, !tbaa !2
  ret i32 0
}

You can see the unnecessary load to z.

With mustcontrol:

define dso_local i32 @main(i32 %argc, i8** nocapture readnone %argv) local_unnamed_addr #0 {
entry:
  store i32 42, i32* @z, align 4, !tbaa !3
  %0 = load volatile i32, i32* @x, align 4, !tbaa !3
  %tobool.not = icmp eq i32 %0, 0
  br i1 %tobool.not, label %if.end, label %if.then

if.then:                                          ; preds = %entry
  tail call void (...) @llvm.sideeffect(i64 42)
  br label %if.end

if.end:                                           ; preds = %entry, %if.then
  store volatile i32 42, i32* @y, align 4, !tbaa !3
  ret i32 0
}

Of course, the more common case is just

if (READ_ONCE(..)) { WRITE_ONCE(...); }

but as soon as inline asm is involved, the full compiler barrier would also cause any data after the branch to be reloaded.

The bigger worry is that the full compiler barrier does not guarantee emission of a branch, and the asmgoto variant is pretty fragile. arm64 maintainers worry about LTO, and better compiler optimizations. It really begs for compiler support for the architectures where it is relevant. The main one being arm64, which ld->st can be ordered by a control dependency.

While the issue at hand is related to memory models, I've tried to steer clear of the C/C++ memory models because the Linux kernel defines its own memory model. Therefore, defining the new primitive at a lower-level that relates to generated code (closer to 'volatile' or e.g. 'musttail' which inspired the name) is a goal here. This will satisfy the Linux kernel's requirements and can use 'mustcontrol' as a building block for the Linux-kernel memory model (LKMM) [ http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0124r6.html ].

I'm intending to define it as follows:

| Marking a conditional control statement as ``mustcontrol`` indicates that the
| compiler must generate a conditional branch in machine code, and such
| conditional branch is placed *before* conditionally executed instructions. The
| attribute may be ignored if the condition of the control statement is a
| constant expression.
|
| This typically affects optimizations that would cause removal of a conditional
| branch. However, it also ensures that a conditional branch and subsequent
| instructions are not replaced with non-branching conditional instructions.
|
| Requesting the generation of a branch may be required in execution environments
| where execution of a specific conditional branch inhibits speculation or has
| observable side-effects of interest otherwise.

Please bear with me, I'm updating examples and documentation. I didn't think anybody would look at this while [WIP]. :-)
Thanks.

[jdoerfert]

Please bear with me, I'm updating examples and documentation. I didn't think anybody would look at this while [WIP]. :-)

People try to help so you have early design feedback ;)

[melver]

In D103958#2808967, @jdoerfert wrote:

Please bear with me, I'm updating examples and documentation. I didn't think anybody would look at this while [WIP]. :-)

People try to help so you have early design feedback ;)

Thank you for that. The LKML discussion got a little heated, so I worry slightly that underpresenting the issue will cause a bad first impression.

But while we're here:

There is the consideration to make this a __builtin and not an attribute.

AFAIK a __builtin suffers from the usual problem that the information cannot be propagated between TUs:

file1.c:
  bool foo(void) { return __builtin_mustcontrol(READ_ONCE(...)); }

file2.c:
  void bar(void) { if (foo()) { WRITE_ONCE(...); } }

Or is a language builtin that gives you an error when used in the wrong context acceptable? It seems a little odd because I'm unaware of other builtins that do that.

GCC devs expressed that GNU attribute syntax may be abused: https://lkml.kernel.org/r/[e-mail]

The attribute is simpler, and hypothetically, if it were to become part of the language std we'd have to use [[...]] syntax anyway, so the GNU attribute problem seems somewhat artificial to me.

[[mustcontrol]] if (READ_ONCE(...)) { ... }
[[mustcontrol]] while (...) { }

Preferences?

[jdoerfert]

This starts to sound an awful lot like convergent to me, basically: Do not change the control conditions of this call.
Still unsure, maybe you can add a LangRef draft so we know what you try to do, or a nice example what you don't want to happen.

[efriedma]

In D103958#2808966, @melver wrote:

In D103958#2808861, @efriedma wrote:

I don't like using metadata like this. Dropping metadata should generally preserve the semantics of the code.

Anything better for this without introducing new instructions? Would an argument be reasonable?

If we really want to make it part of the branch, maybe add an intrinsic that can be used with callbr. Not something we've done before, but the infrastructure should be mostly there.

That said, I'm not sure this is the best approach. Alternative proposal:

We could add a regular intrinsic. Just ignore the control flow at the IR level, and come up with a straight-line blob that just does the right thing. I think we'd want to actually perform the load as part of the intrinsic, to avoid worrying about the consume dependency. So we'd have an intrinsic "__builtin_load_with_control_dependency()". It would lower to something along the lines of asm("ldr %0, [%1]; cbnz %0, .+4":"=r"(dest):"r"(x):"memory"); on AArch64. The differences between the intrinsic and just using the asm I wrote:

1. We weaken the "memory" clobber to something that more accurately matches what we need.
2. We add a compiler transform to check if the branch is redundant, late in the optimization pipeline, and remove it if it is.

I think this produces the code you want, and it should be easier to understand and maintain.

[melver]

In D103958#2809145, @efriedma wrote:

In D103958#2808966, @melver wrote:

In D103958#2808861, @efriedma wrote:

I don't like using metadata like this. Dropping metadata should generally preserve the semantics of the code.

Anything better for this without introducing new instructions? Would an argument be reasonable?

If we really want to make it part of the branch, maybe add an intrinsic that can be used with callbr. Not something we've done before, but the infrastructure should be mostly there.

That said, I'm not sure this is the best approach. Alternative proposal:

We could add a regular intrinsic. Just ignore the control flow at the IR level, and come up with a straight-line blob that just does the right thing. I think we'd want to actually perform the load as part of the intrinsic, to avoid worrying about the consume dependency. So we'd have an intrinsic "__builtin_load_with_control_dependency()". It would lower to something along the lines of asm("ldr %0, [%1]; cbnz %0, .+4":"=r"(dest):"r"(x):"memory"); on AArch64. The differences between the intrinsic and just using the asm I wrote:

1. We weaken the "memory" clobber to something that more accurately matches what we need.
2. We add a compiler transform to check if the branch is redundant, late in the optimization pipeline, and remove it if it is.

I think this produces the code you want, and it should be easier to understand and maintain.

Interesting, but probably doesn't quite work if I understood right -- however, perhaps it could solve something related (not part of this work, see below [footnote]).

Not every READ_ONCE() the kernel has needs to be a load_with_control_dependency(), which if I read it right, would happen if we just do, e.g.:

#define READ_ONCE __builtin_load_with_control_dependency
int x;
int foo(void) { return READ_ONCE(x); }

And they really want to avoid introducing another set of primitives, like READ_ONCE_CTRL(), because if we did that, I think it'd be reasonable to upgrade all READ_ONCE_CTRL() to acquires and we're done (suggested by Will Deacon in [1]). Yet upgrading all READ_ONCE() to acquire is not acceptable in general (do note, it's not just AArch64, also POWER and Armv7). For now, it'd be good to avoid this -- in particular, existing code like the following would become less clear or less optimal:

x = READ_ONCE(..);
y  = READ_ONCE(..);
... lots of other code ...
if (y) { ... do other stuff ... } // <--- no control dependency here
if (x && y) { WRITE_ONCE(..) } // <-- only want control  dependency here

Which is why the kernel folks probably wouldn't be too happy with more primitives as it likely penalizes more than with just marking the branch itself. Per [1] new load-primitives are probably a last resort assuming the compiler can deliver a nice mechanism to ensure control-dependencies remain (this work here).

Thanks.

---

[1] https://lore.kernel.org/linux-arch/20210607160252.GA7580@willie-the-truck/

[footnote] Re the "memory" clobber, Linus asks for more fine-grained asm clobber: https://lore.kernel.org/linux-arch/CAHk-=[e-mail]/
If you see a way to support this, I think it'd help in other places (e.g. kernel's one-directional memory barriers).

Tangentially, per this presentation:
https://github.com/ClangBuiltLinux/plumbers-2020-slides/blob/master/LPC_2020_--_Dependency_ordering.pdf
there is another problem, which are address dependencies aka memory_order_consume. In reality the kernel wants every READ_ONCE() be something very close to memory_order_consume, with the compiler figuring out the optimal thing to do. Unfortunately, this is not the reality today. Paul McKenney et al. has been exploring this in: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0750r1.html -- but since addr-deps are much less likely to be optimized away, I think the kernel will do nothing about it in the near term. ctrl-deps on the other hand are more of a worry to the Linux kernel community right now.

I can't summarize this well enough here, so I would strongly recommend: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0124r6.html#Control%20Dependencies

[efriedma]

You could break __builtin_load_with_control_dependency(x) into something like __builtin_control_dependency(READ_ONCE(x)). I don't think any transforms will touch that in practice, even if it isn't theoretically sound. The rest of my suggestion still applies to that form, I think. They key point is that the compiler just needs to ensure some branch consumes the loaded value; it doesn't matter which branch it is.

The theoretical problem with separating the load from the branch is that it imposes an implicit contract: the branch has to use the value of the load as input, not an equivalent value produced some other way. This is the general problem with C++11 consume ordering, which nobody has tried to tackle.

re: the memory clobber, LLVM understands acquire/release semantics for atomics; for example, you can write __atomic_signal_fence(3) in clang to get a "release" barrier. (I think that's what the email you linked is asking for?) Adding asm clobbers that are equivalent to the existing fences is probably feasible.

[melver]

In D103958#2809353, @efriedma wrote:

You could break __builtin_load_with_control_dependency(x) into something like __builtin_control_dependency(READ_ONCE(x)). I don't think any transforms will touch that in practice, even if it isn't theoretically sound. The rest of my suggestion still applies to that form, I think. They key point is that the compiler just needs to ensure some branch consumes the loaded value; it doesn't matter which branch it is.

Because the original inline asm version was pretty similar (they just called it volatile_cond()), I think __builtin_control_dependency() is equivalent. Actually a later suggestion just called it __builtin_ctrl_depends(): https://lkml.kernel.org/r/[e-mail]

It was nacked by GCC devs, who expressed concern that it seems impossible to guarantee a branch is emitted but also way too difficult to specify. The emitting-branch part seems straightforward, as you suggested.

I think implementation-wise, we can probably use your idea either way. I just worry about defined semantics, see below.

The theoretical problem with separating the load from the branch is that it imposes an implicit contract: the branch has to use the value of the load as input, not an equivalent value produced some other way. This is the general problem with C++11 consume ordering, which nobody has tried to tackle.

Indeed. Which is why I wanted to steer clear of a __builtin that talks about control-dependencies directly. There are 2 challenges:

1. Defining the value used to establish a control dependency, e.g. the load later writes depend on (kernel only defines writes to be ctrl-dependently ordered).
2. Defining later ops that are control-dependent. With an expression like the __builtin, this could be any operation after, or it becomes too hard to define:

x = __builtin_control_dependency(expr); // __builtin_control_dependency establishes an ordering edge between loads in expr and later ops
y = 1; // control dependently ordered, although there is no explicit control statement yet...
if (x) { z = 1; } // ... this code is only interested in z=1 to be control-dependently ordered.

Both are hard to define, as you suggested it's similar to consume which was also my worry.

Therefore, to get something simple that works and isn't doomed to a definition that is unimplementable, I tried to just talk about the control statement and the fact a branch must be emitted. In theory, (1) might still be a problem, but in practice the compiler has no other way than to use the loaded value if that value was loaded through an __atomic or volatile or similar.

Limiting ourselves to an attribute on control statements solves (2), because we can say that "the conditional branch is placed *before* conditionally executed instructions". Either that, or we make the __builtin give an error if used outside the condition of a control statement.

---

Given we've already gotten this far, I will summarize the options:

A. __builtin_load_with_control_dependency() -- this appears to solve the problem (1) above, but not (2). This approach seems unappealing if we want to solve this for the Linux kernel, because the whole point of compiler support was to avoid more read-primitives (with new primitives they say they'd just upgrade these to acquire and be done with it).

B. __builtin_control_dependency() -- would be nice if this would work, but I think it suffers from problems (1), and (2) above and is very hard to define properly.
B1. Do this but constrain it to only be usable as conditions in control statements, which would solve (2) at least.

C. [[mustcontrol]]:

Marking a conditional control statement as ``mustcontrol`` indicates that the
compiler must generate a conditional branch in machine code, and such
conditional branch is placed *before* conditionally executed instructions. The
attribute may be ignored if the condition of the control statement is a
constant expression.

D. But we can also just rename it to [[control_dependency]] if that's clearer. It looks like it's the same as B1 minus the artificial constraint; implementation should be similar. It'd allow for the same arch-dependent omission if an arch does not care about control dependencies. But I feel that, at least for the Linux kernel, they prefer having as much control over codegen as possible, regardless of arch. Because if there's an arch-agnostic way of doing this, we get it for free for POWER and Armv7.

All we'd like is a robust primitive, without overcomplicating things.

What do you recommend?

Thanks.

[melver]

As promised, some cleanups, docs, and updated test for the current version (no
other major changes yet).

While the identical-writes test is quite contrived, the currently failing
switch test is a more realistic example. The example uses AArch64, where the
optimizer does not emit a branch but instead uses cinc, which would break the
requirement of emitting a real branch.

[efriedma]

Defining the value used to establish a control dependency, e.g. the load later writes depend on (kernel only defines writes to be ctrl-dependently ordered).

[[mustcontrol]] also has this problem.

At the LLVM IR level, if just want to split the load from the control dependency intrinsic, we could define a special kind of load that produces a LLVM IR "token". The control dependency intrinsic then takes the token as an operand, and optimizations understand that they aren't allowed to touch the token.

The problem at that point is, how does clang emit LLVM IR? It would have to do some sort of dataflow analysis to connect the load to the control dependency. And we'd need to define rules for what sort of data/control flow are allowed. That's not impossible, but it's complicated.

2. Defining later ops that are control-dependent. With an expression like the __builtin, this could be any operation after, or it becomes too hard to define:

I don't think this is a problem we need to solve. If the user sticks the builtin in some weird location that doesn't have a branch immediately following it, that's fine. Any branch that depends on a value can enforce a control dependency, so in general, we just insert a no-op branch at the point of the call to the builtin. Like I mentioned before, we can think of removing that no-op branch as an optimization.

---

Whatever we end up doing, I really don't want to mark up LLVM IR branches. I don't want to add more constraints to CFG transforms at the LLVM IR level. The rules are already hard to understand; I don't want to add more weird edge cases. And I don't think it's necessary here.

[melver]

In D103958#2811246, @efriedma wrote:

Defining the value used to establish a control dependency, e.g. the load later writes depend on (kernel only defines writes to be ctrl-dependently ordered).

[[mustcontrol]] also has this problem.

At the LLVM IR level, if just want to split the load from the control dependency intrinsic, we could define a special kind of load that produces a LLVM IR "token". The control dependency intrinsic then takes the token as an operand, and optimizations understand that they aren't allowed to touch the token.

The problem at that point is, how does clang emit LLVM IR? It would have to do some sort of dataflow analysis to connect the load to the control dependency. And we'd need to define rules for what sort of data/control flow are allowed. That's not impossible, but it's complicated.

2. Defining later ops that are control-dependent. With an expression like the __builtin, this could be any operation after, or it becomes too hard to define:

I don't think this is a problem we need to solve. If the user sticks the builtin in some weird location that doesn't have a branch immediately following it, that's fine. Any branch that depends on a value can enforce a control dependency, so in general, we just insert a no-op branch at the point of the call to the builtin. Like I mentioned before, we can think of removing that no-op branch as an optimization.

---

Whatever we end up doing, I really don't want to mark up LLVM IR branches. I don't want to add more constraints to CFG transforms at the LLVM IR level. The rules are already hard to understand; I don't want to add more weird edge cases. And I don't think it's necessary here.

Thanks, all good points. The main thing was that we though it'd be much harder to get a __builtin_control_dependency() right (GCC devs didn't like it). If you think that __builtin_control_dependency() is the cleaner design, then let's try that! From a user's point-of-view, it certainly is more flexible if we can get it!

I'll abandon this change.

Thanks.

[nickdesaulniers]

FWIW, LWN recently published summary of some of the recent discussions on LKML: https://lwn.net/SubscriberLink/860037/aca06acfafce7937/.

clang/include/clang/Basic/Attr.td

 }
 
 def MustTail : StmtAttr {
   let Spellings = [Clang<"musttail">];
   let Documentation = [MustTailDocs];
   let Subjects = SubjectList<[ReturnStmt], ErrorDiag, "return statements">;
 }
 
+def MustControl : StmtAttr {
+  let Spellings = [Clang<"mustcontrol">];
+  let Documentation = [MustControlDocs];
+  let Subjects = SubjectList<[IfStmt, SwitchStmt, ForStmt, WhileStmt, DoStmt],
+                              ErrorDiag, "conditional control statements">;
+}
+
 def FastCall : DeclOrTypeAttr {
   let Spellings = [GCC<"fastcall">, Keyword<"__fastcall">,
                    Keyword<"_fastcall">];
 //  let Subjects = [Function, ObjCMethod];
   let Documentation = [FastCallDocs];
 }
 
 def RegCall : DeclOrTypeAttr {

clang/include/clang/Basic/AttrDocs.td

 qualifiers or array size), including the implicit "this" argument, if any.
 Any variables in scope, including all arguments to the function and the
 return value must be trivially destructible. The calling convention of the
 caller and callee must match, and they must not be variadic functions or have
 old style K&R C function declarations.
   }];
 }
 
+def MustControlDocs : Documentation {
+  let Category = DocCatStmt;
+  let Content = [{
+Marking a conditional control statement as ``mustcontrol`` indicates that the
+compiler must generate a conditional branch in machine code, and such
+conditional branch is placed *before* conditionally executed instructions. The
+attribute may be ignored if the condition of the control statement is a
+constant expression.
+
+This typically affects optimizations that would cause removal of a conditional
+branch. However, it also ensures that a conditional branch and subsequent
+instructions are not replaced with non-branching conditional instructions.
+
+Requesting the generation of a branch may be required in execution environments
+where execution of a specific conditional branch inhibits speculation or has
+observable side-effects of interest otherwise.
+  }];
+}
+
 def AssertCapabilityDocs : Documentation {
   let Category = DocCatFunction;
   let Heading = "assert_capability, assert_shared_capability";
   let Content = [{
 Marks a function that dynamically tests whether a capability is held, and halts
 the program if it is not held.
   }];
 }

clang/lib/CodeGen/CGStmt.cpp

if (getLangOpts().EHAsynch && S.isSideEntry())
     EmitSehCppScopeBegin();
 
   EmitStmt(S.getSubStmt());
 }
 
 void CodeGenFunction::EmitAttributedStmt(const AttributedStmt &S) {
   bool nomerge = false;
   const CallExpr *musttail = nullptr;
+  const Stmt *mustcontrol = nullptr;
 
   for (const auto *A : S.getAttrs()) {
     if (A->getKind() == attr::NoMerge) {
       nomerge = true;
     }
     if (A->getKind() == attr::MustTail) {
       const Stmt *Sub = S.getSubStmt();
       const ReturnStmt *R = cast<ReturnStmt>(Sub);
       musttail = cast<CallExpr>(R->getRetValue()->IgnoreParens());
     }
+    if (A->getKind() == attr::MustControl)
+      mustcontrol = S.getSubStmt();
   }
   SaveAndRestore<bool> save_nomerge(InNoMergeAttributedStmt, nomerge);
   SaveAndRestore<const CallExpr *> save_musttail(MustTailCall, musttail);
+  SaveAndRestore<const Stmt *> save_mustcontrol(MustControlStmt, mustcontrol);
   EmitStmt(S.getSubStmt(), S.getAttrs());
 }
 
 void CodeGenFunction::EmitGotoStmt(const GotoStmt &S) {
   // If this code is reachable then emit a stop point (if generating
   // debug info). We have to do this ourselves because we are on the
   // "simple" statement path.
   if (HaveInsertPoint())
void CodeGenFunction::EmitIfStmt(const IfStmt &S) {
 
   // Prefer the PGO based weights over the likelihood attribute.
   // When the build isn't optimized the metadata isn't used, so don't generate
   // it.
   Stmt::Likelihood LH = Stmt::LH_None;
   uint64_t Count = getProfileCount(S.getThen());
   if (!Count && CGM.getCodeGenOpts().OptimizationLevel)
     LH = Stmt::getLikelihood(S.getThen(), S.getElse());
-  EmitBranchOnBoolExpr(S.getCond(), ThenBlock, ElseBlock, Count, LH);
+  EmitBranchOnBoolExpr(S.getCond(), ThenBlock, ElseBlock, Count, LH,
+                       &S == MustControlStmt);
 
   // Emit the 'then' code.
   EmitBlock(ThenBlock);
+  if (&S == MustControlStmt) {
+    // XXX: Implementation subject to change.
+    // TODO: Make arg unique, so that optimizer doesn't get the bright idea to
+    // collapse nested mustcontrol statement blocks.
+    // TODO: Make LLVM emit this during optimization, so that mustcontrol
+    // doesn't just work for Clang.
+    Builder.CreateCall(CGM.getIntrinsic(llvm::Intrinsic::sideeffect),
+                       {llvm::ConstantInt::get(IntPtrTy, 42)});
+  }
+
   incrementProfileCounter(&S);
   {
     RunCleanupsScope ThenScope(*this);
     EmitStmt(S.getThen());
   }
   EmitBranch(ContBlock);
 
   // Emit the 'else' code if present.

clang/lib/CodeGen/CodeGenFunction.h

public:
 
   /// True if the current statement has nomerge attribute.
   bool InNoMergeAttributedStmt = false;
 
   // The CallExpr within the current statement that the musttail attribute
   // applies to.  nullptr if there is no 'musttail' on the current statement.
   const CallExpr *MustTailCall = nullptr;
 
+  // The Stmt within the current statement that the mustcontrol attribute
+  // applies to. nullptr if there is no 'mustcontrol' on the current statement.
+  const Stmt *MustControlStmt = nullptr;
+
   /// Returns true if a function must make progress, which means the
   /// mustprogress attribute can be added.
   bool checkIfFunctionMustProgress() {
     if (CGM.getCodeGenOpts().getFiniteLoops() ==
         CodeGenOptions::FiniteLoopsKind::Never)
       return false;
 
     // C++11 and later guarantees that a thread eventually will do one of the
public:
 
   /// EmitBranchOnBoolExpr - Emit a branch on a boolean condition (e.g. for an
   /// if statement) to the specified blocks.  Based on the condition, this might
   /// try to simplify the codegen of the conditional based on the branch.
   /// TrueCount should be the number of times we expect the condition to
   /// evaluate to true based on PGO data.
   void EmitBranchOnBoolExpr(const Expr *Cond, llvm::BasicBlock *TrueBlock,
                             llvm::BasicBlock *FalseBlock, uint64_t TrueCount,
-                            Stmt::Likelihood LH = Stmt::LH_None);
+                            Stmt::Likelihood LH = Stmt::LH_None,
+                            bool MustControl = false);
 
   /// Given an assignment `*LHS = RHS`, emit a test that checks if \p RHS is
   /// nonnull, if \p LHS is marked _Nonnull.
   void EmitNullabilityCheck(LValue LHS, llvm::Value *RHS, SourceLocation Loc);
 
   /// An enumeration which makes it easier to specify whether or not an
   /// operation is a subtraction.
   enum { NotSubtraction = false, IsSubtraction = true };

clang/lib/CodeGen/CodeGenFunction.cpp

void CodeGenFunction::EmitBranchToCounterBlock(
   // Go to the next block.
   EmitBranch(NextBlock);
 }
 
 /// EmitBranchOnBoolExpr - Emit a branch on a boolean condition (e.g. for an if
 /// statement) to the specified blocks.  Based on the condition, this might try
 /// to simplify the codegen of the conditional based on the branch.
 /// \param LH The value of the likelihood attribute on the True branch.
-void CodeGenFunction::EmitBranchOnBoolExpr(const Expr *Cond,
-                                           llvm::BasicBlock *TrueBlock,
-                                           llvm::BasicBlock *FalseBlock,
-                                           uint64_t TrueCount,
-                                           Stmt::Likelihood LH) {
+void CodeGenFunction::EmitBranchOnBoolExpr(
+    const Expr *Cond, llvm::BasicBlock *TrueBlock, llvm::BasicBlock *FalseBlock,
+    uint64_t TrueCount, Stmt::Likelihood LH, bool MustControl) {
   Cond = Cond->IgnoreParens();
 
   if (const BinaryOperator *CondBOp = dyn_cast<BinaryOperator>(Cond)) {
 
     // Handle X && Y in a condition.
     if (CondBOp->getOpcode() == BO_LAnd) {
       // If we have "1 && X", simplify the code.  "0 && X" would have constant
       // folded if the case was simple enough.
void CodeGenFunction::EmitBranchOnBoolExpr(
 
   // Emit the code with the fully general case.
   llvm::Value *CondV;
   {
     ApplyDebugLocation DL(*this, Cond);
     CondV = EvaluateExprAsBool(Cond);
   }
 
+  llvm::MDBuilder MDHelper(getLLVMContext());
   llvm::MDNode *Weights = nullptr;
   llvm::MDNode *Unpredictable = nullptr;
+  llvm::MDNode *MustControlMD = nullptr;
 
   // If the branch has a condition wrapped by __builtin_unpredictable,
   // create metadata that specifies that the branch is unpredictable.
   // Don't bother if not optimizing because that metadata would not be used.
   auto *Call = dyn_cast<CallExpr>(Cond->IgnoreImpCasts());
   if (Call && CGM.getCodeGenOpts().OptimizationLevel != 0) {
     auto *FD = dyn_cast_or_null<FunctionDecl>(Call->getCalleeDecl());
-    if (FD && FD->getBuiltinID() == Builtin::BI__builtin_unpredictable) {
-      llvm::MDBuilder MDHelper(getLLVMContext());
+    if (FD && FD->getBuiltinID() == Builtin::BI__builtin_unpredictable)
       Unpredictable = MDHelper.createUnpredictable();
-    }
-  }
 
   // If there is a Likelihood knowledge for the cond, lower it.
   // Note that if not optimizing this won't emit anything.
   llvm::Value *NewCondV = emitCondLikelihoodViaExpectIntrinsic(CondV, LH);
   if (CondV != NewCondV)
     CondV = NewCondV;
   else {
     // Otherwise, lower profile counts. Note that we do this even at -O0.
     uint64_t CurrentCount = std::max(getCurrentProfileCount(), TrueCount);
     Weights = createProfileWeights(TrueCount, CurrentCount - TrueCount);
   }
 
-  Builder.CreateCondBr(CondV, TrueBlock, FalseBlock, Weights, Unpredictable);
+  if (MustControl)
+    MustControlMD = MDHelper.createMustControl();
+
+  Builder.CreateCondBr(CondV, TrueBlock, FalseBlock, Weights, Unpredictable,
+                       MustControlMD);
 }
 
 /// ErrorUnsupported - Print out an error that codegen doesn't support the
 /// specified stmt yet.
 void CodeGenFunction::ErrorUnsupported(const Stmt *S, const char *Type) {
   CGM.ErrorUnsupported(S, Type);
 }
 

clang/lib/Sema/SemaStmtAttr.cpp

static Attr *handleUnlikely(Sema &S, Stmt *St, const ParsedAttr &A,
                             SourceRange Range) {
 
   if (!S.getLangOpts().CPlusPlus20 && A.isCXX11Attribute() && !A.getScopeName())
     S.Diag(A.getLoc(), diag::ext_cxx20_attr) << A << Range;
 
   return ::new (S.Context) UnlikelyAttr(S.Context, A);
 }
 
+static Attr *handleMustControl(Sema &S, Stmt *St, const ParsedAttr &A,
+                               SourceRange Range) {
+  return ::new (S.Context) MustControlAttr(S.Context, A);
+}
+
 #define WANT_STMT_MERGE_LOGIC
 #include "clang/Sema/AttrParsedAttrImpl.inc"
 #undef WANT_STMT_MERGE_LOGIC
 
 static void
 CheckForIncompatibleAttributes(Sema &S,
                                const SmallVectorImpl<const Attr *> &Attrs) {
   // The vast majority of attributed statements will only have one attribute
static Attr *ProcessStmtAttribute(Sema &S, Stmt *St, const ParsedAttr &A,
   case ParsedAttr::AT_NoMerge:
     return handleNoMergeAttr(S, St, A, Range);
   case ParsedAttr::AT_MustTail:
     return handleMustTailAttr(S, St, A, Range);
   case ParsedAttr::AT_Likely:
     return handleLikely(S, St, A, Range);
   case ParsedAttr::AT_Unlikely:
     return handleUnlikely(S, St, A, Range);
+  case ParsedAttr::AT_MustControl:
+    return handleMustControl(S, St, A, Range);
   default:
     // N.B., ClangAttrEmitter.cpp emits a diagnostic helper that ensures a
     // declaration attribute is not written on a statement, but this code is
     // needed for attributes in Attr.td that do not list any subjects.
     S.Diag(A.getRange().getBegin(), diag::err_decl_attribute_invalid_on_stmt)
         << A << St->getBeginLoc();
     return nullptr;
   }

clang/test/CodeGenCXX/attr-mustcontrol.cpp

+// RUN: %clang_cc1 -O2 -S -emit-llvm %s -triple x86_64-unknown-linux-gnu -o - | FileCheck %s
+// RUN: %clang_cc1 -O2 -S -emit-llvm %s -triple x86_64-unknown-linux-gnu -o - | opt -verify
+//
+// TODO: move to .ll test
+// RUN: %clang_cc1 -O2 -S %s -triple aarch64-unknown-linux-gnu -o - | FileCheck %s -check-prefix=ARM
+
+#if __has_attribute(mustcontrol)
+#define mustcontrol [[clang::mustcontrol]]
+#else
+#error "mustcontrol not supported!"
+#endif
+
+volatile int x, y;
+int z;
+
+// CHECK-LABEL: define{{.*}}IfThenIdenticalWrites
+void IfThenIdenticalWrites() {
+  z = 42;
+
+  // CHECK: br{{.*}}mustcontrol
+  // ARM: cbz
+  mustcontrol if (x) {
+    y = z;
+  } else {
+    y = z;
+  }
+}
+
+// CHECK-LABEL: define{{.*}}SupportWhile
+void SupportWhile() {
+  mustcontrol while (x) { y = 1; }
+}
+
+// CHECK-LABEL: define{{.*}}SupportFor
+void SupportFor() {
+  mustcontrol for (; x; y++) { }
+}
+
+// FIXME: This test currently fails because the optimizer turns the switch into
+// a cinc!!!
+//
+// CHECK-LABEL: define{{.*}}SupportSwitch
+// ARM-LABEL: _Z13SupportSwitchv:
+void SupportSwitch() {
+  // ARM-NOT: cinc
+  mustcontrol switch (x) {
+    case 0:
+      y = 1;
+      break;
+    default:
+      y = 2;
+      break;
+  }
+}

llvm/include/llvm/IR/FixedMetadataKinds.def

 LLVM_FIXED_MD_KIND(MD_callees, "callees", 23)
 LLVM_FIXED_MD_KIND(MD_irr_loop, "irr_loop", 24)
 LLVM_FIXED_MD_KIND(MD_access_group, "llvm.access.group", 25)
 LLVM_FIXED_MD_KIND(MD_callback, "callback", 26)
 LLVM_FIXED_MD_KIND(MD_preserve_access_index, "llvm.preserve.access.index", 27)
 LLVM_FIXED_MD_KIND(MD_vcall_visibility, "vcall_visibility", 28)
 LLVM_FIXED_MD_KIND(MD_noundef, "noundef", 29)
 LLVM_FIXED_MD_KIND(MD_annotation, "annotation", 30)
+LLVM_FIXED_MD_KIND(MD_mustcontrol, "mustcontrol", 31)

llvm/include/llvm/IR/IRBuilder.h

private:
 
   Value *getCastedInt8PtrValue(Value *Ptr);
 
   //===--------------------------------------------------------------------===//
   // Instruction creation methods: Terminators
   //===--------------------------------------------------------------------===//
 
 private:
-  /// Helper to add branch weight and unpredictable metadata onto an
-  /// instruction.
+  /// Helper to add branch weight, unpredictable, and mustcontrol metadata onto
+  /// an instruction.
   /// \returns The annotated instruction.
   template <typename InstTy>
-  InstTy *addBranchMetadata(InstTy *I, MDNode *Weights, MDNode *Unpredictable) {
+  InstTy *addBranchMetadata(InstTy *I, MDNode *Weights, MDNode *Unpredictable,
+                            MDNode *MustControl) {
     if (Weights)
       I->setMetadata(LLVMContext::MD_prof, Weights);
     if (Unpredictable)
       I->setMetadata(LLVMContext::MD_unpredictable, Unpredictable);
+    if (MustControl)
+      I->setMetadata(LLVMContext::MD_mustcontrol, MustControl);
     return I;
   }
 
 public:
   /// Create a 'ret void' instruction.
   ReturnInst *CreateRetVoid() {
     return Insert(ReturnInst::Create(Context));
   }
public:
   BranchInst *CreateBr(BasicBlock *Dest) {
     return Insert(BranchInst::Create(Dest));
   }
 
   /// Create a conditional 'br Cond, TrueDest, FalseDest'
   /// instruction.
   BranchInst *CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False,
                            MDNode *BranchWeights = nullptr,
-                           MDNode *Unpredictable = nullptr) {
+                           MDNode *Unpredictable = nullptr,
+                           MDNode *MustControl = nullptr) {
     return Insert(addBranchMetadata(BranchInst::Create(True, False, Cond),
-                                    BranchWeights, Unpredictable));
+                                    BranchWeights, Unpredictable, MustControl));
   }
 
   /// Create a conditional 'br Cond, TrueDest, FalseDest'
   /// instruction. Copy branch meta data if available.
   BranchInst *CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False,
                            Instruction *MDSrc) {
     BranchInst *Br = BranchInst::Create(True, False, Cond);
     if (MDSrc) {
-      unsigned WL[4] = {LLVMContext::MD_prof, LLVMContext::MD_unpredictable,
-                        LLVMContext::MD_make_implicit, LLVMContext::MD_dbg};
-      Br->copyMetadata(*MDSrc, makeArrayRef(&WL[0], 4));
+      unsigned WL[5] = {LLVMContext::MD_prof, LLVMContext::MD_unpredictable,
+                        LLVMContext::MD_make_implicit, LLVMContext::MD_dbg,
+                        LLVMContext::MD_mustcontrol};
+      Br->copyMetadata(*MDSrc, makeArrayRef(&WL[0], 5));
     }
     return Insert(Br);
   }
 
   /// Create a switch instruction with the specified value, default dest,
   /// and with a hint for the number of cases that will be added (for efficient
   /// allocation).
   SwitchInst *CreateSwitch(Value *V, BasicBlock *Dest, unsigned NumCases = 10,
                            MDNode *BranchWeights = nullptr,
-                           MDNode *Unpredictable = nullptr) {
+                           MDNode *Unpredictable = nullptr,
+                           MDNode *MustControl = nullptr) {
     return Insert(addBranchMetadata(SwitchInst::Create(V, Dest, NumCases),
-                                    BranchWeights, Unpredictable));
+                                    BranchWeights, Unpredictable, MustControl));
   }
 
   /// Create an indirect branch instruction with the specified address
   /// operand, with an optional hint for the number of destinations that will be
   /// added (for efficient allocation).
   IndirectBrInst *CreateIndirectBr(Value *Addr, unsigned NumDests = 10) {
     return Insert(IndirectBrInst::Create(Addr, NumDests));
   }

llvm/include/llvm/IR/Intrinsics.td

 
 // NOP: calls/invokes to this intrinsic are removed by codegen
 def int_donothing : DefaultAttrsIntrinsic<[], [], [IntrNoMem, IntrWillReturn]>;
 
 // This instruction has no actual effect, though it is treated by the optimizer
 // has having opaque side effects. This may be inserted into loops to ensure
 // that they are not removed even if they turn out to be empty, for languages
 // which specify that infinite loops must be preserved.
-def int_sideeffect : DefaultAttrsIntrinsic<[], [], [IntrInaccessibleMemOnly, IntrWillReturn]>;
+def int_sideeffect : DefaultAttrsIntrinsic<[], [llvm_vararg_ty],
+                                           [IntrInaccessibleMemOnly, IntrWillReturn]>;
 
 // The pseudoprobe intrinsic works as a place holder to the block it probes.
 // Like the sideeffect intrinsic defined above, this intrinsic is treated by the 
 // optimizer as having opaque side effects so that it won't be get rid of or moved 
 // out of the block it probes.
 def int_pseudoprobe : Intrinsic<[], [llvm_i64_ty, llvm_i64_ty, llvm_i32_ty, llvm_i64_ty],
                                     [IntrInaccessibleMemOnly, IntrWillReturn]>;
 

llvm/include/llvm/IR/MDBuilder.h

public:
   MDNode *createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight);
 
   /// Return metadata containing a number of branch weights.
   MDNode *createBranchWeights(ArrayRef<uint32_t> Weights);
 
   /// Return metadata specifying that a branch or switch is unpredictable.
   MDNode *createUnpredictable();
 
+  /// Return metadata specifying that a branch or switch must not be removed.
+  MDNode *createMustControl();
+
   /// Return metadata containing the entry \p Count for a function, a boolean
   /// \Synthetic indicating whether the counts were synthetized, and the
   /// GUIDs stored in \p Imports that need to be imported for sample PGO, to
   /// enable the same inlines as the profiled optimized binary
   MDNode *createFunctionEntryCount(uint64_t Count, bool Synthetic,
                                    const DenseSet<GlobalValue::GUID> *Imports);
 
   /// Return metadata containing the section prefix for a function.

llvm/lib/CodeGen/BranchFolding.cpp

bool BranchFolder::OptimizeBranches(MachineFunction &MF) {
   }
 
   return MadeChange;
 }
 
 // Blocks should be considered empty if they contain only debug info;
 // else the debug info would affect codegen.
 static bool IsEmptyBlock(MachineBasicBlock *MBB) {
-  return MBB->getFirstNonDebugInstr(true) == MBB->end();
+  if (MBB->getFirstNonDebugInstr(true) != MBB->end())
+    return false;
+
+  // Even though this block is empty, check if we should preserve it.
+  // XXX: Implementation subject to change.
+  if (const auto *BB = MBB->getBasicBlock()) {
+    for (const BasicBlock *PredBB : predecessors(BB)) {
+      const auto *PredBr = dyn_cast<BranchInst>(PredBB->getTerminator());
+      if (PredBr && PredBr->getMetadata(LLVMContext::MD_mustcontrol))
+        return false;
+    }
+  }
+
+  return true;
 }
 
 // Blocks with only debug info and branches should be considered the same
 // as blocks with only branches.
 static bool IsBranchOnlyBlock(MachineBasicBlock *MBB) {
   MachineBasicBlock::iterator I = MBB->getFirstNonDebugInstr();
   assert(I != MBB->end() && "empty block!");
   return I->isBranch();

llvm/lib/IR/IRBuilder.cpp

if (auto *CC = dyn_cast<Constant>(C))
     if (auto *TC = dyn_cast<Constant>(True))
       if (auto *FC = dyn_cast<Constant>(False))
         return Insert(Folder.CreateSelect(CC, TC, FC), Name);
 
   SelectInst *Sel = SelectInst::Create(C, True, False);
   if (MDFrom) {
     MDNode *Prof = MDFrom->getMetadata(LLVMContext::MD_prof);
     MDNode *Unpred = MDFrom->getMetadata(LLVMContext::MD_unpredictable);
-    Sel = addBranchMetadata(Sel, Prof, Unpred);
+    Sel = addBranchMetadata(Sel, Prof, Unpred, nullptr /*TODO*/);
   }
   if (isa<FPMathOperator>(Sel))
     setFPAttrs(Sel, nullptr /* MDNode* */, FMF);
   return Insert(Sel, Name);
 }
 
 Value *IRBuilderBase::CreatePtrDiff(Value *LHS, Value *RHS,
                                     const Twine &Name) {

llvm/lib/IR/MDBuilder.cpp

MDNode *MDBuilder::createBranchWeights(ArrayRef<uint32_t> Weights) {
 
   return MDNode::get(Context, Vals);
 }
 
 MDNode *MDBuilder::createUnpredictable() {
   return MDNode::get(Context, None);
 }
 
+MDNode *MDBuilder::createMustControl() { return MDNode::get(Context, None); }
+
 MDNode *MDBuilder::createFunctionEntryCount(
     uint64_t Count, bool Synthetic,
     const DenseSet<GlobalValue::GUID> *Imports) {
   Type *Int64Ty = Type::getInt64Ty(Context);
   SmallVector<Metadata *, 8> Ops;
   if (Synthetic)
     Ops.push_back(createString("synthetic_function_entry_count"));
   else