commit 1ba69d96fa77b13a9953f93ecd755361d174af53
author Scott Todd <scotttodd@google.com> Mon Nov 09 10:37:42 2020 -0800
committer GitHub <noreply@github.com> Mon Nov 09 10:37:42 2020 -0800
tree 600b387d852954c826750ed70fc6c81b96d44eba
parent 848b893885da381ce5b4493b37cb169ace6475ee

Deduplicate flow.executable ops during Flow dialect transformation. (#3702)

This works towards https://github.com/google/iree/issues/1144, but is not generalized beyond `flow.executable`.

Deep equivalence checks are performed between pairs of `flow.executable` ops in a new pass run after outlining dispatch regions. These executables will, by construction, have different symbol names so some special comparison logic is needed. When an executable is identified as a duplicate, it is deleted and references to it are updated to point to the canonical executable. This cleans up cases where duplicate executables are generated from the same library calls throughout a program, prior to running further compiler passes or dropping down to codegen.

I iterated on the comparison algorithm quite a bit, first printing ops to strings and checking string equality, then caching hashes of those strings using `getChildAnalysis<>` (see [this documentation](https://mlir.llvm.org/docs/PassManagement/#analysis-management)). That had the correctness and performance traits I wanted and was easy to read, but was thread-hostile.  The comparison code I settled on is still fast even without multithreading (milliseconds on mobilebert in RelWithDebInfo), thanks to efficient structural checks and plenty of places to short circuit and return early. If we find it needs speeding up, we can
1) Write a `llvm::hash_code` analysis for executables, traversing regions/blocks and using `OperationEquivalence::computeHash()` 
2) Query and compare hashes use `getChildAnalysis<>` as a first check (like a bounding box test prior to collision tests)
3) Run the existing deep equivalence check to verify that a hash collision didn't happen

The new pass emits [statistics](https://mlir.llvm.org/docs/PassManagement/#pass-statistics), like these for mobilebert (debug build + `-pass-statistics` flag):

```
mlir::iree_compiler::IREE::Flow::DeduplicateExecutablesPass
  (S) 930 total executable(s)     - Number of flow.executable ops before deduplication
  (S) 891 duplicate executable(s) - Number of flow.executable ops removed as duplicates
  (S)  39 unique executable(s)    - Number of flow.executable ops remaining after deduplication
```