This is an archive of the discontinued LLVM Phabricator instance.

[mlir][sparse] Renaming "pointer/index" to "position/coordinate"
ClosedPublic

Authored by wrengr on Feb 24 2023, 8:34 PM.

Details

Summary

The old "pointer/index" names often cause confusion since these names clash with names of unrelated things in MLIR; so this change rectifies this by changing everything to use "position/coordinate" terminology instead.

In addition to the basic terminology, there have also been various conventions for making certain distinctions like: (1) the overall storage for coordinates in the sparse-tensor, vs the particular collection of coordinates of a given element; and (2) particular coordinates given as a Value or TypedValue<MemRefType>, vs particular coordinates given as ValueRange or similar. I have striven to maintain these distinctions
as follows:

  • "p/c" are used for individual position/coordinate values, when there is no risk of confusion. (Just like we use "d/l" to abbreviate "dim/lvl".)
  • "pos/crd" are used for individual position/coordinate values, when a longer name is helpful to avoid ambiguity or to form compound names (e.g., "parentPos"). (Just like we use "dim/lvl" when we need a longer form of "d/l".)

    I have also used these forms for a handful of compound names where the old name had been using a three-letter form previously, even though a longer form would be more appropriate. I've avoided renaming these to use a longer form purely for expediency sake, since changing them would require a cascade of other renamings. They should be updated to follow the new naming scheme, but that can be done in future patches.
  • "coords" is used for the complete collection of crd values associated with a single element. In the runtime library this includes both std::vector and raw pointer representations. In the compiler, this is used specifically for buffer variables with C++ type Value, TypedValue<MemRefType>, etc.

    The bare form "coords" is discouraged, since it fails to make the dim/lvl distinction; so the compound names "dimCoords/lvlCoords" should be used instead. (Though there may exist a rare few cases where is is appropriate to be intentionally ambiguous about what coordinate-space the coords live in; in which case the bare "coords" is appropriate.)

    There is seldom the need for the pos variant of this notion. In most circumstances we use the term "cursor", since the same buffer is reused for a 'moving' pos-collection.
  • "dcvs/lcvs" is used in the compiler as the ValueRange analogue of "dimCoords/lvlCoords". (The "vs" stands for "Values".) I haven't found the need for it, but "pvs" would be the obvious name for a pos-ValueRange.

    The old "ind"-vs-"ivs" naming scheme does not seem to have been sustained in more recent code, which instead prefers other mnemonics (e.g., adding "Buf" to the end of the names for TypeValue<MemRefType>). I have cleaned up a lot of these to follow the "coords"-vs-"cvs" naming scheme, though haven't done an exhaustive cleanup.
  • "positions/coordinates" are used for larger collections of pos/crd values; in particular, these are used when referring to the complete sparse-tensor storage components.

    I also prefer to use these unabbreviated names in the documentation, unless there is some specific reason why using the abbreviated forms helps resolve ambiguity.

In addition to making this terminology change, this change also does some cleanup along the way:

  • correcting the dim/lvl terminology in certain places.
  • adding const when it requires no other code changes.
  • miscellaneous cleanup that was entailed in order to make the proper distinctions. Most of these are in CodegenUtils.{h,cpp}

Diff Detail

Event Timeline

wrengr created this revision.Feb 24 2023, 8:34 PM
Herald added a reviewer: ftynse. · View Herald Transcript
Herald added a project: Restricted Project. · View Herald Transcript
wrengr requested review of this revision.Feb 24 2023, 8:34 PM

The one remaining concern I have with our new naming convention, is what exactly to name the bitwidth fields of the encoding attribute. Originally (and as currently uploaded) I went with the long-form names positionWidth/coordinateWidth, because I was worried about the UX of leaking our coding convention into the dialect syntax itself. However, when doing my final editing pass I noticed that there are other places where our naming convention leaks into the dialect syntax already (e.g., ops which take lvlCoords vs coordinates). So now I'm wondering if we should use the names posWidth/crdWidth afterall, to be consistent with the naming convention within the compiler itself.

Thoughts?

Peiming added inline comments.Feb 28 2023, 1:48 PM
mlir/include/mlir/Dialect/SparseTensor/IR/SparseTensorAttrDefs.td
150–154

So, the convention here is we apply dim ordering transformation *before* high order mapping to translate lvlCrds to dimCrds?

231

To answer your question, I would vote for posBitWidth and crdBitWidth, but this looks good to me too.

mlir/include/mlir/Dialect/SparseTensor/IR/SparseTensorOps.td
122

Same here, but probably need to make it clear that we returns lvlCrds instead of dimCrds array

486

This is not related to this patch, but @aartbik do you think it is better for us to use dimCoords here to make it more similar to tensor.insert operation?

Let's say, if users wants to insert a elements into block sparsity tensor, do we want the whole list of lvlCrds to be provided, or just the dimCrds?

Both way works, but just want to make it clear.

An ideal world is that we can provide seamless APIs to sparse tensors as if they are dense ones (i.e., any operation that uses lvl are internal in sparse compiler, otherwise they can be used by other dialects with little risk).

Peiming added inline comments.Feb 28 2023, 1:52 PM
mlir/include/mlir/Dialect/SparseTensor/IR/SparseTensorOps.td
62–63

Though I have to admit that I did not think about this when introducing the operation, I think there should be no such restriction.

If user requests a result tensor with dimOrdering, all they have to do this to ensure that the coordinates they provided are indeed in the provided ordering.

We just to make it clear that we will not permute the coordinates in the provided array but simply takes it .

So now I'm wondering if we should use the names posWidth/crdWidth afterall, to be consistent with the naming convention within the compiler itself.

Answering this "inline", I think we should use posWidth/crdWidth indeed to have a single convention, *and* because it is just shorter...

aartbik added inline comments.Feb 28 2023, 2:56 PM
mlir/include/mlir/Dialect/SparseTensor/IR/SparseTensorAttrDefs.td
23

period at end for pedantic consistency

25

can we link to def of IndexAttr?

(I am not a proponent of linking too much, but since this is not a sparse tensor type specific thing, it may be worthwhile)

26

maybe summary string or something like that, since in the code below, the field name is not immediately apperent?

134

perhaps add "no sibling at this level" to make the distinction Stephen explained to us very clear?

147

Perhaps even make this a FIXME, or TODO since your upcoming syntax changes will fix that?

174

FIXME/TODO?

231

+1 on the pos/crd syntax? perhaps also dependent on how you plan to represent this in the upcoming change?

301–302

Is adding "MLIR" really useful. It feels like we need to do that at (too) many other places too then?

mlir/include/mlir/Dialect/SparseTensor/IR/SparseTensorOps.td
113

number-of-stored-entries?

138

nice catch! ;-)

mlir/include/mlir/ExecutionEngine/SparseTensor/Storage.h
18

I somehow find the PCV notation a lot more readable ;-)

mlir/lib/Dialect/SparseTensor/Transforms/CodegenUtils.cpp
320

changes here are a bit more than just mechanical....

mlir/lib/Dialect/SparseTensor/Transforms/CodegenUtils.h
51

also pos/crd?

wrengr updated this revision to Diff 501986.Mar 2 2023, 2:24 PM
wrengr marked 15 inline comments as done.

Addressing comments

mlir/include/mlir/Dialect/SparseTensor/IR/SparseTensorAttrDefs.td
25

I really wish tablegen allowed deriving from def (instead of only from class), since that'd obviate the need for most of this commentary explanation (let alone duplicating the code for the predicate etc)

134

This is one of those examples I mentioned where I feel like the wording used in the StableHLO spec is very good, whereas the wording here is a bit outdated / less clear. (I was hoping to get away with relatively cursory documentation cleanup for this CL; and was planning to copy over the StableHLO description in the CL that implements the new "hybrid" syntax.)

150–154

Yep. (I'm just documenting the currently implemented behavior/semantics; this CL doesn't change the intended semantics nor the implementation thereof.)

231

Cool cool, I'll switch to "pos/crd" to make it more consistent

Re future changes, my thoughts are: (1) so long as we only support "one size fits all" bitwidths, I'm planning to leave these as top-level fields. (2) once we support per-level bitwidths, I'm planning to add fields of the same name to the struct/dict for each level-type where the bitwidths are relevant. (3) once we have per-level bitwidths, we may want to keep the top-level fields around to specify a default value shared by all levels (which individual levels can then override), or we may want to remove the top-level fields in order to simplify the roundtripping problem.

301–302

I forget why I added that here...

I do think there are places where we should be more explicit about the "MLIR Type" vs "C++ type" distinction (especially when having team discussions). Though I agree that it's not necessary/useful to do so everywhere in the code (since it's usually obvious).

mlir/include/mlir/Dialect/SparseTensor/IR/SparseTensorOps.td
62–63

I agree that it'd be nice to lift the restriction (so long as it's clearly documented what coordinate-space the $coordinates are in); however, I'm not sure whether the current implementation supports it (feel free to let me know :). Fwiw, this CL isn't trying to change anything, it's just trying to clarify the (currently) intended semantics. I'll reword this to try making it clearer that the restriction is with the current implementation rather than with the intended semantics.

Supposing that $coordinates remain level-coordinates that are un/packed directly, the main issue I foresee re supporting dimOrdering and higherOrdering is re type inference/checking. In particular, if we want to ensure safety then I see two options: (1) the $coordinates needs to come equipped with the lvlSizes the coordinates are valid for, so that we can check those lvlSizes against the ones inferred from the dimSizes+orderings; (2) we'd need to scan through $coordinates to check that all the coords are in-bounds for the lvlSizes inferred from the dimSizes+orderings. The first option is clearly preferable from a performance perspective, though for it to actually ensure safety we need to trust whoever provides the lvlSizes.

486

I think we really want two different ops here:

  • For the sake of offering a drop-in replacement for dense tensors, it makes sense to have an op that takes dimCoords. Though since the goal is to be a drop-in replacement, why not just have our passes rewrite tensor.insert itself (like we do for other tensor-dialect ops)?
  • However, the current sparse_tensor::InsertOp serves as an IR for the sparse-compiler itself and isn't intended for end-users. In particular, the op serves as a proxy for the runtime library's function —which takes lvlCoords, since it expects the compiler to have handled all the dim<->lvl stuff beforehand. (And for the codegen pass, the op is lowered to analogous code.)

We have a whole bunch of these internal-only ops. It would probably be a good idea to move all these off to a "subdialect" sparse_tensor.internal (or whatever) to keep them distinct from the user-facing ops. That would be especially nice as we start picking up users, since it helps clarify how stable the API is/isn't. (It would be more ideal to split these off into a proper Dialect, since that'd clean up the code for declaring which ops are/aren't legal after a pass finishes. However that'd require a whole lot of extra boilerplate.)

mlir/include/mlir/ExecutionEngine/SparseTensor/Storage.h
18

:)

mlir/lib/Dialect/SparseTensor/Transforms/CodegenUtils.cpp
320

Yeah. I considered splitting this (and other changes to this file) off into a separate CL, but it didn't feel right to rename everything else but then leave these in an inconsistent state. But I can split them off to a separate CL if you'd prefer

Peiming added inline comments.Mar 2 2023, 3:11 PM
mlir/lib/Dialect/SparseTensor/Transforms/CodegenUtils.cpp
624

I feel that you probably do not need (void)vsize, since assert are also guarded by ifndef NDEBUG.

But maybe it is better to keep it to make it more robust.

mlir/lib/Dialect/SparseTensor/Transforms/LoopEmitter.cpp
404–405

I think you can safely rename all dim in LoopEmitter.cpp to lvl, it does not take care of dimOrdering (but already handled by Sparsification.cpp)

mlir/lib/Dialect/SparseTensor/Transforms/LoopEmitter.h
263

I think pos is the right name here, it is a value *loaded* from posBuffer, rather than a index to the buffer. (See L970 in LoopEmitter.cpp)

wrengr added inline comments.Mar 2 2023, 4:10 PM
mlir/lib/Dialect/SparseTensor/Transforms/LoopEmitter.cpp
404–405

Yep. As per my previous comment though, cleaning up the LoopEmitter and Utils/Merger stuff snowballed into another huge CL. Thankfully those files are fairly well insulated from the rest of the compiler, so it's easy enough to fork that off into a separate patch

mlir/lib/Dialect/SparseTensor/Transforms/LoopEmitter.h
263

Yeah, I was pretty sure it's the position analogue of "coords". (We still don't have a good name for that though...)

I'll leave it as a todo for now though. I've avoided doing much renaming in this file, since when I tried, it snowballed into another huge CL (since all the stuff in LoopEmitter and Utils/Merger also needs to switch to using "lvl" instead of "dim"). That'll prolly come out next week or so

wrengr updated this revision to Diff 502229.Mar 3 2023, 12:43 PM
wrengr marked an inline comment as done.

rebase

aartbik accepted this revision.Mar 3 2023, 12:48 PM
aartbik added inline comments.
mlir/lib/Dialect/SparseTensor/Transforms/SparseVectorization.cpp
63–65

interesting cleanup, yes. I really meant pointer here due to the way I view memref as the base address at this point, but it is good to avoid the confusion of all different meanings here, and it is indeed a memref ;-)

This revision is now accepted and ready to land.Mar 3 2023, 12:48 PM
wrengr added inline comments.Mar 6 2023, 12:22 PM
mlir/lib/Dialect/SparseTensor/Transforms/SparseVectorization.cpp
63–65

fwiw, I was following the precedent set by some of our other code for similar sorts of MemRef helper functions :)