## PIPS: Interval Graph

Ronan KERYELL

CRI, Ecole des Mines de Paris

October 20, 2021

The interval graph is used at least in the hierarchical restructurer of
the control graph in PIPS. This file defines the data structures used by the
algorithm to build and represent the interval graphs embedding control flow
graph.

### 1 Imported NewGen Types

Since the interval graph is on the control graph, import the following type:

Import control from "ri.newgen"

### 2 The Interval Graph

An interval graph is represented by a graph (from package “graph” with
interval_vertex_label decorations. The first interval of the graph is the entry
interval of the interval graph and the first control node of an interval is the entry
control node of the interval.

#### 2.1 Vertex Label of the Interval Graph

Each interval node of the graph contains a list of corresponding nodes in the control
graph.

interval_vertex_label = controls:control*