analyze method

Implementation

AnalysisResult<D> analyze(ControlFlowGraph cfg) {
  final entryStates = <int, AbstractState<D>>{};
  final exitStates = <int, AbstractState<D>>{};
  var wideningApplied = false;
  var iterations = 0;

  // Initialize all blocks with bottom state
  for (final block in cfg.blocks) {
    entryStates[block.id] = AbstractState<D>(_defaultValue);
    exitStates[block.id] = AbstractState<D>(_defaultValue);
    _blockVisitCount[block.id] = 0;
  }

  // Worklist algorithm using Queue for O(1) dequeue
  final worklist = Queue<BasicBlock>()..add(cfg.entry);
  final inWorklist = <int>{cfg.entry.id};

  while (worklist.isNotEmpty && iterations < maxIterations) {
    iterations++;

    final block = worklist.removeFirst();
    inWorklist.remove(block.id);

    // Compute entry state by joining predecessor exit states
    AbstractState<D> entryState;
    if (block.predecessors.isEmpty) {
      entryState = AbstractState<D>(_defaultValue);
    } else {
      entryState = block.predecessors
          .map((p) => exitStates[p.id]!)
          .reduce((a, b) => a.join(b));
    }

    // Apply widening if we've visited this block too many times
    _blockVisitCount[block.id] = (_blockVisitCount[block.id] ?? 0) + 1;
    if (_blockVisitCount[block.id]! > wideningThreshold) {
      entryState = entryStates[block.id]!.widen(entryState);
      wideningApplied = true;
    }

    // Check if entry state changed
    final oldEntryState = entryStates[block.id]!;
    if (_statesEqual(entryState, oldEntryState) &&
        _blockVisitCount[block.id]! > 1) {
      continue; // No change, skip processing
    }

    entryStates[block.id] = entryState;

    // Transfer function: process instructions
    final exitState = _transferBlock(block, entryState, exitStates);
    exitStates[block.id] = exitState;

    // Add successors to worklist
    for (final succ in block.successors) {
      if (!inWorklist.contains(succ.id)) {
        worklist.add(succ);
        inWorklist.add(succ.id);
      }
    }
  }

  // Apply narrowing phase to recover precision after widening
  var narrowingIterations = 0;
  var narrowingApplied = false;
  if (wideningApplied) {
    narrowingIterations = _applyNarrowing(cfg, entryStates, exitStates);
    narrowingApplied = narrowingIterations > 0;
  }

  return AnalysisResult(
    entryStates: entryStates,
    exitStates: exitStates,
    iterations: iterations,
    wideningApplied: wideningApplied,
    narrowingApplied: narrowingApplied,
    narrowingIterations: narrowingIterations,
  );
}