Futhark.Analysis.Interference

Interference analysis for Futhark programs.

Documentation

type Graph a = Set (a, a)

An interference graph. An element `(x, y)` in the set means that there is an undirected edge between x and y, and therefore the lifetimes of x and y overlap and they "interfere" with each other. We assume that pairs are always normalized, such that x < y, before inserting. This should prevent any duplicates. We also don't allow any pairs where `x == y`.

analyseGPU :: LocalScope GPUMem m => LastUseMap -> Stms GPUMem -> m (Graph VName)

Perform interference analysis on the given statements. The result is a triple of the names currently in use, names that hit their last use somewhere within, and the resulting graph.