Page MenuHomePhabricator

[MLIR][Presburger] Add intersectDomain/Range to IntegerRelation
ClosedPublic

Authored by Groverkss on May 24 2022, 2:05 PM.

Details

Summary

This patch adds support for intersection a set with a relation.

Diff Detail

Event Timeline

Groverkss created this revision.May 24 2022, 2:05 PM
Groverkss requested review of this revision.May 24 2022, 2:05 PM
ftynse added inline comments.May 25 2022, 5:55 AM
mlir/lib/Analysis/Presburger/IntegerRelation.cpp
2123

Not blocking, but I would be interested to see a more efficient implementation. Currently, it will first copy the constraints from poly to rel, then resize rel to accommodate range variables that likely leads to copies, then resize it *again* to accommodate local ids, and then copy the constraints from rel to this. Sounds like a whole lot of copying for a relatively simple operation. Perhaps we could get this done with only one resize (of the constraints of this relation, which increases both the number of rows and the number of ranges) and a direct copy of coefficients from poly to this. It may be less concise and use non-trivial indexing, but likely more efficient.

Groverkss updated this revision to Diff 432004.May 25 2022, 8:10 AM
Groverkss marked an inline comment as done.

Rebase

mlir/lib/Analysis/Presburger/IntegerRelation.cpp
2123

The reason we need to do the space alignment is for the call to mergeLocalIds. Without merging the locals, we cannot directly append constraints, so I don't think this will work.

ftynse added inline comments.May 25 2022, 9:31 AM
mlir/lib/Analysis/Presburger/IntegerRelation.cpp
2123

That's why I mentioned the increase of both the rows and columns in one sweep. I had drilled down a bit in the code and had seen that mereLocalIds does additional column manipulations itself (with even more copies!), which led me to conclude that decreasing the number of copies required non-trivial work and it was not reasonable to block this patch until that work is done. I am quite positive that what I have in mind will ultimately work, it's just harder to implement; if one transitively inlined mergeLocalIds into this call, it would become more obvious.

On a general design point, I think more care should be taken, eventually, about the memory effects of copies hidden under the layers of API. Copies are not free (although small copies may be cheap) and may have larger effects on memory behavior of the objects copied take, e.g., a little bit more than half of L1. It is not clear to me how much this affects performance of some compilation flow, largely because I don't have access to an end-to-end flow that extensively uses affine, especially compared to algorithmically-expensive things like the simplex, but I take small gains whenever possible. (One could imagine some sort of transactional protocol for updating the contraint matrices that has an indirection table for column accesses and doesn't actually remove/reshuffle the columns until the transaction is committed. Depending on the amount of data copied vs. the cost of extra indirection in address computation, this may end up beneficial.)

There is another small trade-off here: increase the API surface by having overloads that take rvalue-references but let the user spare the copy if they know they don't need the object anymore after the operation.

Groverkss added inline comments.May 25 2022, 10:58 AM
mlir/lib/Analysis/Presburger/IntegerRelation.cpp
2123

Right, I see what you mean.

We have some more work in the pipeline to improve the interface and de-virtualize the hierarchy. After that, we can benchmark, try out the transaction idea, try to remove copies as much as possible and see how it impacts performance.

The rvalue-reference idea also seems interesting and I think we can try to prototype that.

arjunp added inline comments.May 26 2022, 10:17 AM
mlir/include/mlir/Analysis/Presburger/IntegerRelation.h
507–514
508–511

Can you explicitly write that these mutates this, and also write a formal description? i.e., if this is R1: A -> B and poly is C, return R2: (A intersection C) -> B such that ...

mlir/lib/Analysis/Presburger/IntegerRelation.cpp
2115–2116

use inverse here?

2118
2132
2135–2136

Not for this patch, but I would like an intersect function to mergeLocalIds and append.

Groverkss updated this revision to Diff 432501.May 27 2022, 2:24 AM
Groverkss marked 7 inline comments as done.

Address Arjun's comments

arjunp accepted this revision.May 27 2022, 3:01 AM

In the operations that were added previously, we've been following a system where most operations return their results, with operations that mutate in-place having a suffix InPlace, like unionInPlace. Not for this patch, but we should have uniformity in naming here.

This revision is now accepted and ready to land.May 27 2022, 3:01 AM