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

    <tr>
        <th>Summary</th>
        <td>
            [MLIR] Dependencies of (Sparse)DataFlowAnalysis
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            new issue
      </td>
    </tr>

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

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

<pre>
    I've seen the following pattern pop up a few times in third party code:

```
DataFlowSolver solver;
solver.load<DeadCodeAnalysis>();
solver.load<SomeAnalysis>();
solver.initializeAndRun(op);
```

This is typically broken: `SparseDataFlowAnalysis` queries lattice elements from `DeadCodeAnalysis` (`Executable` and `PredecessorState`). So far, so good, but `DeadCodeAnalysis` also [queries ConstantValue lattice elements]( 
https://github.com/llvm/llvm-project/blob/main/mlir/lib/Analysis/DataFlow/DeadCodeAnalysis.cpp#L331), and will mark all blocks as dead which have inputs that have uninitialized `ConstantValue` lattice elements. (Which they will if there's no analysis to fill them in)

So the above really needs to be

```
DataFlowSolver solver;
solver.load<DeadCodeAnalysis>();
solver.load<SparseConstantPropagation>();
solver.load<SomeAnalysis>();
solver.initializeAndRun(op);
```

The first code block above was likely cargo-culted from MLIR itself, which does e.g.

```
DataFlowSolver solver;
solver.load<DeadCodeAnalysis>();
solver.load<IntegerRangeAnalysis>();
solver.initializeAndRun(op);
```

But here, the subtle difference is that `IntegerRangeAnalysis` fills in the needed `ConstantValue` lattice (i.e., acts as a replacement for `SparseConstantPropagation`). But that wasn't true for the analyses in third party code.

Options:

1. Leave things as is, but add some documentation and comments to point out this caveat.
2. Make `DataFlowSolver::load` also load dependencies. That is, each analysis would know what other analyses it need to run in parallel, e.g. through a virtual `getDependentAnalyses()` method. (`DeadCodeAnalysis` would then declare to need `SparseConstantPropagation`, and the latter would be the only user of `ConstantValue` lattices, so it doesn't conflict with things like `IntegerRangeAnalysis` since now both will get pulled in at the same time.)
3. Make analyses more self-contained. In particular, change `(Sparse)DataFlowAnalysis` to not depend on `DeadCodeAnalysis`.
4. Make it an error if an analysis pulls in a lattice element from an analysis that's not loaded into the solver. Tricky to detect (since at the start, everything is uninitialized), but there could e.g. be a check at the end of an analysis run that disallows any remaining uninitialized lattice elements on any dependency edge.
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzFVk1v2zgQ_TXyhahgSY4TH3zIRwMEaLFFU-yeKXEkc02RWpKK1_vr9w0l56tpgz0sChi2KY2oN2_evGHt1HF7l5XnDyQCkRVxR6J1xriDtp0YZIzkrRjcIMZBSNHSQUTdUxCaY7VXiPHxKBqnKKsus-VNtjx9r5fzJy1vZJS32PfemQfyIqSfrLqa7k7L3Dipsur6hqS6xo6XVppj0CGrPmblRVZufhB_7_r3Y7XVUUuj_0Go-jpaRLnhedwrwNP3t51GskHE46AbacxR1N7tySJZgdB7pB_olNsjhvVS_DWS1yDKgEPdkCBDPdkYROtdz49-lyQeYuTr5ce_qRmjrA3xNWkVh3_xpKihEJy_jzLyLYDPxb0TrfRZeQ1KReec4r_1GH_0CmkQl51dnfBdOxuitPF3aUb6Dm12dgNMYuJiF-MQuMrlLT6djruxzhvXY2HMw-nnw-Ddn9RELGvjavz0Ulv-MdpzjOZrj5DK2xN7_PcV4LwZUKLqU1UVXClkxmwctDGil36PZIzAS5p9EDIIhafFYaebndhJKFrbYQThcSfjdGG0TyJIpL5Intl5nX_OJfkjbYnWOE6v1i0vPKFvgrAOmCa0IqIWHIC7veCcN8-lhEpxe8naAYqnJCZLpNJzNf2q3kkKPhHxxbtBdjJqZ39p08GFtA8x-cpU4Zm3A-ps9J7AXSN95z40o4koZuqqz5_uvgodA5mWtTJJQTmonPIu_0UE39lIHfmv0nb_F19XaPdJkNdJYmGsoyGhdNviqoWe9dwGePBNPJA-K3f2dUq6fKdFAE3nlKembGJqQAlZD0Y2qXcwR_yTRb4lsNnBGH0Ch9oi4XOs_Ejp8dQvCePbI-dFTX8beNfwagwVufhE3Px41nYJJrvO5JFSKRS7B1WuGRl0ApZMBr42-TWac3Aa-biEE0w22E7G-d1lLj7LPSW7faEixlFdJhGcbJcXcKmBrEJV4L65-MaJT4BIQq2PXnJwo1Fib90BOkaMY8t5RkZMNWJ0frTMDViBpZBJW0HuwOrd2GFL8aB9HKVhjB3FmxlAvJw3m6UIlD3FnVP5PIfeGh8TLGCxSKQx0hNDSFDerfXk3lxTkw4W82Y1pWvOoqfHgMuu_ZnwwjzrwAC39qSYxtnW6AYawlQ6lZp94meKD5pbgxmuwe7k7eBHDCN4VMypjFM_SUiEzz35o6VXc9kfC9I7z2co034AloiJR-DxLpUFqEczzehmxyBEouNiYgtbvnV-YFZdnNUCcn4wz2cVrmY4IEVaQd6jeTCmpH0SFGeVmki-nnKTeT6P5Xacp1tMqk10xGmAzVYlvnnd7I8MVFHEwGfVTJSeaIvIPckR8cdUFDaiF1N4Hut16i2YFSrJmkgChjAkGCM2_2nHRMXLtFj9yT2UDpIPrmhxe4QR8amD3_hy6H93HEvtfnzqyqMg1VG-oG2xXl8UxdmmKBdqW6lNtZGLqGGsWxyfeNTgcCRunnVzEu5PyroYvdn-50OUDmFk0d-eXWzKcrHbrgq1OV-p9bJRm815Q2dVUZfNkmS7ksvVulkYWZMJjDIrS4sje9oC_wF4obflsiyLoliWRVWclfmG2mqNJdItV5uLOlstmTuTM47c-W7htwlSPXYBN40OOBc93pQh6A79n16H_eUIC_HbHjzvtAx7L_t-kQBsUwL_Ai6xHdw">