Compute the intervals of the graph
    Returns
    interval_graph: a graph of the intervals of G
    interv_heads: a dict of (header node, interval)

def intervals(graph):
    """
    Compute the intervals of the graph
    Returns
    interval_graph: a graph of the intervals of G
    interv_heads: a dict of (header node, interval)
    """
    interval_graph = Graph()  # graph of intervals
    heads = [graph.entry]  # list of header nodes
    interv_heads = {}  # interv_heads[i] = interval of header i
    processed = {i: False for i in graph}
    edges = defaultdict(list)

    while heads:
        head = heads.pop(0)

        if not processed[head]:
            processed[head] = True
            interv_heads[head] = Interval(head)

            # Check if there is a node which has all its predecessor in the
            # current interval. If there is, add that node to the interval and
            # repeat until all the possible nodes have been added.
            change = True
            while change:
                change = False
                for node in graph.rpo[1:]:
                    if all(
                                    p in interv_heads[head] for p in graph.all_preds(node)):
                        change |= interv_heads[head].add_node(node)

            # At this stage, a node which is not in the interval, but has one
            # of its predecessor in it, is the header of another interval. So
            # we add all such nodes to the header list.
            for node in graph:
                if node not in interv_heads[head] and node not in heads:
                    if any(
                                    p in interv_heads[head] for p in graph.all_preds(node)):
                        edges[interv_heads[head]].append(node)
                        assert (node not in heads)
                        heads.append(node)

            interval_graph.add_node(interv_heads[head])
            interv_heads[head].compute_end(graph)

    # Edges is a mapping of 'Interval -> [header nodes of interval successors]'
    for interval, heads in edges.items():
        for head in heads:
            interval_graph.add_edge(interval, interv_heads[head])

    interval_graph.entry = graph.entry.interval
    if graph.exit:
        interval_graph.exit = graph.exit.interval

    return interval_graph, interv_heads