Skip to content

Instantly share code, notes, and snippets.

@navyxliu

navyxliu/gist:c32053f8b7f49df872804cf426d9f2f8

Last active January 6, 2026 22:59
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save navyxliu/c32053f8b7f49df872804cf426d9f2f8 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save navyxliu/c32053f8b7f49df872804cf426d9f2f8 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
gistfile1.txt
CSE of MLIR is pretty much hash-based global value numbering. For each region, it Depth-First-Search(DFS) the dominator tree using a very efficient implementation.
https://github.com/llvm/llvm-project/blob/main/mlir/lib/Transforms/CSE.cpp#L333-L359
I learned is that we don't need to push all children to the stack. we can push just one child and increase the iterator!
currentNode->childIterator++.
There are 2 benefits:
1) worst space complexity is the height of the tree.
2) this code accesses memory sequentially.
cache locality is the king!
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment