PyPTO Structural Comparison¶

Overview¶

PyPTO provides two utility functions for comparing IR nodes by structure rather than pointer identity:

structural_equal(lhs, rhs, enable_auto_mapping=False) -> bool
structural_hash(node, enable_auto_mapping=False) -> int

Use Cases: CSE, IR optimization, pattern matching, testing

Key Feature: Both functions ignore Span (source location), focusing only on logical structure.

Reference vs Structural Equality¶

Reference Equality (Default `==`)¶

Compares pointer addresses (O(1), fast):

from pypto import DataType, ir

x1 = ir.Var("x", ir.ScalarType(DataType.INT64), ir.Span.unknown())
x2 = ir.Var("x", ir.ScalarType(DataType.INT64), ir.Span.unknown())
assert x1 != x2  # Different pointers

Structural Equality¶

Compares content and structure:

ir.assert_structural_equal(x1, x2, enable_auto_mapping=True)  # True

Comparison Process¶

The structural_equal function follows these steps:

Fast Path Checks
Reference equality: If same pointer, return true
Null check: If either is null, return false
Type check: Compare TypeName() - must match exactly
Type Dispatch
Variables get special handling (auto-mapping)
Other types use reflection-based field comparison
Field-Based Recursive Comparison
Get field descriptors via GetFieldDescriptors()
Iterate through all fields using reflection
Compare each field based on its type
Combine results with AND logic

Reflection and Field Types¶

The reflection system defines three field types:

Field Type	Auto-Mapping	Compared?	Use Case	Effect
IgnoreField	N/A	❌ No	Source locations (`Span`), names	Always considered equal
UsualField	Follows parameter	✅ Yes	Operands, expressions, types	Compared with current `enable_auto_mapping`
DefField	✅ Always enabled	✅ Yes	Variable definitions, parameters	Always uses auto-mapping

Example Field Definitions¶

class IRNode {
  Span span_;
  static constexpr auto GetFieldDescriptors() {
    return std::make_tuple(
      reflection::IgnoreField(&IRNode::span_, "span")
    );
  }
};

class BinaryExpr : public Expr {
  ExprPtr left_;
  ExprPtr right_;
  static constexpr auto GetFieldDescriptors() {
    return std::tuple_cat(
      Expr::GetFieldDescriptors(),
      std::make_tuple(
        reflection::UsualField(&BinaryExpr::left_, "left"),
        reflection::UsualField(&BinaryExpr::right_, "right")
      )
    );
  }
};

class AssignStmt : public Stmt {
  VarPtr var_;     // Definition
  ExprPtr value_;  // Usage
  static constexpr auto GetFieldDescriptors() {
    return std::tuple_cat(
      Stmt::GetFieldDescriptors(),
      std::make_tuple(
        reflection::DefField(&AssignStmt::var_, "var"),
        reflection::UsualField(&AssignStmt::value_, "value")
      )
    );
  }
};

Why DefField Matters¶

DefFields represent variable definitions. When comparing definitions, we care about structural position, not identity:

# Build: x = y
x1 = ir.Var("x", ir.ScalarType(DataType.INT64), span)
y1 = ir.Var("y", ir.ScalarType(DataType.INT64), span)
stmt1 = ir.AssignStmt(x1, y1, span)

# Build: a = b
a = ir.Var("a", ir.ScalarType(DataType.INT64), span)
b = ir.Var("b", ir.ScalarType(DataType.INT64), span)
stmt2 = ir.AssignStmt(a, b, span)

# var_ is DefField, so x1 and a are mapped automatically
ir.assert_structural_equal(stmt1, stmt2, enable_auto_mapping=True)

structural_equal Function¶

Basic Usage¶

# Same value
c1 = ir.ConstInt(42, DataType.INT64, ir.Span.unknown())
c2 = ir.ConstInt(42, DataType.INT64, ir.Span.unknown())
ir.assert_structural_equal(c1, c2)  # True

# Different types
var = ir.Var("x", ir.ScalarType(DataType.INT64), ir.Span.unknown())
const = ir.ConstInt(1, DataType.INT64, ir.Span.unknown())
assert not ir.structural_equal(var, const)  # False

Auto-Mapping Behavior¶

Scenario	enable_auto_mapping=False	enable_auto_mapping=True
Same variable pointer	✅ Equal	✅ Equal
Different variable pointers	❌ Not equal	✅ Equal (if type matches)
Consistent mapping (`x + x` vs `y + y`)	❌ Not equal	✅ Equal
Inconsistent mapping (`x + x` vs `y + z`)	❌ Not equal	❌ Not equal

When to Enable Auto-Mapping¶

Use Case	Setting
Pass transform tests (Before/Expected pattern)	`False` (default) — DefFields always auto-map
Serialization round-trip tests	`True` — deserialized Vars are never DefFields
Pattern matching regardless of variable names	`True`
Template matching for optimization rules	`True`
Exact matching with same variables	`False`
CSE (Common Subexpression Elimination)	`False`

Why pass tests don't need it: VisitDefField always enables auto-mapping internally (see structural_equal.cpp:650), populating the bidirectional Var maps. When the same Vars later appear as UsualField references, they are found in the maps — even with enable_auto_mapping=False.

structural_hash Function¶

Basic Usage¶

c1 = ir.ConstInt(42, DataType.INT64, ir.Span.unknown())
c2 = ir.ConstInt(42, DataType.INT64, ir.Span.unknown())
assert ir.structural_hash(c1) == ir.structural_hash(c2)

Determinism¶

structural_hash is deterministic within a single process run. Variable identity is based on monotonic unique IDs (Var::unique_id_) assigned at construction, not pointer addresses or name_hint_ strings, so the same construction sequence always produces the same hashes. The name_hint_ field is an IgnoreField and is excluded from both structural comparison and hashing.

Hash Consistency Guarantee¶

Rule: If structural_equal(a, b, mode) is True, then structural_hash(a, mode) == structural_hash(b, mode)

Using with Containers¶

class CSEPass:
    def __init__(self):
        self.expr_cache = {}

    def deduplicate(self, expr):
        hash_val = ir.structural_hash(expr, enable_auto_mapping=False)
        if hash_val in self.expr_cache:
            for cached_expr in self.expr_cache[hash_val]:
                if ir.structural_equal(expr, cached_expr, enable_auto_mapping=False):
                    return cached_expr
            self.expr_cache[hash_val].append(expr)
        else:
            self.expr_cache[hash_val] = [expr]
        return expr

Auto-Mapping Algorithm¶

The implementation maintains bidirectional maps:

class StructuralEqual {
  std::unordered_map<VarPtr, VarPtr> lhs_to_rhs_var_map_;
  std::unordered_map<VarPtr, VarPtr> rhs_to_lhs_var_map_;

  bool EqualVar(const VarPtr& lhs, const VarPtr& rhs) {
    if (!enable_auto_mapping_) {
      return lhs.get() == rhs.get();  // Strict pointer equality
    }

    // Check type equality first
    if (!EqualType(lhs->GetType(), rhs->GetType())) return false;

    // Check existing mapping
    auto it = lhs_to_rhs_var_map_.find(lhs);
    if (it != lhs_to_rhs_var_map_.end()) {
      return it->second == rhs;  // Verify consistent
    }

    // Ensure rhs not already mapped to different lhs
    auto rhs_it = rhs_to_lhs_var_map_.find(rhs);
    if (rhs_it != rhs_to_lhs_var_map_.end() && rhs_it->second != lhs) {
      return false;
    }

    // Create new mapping
    lhs_to_rhs_var_map_[lhs] = rhs;
    rhs_to_lhs_var_map_[rhs] = lhs;
    return true;
  }
};

Key Points:

Without auto-mapping: strict identity comparison (pointer equality for structural_equal, unique IDs for structural_hash)
With auto-mapping: establish and enforce consistent mapping
Type equality checked before mapping
Bidirectional maps prevent inconsistent mappings

Implementation Details¶

Hash Combine Algorithm¶

Uses Boost-inspired algorithm:

inline uint64_t hash_combine(uint64_t seed, uint64_t value) {
  return seed ^ (value + 0x9e3779b9 + (seed << 6) + (seed >> 2));
}

Reflection-Based Field Visitor¶

Generic traversal without type-specific code:

template <typename NodePtr>
bool EqualWithFields(const NodePtr& lhs_op, const NodePtr& rhs_op) {
  using NodeType = typename NodePtr::element_type;
  auto descriptors = NodeType::GetFieldDescriptors();
  return std::apply([&](auto&&... descs) {
    return reflection::FieldIterator<...>::Visit(
      *lhs_op, *rhs_op, *this, descs...);
  }, descriptors);
}

Types Are Compared by Hand, Not by Reflection¶

Expr and Stmt go through the reflection visitor above. Type does not. Four independent if/else ladders each re-encode "what fields does this Type have", and nothing links them:

Ladder	Location
`EqualType`	`src/ir/transforms/structural_equal.cpp`
`HashType`	`src/ir/transforms/structural_hash.cpp`
`SerializeType`	`src/ir/serialization/serializer.cpp`
`DeserializeType`	`src/ir/serialization/deserializer.cpp`

Adding a Type means editing all four. A Type added to three of them compiles, passes serialization round-trips, and compares correctly — then hits HashType's trailing INTERNAL_CHECK(false) the first time a user writes hash(t) or puts the Type in a set. That breaks the equal-nodes-hash-equally guarantee above, since structural_equal accepts what structural_hash rejects.

Three dispatch hazards to mirror across the ladders:

Subclass kinds. As<T>() is a precise ObjectKind match, so As<TensorType>(dt) returns nullptr for a DistributedTensorType by design (see include/pypto/ir/kind_traits.h). A shared branch must name both kinds explicitly and static_pointer_cast — see .claude/rules/ir-kind-traits.md.
Subclass-only fields. DistributedTensorType::window_buffer_ has no TensorType counterpart; a shared branch has to hash and compare it under a kind guard.
Nullable fields. A bare ExprPtr field with no non-null invariant — TileView::start_offset, which the default ctor and pl.TileView(...) both leave unset — is a legal, distinct state, not a construction bug. EqualType gets that for free by routing it through the null-tolerant Equal(...), so HashType must hash a presence tag rather than INTERNAL_CHECK on it. Guarding one ladder and not the other breaks the guarantee in the same direction as a missing Type: structural_equal reports a value equal to itself that structural_hash aborts on. Reserve INTERNAL_CHECK in HashType for fields that genuinely cannot be null, such as shape_ elements.

tests/ut/ir/transforms/test_hash.py::TestHashTypeLadderParity walks every Python-constructible Type and fails when one is missing from HashType. Add a factory there for each new Type.

Summary¶

Key Takeaways:

Three Field Types:
IgnoreField: Never compared (Span, names)
UsualField: Compared with user's enable_auto_mapping
DefField: Always uses auto-mapping
Auto-Mapping:
Enable for pattern matching
Disable for exact CSE
Always consistent: maintains bijective variable mapping
Hash Consistency:
Equal nodes → equal hashes (guaranteed)
Use same enable_auto_mapping for both functions

For IR node types and construction, see IR Overview.

PyPTO Structural Comparison¶

Overview¶

Reference vs Structural Equality¶

Reference Equality (Default ==)¶

Structural Equality¶

Comparison Process¶

Reflection and Field Types¶

Example Field Definitions¶

Why DefField Matters¶

structural_equal Function¶

Basic Usage¶

Auto-Mapping Behavior¶

When to Enable Auto-Mapping¶

structural_hash Function¶

Basic Usage¶

Determinism¶

Hash Consistency Guarantee¶

Using with Containers¶

Auto-Mapping Algorithm¶

Implementation Details¶

Hash Combine Algorithm¶

Reflection-Based Field Visitor¶

Types Are Compared by Hand, Not by Reflection¶

Summary¶

Reference Equality (Default `==`)¶