@vbrankov I forgot that in ocaml all the registers are caller saved,
so I agree that if at the assembly level "a branch" of a conditionnal
does a function call spilling must be done for all the values that are
needed after the branch. However it is not the end of the story,
because optimisation (as I mentionned before inlining, tail call) can
remove this bad case. Firstly I will look at your C example and
compare what does GCC. Secondly I will look at your OCaml example and
show how OCaml's optimisation remove the bad case. I hope to prove
with these arguments that it is interesting to let the compiler do the
call itself because it can optimise it.

GCC

You said:

This is an illustration that even C spills registers despite goto
being used. If C had a strategy to spill the registers right before
the call, that would mean that having calls in a loop would mean a
lot of spilling and reloading.

int slow_add(int a, int b);

int add(int a, int b)
{
  if (a < 0) goto slow;
  if (b < 0) goto slow;
  return a + b;
slow:
  return slow_add(a, b);
}


int loop(int a, int b){

  while(a < 1000){
    if (a < 0) goto slow;
    if (b < 0) goto slow;
    a = a + b;
    continue;
  slow:
    a = slow_add(a, b);
  }

}

I don't understand your affirmation, if I compile that with just gcc -O1 -S -fverbose-asm test_alloc_c.c, gcc does not spill registers in the add function:

add:
.LFB0:
    .cfi_startproc
    subq    $8, %rsp    #,
    .cfi_def_cfa_offset 16
    movl    %edi, %eax  # a, tmp91
    shrl    $31, %eax   #, tmp91
    testb   %al, %al    # tmp91
    jne .L2 #,
    movl    %esi, %eax  # b, tmp94
    shrl    $31, %eax   #, tmp94
    testb   %al, %al    # tmp94
    jne .L2 #,
    leal    (%rdi,%rsi), %eax   #, D.1786
    jmp .L3 #
.L2:
    call    slow_add    #
.L3:
    addq    $8, %rsp    #,
    .cfi_def_cfa_offset 8
    ret
    .cfi_endproc

For the loop GCC spills some before the loop but just because they are
callee-saved registers, inside the loop only registers are used :

loop:
.LFB1:
    .cfi_startproc
    cmpl    $999, %edi  #, a
    jg  .L14    #,
    pushq   %rbp    #
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    pushq   %rbx    #
    .cfi_def_cfa_offset 24
    .cfi_offset 3, -24
    subq    $8, %rsp    #,
    .cfi_def_cfa_offset 32
    movl    %esi, %ebx  # b, b
    movl    %esi, %ebp  # b, tmp95
    shrl    $31, %ebp   #, tmp95
.L10:
    movl    %edi, %eax  # a, tmp90
    shrl    $31, %eax   #, tmp90
    testb   %al, %al    # tmp90
    jne .L7 #,
    testb   %bpl, %bpl  # tmp95
    jne .L7 #,
    addl    %ebx, %edi  # b, a
    jmp .L8 #
.L7:
    movl    %ebx, %esi  # b,
    call    slow_add    #
    movl    %eax, %edi  #, a
.L8:
    cmpl    $999, %edi  #, a
    jle .L10    #,
    addq    $8, %rsp    #,
    .cfi_def_cfa_offset 24
    popq    %rbx    #
    .cfi_restore 3
    .cfi_def_cfa_offset 16
    popq    %rbp    #
    .cfi_restore 6
    .cfi_def_cfa_offset 8
.L14:
    rep ret
    .cfi_endproc

If I take your OCaml example translated in C:

int max(int x, int y);

int add(int x, int y){

  int z;
  if (x < 1){
    z = 1;
  } else {
    z = max(x, y);
  };

  return z + x + y - 2;

}

Only callee saved registers are saved at the start of the function,
everything else is done in registers.

add:
.LFB0:
    .cfi_startproc
    pushq   %rbp    #
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    pushq   %rbx    #
    .cfi_def_cfa_offset 24
    .cfi_offset 3, -24
    subq    $8, %rsp    #,
    .cfi_def_cfa_offset 32
    movl    %edi, %ebx  # x, x
    movl    %esi, %ebp  # y, y
    movl    $1, %eax    #, z
    testl   %edi, %edi  # x
    jle .L2 #,
    call    max #
.L2:
    leal    -2(%rax,%rbx), %eax #, D.1762
    leal    -2(%rbp,%rax), %eax #, D.1762
    addq    $8, %rsp    #,
    .cfi_def_cfa_offset 24
    popq    %rbx    #
    .cfi_def_cfa_offset 16
    popq    %rbp    #
    .cfi_def_cfa_offset 8
    ret
    .cfi_endproc

Other optimizations could reduce even more the penalty for the call.
For example if -O2 is used and the condition is replaced by
__builtin_expect(!!(x < 1),1) then the compiler duplicates the end
of the function. It is as if the function is written like:

int add(int x, int y){

  int z;
  if (__builtin_expect(!!(x < 1),1)){
    z = 1;
    return z + x + y - 2;
  } else {
    z = max(x, y);
    return z + x + y - 2;
  };

}

That proves that C compilers are able to avoid spilling when there is
a function call in one path. Or did I miss your point, did I miss
something in the asm?

OCaml

For this example:

let add x y =
  let z = if x < 0 then 0 else max x y in
  z + x + y

I agree that I was wrong when I said that OCaml could keep some data
in registers at the end of the condition if a call is done in the else
branch, I forgot that there is no callee-saved register in ocaml.
However OCaml can use inlining as usual in order to improve register
allocation. With the current version of the compiler:

1. max x y is not inlined, if max is defined in Pervasives and whatever
   the value of -inline.
2. max x y is not inlined, if max is defined locally and -inline
   is smaller than 2.
3. max x y is inlined but the >= of max remains polymorphic, if max is
   defined locally and -inline is greater than 2.
4. max x y is inlined and is just a compare-jump, if max is
   defined locally, specialized to int and whatever the value of -inline.

let max (x:int) y = if x >= y then x else y

I think we want one day to be able to use Pervasives.max on integer
and have just a comparison in assembly (perhaps with the final
flambda?) (case 4.). In that case asm-goto is interesting because it allows the
compiler to inline the function call or to do other optimizations.

In conclusion

• I agree that in the Zarith example, doing the call inside the inline
  assembly or in ocaml will change nothing in the final assembly.
  But with asm-goto, you write the call in ocaml and don't have to
  bother with all the complications yourself.
• If you want to call an ocaml function or just evaluate different expressions,
  asm-goto let the compilers do further optimization.

So I think inline asm need to handle multiple exit point.

Writing this answer took me more time than I though, perhaps I should
have kept this time to continue coding a proposition with asm-goto. ;)

@bobot In order to check whether an operation causes spilling, we should use some variables, do the operation and use the variables again. The C add function doesn't spill because it does nothing after the call. The loop doesn't spill b because it's in ebx which is caller safe. And generally, providing an example, even if it was correct, could not be a proof.

In your OCaml discussion, I used max exactly because I know it would produce a call and not get inlined.

I disagree with the conclusion that having asm-goto would make things simpler. The only argument that I see is that the calls would be in OCaml. How much simpler is that, can we have a side-by-side example? On the other hand, asm-goto looks like Pandora's box. For start, OCaml syntax doesn't have the means to represent it, so we need to come up with new language constructs. The compiler support would also be very complicated since an inline assembly is an OCaml primitive. I don't see any free lunch in trying to treat asm-goto differently, it would come down to introducing goto capability in OCaml.

On a more general viewpoint, my understanding of vbrankov's proposition is that its main advantage (compared to safer and also interesting approaches such as letting users write lambda and cmm code directly to define some of their primitives to avoid the cost of the C boundary without having to fork the compiler) is the support for exotic assembly instructions that the OCaml backend doesn't know about. If this is the problem that we aim to solve in this pull request, we should maybe focus on this use-case by assuming small ASM snippets with little to no control-flow.

That is not to diminish bobot's efforts to allow richer control flow to be expressed: it could be very interesting of course, but maybe we could converge on the simpler thing for this PR, discuss whether it is mergeable for this more specific purpose, and consider extensions that solve other problems only a second step.

@bobot Leo and me discussed possible solutions for your problem to avoid spills and some ideas came up.

• A special pair of primitives which spills and reads back all live registers. The code around this "block" would be treated as if it destroys no registers. In this example the effect would be that the registers would be spilled only if a branch with the call is taken, but then the cost of the call would eclipse the cost of spilling:

let add x y =
  let z = if x < 0 then 0 else begin
    spill_live ();
    max x y
    restore_live ()
  end in
  z + x + y

• Write the C function with register variables to control precisely which registers are destroyed and hence reduce the set of destroyed variables on that call.

Regarding alternative syntax for the calls, @lpw25 had a good suggestion to use attributes. Some possibilities

(* GCC identifiers, less verbose *)
external floor : (float [@unbox][@param "x"]) -> (float [@unbox][@param "=x"])
  = "%asm" "round_stub" "roundsd $0, %0, %1"
external mov : (int [@param "m,r,r"]) -> (int ref [@param "=r,m,r"]) -> unit
  = "%asm" "mov_stub" "mov %0, %1"

(* more verbose *)
external floor :
     (float [@unbox][@xmm])
  -> (float [@unbox][@output][@xmm])
  [@asm "roundsd $0, %0, %1"] = "round_stub"
external mov :
     (int [@memory][@alt][@register][@alt][@register])
  -> (int ref [@output][@register][@alt][@memory][@alt][@register])
  -> unit
  [@asm "mov %0, %1"] = "mov_stub"

Inline asm with jump is implemented 1. Perhaps some ideas can be reused:

• It defines a new module Asm in the stdlib 2, parsing, typing is done as usual, and third party tools (merlin, odoc) should already understand it. But as @lpw25 predicted if some sub-term is not a constant you have a strange error (yet localized :) ) "Configuration parameters of inline assembly must be constant" and "Configuration function for inline assembly can't be used outside inline assembly application".
• It defines a function Asm.arch that return the current architecture(bytecode is considered as an architecture) and allows to match on it (the match is naturally eliminated early) in order to have different code or assembly for each architecture.
• You can jump to a specified ocaml expression 3
• Asm.ivalue and Asm.ovalue work with boxed value, Asm.ifloat and Asm.ofloat work with unboxed float.
• Many things are not implemented, only registers are used (no direct access to the stack), all the virtual register used are said interfering, no unboxed integer, some errors are not catched during parsing but in late compilation phase...
• Thank you for looking at my problem to avoid spills. In the spirit of your proposition with spill_live/spill_restore I created Reload registers early in branches #180 which reloads early in the branch that destroy registers. If this optimization is deemed too much invasive it could be activated only on annotated branch [@slow_branch]. But I prefer the compiler to do directly the right thing 😀 .

Now that I understand better the problem I will review more in depth this merge-request.

PS: I can create a merge request for simplifying reading and testing of 1 .

@bobot Thanks for the comprehensive example. Regarding multiple branches, I'm nicely surprised that avoiding creating closures doesn't look as difficult as I expected, although I haven't read the code. However, I am not convinced that all the problems are solved. This example boxes floats:

let x =
  let i = 1. in
  let open Asm in
  let y =
    match arch with
    | AMD64 ->
        amd64
          ~input:[ifloat "%0" i]
          "addsd        %0, %1  # func1"
          ~effect:[`VReg "%1"]
          ~output:(ofloat "%1" oend)
          ~label:[`End,(fun x () -> x)]
    | _ -> assert false
  in
  y > 1.

        movsd   .L105(%rip), %xmm0
        addsd   %xmm0, %xmm1    # func1
.L103:
        call    caml_alloc1@PLT
.L106:
        leaq    8(%r15), %rax
        movq    $1277, -8(%rax)
        movsd   %xmm1, (%rax)
.L102:
        movsd   .L105(%rip), %xmm0
        movsd   (%rax), %xmm1
        comisd  %xmm0, %xmm1

Not having branches allows the compiler to eliminate boxing. I feel it is difficult to implement this optimization with multiple branches.

external addsd : float -> float = "%asm" "" "addsd %0, %1" "x" "=x"

let x =
  let i = 1. in
  let y = addsd i in
  y > 1.

        movsd   .L103(%rip), %xmm0
        addsd %xmm0, %xmm1
        comisd  %xmm0, %xmm1

This is just an example, there may be more optimizations that may be difficult because the compiler needs to "see" and modify the code inside the branches.

The closure is not created simply because (fun x y -> t) t1 t2 is simplified early into let x = t1 in let y = t2 in t and I applied each branch with as many variable that there is output register and unit.

My motto is if Cifthenelse can do it Casminline should be able to do it 😜 . And for Cifthenelse there is some float boxing in g and not in f (Is there no patch for improving the g case?)

let g x b =
  let i = 1.0 in
  let y = if b then x +. 1. else x +. 2. in
  y > 1.

let f x b =
  let i = 1.0 in
  (if b then x +. 1. else x +. 2.) > 1.

So by modifying Cmmgen.unbox_float, a version of f with Casminline should be unboxed. But not with your example, when it is optimized for if, it should be possible to optimize it for asminline.

It is your patch indeed 😄 #6260, but it is on let and it is applied. If the Uifthenelse case is also handled, g doesn't allocate anymore:

diff --git a/asmcomp/cmmgen.ml b/asmcomp/cmmgen.ml
index e3c723a..9a9f30f 100644
--- a/asmcomp/cmmgen.ml
+++ b/asmcomp/cmmgen.ml
@@ -1260,6 +1260,10 @@ let rec is_unboxed_number = function
         | _ -> No_unboxing
       end
   | Ulet (_, _, e) | Usequence (_, e) -> is_unboxed_number e
+  | Uifthenelse(_, e2, e3) ->
+      let is_e2 = is_unboxed_number e2 in
+      let is_e3 = is_unboxed_number e3 in
+      if is_e3 = is_e2 then is_e2 else No_unboxing
   | _ -> No_unboxing

 let subst_boxed_number unbox_fn boxed_id unboxed_id box_chunk box_offset exp =

Instead of writing one patch for one case, someone should perhaps try to complete is_unboxed_number as much as possible. I think I should be able to complete for Uasminline is_unboxed_number in a satisfactory way (just need to add an environment in is_unboxed_number for variables that are unboxed).

@bobot The pull request 107 should do more unboxing.

@bobot All right, I now feel multiple branches is doable. I will examine it in detail and get back.

I've heard that there had been a discussion about this patch in the last OCaml Dev meeting and the conclusion was generally negative. Whoever knows about that meeting please let me know if there's any followup, questions or if anything can be salvaged out of this patch. For example, easily adding native primitives might still be a useful thing to have.

At the dev meeting, the following points were raised (in no particular order).

• Complexity. Even with your best efforts, this is a fairly big and complex extension. (I know exactly what you went through here because at about the same time I was adding extended inline asm to the CompCert C compiler...).
• Further adding to the complexity is the need for a mechanism (preprocessor or otherwise) to select the appropriate asm fragment for the target, or a fallback implementation.
• Aesthetics. Some developers just don't want to see ugly asm templates with obscure % holes in their nifty Caml source files, and feel that the proper place for such code is in separate .s or .c with inline assembly files.
• Performance gains wrt "noalloc" C/asm external functions. Calling "alloc" external functions is expensive indeed. However, with the new unboxing annotations (which all devs at the meeting liked, by the way), many more external functions can be declared "noalloc", including those for which you would typically feel the need for inline asm. The overhead of calling a "noalloc" external functions is relatively low. So, a plausible alternative to inline asm is just "noalloc" external functions implemented either in C with inline asm, or in assembly.
• As a performance data point, I mentioned a recent experiment with the Zarith library where some "fast paths" are rewritten in portable OCaml, using Hacker's Delight tricks for overflow detection and what not, then inlined by ocamlopt, leaving the "alloc" external calls to the slow path. The performance obtained is not quite what you'd get with inlining "branch on overflow" asm instructions, but not that far either. Sometimes, the best way to use asm is to recognize that you don't need it :-)

The conclusion of our discussions is that we are not going to integrated this PR.

The question you raise about the difficulty of adding new, inlined primitives is a good one and remains open. My personal take on it is that perhaps we should think twice before adding such primitives and try "noalloc" external functions first.

One approach would be to allow inline primitives to be written as compiler plug-ins, written in OCaml, that use an embedded DSL (possibly Camlp4/ppx based?) to describe the assembly code and/or bytecode that needs to be generated.

Note that external functions – even if "noalloc" – are still far too heavyweight for primitives that are single machine instructions.

I'm closing this pull request so that we can better focus on other requests.