<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/86765>86765</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            [MLIR] Top-down applyPatternsAndFoldGreedily fails to remove dead code that bottom-up applyPatternsAndFoldGreedily removes
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            mlir
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          mlevesquedion
      </td>
    </tr>
</table>

<pre>
    Consider the following IR:

```
func.func @foo(%arg0: i1, %arg1: i32) {
 %0 = arith.constant 0 : i32
  %1 = arith.bitcast %arg1 : i32 to i32
 %if = scf.if %arg0 -> (i32) {
    scf.yield %0 : i32
  } else {
 scf.yield %1 : i32
  }
  %dead_leaf = arith.addi %if, %if : i32
 func.return
}
```

When applying a single iteration of `applyPatternsAndFoldGreedily` with `config.useTopDownTraversal = true`, we get:

```
func.func @foo(%arg0: i1, %arg1: i32) {
  %c0_i32 = arith.constant 0 : i32
  return
}
```

That's pretty good, but `%c0_i32` is clearly dead, and probably should have been removed. Indeed, when doing a bottom-up traversal (`config.useTopDownTraversal = false`) we get:

```
func.func @foo(%arg0: i1, %arg1: i32) {
 return
}
```

Interestingly, if instead of `%dead_leaf = arith.addi %if, %if : i32`, we use `%dead_leaf = arith.bitcast %if : i32 to i32`, both types of traversal manage to remove all the dead code.

Note also that this pattern can be chained, in which case a bottom-up traversal will still remove all dead values, whereas a top-down traversal will require 1 iteration for each repetition of the pattern in order to remove all the dead values. This is in fact how I ran into this in the first place: I was working with a fairly large (generated) function where it took 10 iterations to fully remove all the dead code with a top-down traversal, whereas a bottom-up traversal required a single iteration.

For additional context, see this thread in the MLIR Discord: https://discordapp.com/channels/636084430946959380/1221989192826097774

In order to produce the above examples, I used `mlir-opt --canonicalize`, with the following patch applied:

```
diff --git a/mlir/lib/Transforms/Canonicalizer.cpp b/mlir/lib/Transforms/Canonicalizer.cpp
index d50019bd6aee..200220a297ab 100644
--- a/mlir/lib/Transforms/Canonicalizer.cpp
+++ b/mlir/lib/Transforms/Canonicalizer.cpp
@@ -43,24 +43,16 @@ struct Canonicalizer : public impl::CanonicalizerBase<Canonicalizer> {
   /// execution.
   LogicalResult initialize(MLIRContext *context) override {
     // Set the config from possible pass options set in the meantime.
-    config.useTopDownTraversal = topDownProcessingEnabled;
+ config.useTopDownTraversal = true;
 config.enableRegionSimplification = enableRegionSimplification;
- config.maxIterations = maxIterations;
+    config.maxIterations = 1;
 config.maxNumRewrites = maxNumRewrites;

-    RewritePatternSet owningPatterns(context);
-    for (auto *dialect : context->getLoadedDialects())
- dialect->getCanonicalizationPatterns(owningPatterns);
-    for (RegisteredOperationName op : context->getRegisteredOperations())
- op.getCanonicalizationPatterns(owningPatterns, context);
-
- patterns = std::make_shared<FrozenRewritePatternSet>(
- std::move(owningPatterns), disabledPatterns, enabledPatterns);
     return success();
   }
   void runOnOperation() override {
 LogicalResult converged =
- applyPatternsAndFoldGreedily(getOperation(), *patterns, config);
+ applyPatternsAndFoldGreedily(getOperation(), RewritePatternSet(&getContext()), config);
     // Canonicalization is best-effort. Non-convergence is not a pass failure.
     if (testConvergence && failed(converged))
       signalPassFailure();
 ```
 
 (The same results can be obtained by writing a new pass that doesn't use any patterns and merely calls `applyPatternsAndFoldGreedily` with the desired `config`. The above is just an easy way to isolate the behavior of interest.)
 
 This was observed at `HEAD` specifically `4d03a9ecc697a11f0edd3c31440a7cae3398e24a` at time of writing.
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJy8WNtu4zjSfhrmpmBDomzJushFDu3_DzDbM-gJsJcNSixZnKZJDUnZ8Tz9oigplhP3EdhtCEparCpWfXXgxwjv1c4g3rL1PVs_3og-tNbd7jUe0P_do1TW3FRWnm4frPFKooPQIjRWa3tUZgdPn1h2x5JHlkzvPBmf-N-mN_WSXsBWSWMt4xvG18LtEpbdgUoZf4DhQxo_ZJzxElhxP6jTWgIsewThVGiXtTU-CBOAPg7igxwJpjPBSoVa-DDZnqQh2JkS42vVRCVfN0v6dXANFiz7AIxv3rkDEEVPCrWcfLt0o3gE1B5nOhcK6RWFWQgShfysUTSzUISUanB1BCv6PDcSQXYYemfGJExG32RjeP-7RQOi6_SJMijAK7PTCCqgE0FZA7YBlidR4g8RAjrj74zcWi3_zyFKpU8sT-CoQktytTWN2i17j8-2e7RH8-zEAZ0XOgYRXI_kAH-AI8IOw3-3YGixTj5Trn-kbH4ctedWBMYLD53DEE6ws1aSM1UfIMY3bkvQKA-1RuH0CSijJCaMhM7ZSlT6BL61vZbQigNChWjA4d4eUC7hyUjEqHCkLEk7pKiyIdj9ou8gnMHlm--j3wjtB_jL_wn8P47nkwno0AcqvhOZVQ0o4wMKORbgL_TDa5311IJfNTGbDmflaTYMNiobWginDj15c0Z9L4zYIckOOQOhdZyJtA_UVuJyHuVHG0jEWwitCBBa5aEbegpqYaBCqFuhzJBzZeDYqrqFWnj8StqPSmvwgd4zD-LuB6F79GPxOBQeBATbLaQ9mrcWHP7dK4eQzvq-sQ5Q1C047DCoaRZQdJPPyoB18Ri4DsDgwhKeKVB6DDSiDtDaIzyBE2Qh2AEHZYbDRDkfoNOiRsrEExyFh6N1X6j045AR0AhFzaSF2yEV_g4NOU2olXH8RV9j1KACBGu_QJqcQ_Pkb9Nrffpq2qat3gN2Cei1nIxgyivD9KIattYBlS8tCA21NQFfAtn3iAMooXXk0YjNv357-gSPytfWSQKnDaHz1MF8y_hWDgui65a13TO-rVthDGrP-DbP8mSzWmVJucrLdZltEsa3KedpuSnTkm94npRFUawuW_Kc3M5Z2dcYvRAVIYYvYt_pob6eqMEkddheK7ewXYDFohbGGlULrf55nfiE6SVj6ESo23j8KJTfHkZSNQ0sFjsVQDC-pa0Y32pVMb59dsL4xro9Bfsw29kt666D6ufkh_2UkfgCcp0kaVnJXCAulzxJOE8ELwtRQZok-WqEbLFY_KxXY5D8fnh-zUm2StgqgcUqY_yBr4Dx-_hrmsO45IPr6wAX-nHIdX2lVQ1q32kCPru7ELkXHln2cPEt8qAZ-xnqjvEt4AvW_azAAeA3uyO9T-h7HUAZFdRQC3xDdfwwVDswfvda-CXYAzqnJF6SrHEj-BNDLJ_hlIPG2T101ntVaZpJ3oPthv72GKam2aMwQe2nQbwge98jKcPHP5yt0VMLfzCi0lSf969J-64NIjqT_CSM0c4n3Clr_iTgVaPqYdqSzteXXy0tJlN78fJ0nmekffHlwtVzxO-10ndO7sXLx37_CY9OBXw1Pft0tn1GdFwbCSIlyh6NMruJMTK-Oad5Fg1APGcY34g-WKoGqYTGOsQSHVWIgO8w_GaFRPk4rPvIRUp6RlOj4ig8K9wY7cyRt55d94fS4ImUyN-7EbGPYo9guyuuXRF-76Dtlj_n2ANcw2wyNx7CQ4Z8kEMT78UX_Oxb4ahcH7bO_oPmXXJY9oG8Gw2dde0Br-LDH0AqH3tg7t1Qr_IakrFtB_oHvq-pj0Y8ZhKz2w4crJLgevO7eUVwULg2Ey5nS23NAd2OTqDscQrqm_cVogzhzT4DfbzrLtFv1G7uNHXTL1l-nwJayqkephRP1XJ14_kYfFtBxKwq9GGBTWNdWMJHaxYTKKZGWjc2gBhmZCOU7h0uZ4bjZXcT0JM3r2qM54znUZ6o1eYV53lZw_DPq50R-g_h_XYw_zbbbw5zeL10b55bBE-d5WI6_cSEbRUiFYbqBATecPcxeBzCiAxaWvSG8SJEii_M6dwVdMXao0N9glpo7X_4EjvwQB8Z3OuViuUJ0diJ_SgPf_U-gDCAwp_gKE7xwuCtFmGgSRW24qCsI86sxtvN8gzb-CMyY6K4tvLoDkQa4wXy_z_cPZJHvsM6ngJEVlmerGSSiRLrOi8LkaZNglJmdZauVokoaoFZVm6QrwTp0g1D0cRqJvyWN_I2k2VWihu8TYs0XadZvs5u2luRF0mR8zwVWBTrKhVFUYgmxabO6iYRzY265QlfJRkvkhUvsmyJzSqra14lZVmUZZWzVYJ7ofRS68N-ad3uRnnf4-0mL_L1jRYVah__sMT5wHI4Wz_euFsSX1T9zrNVopUP_mwgqKDjH6OIMLD1IzxPbPxbiYwF62dXkjOpjzVzpuzftDIo-5ve6dtLor1Toe2rkWSTs-OPRefsX1gHxrcxdKJtMfr_BAAA__8Jwxy4">