llvm dev - May 2016 - RFC: callee saved register verifier

Hi,

This is a proposal to introduce a mechanism to LLVM that uses runtime
instrumentation to verify that a call target preserves all of the
registers it says it does.  Internally, we have a diverse set of
calling conventions for runtime functions that get called from LLVM
compiled code, and having some sort of validation mechanism will give
us more confidence in selecting aggressive calling conventions for
these.

The general idea is this: before every call store a cookie in all the
registers that the call is supposed to preserve, and after the call
returns, assert that the supposedly callee saved registers weren't
clobbered.  So for a call target that respects the C calling
convention, we'll generate something like:

   movabsq $0xCA5FCA5FCA5FCA5F, %rbp
   movabsq $0xCA5FCA5FCA5FCA5F, %rbx  # can also be movq %rbp, %rbx etc.
   movabsq $0xCA5FCA5FCA5FCA5F, %r12
   movabsq $0xCA5FCA5FCA5FCA5F, %r13
   movabsq $0xCA5FCA5FCA5FCA5F, %r14
   movabsq $0xCA5FCA5FCA5FCA5F, %r15
   callq   foo
   movabsq $0xCA5FCA5FCA5FCA5F, %rax
   cmpq    %rax, %rbp
   jne     .LBB1_5
   movabsq $0xCA5FCA5FCA5FCA5F, %rax
   cmpq    %rax, %rbx
   jne     .LBB1_5
   movabsq $0xCA5FCA5FCA5FCA5F, %rax
   cmpq    %rax, %r12
   jne     .LBB1_5
   movabsq $0xCA5FCA5FCA5FCA5F, %rax
   cmpq    %rax, %r13
   jne     .LBB1_5
   movabsq $0xCA5FCA5FCA5FCA5F, %rax
   cmpq    %rax, %r14
   jne     .LBB1_5
   movabsq $0xCA5FCA5FCA5FCA5F, %rax
   cmpq    %rax, %r15
   jne     .LBB1_5


The 0xCA5FCA5FCA5FCA5F cookie was selected arbitrarily, but in general
it can be anything that the call target is unlikely to clobber a CSR
with (so it shouldn't be 0, 1, -1 etc.).

This isn't intended to be fast, but is something you turn on in a slow
"validate corner cases" mode.  I think for this to be practical
we'll
need to be able to switch this on and off per calling convention,
since I suspect doing this for every call will be impractically slow,
even for a validation run.

Does the general idea sound reasonable?

Note: the focus here is **not** verifying the register allocator or
any other part of _LLVM_, but to verify that e.g. a custom calling
convention that says that a call target preserves %r10 actually does
preserve %r10.  This is the compiler enforcing a contract, just at a
very low level.


Implementation wise, I have a rough prototype that works by running a
MachineFunctionPass before register allocation that emits the
necessary MachineInstrs / control flow to make this happen.  Is that a
right way to solve the problem?  If so, I'll clean up what I have and
put it up for review on llvm-commits.  If there are better ways to do
this, then I'm happy to hear them.

-- Sanjoy

Hi Sanjay,

> On May 13, 2016, at 3:32 PM, Sanjoy Das <sanjoy at
playingwithpointers.com> wrote:
> 
> Hi,
> 
> This is a proposal to introduce a mechanism to LLVM that uses runtime
> instrumentation to verify that a call target preserves all of the
> registers it says it does.  Internally, we have a diverse set of
> calling conventions for runtime functions that get called from LLVM
> compiled code, and having some sort of validation mechanism will give
> us more confidence in selecting aggressive calling conventions for
> these.
> 
> The general idea is this: before every call store a cookie in all the
> registers that the call is supposed to preserve, and after the call
> returns, assert that the supposedly callee saved registers weren't
> clobbered.  So for a call target that respects the C calling
> convention, we'll generate something like:
> 
>  movabsq $0xCA5FCA5FCA5FCA5F, %rbp
>  movabsq $0xCA5FCA5FCA5FCA5F, %rbx  # can also be movq %rbp, %rbx etc.
>  movabsq $0xCA5FCA5FCA5FCA5F, %r12
>  movabsq $0xCA5FCA5FCA5FCA5F, %r13
>  movabsq $0xCA5FCA5FCA5FCA5F, %r14
>  movabsq $0xCA5FCA5FCA5FCA5F, %r15
>  callq   foo
>  movabsq $0xCA5FCA5FCA5FCA5F, %rax
>  cmpq    %rax, %rbp
>  jne     .LBB1_5
>  movabsq $0xCA5FCA5FCA5FCA5F, %rax
>  cmpq    %rax, %rbx
>  jne     .LBB1_5
>  movabsq $0xCA5FCA5FCA5FCA5F, %rax
>  cmpq    %rax, %r12
>  jne     .LBB1_5
>  movabsq $0xCA5FCA5FCA5FCA5F, %rax
>  cmpq    %rax, %r13
>  jne     .LBB1_5
>  movabsq $0xCA5FCA5FCA5FCA5F, %rax
>  cmpq    %rax, %r14
>  jne     .LBB1_5
>  movabsq $0xCA5FCA5FCA5FCA5F, %rax
>  cmpq    %rax, %r15
>  jne     .LBB1_5
> 
> 
> The 0xCA5FCA5FCA5FCA5F cookie was selected arbitrarily, but in general
> it can be anything that the call target is unlikely to clobber a CSR
> with (so it shouldn't be 0, 1, -1 etc.).
> 
> This isn't intended to be fast, but is something you turn on in a slow
> "validate corner cases" mode.  I think for this to be practical
we'll
> need to be able to switch this on and off per calling convention,
> since I suspect doing this for every call will be impractically slow,
> even for a validation run.
> 
> Does the general idea sound reasonable?
The solution definitely solves your problems, I just wonder in what “corner
case” mode this even makes sense.
> 
> Note: the focus here is **not** verifying the register allocator or
> any other part of _LLVM_, but to verify that e.g. a custom calling
> convention that says that a call target preserves %r10 actually does
> preserve %r10.  This is the compiler enforcing a contract, just at a
> very low level.
You mean with code generated by another compiler/handwritten, because otherwise,
this is pretty easy to verify in the machine verifier :).
(We probably do not verify that though, but we should.)
Thus, could you elaborate on the use cases.
> 
> 
> Implementation wise, I have a rough prototype that works by running a
> MachineFunctionPass before register allocation that emits the
> necessary MachineInstrs / control flow to make this happen.  Is that a
> right way to solve the problem?
I’d say yes, assuming the use cases do not involve llvm, otherwise the verifier
approach seems preferable to me.
> If so, I'll clean up what I have and
> put it up for review on llvm-commits.  If there are better ways to do
> this, then I'm happy to hear them.
> 
> -- Sanjoy
Cheers,
-Quentin

On Fri, May 13, 2016 at 3:45 PM, Quentin Colombet via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Hi Sanjay,
>
>
> > On May 13, 2016, at 3:32 PM, Sanjoy Das <sanjoy at
playingwithpointers.com>
> wrote:
> >
> > Hi,
> >
> > This is a proposal to introduce a mechanism to LLVM that uses runtime
> > instrumentation to verify that a call target preserves all of the
> > registers it says it does.  Internally, we have a diverse set of
> > calling conventions for runtime functions that get called from LLVM
> > compiled code, and having some sort of validation mechanism will give
> > us more confidence in selecting aggressive calling conventions for
> > these.
> >
> > The general idea is this: before every call store a cookie in all the
> > registers that the call is supposed to preserve, and after the call
> > returns, assert that the supposedly callee saved registers weren't
> > clobbered.  So for a call target that respects the C calling
> > convention, we'll generate something like:
> >
> >  movabsq $0xCA5FCA5FCA5FCA5F, %rbp
> >  movabsq $0xCA5FCA5FCA5FCA5F, %rbx  # can also be movq %rbp, %rbx etc.
> >  movabsq $0xCA5FCA5FCA5FCA5F, %r12
> >  movabsq $0xCA5FCA5FCA5FCA5F, %r13
> >  movabsq $0xCA5FCA5FCA5FCA5F, %r14
> >  movabsq $0xCA5FCA5FCA5FCA5F, %r15
> >  callq   foo
> >  movabsq $0xCA5FCA5FCA5FCA5F, %rax
> >  cmpq    %rax, %rbp
> >  jne     .LBB1_5
> >  movabsq $0xCA5FCA5FCA5FCA5F, %rax
> >  cmpq    %rax, %rbx
> >  jne     .LBB1_5
> >  movabsq $0xCA5FCA5FCA5FCA5F, %rax
> >  cmpq    %rax, %r12
> >  jne     .LBB1_5
> >  movabsq $0xCA5FCA5FCA5FCA5F, %rax
> >  cmpq    %rax, %r13
> >  jne     .LBB1_5
> >  movabsq $0xCA5FCA5FCA5FCA5F, %rax
> >  cmpq    %rax, %r14
> >  jne     .LBB1_5
> >  movabsq $0xCA5FCA5FCA5FCA5F, %rax
> >  cmpq    %rax, %r15
> >  jne     .LBB1_5
> >
> >
> > The 0xCA5FCA5FCA5FCA5F cookie was selected arbitrarily, but in general
> > it can be anything that the call target is unlikely to clobber a CSR
> > with (so it shouldn't be 0, 1, -1 etc.).
> >
> > This isn't intended to be fast, but is something you turn on in a
slow
> > "validate corner cases" mode.  I think for this to be
practical we'll
> > need to be able to switch this on and off per calling convention,
> > since I suspect doing this for every call will be impractically slow,
> > even for a validation run.
> >
> > Does the general idea sound reasonable?
>
> The solution definitely solves your problems, I just wonder in what
> “corner case” mode this even makes sense.
>
Yeah, that's sort of what I'd be wondering too.

It seems like if the compiler does the right thing for existing calling
conventions - I hope our architecture is such that changing the set of
callee save registers reflects on both sides (both the caller - relying on
them to be saved, and the caller implementing that guarantee). So I
wouldn't expect making weird/random calling conventions to be likely to
have any new/interesting bugs here.

But perhaps the architecture doesn't & can't work that way?

>
> >
> > Note: the focus here is **not** verifying the register allocator or
> > any other part of _LLVM_, but to verify that e.g. a custom calling
> > convention that says that a call target preserves %r10 actually does
> > preserve %r10.  This is the compiler enforcing a contract, just at a
> > very low level.
>
> You mean with code generated by another compiler/handwritten, because
> otherwise, this is pretty easy to verify in the machine verifier :).
> (We probably do not verify that though, but we should.)
> Thus, could you elaborate on the use cases.
>
> >
> >
> > Implementation wise, I have a rough prototype that works by running a
> > MachineFunctionPass before register allocation that emits the
> > necessary MachineInstrs / control flow to make this happen.  Is that a
> > right way to solve the problem?
>
> I’d say yes, assuming the use cases do not involve llvm, otherwise the
> verifier approach seems preferable to me.
>
> > If so, I'll clean up what I have and
> > put it up for review on llvm-commits.  If there are better ways to do
> > this, then I'm happy to hear them.
> >
> > -- Sanjoy
>
> Cheers,
> -Quentin
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160513/4d7eea83/attachment.html>

Hi Quentin,

Thanks for the quick response!

Quentin Colombet wrote:
 >
 > You mean with code generated by another compiler/handwritten,
 > because otherwise, this is pretty easy to verify in the machine
 > verifier :).
 >
 > (We probably do not verify that though, but we should.)
 > Thus, could you elaborate on the use cases.

The runtime functions in question are usually hand-written assembly,
or generated from another ("tier-1") JIT.

I expect this to be more useful when calling into hand-written
assembly routines than when calling into other-compiler-generated
code, since hand-written assembly tends to be more prone to the kind
of mistakes I'm verifying against (accidentally clobbering a CSR on a
rarely taken path).

So far we've not seen any bugs around _LLVM_ failing to obey a calling
convention, so (as yet! :) ) I'm not too worried around LLVM
miscompiling due to some exotic calling convention.

Thanks!
-- Sanjoy

 >
 >>
 >> Implementation wise, I have a rough prototype that works by running a
 >> MachineFunctionPass before register allocation that emits the
 >> necessary MachineInstrs / control flow to make this happen.  Is that a
 >> right way to solve the problem?
 >
 > I’d say yes, assuming the use cases do not involve llvm, otherwise 
the verifier approach seems preferable to me.
 >
 >> If so, I'll clean up what I have and
 >> put it up for review on llvm-commits.  If there are better ways to do
 >> this, then I'm happy to hear them.
 >>
 >> -- Sanjoy
 >
 > Cheers,
 > -Quentin

> On May 13, 2016, at 3:32 PM, Sanjoy Das <sanjoy at
playingwithpointers.com> wrote:
> 
> Hi,
> 
> This is a proposal to introduce a mechanism to LLVM that uses runtime
> instrumentation to verify that a call target preserves all of the
> registers it says it does.  Internally, we have a diverse set of
> calling conventions for runtime functions that get called from LLVM
> compiled code, and having some sort of validation mechanism will give
> us more confidence in selecting aggressive calling conventions for
> these.
> 
> The general idea is this: before every call store a cookie in all the
> registers that the call is supposed to preserve, and after the call
> returns, assert that the supposedly callee saved registers weren't
> clobbered.  
More importantly, the runtime needs to have a mode that forcibly clobbers all
caller-save registers, which I’m sure you’re already doing.

You could do this after regalloc and verify only the callee-save registers that
are not already live to avoid slowdowns due to spilling. Your approach sounds
like it would work ok in practice though.

Andy