Page MenuHomePhabricator

[MLIR][PDL] Execute nondeterministic bytecode & lower some PDLInterp ops
Needs ReviewPublic

Authored by srishti-pm on Feb 1 2022, 3:05 AM.


  1. This commit first adds a stack of bytecode positions within the

ByteCodeExecutor. This is needed because in pdl_interp.choose_range,
we iterate over a range of operands/values from a list of permutations
returned by pdl_interp.get_permutations until we reach finalize. When
we reach finalize, we need to return back to the position marked in the

  1. Then a functionality to extend the lifetime of values that cross the

nondeterministic choice is added. The existing bytecode generator
allocates the values to memory positions by representing the liveness of
values as a collection of disjoint intervals over the matcher positions.
This is akin to register allocation, and substantially reduces the
footprint of the bytecode executor. However, because with
nondeterministic op pdl_interp.choose_range, execution "returns" back,
so any values whose original liveness cross the nondeterminstic choice
must have their lifetime executed until finalize.

  1. Then, lowerings of pdl_interp.choose_range, pdl_interp.get_item,

pdl_interp.get_permutations, and pdl_interp.is_commutative ops to
bytecode is added.

Co-authors: Srishti Srivastava, Stanislav Funiak, Prateek Gupta

Signed-off-by: Srishti Srivastava <>

Diff Detail

Event Timeline

srishti-pm created this revision.Feb 1 2022, 3:05 AM
srishti-pm requested review of this revision.Feb 1 2022, 3:05 AM
sfuniak requested changes to this revision.Feb 3 2022, 4:33 AM

As I mentioned in the previous diff on this stack, instead of implementing a new op ChooseRange, you should generalize ForEach. Also, GetItem is a duplicate of Extract.

As a side note: is there going to be one more diff stacked on top of this one that implements the lowering of commutative pdl.operations?


Now that ForEach is implemented with subregions, extending the lifetime should not be needed.


Deprecated code; delete.


The range-of-ranges use case seems parallel to operation ranges above. Now that pdl_interp.foreach does not mutate the range (of operations/ranges) it iterates over, can we replace

std::vector<RangeRange> rangeRangeMemory;
std::vector<llvm::OwningArrayRef<ValueRange>> allocatedRangeRangeMemory;


using OwningRangeRange = llvm::OwningArrayRef<ValueRange>;
std::vector<OwningRangeRange> rangeRangeMemory;


This revision now requires changes to proceed.Feb 3 2022, 4:33 AM
Mogball requested changes to this revision.Feb 20 2022, 4:37 PM
Mogball added inline comments.

There needs to be a limit on the number of operands allowed to be commutative.

As a side note: is there going to be one more diff stacked on top of this one that implements the lowering of commutative pdl.operations?

Yes, I intended to do that. But, I think I will add that after I am able to complete this lowering. What are your views about this?

Herald added a project: Restricted Project. · View Herald TranscriptMar 2 2022, 11:05 AM
srishti-pm added inline comments.Mar 2 2022, 11:11 AM

Oh okay. I'll do that, thanks!


Okay, what would you want to happen if that limit is exceeded? Should the op not be treated as commutative?


Sure. But how do we define allocatedRangeRangeMemory in that case?

srishti-pm marked 3 inline comments as not done.May 16 2022, 8:19 PM
This revision now requires review to proceed.May 16 2022, 8:19 PM