The methods in `SideEffectUtils.h` (and their implementations in
`SideEffectUtils.cpp`) seem to have similar intent to methods already
existing in `SideEffectInterfaces.h`. Move the decleration (and
implementation) from `SideEffectUtils.h` (and `SideEffectUtils.cpp`)
into `SideEffectInterfaces.h` (and `SideEffectInterface.cpp`).

Also drop the `SideEffectInterface::hasNoEffect` method in favor of
`mlir::isMemoryEffectFree` which actually recurses into the operation
instead of just relying on the `hasRecursiveMemoryEffectTrait`
exclusively.

Differential Revision: https://reviews.llvm.org/D137857

This patch takes the first step towards a more principled modeling of undefined behavior in MLIR as discussed in the following discourse threads:

 1. https://discourse.llvm.org/t/semantics-modeling-undefined-behavior-and-side-effects/4812
 2. https://discourse.llvm.org/t/rfc-mark-tensor-dim-and-memref-dim-as-side-effecting/65729

This patch in particular does the following:

 1. Introduces a ConditionallySpeculatable OpInterface that dynamically determines whether an Operation can be speculated.
 2. Re-defines `NoSideEffect` to allow undefined behavior, making it necessary but not sufficient for speculation.  Also renames it to `NoMemoryEffect`.
 3. Makes LICM respect the above semantics.
 4. Changes all ops tagged with `NoSideEffect` today to additionally implement ConditionallySpeculatable and mark themselves as always speculatable.  This combined trait is named `Pure`.  This makes this change NFC.

For out of tree dialects:

 1. Replace `NoSideEffect` with `Pure` if the operation does not have any memory effects, undefined behavior or infinite loops.
 2. Replace `NoSideEffect` with `NoSideEffect` otherwise.

The next steps in this process are (I'm proposing to do these in upcoming patches):

 1. Update operations like `tensor.dim`, `memref.dim`, `scf.for`, `affine.for` to implement a correct hook for `ConditionallySpeculatable`.  I'm also happy to update ops in other dialects if the respective dialect owners would like to and can give me some pointers.
 2. Update other passes that speculate operations to consult `ConditionallySpeculatable` in addition to `NoMemoryEffect`.  I could not find any other than LICM on a quick skim, but I could have missed some.
 3. Add some documentation / FAQs detailing the differences between side effects, undefined behavior, speculatabilty.

Reviewed By: rriddle, mehdi_amini

Differential Revision: https://reviews.llvm.org/D135505

The patch introduces the required changes to update the pass declarations and definitions to use the new autogenerated files and allow dropping the old infrastructure.

Reviewed By: mehdi_amini, rriddle

Differential Review: https://reviews.llvm.org/D132838

This reverts commit 2be8af8f0e0780901213b6fd3013a5268ddc3359.

The patch introduces the required changes to update the pass declarations and definitions to use the new autogenerated files and allow dropping the old infrastructure.

Reviewed By: mehdi_amini, rriddle

Differential Review: https://reviews.llvm.org/D132838

LICM is refactored into a utility that is application on any region. The implementation is moved to Transform/Utils.

This reverts commit 3131f808243abe3746280e016ab9459c14d9e53b.

This commit broke the Windows mlir bot:
https://lab.llvm.org/buildbot/#/builders/13/builds/19745

LICM is refactored into a utility that is application on any region. The implementation is moved to Transform/Utils.

(This was a TODO from the initial patch).

The control-flow sink utility accepts a callback that is used to sink an operation into a region.
The `moveIntoRegion` is called on the same operation and region that return true for `shouldMoveIntoRegion`.
The callback must preserve the dominance of the operation within the region. In the default control-flow
sink implementation, this is moving the operation to the start of the entry block.

Reviewed By: mehdi_amini

Differential Revision: https://reviews.llvm.org/D122445