test/gtest/wto.cpp

/*
 * Copyright 2026 WebAssembly Community Group participants
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include <memory>
#include <sstream>
#include <unordered_map>
#include <unordered_set>
#include <variant>
#include <vector>

#include "cfg/wto.h"
#include "gtest/gtest.h"

using namespace wasm;

namespace {

// The WTO utility is parameterized on the BasicBlock type associated with a
// CFG. Since BasicBlock itself contains a user-provided Contents type, there is
// no canonical BasicBlock type ready to use. Since we don't need a full
// CFGWalker, just create a mini version of CFGWalker for testing that has all
// the expected associated types and fields.
struct TestCFG {
  struct Contents {
    bool inQueue = false;
    Index index = 0;
  };

  struct BasicBlock {
    Contents contents;
    std::vector<BasicBlock*> out;
    std::vector<BasicBlock*> in;
  };

  std::vector<std::unique_ptr<BasicBlock>> basicBlocks;
  std::vector<BasicBlock*> loopTops;
  BasicBlock* entry = nullptr;

  explicit TestCFG(Index numBlocks) {
    basicBlocks.reserve(numBlocks);
    for (Index i = 0; i < numBlocks; ++i) {
      auto block = std::make_unique<BasicBlock>();
      block->contents.index = i;
      basicBlocks.push_back(std::move(block));
    }
    if (numBlocks > 0) {
      entry = basicBlocks[0].get();
    }
  }

  void addEdge(Index u, Index v) {
    assert(u < basicBlocks.size());
    assert(v < basicBlocks.size());
    basicBlocks[u]->out.push_back(basicBlocks[v].get());
    basicBlocks[v]->in.push_back(basicBlocks[u].get());
    if (u >= v) {
      loopTops.push_back(basicBlocks[v].get());
    }
  }
};

// Index-based mirror of a Weak Topological Ordering used in tests so that:
//   1. Expected orderings can be written concisely with block indices (e.g.
//      `WTOList{0, C({1, 2}), 3}`) and pretty-printed on failure.
//   2. Test assertions remain independent of the internal representation of
//      `WeakTopologicalOrdering` (which will be flattened into a contiguous
//      entry array in a follow-on commit).
struct WTOCycle;
struct WTOElem;
using WTOList = std::vector<WTOElem>;

struct WTOCycle {
  WTOList elems;

  WTOCycle(std::initializer_list<WTOElem> list);
  explicit WTOCycle(WTOList elems);

  Index head() const;
  bool operator==(const WTOCycle& other) const;
};

struct WTOElem : std::variant<Index, WTOCycle> {
  using Base = std::variant<Index, WTOCycle>;
  using Base::Base;
  WTOElem(Index v) : Base(v) {}
  WTOElem(int v) : Base(Index(v)) {}
  WTOElem(WTOCycle c) : Base(std::move(c)) {}
};

WTOCycle::WTOCycle(std::initializer_list<WTOElem> list) : elems(list) {}
WTOCycle::WTOCycle(WTOList elems) : elems(std::move(elems)) {}
Index WTOCycle::head() const { return std::get<Index>(elems.front()); }
bool WTOCycle::operator==(const WTOCycle& other) const {
  return elems == other.elems;
}

WTOCycle C(std::initializer_list<WTOElem> list) { return WTOCycle(list); }

std::ostream& operator<<(std::ostream& os, const WTOElem& elem);
std::ostream& operator<<(std::ostream& os, const WTOList& list);

std::ostream& operator<<(std::ostream& os, const WTOCycle& cycle) {
  return os << "(" << cycle.elems << ")";
}

std::ostream& operator<<(std::ostream& os, const WTOElem& elem) {
  if (auto* v = std::get_if<Index>(&elem)) {
    return os << *v;
  }
  return os << std::get<WTOCycle>(elem);
}

std::ostream& operator<<(std::ostream& os, const WTOList& list) {
  for (size_t i = 0; i < list.size(); ++i) {
    if (i > 0) {
      os << " ";
    }
    os << list[i];
  }
  return os;
}

using BasicBlock = TestCFG::BasicBlock;

WTOList toIndexWTO(const WeakTopologicalOrdering<BasicBlock>& wto) {
  constexpr Index NoIndex = WeakTopologicalOrdering<BasicBlock>::NoIndex;
  std::vector<std::pair<Index, WTOElem>> stack;
  for (Index pc = 0; pc < wto.entries.size(); ++pc) {
    const auto& entry = wto.entries[pc];
    if (entry.cycleTarget == NoIndex) {
      stack.emplace_back(pc, WTOElem(entry.block->contents.index));
    } else {
      EXPECT_EQ(entry.block, wto.entries[entry.cycleTarget].block);
      size_t start = stack.size();
      while (stack[start - 1].first != entry.cycleTarget) {
        --start;
      }
      WTOList cycleElems;
      for (size_t i = start - 1; i < stack.size(); ++i) {
        cycleElems.push_back(std::move(stack[i].second));
      }
      stack.erase(stack.begin() + start, stack.end());
      stack.back() = {NoIndex, WTOElem(WTOCycle(std::move(cycleElems)))};
    }
  }
  WTOList dst;
  for (auto& [_, elem] : stack) {
    dst.push_back(std::move(elem));
  }
  return dst;
}

// Check the formal properties of a Weak Topological Ordering (Bourdoncle 1993,
// Definition 1) over the reachable subgraph of `cfg`.
void verifyWTOInvariants(const TestCFG& cfg, const WTOList& wto) {
  std::vector<Index> flatOrder;
  std::unordered_map<Index, size_t> pos;
  std::unordered_map<Index, std::unordered_set<Index>> cycleMembers;

  auto walk = [&](auto& self,
                  const WTOList& list,
                  std::vector<Index>& activeHeads) -> void {
    for (const auto& elem : list) {
      if (auto* v = std::get_if<Index>(&elem)) {
        // Every vertex appears at most once in the flattened ordering.
        EXPECT_FALSE(pos.contains(*v)) << "Duplicate vertex " << *v;
        pos[*v] = flatOrder.size();
        flatOrder.push_back(*v);
        for (Index head : activeHeads) {
          cycleMembers[head].insert(*v);
        }
      } else {
        // Every cycle is non-empty and its head (first element) is a single
        // vertex, not a nested cycle.
        const auto& cycle = std::get<WTOCycle>(elem);
        ASSERT_FALSE(cycle.elems.empty()) << "Empty cycle in WTO";
        ASSERT_TRUE(std::holds_alternative<Index>(cycle.elems.front()))
          << "Cycle head must be a single vertex, not a nested cycle";
        Index head = cycle.head();
        activeHeads.push_back(head);
        self(self, cycle.elems, activeHeads);
        activeHeads.pop_back();
      }
    }
  };

  std::vector<Index> activeHeads;
  walk(walk, wto, activeHeads);

  // Check invariants for edges u -> v.
  for (Index u : flatOrder) {
    for (auto* succ : cfg.basicBlocks[u]->out) {
      Index v = succ->contents.index;
      // Every reachable vertex appears at least once in the ordering.
      ASSERT_TRUE(pos.contains(v))
        << "Reachable vertex " << v << " missing from WTO";
      if (pos[u] >= pos[v]) {
        // Backedges must be to the head of a cycle containing both v and u.
        ASSERT_TRUE(cycleMembers.contains(v))
          << "Back-edge " << u << " -> " << v << " targets non-head vertex "
          << v;
        EXPECT_TRUE(cycleMembers[v].contains(u))
          << "Back-edge " << u << " -> " << v
          << " is not enclosed in the cycle headed by " << v;
      }
    }
  }
}

WTOList getWTO(TestCFG& cfg) {
  WeakTopologicalOrdering<BasicBlock> wto(cfg.basicBlocks);
  auto list = toIndexWTO(wto);
  EXPECT_EQ(list, list);
  verifyWTOInvariants(cfg, list);
  return list;
}

} // namespace

TEST(WTOTest, Empty) {
  TestCFG cfg(0);
  EXPECT_EQ(getWTO(cfg), WTOList{});
}

TEST(WTOTest, Singleton) {
  TestCFG cfg(1);
  EXPECT_EQ(getWTO(cfg), WTOList{0});
}

TEST(WTOTest, LinearChain) {
  TestCFG cfg(3);
  cfg.addEdge(0, 1);
  cfg.addEdge(1, 2);
  EXPECT_EQ(getWTO(cfg), (WTOList{0, 1, 2}));
}

TEST(WTOTest, Diamond) {
  {
    TestCFG cfg(4);
    cfg.addEdge(0, 1);
    cfg.addEdge(0, 2);
    cfg.addEdge(1, 3);
    cfg.addEdge(2, 3);
    EXPECT_EQ(getWTO(cfg), (WTOList{0, 1, 2, 3}));
  }
  {
    // Reversed edge insertion order at the split and join.
    TestCFG cfg(4);
    cfg.addEdge(0, 2);
    cfg.addEdge(0, 1);
    cfg.addEdge(2, 3);
    cfg.addEdge(1, 3);
    EXPECT_EQ(getWTO(cfg), (WTOList{0, 1, 2, 3}));
  }
  {
    // Asymmetric diamond (one arm has two blocks, the other has one) under both
    // valid RPO block orderings.
    TestCFG leftFirst(5);
    leftFirst.addEdge(0, 1);
    leftFirst.addEdge(1, 2);
    leftFirst.addEdge(0, 3);
    leftFirst.addEdge(2, 4);
    leftFirst.addEdge(3, 4);
    EXPECT_EQ(getWTO(leftFirst), (WTOList{0, 1, 2, 3, 4}));

    TestCFG rightFirst(5);
    rightFirst.addEdge(0, 2);
    rightFirst.addEdge(2, 3);
    rightFirst.addEdge(0, 1);
    rightFirst.addEdge(3, 4);
    rightFirst.addEdge(1, 4);
    EXPECT_EQ(getWTO(rightFirst), (WTOList{0, 1, 2, 3, 4}));
  }
}

TEST(WTOTest, SelfLoop) {
  TestCFG cfg(3);
  cfg.addEdge(0, 0);
  cfg.addEdge(0, 1);
  cfg.addEdge(1, 1);
  cfg.addEdge(1, 2);
  EXPECT_EQ(getWTO(cfg), (WTOList{C({0}), C({1}), 2}));
}

TEST(WTOTest, SimpleCycle) {
  TestCFG cfg(2);
  cfg.addEdge(0, 1);
  cfg.addEdge(1, 0);
  EXPECT_EQ(getWTO(cfg), (WTOList{C({0, 1})}));
}

TEST(WTOTest, ThreeNodeCycle) {
  TestCFG cfg(3);
  cfg.addEdge(0, 1);
  cfg.addEdge(1, 2);
  cfg.addEdge(2, 0);
  EXPECT_EQ(getWTO(cfg), (WTOList{C({0, 1, 2})}));
}

TEST(WTOTest, SharedLoopHeader) {
  // Two loops sharing header 0: 0 -> 1 -> 0 and 0 -> 2 -> 0.
  TestCFG cfg(3);
  cfg.addEdge(0, 1);
  cfg.addEdge(1, 0);
  cfg.addEdge(0, 2);
  cfg.addEdge(2, 0);
  EXPECT_EQ(getWTO(cfg), (WTOList{C({0, 1, 2})}));
}

TEST(WTOTest, BourdonclePaperExample) {
  // The example control-flow graph from Bourdoncle's 1993 paper "Efficient
  // chaotic iteration strategies with widenings", Figure 1 (0-indexed: vertices
  // 0..7 correspond to 1..8 in the paper):
  //   0 -> 1
  //   1 -> 2, 1 -> 7
  //   2 -> 3
  //   3 -> 4, 3 -> 6
  //   4 -> 5
  //   5 -> 4, 5 -> 6
  //   6 -> 2, 6 -> 7
  // Expected WTO from the paper: 0 1 (2 3 (4 5) 6) 7
  TestCFG cfg(8);
  cfg.addEdge(0, 1);
  cfg.addEdge(1, 2);
  cfg.addEdge(1, 7);
  cfg.addEdge(2, 3);
  cfg.addEdge(3, 4);
  cfg.addEdge(3, 6);
  cfg.addEdge(4, 5);
  cfg.addEdge(5, 4);
  cfg.addEdge(5, 6);
  cfg.addEdge(6, 2);
  cfg.addEdge(6, 7);
  auto wto = getWTO(cfg);
  EXPECT_EQ(wto, (WTOList{0, 1, C({2, 3, C({4, 5}), 6}), 7}));
  std::ostringstream ss;
  ss << wto;
  EXPECT_EQ(ss.str(), "0 1 (2 3 (4 5) 6) 7");
}

TEST(WTOTest, LoopHeaderDominatesExit) {
  // Same as Bourdoncle's paper graph, except block 7 is only reachable from
  // block 6 (no direct edge 1 -> 7). Block 2 dominates block 7 even though
  // block 7 is outside the natural loop of 2. Block 7 must remain outside the
  // cycle of 2.
  TestCFG cfg(8);
  cfg.addEdge(0, 1);
  cfg.addEdge(1, 2);
  cfg.addEdge(2, 3);
  cfg.addEdge(3, 4);
  cfg.addEdge(3, 6);
  cfg.addEdge(4, 5);
  cfg.addEdge(5, 4);
  cfg.addEdge(5, 6);
  cfg.addEdge(6, 2);
  cfg.addEdge(6, 7);
  EXPECT_EQ(getWTO(cfg), (WTOList{0, 1, C({2, 3, C({4, 5}), 6}), 7}));
}

TEST(WTOTest, DiamondOfLoops) {
  // 01 -> 23 -> 67 and 01 -> 45 -> 67, where each pair is a 2-block loop.
  TestCFG cfg(8);
  cfg.addEdge(0, 1);
  cfg.addEdge(1, 0);
  cfg.addEdge(1, 2);
  cfg.addEdge(1, 4);

  cfg.addEdge(2, 3);
  cfg.addEdge(3, 2);
  cfg.addEdge(3, 6);

  cfg.addEdge(4, 5);
  cfg.addEdge(5, 4);
  cfg.addEdge(5, 6);

  cfg.addEdge(6, 7);
  cfg.addEdge(7, 6);

  EXPECT_EQ(getWTO(cfg), (WTOList{C({0, 1}), C({2, 3}), C({4, 5}), C({6, 7})}));
}

TEST(WTOTest, UnreachableBlocks) {
  // Blocks 0, 1, 2 form a reachable loop 0 -> 1 -> 2 -> 1.
  // Blocks 3, 4 form an unreachable cycle 3 -> 4 -> 3 with edges into 1 and 2.
  TestCFG cfg(5);
  cfg.addEdge(0, 1);
  cfg.addEdge(1, 2);
  cfg.addEdge(2, 1);
  cfg.addEdge(3, 4);
  cfg.addEdge(4, 3);
  cfg.addEdge(3, 1);
  cfg.addEdge(4, 2);
  EXPECT_EQ(getWTO(cfg), (WTOList{0, C({1, 2})}));
}

TEST(WTOTest, WorklistEvaluation) {
  // Evaluate a chaotic iteration sequence on Bourdoncle's paper graph where the
  // inner cycle (4 5) stabilizes in 2 iterations and the outer cycle
  // (2 3 (4 5) 6) stabilizes in 2 iterations.
  TestCFG cfg(8);
  cfg.addEdge(0, 1);
  cfg.addEdge(1, 2);
  cfg.addEdge(1, 7);
  cfg.addEdge(2, 3);
  cfg.addEdge(3, 4);
  cfg.addEdge(3, 6);
  cfg.addEdge(4, 5);
  cfg.addEdge(5, 4);
  cfg.addEdge(5, 6);
  cfg.addEdge(6, 2);
  cfg.addEdge(6, 7);

  WTOWorklist<TestCFG> work(cfg);
  work.push(cfg.entry);

  std::vector<Index> visits;
  unsigned count4 = 0;
  unsigned count2 = 0;
  work.run([&](BasicBlock* block) {
    Index id = block->contents.index;
    visits.push_back(id);
    for (auto* out : block->out) {
      Index outId = out->contents.index;
      if (id == 5 && outId == 4) {
        if (++count4 < 2) {
          work.push(out);
        }
      } else if (id == 6 && outId == 2) {
        if (++count2 < 2) {
          count4 = 0;
          work.push(out);
        }
      } else {
        work.push(out);
      }
    }
  });

  // Expected recursive evaluation order:
  // 0, 1,
  // first iteration of (2 3 (4 5) 6): 2, 3, 4, 5, 4, 5, 6,
  // second iteration of (2 3 (4 5) 6): 2, 3, 4, 5, 4, 5, 6,
  // 7
  EXPECT_EQ(
    visits,
    (std::vector<Index>{0, 1, 2, 3, 4, 5, 4, 5, 6, 2, 3, 4, 5, 4, 5, 6, 7}));
}

TEST(WTOTest, WorklistSelectivePropagation) {
  // In Bourdoncle's graph, test when block 3 only queues block 6 (skipping the
  // inner cycle (4 5) completely) and block 6 does not re-queue block 2.
  TestCFG cfg(8);
  cfg.addEdge(0, 1);
  cfg.addEdge(1, 2);
  cfg.addEdge(1, 7);
  cfg.addEdge(2, 3);
  cfg.addEdge(3, 4);
  cfg.addEdge(3, 6);
  cfg.addEdge(4, 5);
  cfg.addEdge(5, 4);
  cfg.addEdge(5, 6);
  cfg.addEdge(6, 2);
  cfg.addEdge(6, 7);

  WTOWorklist<TestCFG> work(cfg);
  work.push(cfg.entry);

  std::vector<Index> visits;
  work.run([&](BasicBlock* block) {
    Index id = block->contents.index;
    visits.push_back(id);
    if (id == 0) {
      work.push(cfg.basicBlocks[1].get());
    } else if (id == 1) {
      work.push(cfg.basicBlocks[2].get());
    } else if (id == 2) {
      work.push(cfg.basicBlocks[3].get());
    } else if (id == 3) {
      work.push(cfg.basicBlocks[6].get());
    } else if (id == 6) {
      work.push(cfg.basicBlocks[7].get());
    }
  });

  EXPECT_EQ(visits, (std::vector<Index>{0, 1, 2, 3, 6, 7}));
}