void run()

in include/MonotonicFixpointIterator.h [551:631]

• 61 lines of code
• 12 McCabe index (conditional complexity)

  void run(const Domain& init) {
    this->clear();
    Context context(init);
    std::unique_ptr<std::atomic<uint32_t>[]> wpo_counter(
        new std::atomic<uint32_t>[m_wpo.size()]);
    std::fill_n(wpo_counter.get(), m_wpo.size(), 0);
    std::queue<uint32_t> work_queue;
    auto entry_idx = m_wpo.get_entry();
    assert(m_wpo.get_num_preds(entry_idx) == 0);
    // Prepare work queue.
    auto process_node = [&](uint32_t wpo_idx) {
      assert(wpo_counter[wpo_idx] == m_wpo.get_num_preds(wpo_idx));
      wpo_counter[wpo_idx] = 0;
      // NonExit node
      if (!m_wpo.is_exit(wpo_idx)) {
        this->analyze_vertex(&context, m_wpo.get_node(wpo_idx));
        for (auto succ_idx : m_wpo.get_successors(wpo_idx)) {
          // Increase succ node's counter, push succ nodes in work queue if
          // their counter number matches their NumSchedPreds.
          if (++wpo_counter[succ_idx] == m_wpo.get_num_preds(succ_idx)) {
            work_queue.emplace(succ_idx);
          }
        }
        return nullptr;
      }
      // Exit node
      // Check if component of the exit node has stabilized.
      uint32_t head_idx = m_wpo.get_head_of_exit(wpo_idx);
      NodeId head = m_wpo.get_node(head_idx);
      Domain* current_state = &this->m_entry_states[head];
      Domain new_state = Domain::bottom();
      this->compute_entry_state(&context, head, &new_state);
      if (new_state.leq(*current_state)) {
        // Component stabilized.
        context.reset_local_iteration_count_for(head);
        *current_state = std::move(new_state);
        for (auto succ_idx : m_wpo.get_successors(wpo_idx)) {
          // Increase succ node's counter, push succ nodes in work queue if
          // their counter number matches their NumSchedPreds.
          if (++wpo_counter[succ_idx] == m_wpo.get_num_preds(succ_idx)) {
            work_queue.emplace(succ_idx);
          }
        }
      } else {
        // Component didn't stabilize.
        this->extrapolate(context, head, current_state, new_state);
        context.increase_iteration_count_for(head);
        // Set component nodes v's counter to their
        // NumOuterSchedPreds(v, wpo_idx)
        for (auto pred_pair : m_wpo.get_num_outer_preds(wpo_idx)) {
          auto component_idx = pred_pair.first;
          assert(component_idx != entry_idx);
          // Push component nodes in work queue if their counter number
          // matches their NumSchedPreds.
          if ((wpo_counter[component_idx] += pred_pair.second) ==
              m_wpo.get_num_preds(component_idx)) {
            work_queue.emplace(component_idx);
          }
        }
        if (head_idx == entry_idx) {
          // Handle special case when there is a loop on entry node.
          // Because entry node have num_preds = 0, and for
          // get_num_outer_preds the nodes with num_outer_preds are ignored.
          // So we need to manually add entry node back to work queue if
          // the component didn't stabilize.
          work_queue.emplace(head_idx);
        }
      }
      return nullptr;
    };
    // Start from wpo entry node.
    work_queue.emplace(entry_idx);
    while (!work_queue.empty()) {
      auto item = work_queue.front();
      work_queue.pop();
      process_node(item);
    }
    for (uint32_t idx = 0; idx < m_wpo.size(); ++idx) {
      assert(wpo_counter[idx] == 0);
    }
  }