Is there any implementation for calculating the distance between two operations cross blocks? I am working on a trivial register allocator, but would like to at least have some heuristics that can be used to calculate what to spill.
It should be easy enought to write using a DFS, but I am wondering if there is something I missed somewhere.
I think you should accumulate any Op you need into a SmallVector(or things like this), analysis IR directly maybe difficult.
And yes, by using block.walk(...) method can look Ops in block by post order, block.walk<WalkOrder::PreOrder>(...) can do it in pre order.
According to your describe, I’m not sure op.getLoc() may suitable for this issue?
Months ago, i have the same problem, writing a pass that early frees the allocateOp after its last use.
my solution is comparing the distance between the last users(different operations), which uses similar algorithms like DFS you metioned. At last, i found a pass MLIR has offered that could easily solve this problem.
You may find some inspirations in this pass
lib/Dialect/Async/Transforms/AsyncRuntimeRefCounting.cpp