Add ILP to select optimal relinearization points

[j2kun]

Fixes https://github.com/google/heir/issues/599

@ahmedshakill got most of the way in https://github.com/google/heir/pull/765. This PR cherry-picks their commits and finishes the ILP.

For the Cmake build changes in this PR, note that building all the dependencies of or-tools the CMake flag -DBUILD_DEPS=ON. I also found that one of the dependencies didn't build properly for me, so I added -DUSE_COINOR=OFF since we don't use CLP as a solver (just SCIP). That said, even after this PR I get linker errors for lib/libMLIRHEIRInterfaces.so.19.0, which seems unrelated to this PR.

[j2kun]

Ready for an initial review while I finish up tests.

Also an open question for me: how should we document the mathematical formulation of the ILP? In a page on heir.dev? In situ in the code? In the tablegen?

[j2kun]

Discovered when writing more tests:

• Rotate ops need to have linearized inputs, so this needs to be added as an additional constraint in the ILP
• For some reason, the smoke test I added isn't solving the way I expect it to (it leaves the relinearize ops in place instead of factoring them through the rest of the IR). I suspect my solver model isn't handling non-add/mul ops correctly.

[AlexanderViand-Intel]

Ready for an initial review while I finish up tests.

Given your most recent comment, do you still want (initial) reviews already, or should we wait until those issues are resolved?

[j2kun]

I don't think the remaining issues will drastically change the structure of the PR, so it is ready for a first round of reviews.

[ahmedshakill]

I tried to modify secret-to-bgv pass to output only bgv.mul and no relin op for arith.muli. But got stuck there as #860. 🙂

[j2kun]

OK, fixed up all the tests. Last two things

• Whether we should rename the "lazy" part to something closer to its actual behavior (maybe "optimize-relinearization"?)
• Where to put model documentation

[AlexanderViand-Intel]

OK, fixed up all the tests. Last two things

• Whether we should rename the "lazy" part to something closer to its actual behavior (maybe "optimize-relinearization"?)
• Where to put model documentation

I like optimize-relinearization 👍 (and don't have a good suggestion for the second point)

[j2kun]

@asraa this is ready for a final review.

[j2kun]

Hmmm. I think this will also break the CMake build because we don't yet have the ortools dependency in cmake, right?

[AlexanderViand-Intel]

Hmmm. I think this will also break the CMake build because we don't yet have the ortools dependency in cmake, right?

Yes, unfortunately. Though it looks like ortools is available as a binary, so we can just make install it system wide I think (unless you're doing something that would require building it from source?)

EDIT: even better, the or-tools repo has a CMakelists.txt and seems to be setup "nicely" (as opposed to the mess that is LLVM/MLIR), so we can just FetchContent it

[j2kun]

Can't use it as a binary because we're depending directly on the C++ API. I'll try FetchContent.

[AlexanderViand-Intel]

Can't use it as a binary because we're depending directly on the C++ API. I'll try FetchContent.

Yep, they even have a nice example of how to do it here: https://github.com/google/or-tools/blob/stable/cmake/README.md#using-fetchcontent

[j2kun]

Can't use it as a binary because we're depending directly on the C++ API. I'll try FetchContent.

Yep, they even have a nice example of how to do it here: https://github.com/google/or-tools/blob/stable/cmake/README.md#using-fetchcontent

Facepalm: there is a CMake config for my mlir-tutorial, which includes or-tools 🤣

[j2kun]

I admit I'm glossed over a little bit at the solver's implementation, I'll keep digging in it though.

@asraa I think it's fair to not devote too much time to this right now, I can write up a better doc and walk you through it after I'm back from leave.

[asraa]

@asraa I think it's fair to not devote too much time to this right now, I can write up a better doc and walk you through it after I'm back from leave.

Thank you! I do understand the simpler constraints like operand1.deg - operand2.deg = 0, but the later parts confuse me :)

[j2kun]

Squashing the PR.

[asraa]

Getting around to merging this now, thank you for the wait! I'll take care of the rebase internally since it needs a BUILD fix for the dependency.

[j2kun]

Due to the internal deprecation of the MPSolver API, I migrated the solver API to math_opt and squashed the changes from https://github.com/google/heir/pull/1033 into this PR (since https://github.com/google/heir/pull/1033 contained simplifications of the model building step).

[j2kun]

The build failure doesn't occur on my machine, looks like an outdated cstdlib on the GH action runner:

external/com_google_ortools/ortools/util/fp_roundtrip_conv.cc:66:7: error: call to 'to_chars' is ambiguous
      std::to_chars(buffer.data(), buffer.data() + buffer.size(), value);
      ^~~~~~~~~~~~~
/usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/charconv:363:1: note: candidate function
_GLIBCXX_TO_CHARS(char)

@asraa How can we resolve this? Maybe use ubuntu 22.04 or 24.04 instead of 20.04?