llvm/test/Transforms/InstCombine/infinite-loop-postdom.ll

   1 ; RUN: opt < %s -disable-output -passes=instcombine -verify-dom-info
   2 ; RUN: opt < %s -passes='print<postdomtree>' 2>&1 | FileCheck --check-prefixes=CHECK-POSTDOM %s
   3
   4 ; Demonstrate that Predicate Canonicalization (InstCombine) does not invalidate PostDomTree
   5 ; if the basic block is post-dom unreachable.
   6
   7 define void @test1(i24 %a, i24 %b) {
   8 entry:
   9   br label %LOOP
  10
  11 LOOP:
  12   %f = icmp uge i24 %a, %b
  13   br i1 %f, label %B1, label %B2
  14
  15 B1:
  16   %x = add i24 %a, %b
  17   br label %B2
  18
  19 B2:
  20   br label %LOOP
  21 }
  22
  23 ; The same as @test1 except the LOOP condition canonicalized (as by instcombine).
  24 define void @test1-canonicalized(i24 %a, i24 %b) {
  25 entry:
  26   br label %LOOP
  27
  28 LOOP:
  29   %f.not = icmp ult i24 %a, %b
  30   br i1 %f.not, label %B2, label %B1
  31
  32 B1:
  33   %x = add i24 %a, %b
  34   br label %B2
  35
  36 B2:
  37   br label %LOOP
  38 }
  39
  40 ; The same as @test1 but different order of B1 and B2 in the function.
  41 ; The different order makes PostDomTree different in presense of postdom
  42 ; unreachable blocks.
  43 define void @test2(i24 %a, i24 %b) {
  44 entry:
  45   br label %LOOP
  46
  47 LOOP:
  48   %f = icmp uge i24 %a, %b
  49   br i1 %f, label %B1, label %B2
  50
  51 B2:
  52   br label %LOOP
  53
  54 B1:
  55   %x = add i24 %a, %b
  56   br label %B2
  57 }
  58
  59 ; The same as @test2 except the LOOP condition canonicalized (as by instcombine).
  60 define void @test2-canonicalized(i24 %a, i24 %b) {
  61 entry:
  62   br label %LOOP
  63
  64 LOOP:
  65   %f.not = icmp ult i24 %a, %b
  66   br i1 %f.not, label %B2, label %B1
  67
  68 B2:
  69   br label %LOOP
  70
  71 B1:
  72   %x = add i24 %a, %b
  73   br label %B2
  74 }
  75
  76 ; Two reverse unreachable subgraphs with RU1* and RU2* basic blocks respectively.
  77 define void @test3(i24 %a, i24 %b, i32 %flag) {
  78 entry:
  79   switch i32 %flag, label %EXIT [
  80     i32 1, label %RU1
  81     i32 2, label %RU2
  82     i32 3, label %RU2_B1
  83   ]
  84
  85 RU1:
  86   %f = icmp uge i24 %a, %b
  87   br label %RU1_LOOP
  88
  89 RU1_LOOP:
  90   br i1 %f, label %RU1_B1, label %RU1_B2
  91
  92 RU1_B1:
  93   %x = add i24 %a, %b
  94   br label %RU1_B2
  95
  96 RU1_B2:
  97   br label %RU1_LOOP
  98
  99 RU2:
 100   %f2 = icmp uge i24 %a, %b
 101   br i1 %f2, label %RU2_B1, label %RU2_B2
 102
 103 RU2_B1:
 104   br label %RU2_B2
 105
 106 RU2_B2:
 107   br label %RU2_B1
 108
 109 EXIT:
 110   ret void
 111 }
 112
 113 ; The same as @test3 except the icmp conditions are canonicalized (as by instcombine).
 114 define void @test3-canonicalized(i24 %a, i24 %b, i32 %flag) {
 115 entry:
 116   switch i32 %flag, label %EXIT [
 117     i32 1, label %RU1
 118     i32 2, label %RU2
 119     i32 3, label %RU2_B1
 120   ]
 121
 122 RU1:
 123   %f.not = icmp ult i24 %a, %b
 124   br label %RU1_LOOP
 125
 126 RU1_LOOP:
 127   br i1 %f.not, label %RU1_B2, label %RU1_B1
 128
 129 RU1_B1:
 130   %x = add i24 %a, %b
 131   br label %RU1_B2
 132
 133 RU1_B2:
 134   br label %RU1_LOOP
 135
 136 RU2:
 137   %f2.not = icmp ult i24 %a, %b
 138   br i1 %f2.not, label %RU2_B2, label %RU2_B1
 139
 140 RU2_B1:
 141   br label %RU2_B2
 142
 143 RU2_B2:
 144   br label %RU2_B1
 145
 146 EXIT:
 147   ret void
 148 }
 149
 150 ; PostDomTrees of @test1(), @test2() and @test3() are different.
 151 ; PostDomTrees of @testX() and @testX-canonicalize() are the same.
 152
 153 ; CHECK-POSTDOM-LABEL: test1
 154 ; CHECK-POSTDOM-NEXT: =============================--------------------------------
 155 ; CHECK-POSTDOM-NEXT: Inorder PostDominator Tree: DFSNumbers invalid: 0 slow queries.
 156 ; CHECK-POSTDOM-NEXT:   [1]  <<exit node>>
 157 ; CHECK-POSTDOM-NEXT:     [2] %B1
 158 ; CHECK-POSTDOM-NEXT:       [3] %LOOP
 159 ; CHECK-POSTDOM-NEXT:         [4] %entry
 160 ; CHECK-POSTDOM-NEXT:         [4] %B2
 161 ; CHECK-POSTDOM-NEXT: Roots: %B1
 162
 163 ; CHECK-POSTDOM-LABEL: test1-canonicalized
 164 ; CHECK-POSTDOM-NEXT: =============================--------------------------------
 165 ; CHECK-POSTDOM-NEXT: Inorder PostDominator Tree: DFSNumbers invalid: 0 slow queries.
 166 ; CHECK-POSTDOM-NEXT:   [1]  <<exit node>>
 167 ; CHECK-POSTDOM-NEXT:     [2] %B1
 168 ; CHECK-POSTDOM-NEXT:       [3] %LOOP
 169 ; CHECK-POSTDOM-NEXT:         [4] %entry
 170 ; CHECK-POSTDOM-NEXT:         [4] %B2
 171 ; CHECK-POSTDOM-NEXT: Roots: %B1
 172
 173 ; CHECK-POSTDOM-LABEL: test2
 174 ; CHECK-POSTDOM-NEXT: =============================--------------------------------
 175 ; CHECK-POSTDOM-NEXT: Inorder PostDominator Tree: DFSNumbers invalid: 0 slow queries.
 176 ; CHECK-POSTDOM-NEXT:   [1]  <<exit node>>
 177 ; CHECK-POSTDOM-NEXT:     [2] %B2
 178 ; CHECK-POSTDOM-NEXT:       [3] %LOOP
 179 ; CHECK-POSTDOM-NEXT:         [4] %entry
 180 ; CHECK-POSTDOM-NEXT:       [3] %B1
 181 ; CHECK-POSTDOM-NEXT: Roots: %B2
 182
 183 ; CHECK-POSTDOM-LABEL: test2-canonicalized
 184 ; CHECK-POSTDOM-NEXT: =============================--------------------------------
 185 ; CHECK-POSTDOM-NEXT: Inorder PostDominator Tree: DFSNumbers invalid: 0 slow queries.
 186 ; CHECK-POSTDOM-NEXT:   [1]  <<exit node>>
 187 ; CHECK-POSTDOM-NEXT:     [2] %B2
 188 ; CHECK-POSTDOM-NEXT:       [3] %LOOP
 189 ; CHECK-POSTDOM-NEXT:         [4] %entry
 190 ; CHECK-POSTDOM-NEXT:       [3] %B1
 191 ; CHECK-POSTDOM-NEXT: Roots: %B2
 192
 193 ; CHECK-POSTDOM-LABEL: test3
 194 ; CHECK-POSTDOM-NEXT:=============================--------------------------------
 195 ; CHECK-POSTDOM-NEXT:Inorder PostDominator Tree: DFSNumbers invalid: 0 slow queries.
 196 ; CHECK-POSTDOM-NEXT:  [1]  <<exit node>>
 197 ; CHECK-POSTDOM-NEXT:    [2] %EXIT
 198 ; CHECK-POSTDOM-NEXT:    [2] %entry
 199 ; CHECK-POSTDOM-NEXT:    [2] %RU1_B1
 200 ; CHECK-POSTDOM-NEXT:      [3] %RU1_LOOP
 201 ; CHECK-POSTDOM-NEXT:        [4] %RU1
 202 ; CHECK-POSTDOM-NEXT:        [4] %RU1_B2
 203 ; CHECK-POSTDOM-NEXT:    [2] %RU2_B1
 204 ; CHECK-POSTDOM-NEXT:      [3] %RU2
 205 ; CHECK-POSTDOM-NEXT:      [3] %RU2_B2
 206 ; CHECK-POSTDOM-NEXT:Roots: %EXIT %RU1_B1 %RU2_B1
 207
 208 ; CHECK-POSTDOM-LABEL: test3-canonicalized
 209 ; CHECK-POSTDOM-NEXT:=============================--------------------------------
 210 ; CHECK-POSTDOM-NEXT:Inorder PostDominator Tree: DFSNumbers invalid: 0 slow queries.
 211 ; CHECK-POSTDOM-NEXT:  [1]  <<exit node>>
 212 ; CHECK-POSTDOM-NEXT:    [2] %EXIT
 213 ; CHECK-POSTDOM-NEXT:    [2] %entry
 214 ; CHECK-POSTDOM-NEXT:    [2] %RU1_B1
 215 ; CHECK-POSTDOM-NEXT:      [3] %RU1_LOOP
 216 ; CHECK-POSTDOM-NEXT:        [4] %RU1
 217 ; CHECK-POSTDOM-NEXT:        [4] %RU1_B2
 218 ; CHECK-POSTDOM-NEXT:    [2] %RU2_B1
 219 ; CHECK-POSTDOM-NEXT:      [3] %RU2
 220 ; CHECK-POSTDOM-NEXT:      [3] %RU2_B2
 221 ; CHECK-POSTDOM-NEXT:Roots: %EXIT %RU1_B1 %RU2_B1