Optimise certain pattern matching into identity

[riaqn]

Example:

type t =
  | Foo
  | Bar
  | Foobar of t * t

let rec just_id = function
  | Foo -> Foo
  | Bar -> Bar
  | Foobar (t0, t1) -> Foobar (just_id t0, just_id t1)

Produced cmm:

(data global "camlPat_magic__gc_roots": int 0)
(data int 1792 global "camlPat_magic": addr G:"camlPat_magic__just_id_1")
(data
 int 3063
 global "camlPat_magic__just_id_1":
 addr G:"camlPat_magic__just_id_0_1_code"
 int 108086391056891909)
(function{pat_magic.ml:6,18-111} camlPat_magic__just_id_0_1_code
     (param/295: val)
 (if (and param/295 1) param/295
   (alloc{pat_magic.ml:9,23-54} 2048
     (app{pat_magic.ml:9,31-41} G:"camlPat_magic__just_id_0_1_code"
       (load val param/295) val)
     (app{pat_magic.ml:9,43-53} G:"camlPat_magic__just_id_0_1_code"
       (load val (+a param/295 8)) val))))

(function no_cse reduce_code_size linscan ignore zero_alloc
 camlPat_magic__entry ()
 (catch (exit 1 G:"camlPat_magic") with(1 *ret*/292: val) 1))

(data)

I imagine the just_id should just be optimised into %id.

[lthls]

I actually had an intern working on this subject two years ago. The main issue is that recursive types in OCaml are not inductive, so the function you described is not equivalent to the identity:

let rec loop = Foobar (loop, loop)
let v = just_id loop (* doesn't terminate *)

You can even create examples where a function is the identity on all non-cyclic structures but must not be allowed to terminate on (some) cyclic ones.

On the other hand, if we could solve this issue the rest is easy, so maybe we could try adding inductivity annotations to types to forbid recursive values, and then make use of that for detecting identity functions.