Function OrderBlocks

source/disassemble.cpp:410–484

Given the control flow graph, calculates and returns the reverse post-order ordering of the blocks. The blocks are then disassembled in that order for readability.

// ordering of the blocks.  The blocks are then disassembled in that order for
// readability.
std::vector<uint32_t> OrderBlocks(
    ControlFlowGraph& cfg,
    const std::unordered_map<uint32_t, uint32_t>& id_to_index) {
  std::vector<uint32_t> post_order;

  // Nest level of a function's first block is 0.
  cfg.blocks[0].nest_level = 0;
  cfg.blocks[0].nest_level_assigned = true;

  // Stack of block indices as they are visited.
  std::stack<StackEntry> dfs_stack;
  dfs_stack.push({0, false});

  std::set<uint32_t> visited;

  while (!dfs_stack.empty()) {
    const uint32_t block_index = dfs_stack.top().block_index;
    const bool post_visit = dfs_stack.top().post_visit;
    dfs_stack.pop();

    // If this is the second time the block is visited, that's the post-order
    // visit.
    if (post_visit) {
      post_order.push_back(block_index);
      continue;
    }

    // If already visited, another path got to it first (like a case
    // fallthrough), avoid reprocessing it.
    if (visited.count(block_index) > 0) {
      continue;
    }
    visited.insert(block_index);

    // Push it back in the stack for post-order visit
    dfs_stack.push({block_index, true});

    SingleBlock& block = cfg.blocks[block_index];

    // Assign nest levels of successors right away.  The successors are either
    // nested under this block, or are back or forward edges to blocks outside
    // this nesting level (no farther than the merge block), whose nesting
    // levels are already assigned before this block is visited.
    NestSuccessors(cfg, block, id_to_index);
    block.reachable = true;

    // The post-order visit yields the order in which the blocks are naturally
    // ordered _backwards_. So blocks to be ordered last should be visited
    // first.  In other words, they should be pushed to the DFS stack last.
    VisitSuccesor(&dfs_stack, id_to_index, block.successors.true_block_id);
    VisitSuccesor(&dfs_stack, id_to_index, block.successors.false_block_id);
    VisitSuccesor(&dfs_stack, id_to_index, block.successors.body_block_id);
    VisitSuccesor(&dfs_stack, id_to_index, block.successors.next_block_id);
    for (uint32_t case_block_id : block.successors.case_block_ids) {
      VisitSuccesor(&dfs_stack, id_to_index, case_block_id);
    }
    VisitSuccesor(&dfs_stack, id_to_index, block.successors.continue_block_id);
    VisitSuccesor(&dfs_stack, id_to_index, block.successors.merge_block_id);