Module liveness 

Buffer liveness analysis.

For each buffer in a ComputeGraph, this pass computes the live interval [def_pos, last_use_pos] in terms of positions in the topological order. The memory planner uses these intervals to determine which buffers can share the same physical memory allocation.

Algorithm

1. Run a topological sort to get a linear order of nodes.
2. For each node at position p:
   • For every output buffer b it writes: record def_pos[b] = p.
   • For every input buffer b it reads: record last_use_pos[b] = max(last_use_pos[b], p).
3. The live interval for buffer b is [def_pos[b], last_use_pos[b]]. Buffers that are only written (no reads) have last_use_pos = def_pos. Buffers that are only read (external inputs) have def_pos = 0.

Two buffers a and b interfere if their live intervals overlap, i.e. a.def <= b.last_use && b.def <= a.last_use.

Structs

LiveInterval

The live interval of a buffer in topological-order position space.

LivenessAnalysis

Result of running liveness analysis on a ComputeGraph.

Functions

analyse

Computes live intervals for all buffers referenced in graph.