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

    <tr>
        <th>Summary</th>
        <td>
            [mlir] AbstractSparseDataFlowAnalysis is superlinear
        </td>
    </tr>

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

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

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

<pre>
    Run the script below to reproduce.

```
# N      | time (sec)
# --------------------------------------------------------
# 1000   | 0.2
# 2000   | 0.86
# 4000   | 4.21
# 8000   | 18.73
```

It creates IR like this, which requires propagating the fact that `%arg0` is not constant through N iter args (kind of like a "spiral").
```
func.func @quadratic(%arg0: i32, %arg1: i32, %start: index, %stop: index, %step: index) -> i32 {
%c0 = arith.constant 0 : i32
  %result:3 = scf.for %iv = %start to %stop step %step iter_args(%iter0 = %c0, %iter1 = %c0, %iter2 = %c0) -> (i32, i32, i32) {
    scf.yield %iter1, %iter2, %arg0 : i32, i32, i32
  }
  %eq0 = arith.cmpi eq, %result, %c0 : i32
  %select = arith.select %eq0, %arg0, %arg1 : i32
  return %select : i32
}
```

```
python /tmp/quadratic.py -n 8000 | time build/bin/torch-mlir-opt -sccp >/dev/null
```

```
import argparse



def main(N):
    iter_args = ", ".join(f"%iter{i} = %c0" for i in range(N))
    i32s = ", ".join("i32" for i in range(N))
    yield_operands = ", ".join(f"%iter{i}" for i in range(1, N)) + ", %arg0"
    print(fr"""func.func @quadratic(%arg0: i32, %arg1: i32, %start: index, %stop: index, %step: index) -> i32 {{
%c0 = arith.constant 0 : i32
  %result:{N} = scf.for %iv = %start to %stop step %step iter_args({iter_args}) -> ({i32s}) {{
    scf.yield {yield_operands} : {i32s}
  }}
  %eq0 = arith.cmpi eq, %result, %c0 : i32
  %select = arith.select %eq0, %arg0, %arg1 : i32
  return %select : i32
}}
""")

if __name__ == "__main__":
    parser = argparse.ArgumentParser()
    parser.add_argument("-n", type=int, default=3)
    main(parser.parse_args().n)
```

</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzVVsGO2yoU_Rpng2LZOE7iRRaZSUfqoqOn9gMsbLBNS7AH8MzL3_eCcXDm5UmjdtNGFjYXOBwOhxuqnl4OX0eJTMeQrhUfDKqY6N-Q6ZFig-rpWLM4Sk5RcvTlNvHPVMUZekbuF-0ekeFnhiK816yOcBG6rH_xFxDSJEn8JEmMQxwv4_ttaNiEhk2M09CwDw3pPt5l99flys8G1YoRwzT6_BUJ_oOBUlxH-BG9dbzuQKOXkStoBqkG0hLDZevEbEht4IMYZCFxTlRrwRHXSPaA2kttiLRdVD-2HWjIDVMIummr3w8uKeqbaUoCEawHroiAD9A1vku5GWUd2wJFm-RlJFQBHdiG_Tx9dkQ8w5b8FElvI0BIGReSlP17DfbDf2NsGSvQOso-WSDQ9GHWOa8TFGUnWBE3XXxdrw1Ok7p-yOKBfqOwM2duhK6buOmVbeGvLjKTs670nJAlMZNx2pVWu2m1tprMI-vE07bR9G4UL6N-OYDkpVm-irBEa3lL9cKZoFf8JWpQOqz6Fm_WYHdayMFebpQ7DxyxF4_lpZoq9T0xNRMMrBcA5oADXlBa-OA9jGJmVPIGbdF-ZXv3yLwLDhfT9RbqyZwHKK--jIcLWsvpMF4zRzVyQaFXxaUd0au6W58FV-seEtNa1zVsefYJmih7hVKOQnycCj8PPXgIFjwQpdlNz0VJWYPOxBLYP9sclh3Dfl995g3jtxjH33s3oHEht_vgEw5KLZ2FkbU1h3ODFJEtm2eYE6WbIcP_Bw6fzjofgXGmLPuBQQ_6cbZ3wZ2n_Qww_CEgeR_hMO-guDQWWrlO9vlD0tLvZSYY_jzv5u_mJ5D6WrWSh4Rjm2D_fXTJ-l2y2T3cbvBE7YgWAIvU8tdll2uCmT0U7hLTSW5QWUpyZmVpqXh3l6U9tmVp-y8PrTvtynOezn58VO14ZtL849qcGYv3I2JCqd0l13E6f2vpvW8uAwNAZ_ZHBCmDOJ-cshscn0Y8nHuFf6kilmFZt5lqRQ8ZLbKCrAw3gh2i_MFmwSg_oWOljYK7xTeHdiKGPMF17SiJuGi4W8CjRzCF4JIRtRqVOHTGDNoKgp_gaWHTxgpcf4aKEK_zaw0XmO-wGVDlWo8MOD7l2y1OV90hK7b5vqm3u90GNyTPMU0oLaq8wFVdVFm6EgQujdrSBHkke0MOwkqVn1b8gBOMk11a4CxL8T4ukoZuk802y5tdUTcU0gIDpURsecS9alfq4ChVI0i1SQTXRodGojVvJWN-ui99WxEh_GRkhL8bddBcvBLNiFw5Jge3kp-Lpfyq">