commit | 087c10958b1bdf9b2de07f08d061bf2b290d22da | [log] [tgz] |
---|---|---|
author | Groverkss <groverkss@gmail.com> | Fri Dec 03 03:44:36 2021 +0530 |
committer | Copybara-Service <copybara-worker@google.com> | Thu Dec 02 14:22:15 2021 -0800 |
tree | 420e1e9e9dcc43b93130a88962d7216ce4bedf73 | |
parent | b6cee14b2833d24ce2350375b271e4b548f37061 [diff] |
[MLIR][FlatAffineConstraints] Remove duplicate divisions while merging local ids This patch implements detecting duplicate local identifiers by extracting their division representation while merging local identifiers. For example, given the FACs A, B: ``` A: (x, y)[s0] : (exists d0 = [x / 4], d1 = [y / 4]: d0 <= s0, d1 <= s0, x + y >= 2) B: (x, y)[s0] : (exists d0 = [x / 4], d1 = [y / 4]: d0 <= s0, d1 <= s0, x + y >= 5) ``` The intersection of A and B without this patch would lead to the following FAC: ``` (x, y)[s0] : (exists d0 = [x / 4], d1 = [y / 4], d2 = [x / 4], d3 = [x / 4]: d0 <= s0, d1 <= s0, d2 <= s0, d3 <= s0, x + y >= 2, x + y >= 5) ``` after this patch, merging of local ids will detect that `d0 = d2` and `d1 = d3`, and the intersection of these two FACs will be (after removing duplicate constraints): ``` (x, y)[s0] : (exists d0 = [x / 4], d1 = [y / 4] : d0 <= s0, d1 <= s0, x + y >= 2, x + y >= 5) ``` This reduces the number of constraints by 2 (constraints) + 4 (2 constraints for each extra division) for this case. This is used to reduce the output size representation of operations like PresburgerSet::subtract, PresburgerSet::intersect which require merging local variables. Reviewed By: arjunp, bondhugula Differential Revision: https://reviews.llvm.org/D112867 GitOrigin-RevId: d257f7c1bff3521053d925c616f6f60d0a5c22ec
See https://mlir.llvm.org/ for more information.