Agressive folding

I was looking in to how MLIR could represent the Zig language, which has two novel features:

  1. It has an aggressive interpreter, allowing extensive computation at compile-time in the same language as is compiled.

  2. Types are values, and we run a type legalization pass early in the compilation.

#2 is completely dependent on #1, and I am going to focus on #1 in this post.

MLIR’s isFoldable properly is not suitable for Zig’s comptime. The way we #1 in the Zig compiler is by coloring the IR DAG as runtime or static.

I am open to other suggestion on how to color the DAG, but I am asking for a bit in mlir::Value for this purpose.

On the implementation side, despite static constexpr int NumLowBitsAvailable = 3; in Value.h, the code is refusing to allow more than 2 bits to be taken, and despite PointerIntPair advertising that it supports chaining, there are no tests for chaining, and it is throwing very verbose and hard-to-understand errors when I try to chain it. I wouldn’t have spent multiple hours on this if it was done in C instead of C++.

Hey,

Looking forward to how this develops (I’ve enjoyed some zig posts but have not used the language, perhaps later this would be an excuse to try :slight_smile: ).

Would this bit then interop with isFoldable? And so runtime vs static represents whether the op can be folded? Or is there another use for it?

I’m not really answering your main question, but wanted to understand the use case better.

@River707 will likely know how we use the pointer bits.

A lot of things can be done in MLIR without extending the core types, but it may have a lot of overhead. Since there are essentially two types of values: Op results and block arguments, one can annotate the source of the value rather than the value itself. As an extremely direct approach, any operation defining a value can have an array-of-integers attribute that specifies, for each value defined by this operation, whether it is runtime or static. Additionally, any operation containing a region can have an array-of-array-of-integers attribute that does the same for each argument of every block in that region. (I don’t know Zig well enough to understand if it actually needs coloring the block arguments). This will certainly cost you more than taking a bit from Value’s pointer, but will get the job done.

I don’t see a property or anything with this name in MLIR.

Well, we may be able to understand those if we get to see them.

Are you suggesting to rewrite MLIR in C? That will take multiple hours…

How are these colors updated as transformations modify the IR? What looks at the colors? What assigns the colors?

Currently, an analysis is the typical idiomatic way to represent a mapping from Value to some metadata, but that has issues with how the analysis is invalidated as transformations proceed.

Keeping track of attributes associated with values (rather than ops) is definitely something that I’ve seen come up multiple times and often an analysis isn’t the right solution. I’ve seen a number of approaches similar to using an “identity” op that carries some sort of metadata that it associates with the value. That has the downside that having that op present gets in the way of use-def chains.

I think what I am asking for is alias analysis. LLVM has the attributes for this:

  • Function: readnone, readonly, writeonly, argmemonly,
    inaccessiblememonly, inaccessiblemem_or_argmemonly
  • Argument: noalias, nocapture

But the aliasing ones: argmemonly, inaccessiblememonly, and either, are from my testing not set by LLVM (even if the FCP was still working). My guess is that memref would make this easier in MLIR, and these attributes could also be attached to basic blocks.

Both the name-space and the types need to be able to pull values out of the IR, and get accurate messages if this is not possible, and which branch cannot be computed.