P3: Top-down Global Semantic Analysis

This stage performs whole-program analysis starting from entry methods. Its granularity is the same as the previous bottom-up stage, but it has advantages: many states that could only be determined as anything will be replaced with concrete states, further improving the accuracy of semantic analysis results.

Overall Workflow

This stage uses entry methods as units. Based on method frames, it maintains a method frame stack and performs global semantic analysis. The steps are:

Input: entry method entry_method, frame stack frame_stack
Output: global semantic analysis results

// Initialization: push the entry method frame onto the stack
frame = create_frame(entry_method)
frame_stack.push(frame)

while frame_stack != empty:
    frame = frame_stack.peek()

    // Check whether this frame has callees pending analysis (from the last interruption)
    if frame.pending_callees != empty:
        // Pop one pending callee (depth-first)
        // Analyze the callee first
        callee = frame.pending_callees.pop()
        callee_frame = create_frame(callee)
        frame_stack.push(callee_frame)
        continue

    // Otherwise, try to analyze the current frame
    results = analyze_method(frame)

    if results.success:
        // Analysis finished, pop
        frame_stack.pop()

    elif results.interruptions is not empty:
        // Encounter new unresolved calls, record as pending_callees
        frame.pending_callees = results.interruptions
        // Do not pop the current frame; keep it on top and return after callees are analyzed

    else:
        // Cannot continue (e.g., external call), force pop
        frame_stack.pop()

Reusing Bottom-up Analysis Logic

Method semantic analysis reuses the bottom-up logic. The main differences are:

First, in compute_stmt_state(), bottom-up analysis assumes the states of external symbols as anything, while in global semantic analysis, the states of external symbols are inferred and traced backward based on the frame stack until a determined state is found. This difference is reflected in core/global_semantics.py.

Second, in points-to analysis for each statement, handling of call_stmt also differs. In bottom-up analysis, call_stmt applies method summaries for points-to relations. In global semantic analysis, call_stmt enters the callee method, connects actual arguments at the call site with formal parameters of the callee, and after the callee finishes, applies the return value. This difference is reflected in core/global_stmt_states.py.