> I've been doing some experiments with the OCaml inliner, and have
> walked away from the process very confused.  It seems like inlining
> can be prevented by very simple changes to the code of a function.
> The main surprise for me is that adding a quite trivial allocation of
> a list or a string literal defeats the inliner.
> 
> Does anyone have a better understanding of what's going on here?  I
> feel like my intuition for this stuff is terrible.

The algorithm is very simple: a function is inlinable if

1- its code size (approximate) is below a certain threshold
    (governed by the -inline option)
2- and its body doesn't contain a function definition
    (fun x -> ..., let rec f x = ..., etc) nor a structured constant
    (string literal, [1;2;3], etc).

The reason for 2- is that the inliner is too stupid to inline a
function without duplicating the function definitions/structured
constants contained within.  Such a duplication can be very wasteful
in code and static data size.  (Cue the replies "but not if small
enough!" in 3...2...1...now.)

For your specific examples:

> (* Add in allocation of a list, not inlined *)
> let f x = ignore [1]; x + x
> let g x = f x + f x

"[1]" is not a run-time allocation: its a structured constant, built
at compile-time.  Hence you run into case 2 above.

> (* allocate a string, not inlined *)
> let f x = ignore "foo"; x + x
> let g x = f x + f x

Likewise (no allocation, but case 2).

> (* Call a function that includes an infix operator in prefix form,
>    not inlined. *)
> let list = [1;2;3]
> let f x = x * List.fold_left (+) 0 list
> let g x = f x + f x

Because (+) is really fun x y -> x + y, therefore case 2 again.

- Xavier Leroy