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

    <tr>
        <th>Summary</th>
        <td>
            [mlir] `mergeIdenticalBlocks` is blowing up on a conditional to identical CFGs
        </td>
    </tr>

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

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

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

<pre>
    This example shows the beginnings of algorithmic explosion when run through `mlir-opt -canonicalize`

```mlir
module {
  llvm.func @foo(%arg0: i64)

  llvm.func @rand() -> i1

  llvm.func @top(%arg0: i64) {
    %0 = llvm.mlir.constant(0 : i64) : i64
    %1 = llvm.mlir.constant(8 : i64) : i64
    %2 = llvm.mlir.constant(7 : i64) : i64
    %3 = llvm.mlir.constant(6 : i64) : i64
    %4 = llvm.mlir.constant(5 : i64) : i64
    %5 = llvm.mlir.constant(4 : i64) : i64
    %6 = llvm.mlir.constant(3 : i64) : i64
    %7 = llvm.mlir.constant(1 : i64) : i64
    %8 = llvm.mlir.constant(2 : i64) : i64
    %10 = llvm.icmp "eq" %arg0, %0 : i64
    llvm.cond_br %10, ^bb1, ^bb14
  ^bb1:  // pred: ^bb0
    %11 = llvm.call @rand() : () -> i1
    llvm.cond_br %11, ^bb2, ^bb3
  ^bb2:  // pred: ^bb1
    llvm.call @foo(%7) : (i64) -> ()
    llvm.br ^bb4
  ^bb3:  // pred: ^bb1
    llvm.call @foo(%8) : (i64) -> ()
    llvm.br ^bb4
  ^bb4:  // 2 preds: ^bb2, ^bb3
    %14 = llvm.call @rand() : () -> i1
    llvm.cond_br %14, ^bb5, ^bb6
  ^bb5:  // pred: ^bb4
    llvm.call @foo(%6) : (i64) -> ()
    llvm.br ^bb7
  ^bb6:  // pred: ^bb4
    llvm.call @foo(%5) : (i64) -> ()
    llvm.br ^bb7
  ^bb7:  // 2 preds: ^bb5, ^bb6
    %17 = llvm.call @rand() : () -> i1
    llvm.cond_br %17, ^bb8, ^bb9
  ^bb8:  // pred: ^bb7
    llvm.call @foo(%4) : (i64) -> ()
    llvm.br ^bb10
  ^bb9:  // pred: ^bb7
    llvm.call @foo(%3) : (i64) -> ()
    llvm.br ^bb10
  ^bb10:  // 2 preds: ^bb8, ^bb9
    %20 = llvm.call @rand() : () -> i1
    llvm.cond_br %20, ^bb11, ^bb12
  ^bb11:  // pred: ^bb10
    llvm.call @foo(%2) : (i64) -> ()
    llvm.br ^bb13
  ^bb12:  // pred: ^bb10
    llvm.call @foo(%1) : (i64) -> ()
    llvm.br ^bb13
  ^bb13:  // 2 preds: ^bb11, ^bb12
    llvm.br ^bb27
  ^bb14:  // pred: ^bb0
    %23 = llvm.call @rand() : () -> i1
    llvm.cond_br %23, ^bb15, ^bb16
  ^bb15:  // pred: ^bb14
    llvm.call @foo(%8) : (i64) -> ()
    llvm.br ^bb17
  ^bb16:  // pred: ^bb14
    llvm.call @foo(%7) : (i64) -> ()
    llvm.br ^bb17
  ^bb17:  // 2 preds: ^bb15, ^bb16
    %26 = llvm.call @rand() : () -> i1
    llvm.cond_br %26, ^bb18, ^bb19
  ^bb18:  // pred: ^bb17
    llvm.call @foo(%5) : (i64) -> ()
    llvm.br ^bb20
  ^bb19:  // pred: ^bb17
    llvm.call @foo(%6) : (i64) -> ()
    llvm.br ^bb20
  ^bb20:  // 2 preds: ^bb18, ^bb19
    %29 = llvm.call @rand() : () -> i1
    llvm.cond_br %29, ^bb21, ^bb22
  ^bb21:  // pred: ^bb20
    llvm.call @foo(%3) : (i64) -> ()
    llvm.br ^bb23
  ^bb22:  // pred: ^bb20
    llvm.call @foo(%4) : (i64) -> ()
    llvm.br ^bb23
  ^bb23:  // 2 preds: ^bb21, ^bb22
    %32 = llvm.call @rand() : () -> i1
    llvm.cond_br %32, ^bb24, ^bb25
  ^bb24:  // pred: ^bb23
    llvm.call @foo(%1) : (i64) -> ()
    llvm.br ^bb26
  ^bb25:  // pred: ^bb23
    llvm.call @foo(%2) : (i64) -> ()
    llvm.br ^bb26
  ^bb26:  // 2 preds: ^bb24, ^bb25
    llvm.br ^bb27
  ^bb27:  // 2 preds: ^bb13, ^bb26
    llvm.return
  }
}
```

It corresponds approximately to 

```c++
if (something) {
  foo(1, 2)
  foo(3, 4)
  foo(5, 6)
  foo(7, 8)
} else {
  foo(2, 1)
  foo(4, 3)
  foo(6, 5)
  foo(8, 7)
}
```

The block merger is trying to merge both branches together, since they share similar sub-CFGs, but it's blowing up on the number of block operands. Adding just a few more branches causes 💥
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJy0WF2ToygU_TXk5VanABXjQx66J5Otedi3ed9CQ5RZFRdwe3p__RaYjh-JccvJVqW6CXK4x3PhXAI3Rua1EHsUvaHosOGtLZTe_67ylJflJlWnj_33QhoQP3nVlAJMod4N2EJAKnJZ17LODagz8DJXWtqikhmIn02pjFQ1vBeiBt3WYAut2rwAxHBVSv2iGgsvGa9VLTNeyn8EYhjhA8Kvl78Mdx83uuuq1KktBaD4rfsOUJZ_V9tzW2eAQnxWCtEdohHXOUbBK0gWIpoMJ50gNK9PHpLACwq-giQPBlvV3Jt-SAcA0QgDCg4d1FHfZqo2ltcW0Z171OMuzSGWzGN3S1g6j42XsME8li1hw3lstISN5rHhEpbNY4MlbDyPJUvY3TyWLuZ3sDhkVjWAKBV_IUrhc13RL59raIL2mEzVpz9S3U3lx0Zf05T0rSvg8iBwTXpE9AiNFif33T_BY1qDdZfxspzsDY-6s03u0urJ0GsrGLGis6xu5r1wue7seEDnIrNn1LGboB0hN-tYk2B99N2vRw-H0amPb64E7gjWpSd8XnrCa4zo2mIjitGsQDercSoQWyNQPIrO1kePfj16_Cg9dwTr0hM_Lz3xNcbu2kpGFHezAsVLAoVrBCJ4FD5ZHz54QniCH2XojmZdacRPyxAd2O7Ad-mY5bzxErwkE10l09hiyQOPXSRAnkEgeJSnu8pNJqTjnUnC_1jLaPC8XAc9zX7zk7Fdknm_JIuWtaqikIky85a5TGBVQZ0SeOiad5XrMsWelynWB-lNgIydk8xbJ1k0r1XFhU7Ma948lwmsqq0TAvShe95VrstU8rxMJf35cHBUHPsnnfdPumhfq8oMnRxR5_1zmcCqMjsl8NA_7yrX_ZCjT8tU0B9HaX9qpNGY57wt0-B_KTR0bL903n6XCawqtVMC7GGm7in3uNLRx3ba1yTKJhNqYVtdXyeLD5fbjGvj80pleMvxzUKmtBamUfXJAG8arX7KiltRfoBVcPdOJkP0zX18rzw7wYyqhC1knU_uRDqx_YKlA1G7bv8y4U23LxnsptsfjvvMoPgAojTiNppfueQG73MR3HT72hHddHs3jIfRHqj4vRCQlir7Eyqhc6FBGrD6Q9a509D3QapsAanmdVYIA1blwhZCuyhG1pkAW4gPMAXXAoysZMk1mDZ9-XL8zbhBaWtBWkRj4yK9u6nbBlTtr-LqtkqFBnW-sFCNcNvebOH1dHJDf7TGAoezeIdKadHzyHhrhAF0xCg5ooSi12hz2genJEj4RuwJ27EgYoSFm2KfpHEgxG4XZSIhO3Li2fnMBNslHGdZRs4buaeYBpgRjDFhONziKMFREDCaZYyEoUAhFhWX5dYvWKXzjTSmFXsW0ABvSp6K0vibSEr9vR-lKDps9N4Nf0nb3KAQl9JY009gpS397aUHRAd_w-gE_3YStZUZL9-cJAYx7LIy1o6Dczxppap56VIlP0HgdN-0utwX1jZuA3Y7Mpe2aNNtpipEj47E5d9Lo9UPkVlEj_6VDKJH_1b_BgAA__837nEQ">