1. Overview
  2. Docs
Module type
Class type

Simple approximations to the runtime results of computations. This pass is designed for speed rather than accuracy; the performance is important since it is used heavily during inlining.

type 'a boxed_int =
  1. | Int32 : int32 boxed_int
  2. | Int64 : int64 boxed_int
  3. | Nativeint : nativeint boxed_int
type value_string = {
  1. contents : string option;
  2. size : int;
type unresolved_value =
  1. | Set_of_closures_id of Set_of_closures_id.t
  2. | Symbol of Symbol.t
type unknown_because_of =
  1. | Unresolved_value of unresolved_value
  2. | Other
type t = private {
  1. descr : descr;
  2. var : Variable.t option;
  3. symbol : (Symbol.t * int option) option;

A value of type t corresponds to an "approximation" of the result of a computation in the program being compiled. That is to say, it represents what knowledge we have about such a result at compile time. The simplification pass exploits this information to partially evaluate computations.

At a high level, an approximation for a value v has three parts:

  • the "description" (for example, "the constant integer 42");
  • an optional variable;
  • an optional symbol or symbol field. If the variable (resp. symbol) is present then that variable (resp. symbol) may be used to obtain the value v.

The exact semantics of the variable and symbol fields follows.

Approximations are deduced at particular points in an expression tree, but may subsequently be propagated to other locations.

At the point at which an approximation is built for some value v, we can construct a set of variables (call the set S) that are known to alias the same value v. Each member of S will have the same or a more precise descr field in its approximation relative to the approximation for v. (An increase in precision may currently be introduced for pattern matches.) If S is non-empty then it is guaranteed that there is a unique member of S that was declared in a scope further out ("earlier") than all other members of S. If such a member exists then it is recorded in the var field. Otherwise var is None.

Analogous to the construction of the set S, we can construct a set T consisting of all symbols that are known to alias the value whose approximation is being constructed. If T is non-empty then the symbol field is set to some member of T; it does not matter which one. (There is no notion of scope for symbols.)

Note about mutable blocks:

Mutable blocks are always represented by Value_unknown or Value_bottom. Any other approximation could leave the door open to a miscompilation. Such bad scenarios are most likely a user using Obj.magic or Obj.set_field in an inappropriate situation. Such a situation might be: let x = (1, 1) in Obj.set_field (Obj.repr x) 0 (Obj.repr 2); assert(fst x = 2) The user would probably expect the assertion to be true, but the compiler could in fact propagate the value of x across the Obj.set_field.

Insisting that mutable blocks have Value_unknown or Value_bottom approximations certainly won't always prevent this kind of error, but should help catch many of them.

It is possible that there may be some false positives, with correct but unreachable code causing this check to fail. However the likelihood of this seems sufficiently low, especially compared to the advantages gained by performing the check, that we include it.

An example of a pattern that might trigger a false positive is: type a = { a : int } type b = { mutable b : int } type _ t = | A : a t | B : b t let f (type x) (v:x t) (r:x) = match v with | A -> r.a | B -> r.b <- 2; 3 let v = let r = ref A in r := A; (* Some pattern that the compiler can't understand *) f !r { a = 1 } When inlining f, the B branch is unreachable, yet the compiler cannot prove it and must therefore keep it.

and descr = private
  1. | Value_block of Tag.t * t array
  2. | Value_int of int
  3. | Value_char of char
  4. | Value_constptr of int
  5. | Value_float of float option
  6. | Value_boxed_int : 'a boxed_int * 'a -> descr
  7. | Value_set_of_closures of value_set_of_closures
  8. | Value_closure of value_closure
  9. | Value_string of value_string
  10. | Value_float_array of value_float_array
  11. | Value_unknown of unknown_because_of
  12. | Value_bottom
  13. | Value_extern of Export_id.t
  14. | Value_symbol of Symbol.t
  15. | Value_unresolved of unresolved_value
and value_closure = {
  1. set_of_closures : t;
  2. closure_id : Closure_id.t;
and function_declarations = private {
  1. is_classic_mode : bool;
  2. set_of_closures_id : Set_of_closures_id.t;
  3. set_of_closures_origin : Set_of_closures_origin.t;
  4. funs : function_declaration Variable.Map.t;
and function_body = private {
  1. free_variables : Variable.Set.t;
  2. free_symbols : Symbol.Set.t;
  3. stub : bool;
  4. dbg : Debuginfo.t;
  5. inline : Lambda.inline_attribute;
  6. specialise : Lambda.specialise_attribute;
  7. is_a_functor : bool;
  8. body : Flambda.t;
and function_declaration = private {
  1. closure_origin : Closure_origin.t;
  2. params : Parameter.t list;
  3. function_body : function_body option;
and value_set_of_closures = private {
  1. function_decls : function_declarations;
  2. bound_vars : t Var_within_closure.Map.t;
  3. free_vars : Flambda.specialised_to Variable.Map.t;
  4. invariant_params : Variable.Set.t Variable.Map.t Lazy.t;
  5. recursive : Variable.Set.t Lazy.t;
  6. size : int option Variable.Map.t Lazy.t;

    For functions that are very likely to be inlined, the size of the function's body.

  7. specialised_args : Flambda.specialised_to Variable.Map.t;
  8. freshening : Freshening.Project_var.t;
  9. direct_call_surrogates : Closure_id.t Closure_id.Map.t;
and value_float_array_contents =
  1. | Contents of t array