PIPS: Interval Graph

Ronan KERYELL

CRI, Ecole des Mines de Paris

October 17, 2019

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*