[Experimental][Sharing] New Resource Sharing Pass

[Jiahui17]

This PR introduces a new resource-sharing (one physical unit for multiple operations) strategy that will be presented at IWLS '24.

It introduces a new resource sharing pass (CreditBasedSharingPass) and a new (experimental) HandshakeOp---SharingWrapperOp.

---

The experimental SharingWrapperOp decides which operation to access the shared resource, and dispatches the computed result to the corresponding successor.

The following example describes what this pass does to two sharing targets, muli0 and muli1.

Before sharing:

%succOut1 = arith.muli %pred1In1, %pred1In2 { name=#handshake.name<"muli0"> } : i32
%succOut2 = arith.muli %pred2In1, %pred2In2 { name=#handshake.name<"muli1"> } : i32

After sharing:

%sharedOut1 = arith.muli %selIn1, %selIn1 { name=#handshake.name<"muliShared1"> } : i32
%selIn1, %selIn2, %succOut1, %succOut2 = sharing_wrapper %pred1In1, %pred1In2, %pred2In1, %pred2In2, %sharedOut1 [3, 3] : i32, i32, i32, i32, i32

The sharing wrapper selects the original operands (%pred1In1, %pred1In2, %pred2In1, %pred2In2), and distributes the computed results to the original results (%succOut1, %succOut2).

It sends the selected results to the shared multiplier through %selIn1 and %selIn2, and takes the result %sharedOut1 of the shared multiplier.

The integer array in the attribute is the number of credits per operation that shares it, the number of credits sets the achievable performance of each operation that shares the unit; the sharing pass decides the credit allocation.

---

This proposed pass (CreditBasedSharingPass) is designed as a drop-in replacement of the buffer placement pass, i.e., it provides the same interface as the HandshakePlaceBuffersPass. It internally calls a derived class from HandshakePlaceBufferPass and retrieves data from MILP solutions. The retrieved data are necessary for sustaining the performance achieved during buffer placement.

[lucas-rami]

Hi @Jiahui17! At the moment this is the best way of extracting info from the MILP yes. I see that it's a bit cumbersome but can't think of an immediate way to significantly lower this workload. Let me know if you have an idea.

[Jiahui17]

Great, I also considered dumping the placement results as separate JSON files, but this ended up as extra JSON writer and parser...

[lucas-rami]

There is generally some large code overhead when dumping/parsing JSON indeed... What you did is definitely easier.

[Jiahui17]

@lucas-rami the PR is ready for review!

[Jiahui17]

Thanks for the feedback! I want to try to put all the internal logic of the sharing wrapper instead...

[Jiahui17]

Thanks for the contribution and sorry for the delayed review; I finally managed to go over everything and left small comments here and there.

Two general stylistic comments:

* Avoid overusing `auto`, it makes the code harder to read because I often have to pause and deduce the type of a lot of things that are not necessarily evident. [See LLVM's guidelines on `auto`](https://llvm.org/docs/CodingStandards.html#use-auto-type-deduction-to-make-code-more-readable).

* Do not use brackets around code blocks that contain a single statement that fits on a single line (e.g., for simple for loop). [See LLVM guidelines](https://llvm.org/docs/CodingStandards.html#don-t-use-braces-on-simple-single-statement-bodies-of-if-else-loop-statements).

One question: can I explicit declare the types of the variables when iterating through an enumerate?

[lucas-rami]

One question: can I explicit declare the types of the variables when iterating through an enumerate?

AFAIK this is one situation where you have to use auto. Iterator types are so absurdly complex that you should always use auto for them for everyone's sanity.

[Jiahui17]

@lucas-rami

Thank you so much for the comments again!

I addressed all the comments and added more cosmetic / functional changes; do we try to integrate the code here before I start changing the HW / RTL part?

[lucas-rami]

Yes I'll review this now so that we can integrate it before you start changing the backend stuff.

[Jiahui17]

Great! Thanks!