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

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