# Interval

Перейти к:навигация, поиск

Interval --- интервал.

An interval is such an alt $I$ that its initial node belongs to each strongly connected subgraph of $I$. The initial node of interval $I$ is also called a header node.

An interval $I$ is maximal if there is no such an interval $Z$ that $I$ is a proper subfragment of $Z$.

For a given control flow graph $G$ with its initial node $n_{0}$ and a given node $n$ of $G$, the maximal interval with the header $n$, denoted $I(n)$, can be constructed by the following three rules: (1) $n$ is in $I(n)$; (2) if all the predecessors of some node $m \neq n_{0}$ are in $I(n)$, then $m$ is in $I(n)$; (3) nothing else is in $I(n)$.

The set of all maximal intervals of a cf-graph $G$ form a partition of the set of its nodes.

A node $p$ is a head of some maximal interval of a cf-graph $G$ if and only if either $p$ is the initial node of $G$ or $p$ is a terminal node of another maximal interval of $G$.