Something went wrong. Try again.
forked from raven-ml/raven
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479(*--------------------------------------------------------------------------- Copyright (c) 2026 The Raven authors. All rights reserved. SPDX-License-Identifier: ISC ---------------------------------------------------------------------------*)
open Value
module A = Nx_array
let invalid_argf fmt = Format.kasprintf invalid_arg fmt
(* The live [Extent] interpretations of the process. *)let extents = Atomic.make 0let quiet () = Atomic.get extents = 0
(* The eager meaning *)
(* Raises unless the operand [x] is alive and concrete: an interpretation receives every operation on its traced values before eager execution can. *)let checked (type v s d) ~by (x : (v, s, d) t) = match x with | Traced { owner; _ } -> invalid_argf "%s: a value traced by %s reached eager execution" by owner.name | Array _ | Shards _ | Handle _ -> Prim.alive ~by x
(* [x] placed at [p], a value onto the host from another set waited for first. *)let placed ~by p x = if Devices.on_host_set p && not (Devices.on_host_set (Prim.placement x)) then Check.wait ~by x; Exec.place ~by p x
(* The memory of a handle [c] claimed that [op]'s first result may take ({!Donate.reuse}): the handle's buffer, dead from then on, and the array the result takes. A result written there lies where the handle does, so only an operand that lies where [r] puts the results may hold it. *)let taken c (r : Prim.routed) op = match (Prim.own_index op, r.route) with | Some (own, layout, Nx_array.Dtype.Any dt), Some route -> let (Prim.Operands xs) = Prim.operands op in let xs = Array.of_list xs in let at_result i = let (Value.Any x) = xs.(i) in Devices.equal (Prim.placement x) route.result in let own = List.filter at_result own in Option.map (fun (b, a) -> (b, A.Any a)) (Donate.reuse c ~own dt layout) | Some _, None | None, _ -> None
let rec run : type r. by:string -> r prim -> r = fun ~by op -> if Exec.is_local op then Exec.local ~by op else general ~by op
and general : type r. by:string -> r prim -> r = fun ~by op -> Prim.iteri (fun _ x -> checked ~by x) op; if Prim.exists Donate.is_handle op then donated ~by op else plain ~by op
(* [op] over donated operands: a movement that maps elements one to one passes a new handle on; any other operation checks its rule and its route, then consumes the handles as {!Donate.with_consumer} does, reading their memory and writing its first result into a handle's memory where it may. *)and donated : type r. by:string -> r prim -> r = fun ~by op -> match op with | Move (mv, (Handle { donor; over } as x)) -> (* A view of a handle's one array, made here, leaves the memory unshared, where [run]'s view would share it: the handle it passes on has the same donor, so its consumer may still write into it. The movement claims nothing: the deaths wait for that consumer, which checks every operand first, so an operation that aligns its operands by movements kills nothing when its checks refuse it. *) let moved () = run ~by (Move (mv, Donate.live x)) in let over = match over with | Array r -> ( ignore (Prim.layouts ~by op); match A.move mv r.a with | Some a -> Array { r with a; dead = Live } | None -> moved ()) | Shards _ | Handle _ | Traced _ -> moved () in Handle { donor; over } | Map _ | Reduce _ | Scan _ | Gather _ | Scatter _ | Sort _ | Fft _ | Linalg _ | Fold _ | Assemble _ | Contract _ | Copy _ | Move _ | Bitcast _ | Place _ | Check _ -> ( (* Routed before the claim: an operation its rule refuses neither takes a handle's memory nor shows another domain a handle dead. Once claimed, the donors stay dead whatever the kernels answer. *) let r = Prim.route ~by op in let (Prim.Operands xs) = Prim.operands op in Donate.with_consumer ~by xs (fun c -> let op = Donate.called c op in match taken c r op with | Some (b, (A.Any a as into)) -> (* The handle's memory is the result's, now over [b']: the kernel reads each index of it before it writes the result there. *) let b' = A.buffer a in let as_taken (type v s d) (y : (v, s, d) t) : (v, s, d) t = match y with | Array r when A.buffer r.a == b -> Array { r with a = A.v (A.dtype r.a) (A.layout r.a) b' } | Array _ | Shards _ | Handle _ | Traced _ -> y in routed ~by ~into r (Prim.map as_taken op) | None -> routed ~by r op))
and plain : type r. by:string -> r prim -> r = fun ~by op -> match op with | Place (p, x) -> placed ~by p x | Check { ok; data; fail } -> ignore (Prim.layouts ~by op); Check.issue ~by ok data fail | _ -> routed ~by (Prim.route ~by op) op
(* [op], a placement, a check, or another operation, computed as its rule decided [r] ({!Prim.route}): by partials or by windows as the route computes, its first result into [into] where it is given. *)and routed : type r. by:string -> ?into:A.any -> Prim.routed -> r prim -> r = fun ~by ?into r op -> match op with | Place (p, x) -> placed ~by p x | Check { ok; data; fail } -> Check.issue ~by ok data fail | _ -> ( (* Every operation but a placement and a check has a route. *) let route = Option.get r.Prim.route in match route.compute with | Partials -> Partial.run ~by route op | Windows -> Exec.windows ~by ?into route r.layouts op)
let is_traced (type v s d) (x : (v, s, d) t) = match x with | Traced _ -> true | Array _ | Shards _ | Handle _ -> false
(* Whether [i] receives [o]'s values as its own: [o] is [i] or what [i] adopts. *)let rec adopts i o = o == i || match i.reach with Adopting p -> adopts p o | Values | Extent -> false
let owns i (type v s d) (x : (v, s, d) t) = match x with | Traced { owner; _ } -> adopts i owner | Array _ | Shards _ | Handle _ -> false
let refuse ~by o = if Atomic.get o.live then Format.kasprintf invalid_arg "%s: a value of %s, used outside %s's extent" by o.name o.name else Format.kasprintf invalid_arg "%s: a value of %s, used after %s returned" by o.name o.name
(* Dispatch
[Receive] carries an operation to the handlers around the caller. The innermost whose interpretation reaches it runs the rule in its clause, on the handler's parent fiber: outside the interpretation and every handler inside it, with the extent suspended until the rule returns. The cell is emptied once no handler answered: [Effect.Unhandled] holds the effect, and the runtime keeps the last exception raised reachable while backtraces are recorded.
[Ask] puts a question about the caller to [of_]'s handler. [Around] asks whether that handler is around the caller, which it answers alone. [Readable] asks whether it is around the caller with no [Extent] handler between them, and an [Extent] handler in between answers [false]. Under no handler of [of_], the answer is [false]. *)type question = Around | Readable
type _ Effect.t += | Receive : { by : string; mutable op : 'r prim option } -> 'r Effect.t | Ask : { of_ : interpretation; what : question } -> bool Effect.t
let ask o what = match Effect.perform (Ask { of_ = o; what }) with | b -> b | exception Effect.Unhandled (Ask _) -> false
(* Whether [o]'s handler is around the caller. *)let around o = ask o Around
(* [i]'s rule on [op], in [i]'s clause. Another interpretation's traced operand is refused unless its interpretation is around [i], which is asked once per interpretation; one [i] adopts is around by construction ({!interpret}). The rule reads each handle as its arrays, lent, and kills nothing. *)let deliver i ~by op = let checked = ref ([] : interpretation list) in Prim.iteri (fun _ x -> match x with | Traced { owner; _ } when (not (adopts i owner)) && not (List.memq owner !checked) -> if not (around owner) then refuse ~by owner; checked := List.cons owner !checked | Traced _ | Array _ | Shards _ | Handle _ -> ()) op; Prim.iteri (fun _ x -> Prim.alive ~by x) op; let op = if Prim.exists Donate.is_handle op then Prim.map Donate.lent op else op in i.rule i ~by op
let reaches i op = match i.reach with | Extent -> true | Values | Adopting _ -> Prim.exists (fun x -> owns i x) op
(* Whether [i], whose handler was installed on the domain [here], answers on the calling domain, asked by its handler once it has taken an effect. An adopting interpretation's rule may share its parent's state, which no lock guards: on another domain it answers only where its parent is around too, so that the parent's extent moved with it and no rule of theirs runs elsewhere. *)let present i here = match i.reach with | Values | Extent -> true | Adopting p -> (Domain.self () :> int) = here || around p
(* Refuses [op], which [i] reaches where it is not present: names the first operand's owner that [i] adopts. *)let absent i ~by op = Prim.iteri (fun _ x -> match x with | Traced { owner; _ } when adopts i owner -> refuse ~by owner | Traced _ | Array _ | Shards _ | Handle _ -> ()) op; invalid_arg "Eval.absent: an operation its interpretation does not reach"
(* Re-raised with the backtrace of its raise, which a plain [raise] would restart at the handler. *)let reraise e = Printexc.raise_with_backtrace e (Printexc.get_raw_backtrace ())
let handler i = let here = (Domain.self () :> int) in { Effect.Deep.retc = Fun.id; exnc = reraise; effc = (fun (type a) (e : a Effect.t) -> match e with | Receive { by; op = Some op } when reaches i op -> Some (fun (k : (a, _) Effect.Deep.continuation) -> match if present i here then deliver i ~by op else absent i ~by op with | r -> Effect.Deep.continue k r | exception x -> let bt = Printexc.get_raw_backtrace () in Effect.Deep.discontinue_with_backtrace k x bt) | Ask { of_; _ } when of_ == i -> Some (fun (k : (a, _) Effect.Deep.continuation) -> Effect.Deep.continue k (present i here)) | Ask { what = Readable; _ } when i.reach = Extent -> (* An extent inside the owner stages what it reaches: a read there would hide its value from it. *) Some (fun (k : (a, _) Effect.Deep.continuation) -> Effect.Deep.continue k false) | _ -> None); }
(* Refuses to adopt [p] unless its values may skip the check that [p] is around: [p] reaches its values alone, and is live and around the caller, so around the adopting extent. *)let adoptable ~name p = match p.reach with | Extent -> Format.kasprintf invalid_arg "%s: adopts %s, an Extent" name p.name | Values | Adopting _ -> if not (Atomic.get p.live) then Format.kasprintf invalid_arg "%s: adopts %s, which returned" name p.name; if not (around p) then Format.kasprintf invalid_arg "%s: adopts %s outside %s's extent" name p.name p.name
let interpret ~name reach (rule : 'r. interpretation -> by:string -> 'r prim -> 'r) f = (match reach with | Adopting p -> adoptable ~name p | Values | Extent -> ()); let live = Atomic.make true in let i = { name; reach; rule; live } in let run () = Effect.Deep.match_with f i (handler i) in match reach with | Values | Adopting _ -> Fun.protect ~finally:(fun () -> Atomic.set live false) run | Extent -> Atomic.incr extents; Fun.protect ~finally:(fun () -> Atomic.set live false; Atomic.decr extents) run
let traced i form payload = Traced { form; owner = i; payload; twin = None }
let twinned i c payload = Traced { form = Prim.form c; owner = i; payload; twin = Some c }
(* Whether [o]'s handler is around the caller with no [Extent] handler between them. *)let readable o = Atomic.get o.live && ask o Readable
let read_through (type v s d) (x : (v, s, d) t) : (v, s, d) t = let rec go : (v, s, d) t -> (v, s, d) t = function | Traced { owner; twin = Some c; _ } when readable owner -> go c | x -> x in go x
let payload (type v s d) i (x : (v, s, d) t) = match x with | Traced { owner; payload; _ } when owner == i -> Some payload | Traced _ | Array _ | Shards _ | Handle _ -> None
let owner (type v s d) (x : (v, s, d) t) = match x with | Traced { owner; _ } -> Some owner | Array _ | Shards _ | Handle _ -> None
(* An operation no handler answered computes, unless an operand is traced. *)let unreached ~by op = Prim.iteri (fun _ x -> match x with | Traced { owner; _ } -> refuse ~by owner | Array _ | Shards _ | Handle _ -> ()) op; run ~by op
let eval ~by op = if quiet () && (Exec.is_local op || not (Prim.exists is_traced op)) then run ~by op else let e = Receive { by; op = Some op } in match Effect.perform e with | r -> r | exception Effect.Unhandled e' when Obj.repr e' == Obj.repr e -> (match e with Receive cell -> cell.op <- None | _ -> ()); unreached ~by op
(* The one-node maps, built and evaluated: the paths an interpretation may reach. *)let eval1 ~by k dt x = let v, () = eval ~by (Prim.op1 ~by k dt x) in v
let eval2 ~by k dt x y = let v, () = eval ~by (Prim.op2 ~by k dt x y) in v
let eval3 ~by k c x y = let v, () = eval ~by (Prim.op3 ~by k c x y) in v
(* No traced operand and no live [Extent] is the condition under which {!eval} performs nothing, checked on the operands before the operation is built. Live arrays at physically one placement whose set has kernels, where [k] takes their dtypes, then compute by {!Exec.map}, and every other operand by {!run} of the operation. *)let fast1 ~by k dt x = match (x, Exec.live_kernels x, Prim.node1 k (Prim.dtype x) dt) with | Array { at; a; _ }, Some kernels, Some p -> Exec.map ~by kernels at p dt a [| Nx_kernel.Plain a |] | _ -> fst (run ~by (Prim.op1 ~by k dt x))
let fast2 ~by k dt x y = match (x, y, Exec.live_kernels x, Prim.node2 k (Prim.dtype x)) with | Array { at; a; _ }, Array { a = b; _ }, Some kernels, Some p when Exec.beside x y -> Exec.map ~by kernels at p dt a [| Nx_kernel.Plain a; Nx_kernel.Plain b |] | _ -> fst (run ~by (Prim.op2 ~by k dt x y))
let fast3 ~by k c x y = match (c, x, y, Exec.live_kernels c, Prim.node3 k (Prim.dtype c) (Prim.dtype x)) with | ( Array { at; a = ca; _ }, Array { a; _ }, Array { a = b; _ }, Some kernels, Some p ) when Exec.beside c x && Exec.beside c y -> let loads = [| Nx_kernel.Plain ca; Nx_kernel.Plain a; Nx_kernel.Plain b |] in Exec.map ~by kernels at p (A.dtype a) a loads | _ -> fst (run ~by (Prim.op3 ~by k c x y))
let apply1 ~by k dt x = match x with | Traced _ -> eval1 ~by k dt x | Array _ | Shards _ | Handle _ -> if quiet () then fast1 ~by k dt x else eval1 ~by k dt x
let apply2 ~by k dt x y = match (x, y) with | Traced _, _ | _, Traced _ -> eval2 ~by k dt x y | _ -> if quiet () then fast2 ~by k dt x y else eval2 ~by k dt x y
let apply3 ~by k c x y = match (c, x, y) with | Traced _, _, _ | _, Traced _, _ | _, _, Traced _ -> eval3 ~by k c x y | _ -> if quiet () then fast3 ~by k c x y else eval3 ~by k c x y
(* The map of [prog] over [x], into [dt]. *)let map_of prog dt x = let layout = A.Layout.contiguous (Iarray.of_array (Prim.shape x)) in Map { layout; prog; outs = [ dt ]; loads = [| Plain x |]; at = None }
let apply ~by prog dt x = match (x, Exec.live_kernels x) with | Array { at; a; _ }, Some kernels when quiet () -> Exec.map ~by kernels at prog dt a [| Nx_kernel.Plain a |] | _ -> let v, () = eval ~by (map_of prog dt x) in v
let contract ~by ~batch ~contracting ~acc dt a b init = let fast = if quiet () then Exec.contract ~by ~batch ~contracting ~acc dt a b init else None in match fast with | Some y -> y | None -> eval ~by (Contract { batch; contracting; acc; out = dt; a; b; init; a_scale = None; b_scale = None; segments = None; })
let place ~by p x = match x with | Array r when r.at == p && r.dead == Live && quiet () -> (* A second value over the memory shares it. *) Rig.Claim.share (Nx_array.buffer r.a); Array { at = p; a = r.a; dead = Live } | Array _ | Shards _ | Handle _ | Traced _ -> eval ~by (Place (p, x))
(* Movements *)
let move ~by mv x = eval ~by (Move (mv, x))
(* A movement to the shape [x] holds makes no view: [x]'s memory stays unshared, so a later donation of [x] may still write into it. *)let reshape ~by s x = if Prim.has_shape x s then begin Prim.alive ~by x; x end else move ~by (A.Move.Reshape (Iarray.of_array s)) x
let broadcast ~by s x = if Prim.has_shape x s then begin Prim.alive ~by x; x end else move ~by (A.Move.Broadcast (Iarray.of_array s)) x