SymbolTable linear lookup leads to O(n^2) complexity in verifier

MLIR
1

SymbolTable does linear scan in lookupSymbolIn . Assuming module has N private symbols, it’s reasonable to expect at least N addressof operations, which leads to N^2 complexity when we try to verify all of the addressof operations.

Can this be improved? Any natural location to hide the hash map?

Maybe operation with SymbolTable trait in verifier (canonicalizer?) should sort all symbols by name, and put them at the top of the region, and then lookupSymbolIn can have an optimistic logn step where it does binary search, and falls back on liner scan if symbol is not found (should be rare?).

Any other suggestions?

2

You should be using a SymbolTableCollection to cache the lookup results. You can verify symbol users via SymbolUserOpInterface, which allows you to implement

LogicalResult Op::verifySymbolUses(SymbolTableCollection &table) {...}
2 Likes
3

Thanks! Sent ⚙ D131271 [mlir] Use SymbolUserOpInterface in LLVM::AddressOfOp verifier to fix LLVM::AddressOfOp

1 Like