[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

This revision was automatically updated to reflect the committed changes. Closed by commit rGb508c5649f5e: [MLIR] Add a utility to sort the operands of commutative ops (authored by srishti-pm, committed by Mogball). Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://review

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

srishti-pm updated this revision to Diff 448682. srishti-pm marked 3 inline comments as done. srishti-pm added a comment. Addressed the final NITs. Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D124750/new/ https://reviews.llvm.org/D124750 Files:

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

Mogball added a comment. I'm referring to the nitty gritty details of the while loop inside the comparator. It looks pretty tight to me right now. If the operands are already sorted, worst-case each operand is compared against only its neighbours. Unfortunately, without extra bookkeeping, BFS w

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

mehdi_amini added a comment. > . I haven't thought too hard about the performance of that while loop but it > seems good enough to land for now. What's the finality of it? That is: outside of canonicalization what is its purpose? Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTIO

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

Mogball accepted this revision. Mogball added a comment. This revision is now accepted and ready to land. Got a few small nits but otherwise LGTM. Thanks for all the hard work! This looks really solid now. I haven't thought too hard about the performance of that while loop but it seems good enou

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

srishti-pm updated this revision to Diff 448117. srishti-pm added a comment. Updated an outdated comment. Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D124750/new/ https://reviews.llvm.org/D124750 Files: mlir/include/mlir/Transforms/Commutativit

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

srishti-pm updated this revision to Diff 448094. srishti-pm marked 5 inline comments as done. srishti-pm added a comment. 1. Addressed all the comments. 2. Refactored the code. Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D124750/new/ https://revie

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

srishti-pm marked an inline comment as done. srishti-pm added inline comments. Comment at: mlir/lib/Transforms/Utils/CommutativityUtils.cpp:110 + /// operand at a particular point in time. + DenseSet visitedAncestors; + Mogball wrote: > Since this is a set of p

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

Mogball added inline comments. Comment at: mlir/lib/Transforms/Utils/CommutativityUtils.cpp:238 +// Stores the mapping between an operand and its BFS traversal information. +DenseMap operandToItsBFSMap; + srishti-pm wrote: > Mogball wrote: > > Why can't y

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

srishti-pm marked an inline comment as done. srishti-pm added inline comments. Comment at: mlir/lib/Transforms/Utils/CommutativityUtils.cpp:238 +// Stores the mapping between an operand and its BFS traversal information. +DenseMap operandToItsBFSMap; + Mo

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

Mogball added inline comments. Comment at: mlir/lib/Transforms/Utils/CommutativityUtils.cpp:238 +// Stores the mapping between an operand and its BFS traversal information. +DenseMap operandToItsBFSMap; + Why can't you sort the OperandBFS directly to avoi

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

srishti-pm updated this revision to Diff 446295. srishti-pm added a comment. Used the `stable_sort` function. Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D124750/new/ https://reviews.llvm.org/D124750 Files: mlir/include/mlir/Transforms/Commutat

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

Mogball added a comment. I'm not sure how to check the no-op case without constructing at least a queue. Even assuming only 2 commutative operands, if they look the same `depth=1`, then the comparison has to iterate. Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://re

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

mehdi_amini added a comment. For this to be a usable canonicalization, it is really the case where the operands are already sorted (no-op) that needs to be heavily optimized (that is no complex data structure to populate, etc.) Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

Mogball added inline comments. Comment at: mlir/lib/Transforms/Utils/CommutativityUtils.cpp:329-353 + assert(frontPosition >= 0 && frontPosition < bfsOfOperands.size() && + "`frontPosition` should be valid"); + unsigned positionOfOperandToShift; + bool foundOperandToSh

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

srishti-pm marked 4 inline comments as done. srishti-pm added inline comments. Comment at: mlir/lib/Transforms/Utils/CommutativityUtils.cpp:329-353 + assert(frontPosition >= 0 && frontPosition < bfsOfOperands.size() && + "`frontPosition` should be valid"); + unsigned po

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

Mogball added inline comments. Comment at: mlir/lib/Transforms/Utils/CommutativityUtils.cpp:76 + // `CONSTANT_OP` and `opName` remains "". + type = CONSTANT_OP; +} srishti-pm wrote: > Mogball wrote: > > Constant ops could be sorted by name as well.

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

srishti-pm marked 4 inline comments as done. srishti-pm added inline comments. Comment at: mlir/lib/Transforms/Utils/CommutativityUtils.cpp:76 + // `CONSTANT_OP` and `opName` remains "". + type = CONSTANT_OP; +} Mogball wrote: > Constant ops could b

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

Mogball added inline comments. Comment at: mlir/lib/Transforms/Utils/CommutativityUtils.cpp:523 + shiftTheSmallestUnsortedOperandsToTheSmallestUnsortedPositions( + bfsOfOperands, smallestUnsortedPosition); + And then you'll never need to check `isSo

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

Mogball added a comment. I'm glad the `DenseSet`s are gone, but my three-ish biggest gripes are: - The algorithm is conceptually simple, but there is way more code than is necessary to achieve it. - More comments (excluding "doc" comments) than code is generally not a good sign - The implementa

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

srishti-pm updated this revision to Diff 441253. srishti-pm added a comment. Addressed of all Jeff's comments. Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D124750/new/ https://reviews.llvm.org/D124750 Files: mlir/include/mlir/Transforms/Commuta

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

Mogball added inline comments. Comment at: mlir/lib/Transforms/Utils/CommutativityUtils.cpp:178 +using UniquePtrOperandBFS = std::unique_ptr; +using ArrayRefOperandBFS = ArrayRef; + Please remove these. They don't improve readability. Repository: rG LLVM Gith

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

srishti-pm updated this revision to Diff 440848. srishti-pm marked 2 inline comments as done. srishti-pm added a comment. Fixed memory leak. Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D124750/new/ https://reviews.llvm.org/D124750 Files: mlir/i

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

srishti-pm added a comment. @mehdi_amini, I have made sure that the algorithm is good in terms of both time and space complexity. @Mogball, "handling attributes (e.g. cmpi slt vs cmpi sgt)" doesn't seem hard to me. I think this algorithm can be extended with ease to take attributes into accoun

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

srishti-pm updated this revision to Diff 440570. srishti-pm marked 6 inline comments as done. srishti-pm added a comment. Addressed the final comments. Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D124750/new/ https://reviews.llvm.org/D124750 File

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

Mogball added a comment. In principle, I think the algorithm is fine. I'm pretty sure you can rewrite bits of it to get rid of the map/sets. I'm only concerned about handling attributes. (e.g. `cmpi slt` vs `cmpi sgt`) Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

srishti-pm added a comment. In D124750#3587161 , @mehdi_amini wrote: > Right now I'm not yet understanding all of the algorithm (haven't spent > enough time on it), but I'm mostly concerned by the runtime cost of this > normalization. I understand you

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

mehdi_amini added a comment. Right now I'm not yet understanding all of the algorithm (haven't spent enough time on it), but I'm mostly concerned by the runtime cost of this normalization. Comment at: mlir/lib/Transforms/Utils/CommutativityUtils.cpp:371 +// assigned a sort

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

srishti-pm updated this revision to Diff 437276. srishti-pm added a comment. Increasing pattern benefit + minor typo correction. Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D124750/new/ https://reviews.llvm.org/D124750 Files: mlir/include/mlir/

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

srishti-pm added a comment. Addressed most of the comments. A few remaining. Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D124750/new/ https://reviews.llvm.org/D124750 ___ cfe-commits mailing list cfe-co

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

srishti-pm updated this revision to Diff 437249. srishti-pm marked 20 inline comments as done. srishti-pm added a comment. Addressing comments. Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D124750/new/ https://reviews.llvm.org/D124750 Files: mli

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

mehdi_amini added inline comments. Comment at: mlir/include/mlir/Transforms/CommutativityUtils.h:211 +template +class SortCommutativeOperands : public OpRewritePattern { + using OpRewritePattern::OpRewritePattern; Can we make this not a template? This will be a

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

srishti-pm updated this revision to Diff 436281. srishti-pm added a comment. Minor changes. Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D124750/new/ https://reviews.llvm.org/D124750 Files: clang/docs/tools/clang-formatted-files.txt mlir/inclu

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

Mogball added inline comments. Comment at: mlir/include/mlir/Transforms/CommutativityUtils.h:211 +// If `op` is not commutative, do nothing. +if (!op->template hasTrait()) + return failure(); Mogball wrote: > Please move the body `matchAndRewrite` in

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

Mogball added a comment. I haven't thought too hard about the algorithm itself yet. I'm in the camp of "let's move forward if it works". I have mostly trivial comments. Comment at: clang/docs/tools/clang-formatted-files.txt:8451 mlir/lib/Transforms/SymbolPrivatize.cpp +mlir/l

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

srishti-pm updated this revision to Diff 436274. srishti-pm added a comment. Addressed all the comments. Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D124750/new/ https://reviews.llvm.org/D124750 Files: clang/docs/tools/clang-formatted-files.txt

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

srishti-pm added a comment. Herald added a subscriber: bzcheeseman. @Mogball @mehdi_amini @jpienaar, sorry there haven't been any updates from my side here for the past 10 or so days. I had been busy in some other tasks. I have started working on this again. Repository: rG LLVM Github Monore

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

Mogball added a comment. I'm open to iterating in tree. Landing this utility first and then try adding it as a canonicalization SGTM. The string could be replaced with an array of tuples (yuck) for now. An enum (constant, block arg, everything else) plus the OperationName. Attributes need to b

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

srishti-pm added a comment. **`Replying to the various comments given in this revision:`** **1. Regarding string manipulation:** > I need to look at the algorithm in more detail, but I'm not a fan of using a > string key. Concatenating strings to make compound keys is not very efficient > and

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

srishti-pm added a comment. > Thanks for improving the doc! Are you moving this to be used in > canonicalization next? > I think a first good step would be to make it a pattern and test it with a > pass that applies it in the greedy rewriter. I would land this first and then > try to enable thi

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

mehdi_amini added a comment. Thanks for improving the doc! Are you moving this to be used in canonicalization next? I think a first good step would be to make it a pattern and test it with a pass that applies it in the greedy rewriter. I would land this first and then try to enable this in the

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

srishti-pm updated this revision to Diff 428502. srishti-pm added a comment. Fixing a minor typo. Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D124750/new/ https://reviews.llvm.org/D124750 Files: clang/docs/tools/clang-formatted-files.txt mlir

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

srishti-pm updated this revision to Diff 428498. srishti-pm added a comment. Improving the documentation of the functionality of this utility to make it more clear. Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D124750/new/ https://reviews.llvm.org

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

rriddle added a comment. +1 on all of the other comments, especially related to the use of strings. In D124750#3503607 , @Mogball wrote: > On the matter of whether this should be a canonicalization, my concern with > this is that if an operation has its

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

jpienaar added a comment. > (1) the operands defined by non-constant-like ops come first, followed by (2) > block arguments, and these are followed by (3) the operands defined by > constant-like ops. I would have thought block-arguments would come first as we don't know their values, while non

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

Mogball added a comment. On the matter of whether this should be a canonicalization, my concern with this is that if an operation has its own preferred ordering of operands that conflicts with the sort, then this will cause canonicalization to loop infinitely. It's not actually the canonicaliz

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

Mogball added a comment. I need to look at the algorithm in more detail, but I'm not a fan of using a string key. Concatenating strings to make compound keys is not very efficient and potentially brittle. Can you assign unique IDs and use an array of IDs instead? Comment at:

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

srishti-pm added a comment. > Why? Again your description of the sort is as follow: I think I need to update my commit summary and revision summary. I had thought that this was an intuitive way of explaining the utility. But, I understand that it is quite misleading. Repository: rG LLVM Git

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

srishti-pm added a comment. > Every time the algorithm would consider a commutative op, that is all the op, > it would recurse and try to re-sort the current slice, processing the same > ops over and over. Yes, exactly. Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https:

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

mehdi_amini added a comment. That was the sense of my question about canonicalization indeed :) Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D124750/new/ https://reviews.llvm.org/D124750 ___ cfe-commits

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

srishti-pm added a comment. > So: I understand that the producers should be sorted for a pattern to apply, > but our disconnect earlier is that my usual approach to see canonicalization > is to process an entire block/region, and as such we don't work on slices but > on operation in order until

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

srishti-pm added a comment. > So far you explained "what is canonicalization and why are we > canonicalizing", the same rationale applies to "push constant to the right" > that we do already in canonicalization, and this is exactly why I asked > before whether we could do what you're doing as a

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

srishti-pm added a comment. > My "why?" question is about canonicalization: could this be a > canonicalization and if so why / why not? This is an important thing to > answer before looking into the discussion below actually: I think, yes, it can be a canonicalization. I don't see why not. Re

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

mehdi_amini added a comment. In D124750#3502401 , @srishti-pm wrote: > In D124750#3502295 , @mehdi_amini > wrote: > >> You're telling me "what" while I'm actually more interested in the "why" >> here? > > I'm n

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

srishti-pm updated this revision to Diff 428300. srishti-pm added a comment. Make the sorting strictly stable. Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D124750/new/ https://reviews.llvm.org/D124750 Files: clang/docs/tools/clang-formatted-fil

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

srishti-pm added a comment. In D124750#3502295 , @mehdi_amini wrote: > You're telling me "what" while I'm actually more interested in the "why" here? I'm not sure what your question is, with a "why". Let me think about this a bit. I'll get back to you.

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

mehdi_amini added a comment. In D124750#3502228 , @srishti-pm wrote: > In D124750#3500748 , @mehdi_amini > wrote: > >> Seems like this should be added to canonicalization? The "push constants to >> the right ha

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

srishti-pm updated this revision to Diff 428240. srishti-pm added a comment. Within constant-like ops, removed the requirement for them being sorted alphabetically. Basically, all constants will be treated as equals by the sorting algorithm and it will not distinguish between, say, `arith.consta

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

srishti-pm added a comment. In D124750#3500748 , @mehdi_amini wrote: > Seems like this should be added to canonicalization? The "push constants to > the right hand side" is there already. I think this was not added to canonicalization because we wanted

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

mehdi_amini added a comment. Seems like this should be added to canonicalization? The "push constants to the right hand side" is there already. I also don't understand the complexity of the implementation, I may need an example to understand why you're recursively operating on the producer ops

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

srishti-pm updated this revision to Diff 427964. srishti-pm added a comment. Fixing a comment typo and enhancing the commit summary even further. Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D124750/new/ https://reviews.llvm.org/D124750 Files: c

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

srishti-pm updated this revision to Diff 426335. srishti-pm added a comment. Improving the commit summary Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D124750/new/ https://reviews.llvm.org/D124750 Files: clang/docs/tools/clang-formatted-files.tx

[PATCH] D124750: [MLIR] Add a utility to sort the operands of commutative ops

srishti-pm created this revision. Herald added subscribers: sdasgup3, wenzhicui, wrengr, Chia-hungDuan, dcaballe, cota, teijeong, rdzhabarov, tatianashp, msifontes, jurahul, Kayjukh, grosul1, Joonsoo, liufengdb, aartbik, mgester, arpith-jacob, antiagainst, shauheen, rriddle, mehdi_amini, mgorny.