Page MenuHomePhabricator

Implement recursive support into OperationEquivalence::isEquivalentTo()

Authored by mehdi_amini on Jul 20 2021, 10:32 PM.



This allows to use OperationEquivalence to track structural comparison for equality between two

Diff Detail

Event Timeline

mehdi_amini created this revision.Jul 20 2021, 10:32 PM
mehdi_amini requested review of this revision.Jul 20 2021, 10:32 PM
jpienaar added inline comments.Jul 21 2021, 5:19 AM
197 ↗(On Diff #360361)

So this requires all ops in the same order independent of whether has SSA dominance or not, This equal is identically equal including verifying non-semantic changing differences?

Nit on description, this adds functionality and doesn't feel appropriate marked as NFC which is normally reserved for refactoring/cleanup.

196 ↗(On Diff #360361)

We have pretty large modules with some growing in nesting of regions depth.

jpienaar added inline comments.Jul 21 2021, 12:56 PM
197 ↗(On Diff #360361)

(only exception I think is locations, locations may differ)

mehdi_amini added inline comments.Jul 21 2021, 2:28 PM
196 ↗(On Diff #360361)

You're commenting on the recursive aspect of the algorithm?
Our doc says :

At the moment, we tolerate it for the two following cases:
- The nesting of the IR: we use recursion when traversing nested regions.
- Type nesting: recursion may be used for the nesting of composite types.

Do you think that it is time to revisit this? I always assumed that nesting was fairly bounded (i.e. ~20 would be close to the max we expect to see anytime soon?).

197 ↗(On Diff #360361)

Oh I forgot locations, I should check on this as well (maybe behind an option).

And yes this is really "equality" and not "equivalence" in any way.

mehdi_amini retitled this revision from Add Operation::equals() and Region::equals() methods (NFC) to Add Operation::equals() and Region::equals() methods.Jul 21 2021, 2:28 PM
mehdi_amini marked 3 inline comments as done.

Add an option to strict check the location matching

rriddle added inline comments.Jul 21 2021, 6:37 PM
214 ↗(On Diff #360630)

I'm not sure I understand the distinction between this and the existing OperationEquivalence utils. Can you explain what purpose this serves that the other doesn't/can't? Or why we shouldn't just remove the OperationEquivalence stuff in favor of this? From a glance they serve identical purposes.

169 ↗(On Diff #360630)

Cache the end iterators to avoid recomputing them.

mehdi_amini added inline comments.Jul 21 2021, 6:40 PM
214 ↗(On Diff #360630)

Ah! I just forgot about OperationEquivalence existence.
The difference here seems that OperationEquivalence does not account for region though?

rriddle added inline comments.Jul 21 2021, 6:50 PM
214 ↗(On Diff #360630)

I originally added just enough to support the basic CSE stuff, but the intention was to expand upon it when that became necessary. Should we remove it and wrap everything from it into this equals? I don't have a preference which one we expand, but I don't think we need both.

mehdi_amini added inline comments.Jul 21 2021, 7:59 PM
214 ↗(On Diff #360630)

Since OperationEquivalence supports computing hash, seems like I'll consolidate everything there!

bondhugula added inline comments.

Update file comment.

Merge this into OperationEquivalence

mehdi_amini retitled this revision from Add Operation::equals() and Region::equals() methods to Implement recursive support into OperationEquivalence::isEquivalentTo().Jul 22 2021, 8:41 PM
mehdi_amini edited the summary of this revision. (Show Details)

Remove debug leftover

rriddle accepted this revision.Jul 27 2021, 1:26 PM


(Don't forget to resolve the STLExtras diffbase first)


Can you pull the functors out as separate variables to reduce indent here?

auto allOpsMatchFn = ...;
auto allBlockMatchFn = ...;
return llvm::all_of_zip(*lhs, *rhs, allBlockMatchFn) == true;

Same as below.



Or allBlockMatch.getValueOr(false)


Would a lambda that removed the duplication here be cleaner?


Can you add param comments?

Also, is it possible to just pass hash_value directly for the operand hash? Or do you need to wrap it?


I feel like we should have a util for the default comparison/hash as well as the ignore case.

267 ↗(On Diff #361077)


This revision is now accepted and ready to land.Jul 27 2021, 1:26 PM
mehdi_amini marked 7 inline comments as done.Jul 28 2021, 9:53 PM
mehdi_amini added inline comments.

I need to wrap (unless you see another way) because:

ERROR: mlir/lib/Transforms/CSE.cpp:33:26 no viable conversion from '<overloaded function type>' to 'function_ref<llvm::hash_code (mlir::Value)>'
llvm/include/llvm/ADT/STLExtras.h:171:7 candidate constructor (the implicit copy constructor) not viable: no overload of 'hash_value' matching 'const llvm::function_ref<llvm::hash_code (mlir::Value)> &' for 1st argument
class function_ref<Ret(Params...)> {
llvm/include/llvm/ADT/STLExtras.h:171:7 candidate constructor (the implicit move constructor) not viable: no overload of 'hash_value' matching 'llvm::function_ref<llvm::hash_code (mlir::Value)> &&' for 1st argument
llvm/include/llvm/ADT/STLExtras.h:183:3 candidate constructor not viable: no overload of 'hash_value' matching 'std::nullptr_t' (aka 'nullptr_t') for 1st argument
  function_ref(std::nullptr_t) {}
llvm/include/llvm/ADT/STLExtras.h:186:3 candidate template ignored: couldn't infer template argument 'Callable'
mlir/include/mlir/IR/OperationSupport.h:915:44 passing argument to parameter 'hashOperands' here
      function_ref<llvm::hash_code(Value)> hashOperands =
mehdi_amini marked 2 inline comments as done.

Address comments and rebase

This revision was landed with ongoing or failed builds.Jul 28 2021, 10:12 PM
This revision was automatically updated to reflect the committed changes.