Page MenuHomePhabricator

[DDR] Introduce implicit equality check for the source pattern operands with the same name.

Authored by rdzhabarov on Oct 12 2020, 10:36 AM.



This CL allows user to specify the same name for the operands in the source pattern which implicitly enforces equality on operands with the same name.
E.g., Pat<(OpA $a, $b, $a) ... > would create a matching rule for checking equality for the first and the last operands. Equality of the operands is enforced at any depth, e.g., OpA ($a, $b, OpB($a, $c, OpC ($a))).

Example usage: Pat<(Reshape $arg0, (Shape $arg0)), (replaceWithValue $arg0)>

Note, this feature only covers operands but not attributes.
Current use cases are based on the operand equality and explicitly add the constraint into the pattern. Attribute equality will be worked out on the different CL.

Diff Detail

Event Timeline

rdzhabarov created this revision.Oct 12 2020, 10:36 AM
rdzhabarov requested review of this revision.Oct 12 2020, 10:36 AM
rdzhabarov added inline comments.Oct 12 2020, 10:51 AM

need to revert, probably got in during some merge conflict resolution.

fixing clang-tidy, revert leftovers from merge conflict.

rdzhabarov added inline comments.Oct 12 2020, 11:06 AM
os << formatv("tblgen_values.push_back(", varName);

original varName here was redundant, as it always contains empty string.

Nice, thanks


Could you perhaps rephrase? You are telling me what type is being returned here but not what the value represents.


Multimap is not often used ( and I think this one now copies of the string keys. Seems like a StringRef -> SmallVector<SymbolInfo, 1> mapping could also work. Or could have simply a vector of duplicates of a SymbolInfo in here? So we keep track of the one which got bounded in the map, and all the other ones we keep in an array that we iterate over and insert verifications to? So that the common case is just a map lookup and we don't store anything additional where not needed. I'm wondering as we only have to capture 1 value, the rest we can reject when we see it. Especially with unique renaming pass. You might have thought of this already and this works better for other reasons.


Could we avoid non uniquely? Negation makes this difficult to follow. Also where this is used, this almost seems like "findBoundSymbolName" ? (meaning, I'm not sure whether it matters if unique or not, when will it happen that for a (key, op, argIndex) there will be two matching entries?


getRangeOfEqualElements ? :) (equalRange just doesn't capture it)


Should this just be BaseT ?


Would inserted->first == name in all cases?


Nit: ++i


Would this result in only verifying all equalities together?

mehdi_amini added inline comments.Oct 12 2020, 1:37 PM

FYI the existing StringMap was also copying/owning the key

Will update this Cl in a bit.


I did consider to use something llvm friendly, I do not think there is anything nicely fitting my needs and providing benefits over multimap/unordered_multimap (I might switch to the unordered one for more efficient lookups).

StringRef -> SmallVector<SymbolInfo, 1>

As Mehdi mentioned below this way we still have map owning keys (copy of strings). So I have not found compelling reasons to switch to it.

Or could have simply a vector of duplicates of a SymbolInfo in here

Do you mean to keep all duplicated names in a single vector, e.g., for Op($a, $a, $b, $b, $a) to keep vec = {$a, $b, $a} in a single vector? (Note, i need not only operand name, but also index in the op and op itself for emitting).
This might complicate logic for emitting equality check, since we'd need to group equal operands together before emitting result.
It could work, but I find it convenient to grab equal_range at once for duplicates of any var.


yeah, agree, naming could be better here.


this is mostly to follow naming convention of other methods in this class.
E.g, find(), contains(), etc which delegates to corresponding map methods.
I have no strong feeling one way or the other one. Will rename to be more explicit.




yup, that's correct. The only difference is that inserted->first has std::string type vs StringRef.


will change.


This iterates all nodes in the multimap, but it goes through the unique keys (see symbolInfoIt = endRange).

Keys with the same values are inspected in bulk in the loop below: for (++startRange; startRange != endRange; ++startRange) {

rdzhabarov marked 5 inline comments as done.

Addressed comments.

Harbormaster completed remote builds in B74878: Diff 297731.
rdzhabarov marked 4 inline comments as done.Oct 13 2020, 10:31 AM
jpienaar accepted this revision.Oct 13 2020, 2:41 PM

Looks good, thanks


Gotcha, perhaps leave a TODO. It would seem that if we had

(X $x, $x, .... (Y $x, ...) ....)

we could have exited early once inspecting the 2nd operand, while here we'd try to verify the entire match before considering this equality. This is inline with what we currently do via constraints, but we could also improve on it :)

This revision is now accepted and ready to land.Oct 13 2020, 2:41 PM

Thanks for quick review @jpienaar!

we could have exited early once inspecting the 2nd operand

Yup, will put a comment/TODO there.

added TODO.

to fix merge conflict.

This revision was landed with ongoing or failed builds.Oct 13 2020, 4:17 PM
This revision was automatically updated to reflect the committed changes.

@mehdi_amini is there any way to run those tests prior merging?

No there isn't.

rdzhabarov reopened this revision.Oct 13 2020, 9:45 PM

gcc5 was not happy with StringRef in the emplace call to a map<std::string, ...> , will be fixing it.

This revision is now accepted and ready to land.Oct 13 2020, 9:45 PM

fixing gcc5 issues.

updating to latest.

This comment was removed by saugustine.