use alloc::collections::BTreeMap;
use alloc::collections::BTreeSet;
use alloc::vec::Vec;
use crate::compiled::capture::CapturedGraph;
use crate::err::Result;
use crate::graph::ValueId;
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, serde::Serialize)]
pub struct LivenessInterval {
def_node: usize,
last_use_node: usize,
}
impl LivenessInterval {
const fn new(def_node: usize, last_use_node: usize) -> Self {
Self {
def_node,
last_use_node,
}
}
#[must_use]
pub const fn def_node(self) -> usize {
self.def_node
}
#[must_use]
pub const fn last_use_node(self) -> usize {
self.last_use_node
}
#[must_use]
pub fn overlaps_with(&self, other: &Self) -> bool {
self.def_node <= other.last_use_node && other.def_node <= self.last_use_node
}
}
#[derive(serde::Deserialize)]
struct WireLivenessInterval {
def_node: usize,
last_use_node: usize,
}
impl<'de> serde::Deserialize<'de> for LivenessInterval {
fn deserialize<D: serde::Deserializer<'de>>(
deserializer: D,
) -> core::result::Result<Self, D::Error> {
use serde::de::Error as _;
let wire = <WireLivenessInterval as serde::Deserialize>::deserialize(deserializer)?;
if wire.def_node > wire.last_use_node {
return Err(D::Error::custom(
"liveness interval defines a value after its last use",
));
}
Ok(Self::new(wire.def_node, wire.last_use_node))
}
}
#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
pub struct LivenessMap {
intervals: BTreeMap<ValueId, LivenessInterval>,
}
impl LivenessMap {
#[must_use]
pub fn compute(graph: &CapturedGraph) -> Self {
let mut intervals: BTreeMap<ValueId, LivenessInterval> = BTreeMap::new();
for &value in graph.inputs.iter().chain(graph.initializers.keys()) {
intervals.insert(value, LivenessInterval::new(0, 0));
}
for (node_idx, node) in graph.nodes.iter().enumerate() {
for &out_id in &node.outputs {
intervals
.entry(out_id)
.or_insert(LivenessInterval::new(node_idx, node_idx))
.last_use_node = node_idx;
}
for &in_id in &node.inputs {
if let Some(interval) = intervals.get_mut(&in_id)
&& node_idx > interval.last_use_node
{
interval.last_use_node = node_idx;
}
}
}
for &out_id in &graph.outputs {
if let Some(interval) = intervals.get_mut(&out_id) {
interval.last_use_node = graph.nodes.len();
}
}
Self { intervals }
}
pub fn get(&self, value_id: ValueId) -> Option<LivenessInterval> {
self.intervals.get(&value_id).copied()
}
#[must_use]
pub fn values(&self) -> Vec<ValueId> {
self.intervals.keys().copied().collect()
}
#[must_use]
pub fn alias_candidates(&self) -> Vec<(ValueId, ValueId)> {
let ids: Vec<ValueId> = self.intervals.keys().copied().collect();
let mut candidates = Vec::new();
for i in 0..ids.len() {
for j in (i + 1)..ids.len() {
let a = ids[i];
let b = ids[j];
let ia = &self.intervals[&a];
let ib = &self.intervals[&b];
if !ia.overlaps_with(ib) {
candidates.push((a, b));
}
}
}
candidates
}
pub fn extend_for_saved_tensors(&mut self, saved: &SavedTensorSet, backward_end_node: usize) {
for &vid in &saved.values {
if let Some(interval) = self.intervals.get_mut(&vid)
&& interval.last_use_node < backward_end_node
{
interval.last_use_node = backward_end_node;
}
}
}
}
#[derive(Debug, Clone, PartialEq, Eq, Default, serde::Serialize, serde::Deserialize)]
pub struct SavedTensorSet {
pub values: BTreeSet<ValueId>,
}
impl SavedTensorSet {
#[must_use]
pub fn new() -> Self {
Self::default()
}
pub fn save(&mut self, value_id: ValueId) {
self.values.insert(value_id);
}
#[must_use]
pub fn contains(&self, value_id: ValueId) -> bool {
self.values.contains(&value_id)
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, serde::Serialize)]
pub struct BufferSlot(usize);
impl BufferSlot {
const fn new(index: usize) -> Self {
Self(index)
}
#[must_use]
pub const fn index(self) -> usize {
self.0
}
}
#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize)]
pub struct MemoryPlan {
assignments: BTreeMap<ValueId, BufferSlot>,
peak_live_slots: usize,
}
impl MemoryPlan {
#[must_use]
pub const fn assignments(&self) -> &BTreeMap<ValueId, BufferSlot> {
&self.assignments
}
#[must_use]
pub const fn peak_live_slots(&self) -> usize {
self.peak_live_slots
}
fn validate(&self) -> core::result::Result<(), &'static str> {
if self
.assignments
.values()
.any(|slot| slot.index() >= self.peak_live_slots)
{
return Err("memory-plan slot is outside peak_live_slots");
}
Ok(())
}
}
#[derive(serde::Deserialize)]
struct WireMemoryPlan {
assignments: BTreeMap<ValueId, usize>,
peak_live_slots: usize,
}
impl<'de> serde::Deserialize<'de> for MemoryPlan {
fn deserialize<D: serde::Deserializer<'de>>(
deserializer: D,
) -> core::result::Result<Self, D::Error> {
use serde::de::Error as _;
let wire = <WireMemoryPlan as serde::Deserialize>::deserialize(deserializer)?;
let plan = Self {
assignments: wire
.assignments
.into_iter()
.map(|(value, slot)| (value, BufferSlot::new(slot)))
.collect(),
peak_live_slots: wire.peak_live_slots,
};
plan.validate().map_err(D::Error::custom)?;
Ok(plan)
}
}
#[derive(Debug, Default, Clone, Copy, PartialEq, Eq)]
pub struct AllocationPlanner;
impl AllocationPlanner {
pub fn plan(&self, liveness: &LivenessMap, graph: &CapturedGraph) -> Result<MemoryPlan> {
let mut assignments: BTreeMap<ValueId, BufferSlot> = BTreeMap::new();
let mut free_slots: Vec<BufferSlot> = Vec::new();
let mut next_slot: usize = 0;
let mut peak_live_slots: usize = 0;
let mut currently_live: BTreeSet<ValueId> = BTreeSet::new();
for &input in graph.inputs.iter().chain(graph.initializers.keys()) {
let slot = BufferSlot::new(next_slot);
next_slot = next_slot
.checked_add(1)
.ok_or_else(|| crate::err::Error::Msg("buffer-slot index overflowed".into()))?;
assignments.insert(input, slot);
currently_live.insert(input);
}
peak_live_slots = peak_live_slots.max(currently_live.len());
let node_count = graph.nodes.len();
for node_idx in 0..=node_count {
let to_free: Vec<ValueId> = currently_live
.iter()
.filter(|&&vid| {
liveness
.get(vid)
.is_some_and(|iv| iv.last_use_node < node_idx)
})
.copied()
.collect();
for vid in to_free {
currently_live.remove(&vid);
if let Some(&slot) = assignments.get(&vid) {
free_slots.push(slot);
}
}
for node in graph.nodes.iter().filter(|n| n.id == node_idx) {
for &out_id in &node.outputs {
let slot = if let Some(s) = free_slots.pop() {
s
} else {
let s = BufferSlot::new(next_slot);
next_slot = next_slot.checked_add(1).ok_or_else(|| {
crate::err::Error::Msg("buffer-slot index overflowed".into())
})?;
s
};
assignments.insert(out_id, slot);
currently_live.insert(out_id);
}
}
peak_live_slots = peak_live_slots.max(currently_live.len());
}
Ok(MemoryPlan {
assignments,
peak_live_slots,
})
}
}