✨ MLIR - Transformations vs. Canonicalizations vs. Folds

[DRovara]

What's the problem this feature will solve?

Generally, rewrites of the IR within a dialect can be categorized into Folds, Canonicalizations, and Transformations.

At the moment, all rewrites mqt-core uses are implemented as transformations. However, that's not necessarily the best solution. Patterns that help other transformations be more efficient should be implemented as canonicalizations so that they are applied between other passes.
Canonicalizations that only modify the root operation can also be impelmented as "folds" which are even more powerful.

Use this guide:
https://mlir.llvm.org/docs/Canonicalization/
for larger design decisions.

Describe the solution you'd like

The current transformation passes should be reorganized into:

• Transformations:
  • non-local modifications
  • may change semantics for the sake of optimization
  • may have higher complexities
  • e.g.: mqt-core-round-trip
• Canonicalizations:
  • local modifications
  • don't change semantics
  • constant complexity
  • e.g.: constant-folding, cancel-consecutive-inverses
• Folds:
  • local modifications
  • only modify or replace the root operation
  • no operations are erased or created

A canonicalization pipeline should then be set up that automatically applies all our canonicalizations automatically

[DRovara]

As shortly discussed in a different PR:

MLIR's guide on Canonicalisations says the following about canonicalizations:

Pass pipelines should not rely on the canonicalizer pass for correctness. They should work correctly with all instances of the canonicalization pass removed.

That's a bit confusing because I thought the point of canonicalisations was to make writing optimisations easier. Dan Gohman's article on Canonicalisations (which is suggested reading by the MLIR guide) even says explicitly:

It [using canonicalizations] means that subsequent optimizations that look for specific patterns of code only have to look for the canonical forms, rather than all forms

My intuition says that "correct" here means that it should never produce "wrong" code, not that it should always work, but that's just my best guess. In any case, it should be reasonable to ignore that first quote from MLIR (unless I misunderstand something here).
We should do some more reading on that before setting up the canonicalization pipeline.