SymbolTable and Symbol parent/child relationship

MLIR
1

Should a Symbol’s immediate parent be a SymbolTable? I think so, according to the docs.

A Symbol is a named operation that resides immediately within a region that defines a SymbolTable

But this would not allow nested functions. A function is a symbol but not a SymbolTable. So according to the definition of a Symbol, a function’s parent should not be a function.

I added verification to the Symbol interface to ensure its parent is a SymbolTable in my fork. This mimics this assertion, which was triggered in this issue.

My patch finds 12 failures in the mlir test suite. One example is nested functions in cse tests.

Failed Tests (12):
  MLIR :: Dialect/LLVMIR/global.mlir
  MLIR :: Dialect/Linalg/transform-op-replace.mlir
  MLIR :: Dialect/Transform/ops-invalid.mlir
  MLIR :: IR/invalid-func-op.mlir
  MLIR :: IR/region.mlir
  MLIR :: IR/traits.mlir
  MLIR :: Transforms/canonicalize-dce.mlir
  MLIR :: Transforms/canonicalize.mlir
  MLIR :: Transforms/constant-fold.mlir
  MLIR :: Transforms/cse.mlir
  MLIR :: Transforms/test-legalizer-full.mlir
  MLIR :: mlir-pdll/Integration/test-pdll.mlir

We should move forward with one of the following:

  1. Enforce direct parent-child relationship between SymbolTable and Symbol through verification. Rewrite tests as needed. This is likely to break a lot of downstream MLIR.
  2. Redefine Symbol semantics so the parent-child relationship does not need to be immediate.
  3. Reconsider some ops to be SymbolTable’s. For example, if we want nested functions, maybe func.func’s can be both a SymbolTable and a Symbol.

Going with the docs, I think option 1 makes the most sense, but it can cause a lot of compatibility issues.

2

Thanks for raising this issue!

A clear-cut answer: we do not want nested functions using func.func as we have never considered any implications of having those, e.g., closure. Other dialects, including downstream, may have nested functions and closures with their own semantics. We should remove nested func.func from tests regardless of the outcome of this discussion. We can also have a separate discussion on closures if desired.

A less clear-cut answer: we should likely start by enabling that check and enforcing symbols to be immediately nested in symbol tables as documented. That being said, we may have legitimate cases for “wrapper” operations between symbols and symbol tables so we may as well relax the constraint in the documentation and just check that there is an ancestor that is a symbol table.

1 Like
3

Do you have an example of a “wrapper operation”?

I feel like the first and second sentence are directly conflicting with each other. It sounds like we do want immediately nested Symbols, but we won’t actually be able to enforce it if we allow for in-between operations.

4

Speaking as a downstream, CIRCT has to implement symbol-like things which work for our use cases so as to not break the parent-child relationship specified in the doc when using symbols. This last bit has been harder to enforce as dialect developers keep turning to symbols, but don’t follow the rules. Since they do not see immediate failure when they violate the parent requirement of symbols, they wind up with subtle correctness issues which are hard to catch.

CIRCT uses symbols at the top level, though this is getting more tenuous, to track modules, much like functions. The main problem isn’t so much the symbol-is-immediately-a-child-of-a-symbol-table, but that symbol resolution can’t escape the current symbol table. While this is done for various implementation reasons, it means that symbols become useless to implement constructs such as namespaces as symbol tables with symbols and symbol users in them. Symbol uses in a symbol table cannot (per the docs) refer to things defined as a child of anything but their symbol table. In HW design, we often have operations in a module (function) which are referred to from other modules. This isn’t exactly nested-functions, but functionally equivalent. We have had to make a parallel symbol system to support this (with the associated constraints on pass scheduling and verification to make this safe).

We often need to be able to do:

builtin.module {
  hw.module @M1 (...) {
    %a = op symbol @A
  }
  weirdop @M1::@A
  hw.module @M2 (...) {
    instance @M1 (...)
  }

If hw.module defines a symbol table, the instance in M2 can’t resolve in the global scope. If hw.module doesn’t define a symbol table, weirdop can’t be written (assuming the parenting requirement of symbols).

5

Which is to say, +1 to the verifier enforcing the direct child requirement of symbols and symbol table ops.

And which is also to say we would love the infrastructure for nested symbol tables to be useful, we’ve had to implement it anyway.

6

Correct, right now you need to forward declare as an external symbol:

 hw.module @M2 (...) {
    external hw.module @M1
    instance @M1 (...)
  }

MLIR won’t “resolve” for you accesses to @M1 but this is “well formed”.

7

Opened [mlir][Symbol] Add verification that symbol's parent is a SymbolTable by caojoshua · Pull Request #80590 · llvm/llvm-project · GitHub

8

So, we’ve hit an internal case that resembles the following:

custom.global_func @declaration()

custom.previously_not_a_symbol_table {
  custom.symbol @symbol {
  }
  custom.call_global_func @declaration()
}

so we were relying on the resolution to get to the closest parent symbol table rather than assume the immediately surrounding op is a symbol table. By making previously_not_a_symbol_table a symbol table, the @declaration symbol can no longer be resolved because it is declared in the parent table.

What I’d like to have here is some mechanism to refer to the ancestor symbol table, e.g., @::declaration.