Implementation of Control Flow Analysis from the Paper

README.md

Interval Creation Process:

• The algorithm starts at the entry node and creates the first interval.
• It adds nodes to the current interval if ALL of their predecessors are already in the interval.
• When a node is found that doesn't satisfy this condition, it becomes a new header node, starting a new interval.

Key Stopping Condition: The crucial part of stopping node addition to an interval is the all_preds_in_interval check.

Specifically:

• If all predecessors of a node are already in the current interval, the node is added to that interval.
• If any predecessor is not in the current interval, this signals the start of a new interval.

Example Graph:

• 'Entry' is the start node
• Nodes A, B, C represent branching
• Nodes D, E, F represent merging and exit paths

For this graph, we proceed in the following manner:

1. Start at 'Entry' - create first interval with 'Entry' and 'A'
2. When processing 'B' and 'C', they are added to the interval because Entry/A are their predecessors
3. When processing 'D', it has predecessors from multiple intervals, so it becomes a new header 'E' and 'F' start another interval as they merge at 'Exit'

graph_intervals.py

class GraphNode:
    def __init__(self, name):
        self.name = name
        self.successors = []
        self.predecessors = []

class Graph:
    def __init__(self):
        self.nodes = {}
    
    def add_node(self, name):
        if name not in self.nodes:
            self.nodes[name] = GraphNode(name)
        return self.nodes[name]
    
    def add_edge(self, from_name, to_name):
        from_node = self.add_node(from_name)
        to_node = self.add_node(to_name)
        
        from_node.successors.append(to_node)
        to_node.predecessors.append(from_node)
    
    def partition_into_intervals(self, entry_node_name):
        """
        Partition the graph into intervals based on Frances Allen's method.
        
        The key idea is to create intervals that represent natural regions of control flow.
        An interval captures a set of nodes that are connected and have a specific structure.
        """
        # Start with the entry node
        entry_node = self.nodes[entry_node_name]
        
        # List to store header nodes
        headers = [entry_node]
        
        # Dictionary to track which intervals each node belongs to
        node_intervals = {}
        
        # Current interval being constructed
        current_interval = set([entry_node])
        node_intervals[entry_node] = current_interval
        
        # Worklist to track nodes to process
        worklist = list(entry_node.successors)
        
        while worklist:
            node = worklist.pop(0)
            
            # Check if all predecessors of the node are in the current interval
            all_preds_in_interval = all(
                pred in current_interval for pred in node.predecessors
            )
            
            if all_preds_in_interval:
                # Add node to current interval
                current_interval.add(node)
                node_intervals[node] = current_interval
                
                # Add new successors to worklist
                for succ in node.successors:
                    if succ not in node_intervals:
                        worklist.append(succ)
            else:
                # This node starts a new interval
                # Create a new header and interval
                headers.append(node)
                current_interval = set([node])
                node_intervals[node] = current_interval
                
                # Add successors to worklist
                worklist.extend(node.successors)
        
        # Convert intervals to a list of node names for readability
        return {
            'headers': [h.name for h in headers],
            'intervals': {
                h.name: [node.name for node in interval] 
                for h, interval in zip(headers, [node_intervals[h] for h in headers])
            }
        }

# Example usage
def create_example_graph():
    graph = Graph()
    
    # Create a simple control flow graph
    graph.add_edge('Entry', 'A')
    graph.add_edge('A', 'B')
    graph.add_edge('A', 'C')
    graph.add_edge('B', 'D')
    graph.add_edge('C', 'D')
    graph.add_edge('D', 'E')
    graph.add_edge('D', 'F')
    graph.add_edge('E', 'Exit')
    graph.add_edge('F', 'Exit')
    
    return graph

# Demonstrate the interval partitioning
def main():
    graph = create_example_graph()
    result = graph.partition_into_intervals('Entry')
    
    print("Interval Partitioning:")
    print("Headers:", result['headers'])
    print("\nIntervals:")
    for header, nodes in result['intervals'].items():
        print(f"Header {header}: {nodes}")

# Uncomment the following line to run the example
# main()