test/Transforms/IRCE/range_intersect_miscompile.ll

   1 ; RUN: opt -verify-loop-info -irce-print-changed-loops -irce -S < %s 2>&1 | FileCheck %s
   2 ; RUN: opt -verify-loop-info -irce-print-changed-loops -passes='require<branch-prob>,loop(irce)' -S < %s 2>&1 | FileCheck %s
   3
   4 ; CHECK-LABEL: irce: in function test_01: constrained Loop at depth 1 containing:
   5 ; CHECK-LABEL: irce: in function test_02: constrained Loop at depth 1 containing:
   6 ; CHECK-LABEL: irce: in function test_03: constrained Loop at depth 1 containing:
   7 ; CHECK-LABEL: irce: in function test_04: constrained Loop at depth 1 containing:
   8 ; CHECK-LABEL: irce: in function test_05: constrained Loop at depth 1 containing:
   9
  10 ; This test used to demonstrate a miscompile: the outer loop's IV iterates in
  11 ; range of [2, 400) and the range check is done against value 331. Due to a bug
  12 ; in range intersection IRCE manages to eliminate the range check without
  13 ; inserting a postloop, which is incorrect. We treat the range of this test as
  14 ; an unsigned range and are able to intersect ranges correctly and insert a
  15 ; postloop.
  16
  17 define void @test_01() {
  18
  19 ; CHECK-LABEL: test_01
  20 ; CHECK-NOT:     preloop
  21 ; CHECK:         range_check_block:                                ; preds = %inner_loop
  22 ; CHECK-NEXT:      %range_check = icmp slt i32 %iv, 331
  23 ; CHECK-NEXT:      br i1 true, label %loop_latch
  24 ; CHECK:         loop_latch:
  25 ; CHECK-NEXT:      %iv_next = add i32 %iv, 1
  26 ; CHECK-NEXT:      %loop_cond = icmp ult i32 %iv_next, 400
  27 ; CHECK-NEXT:      [[COND:%[^ ]+]] = icmp ult i32 %iv_next, 331
  28 ; CHECK-NEXT:      br i1 [[COND]], label %loop_header, label %main.exit.selector
  29 ; CHECK:         main.exit.selector:                               ; preds = %loop_latch
  30 ; CHECK-NEXT:      %iv_next.lcssa = phi i32 [ %iv_next, %loop_latch ]
  31 ; CHECK-NEXT:      %iv.lcssa = phi i32 [ %iv, %loop_latch ]
  32 ; CHECK-NEXT:      [[MES_COND:%[^ ]+]] = icmp ult i32 %iv_next.lcssa, 400
  33 ; CHECK-NEXT:      br i1 [[MES_COND]], label %main.pseudo.exit, label %exit
  34 ; CHECK:         loop_latch.postloop:                              ; preds = %range_check_block.postloop
  35 ; CHECK-NEXT:      %iv_next.postloop = add i32 %iv.postloop, 1
  36 ; CHECK-NEXT:      %loop_cond.postloop = icmp ult i32 %iv_next.postloop, 400
  37 ; CHECK-NEXT:      br i1 %loop_cond.postloop, label %loop_header.postloop, label %exit.loopexit
  38
  39 entry:
  40   br label %loop_header
  41
  42 loop_header:                            ; preds = %loop_latch, %entry
  43   %iv = phi i32 [ 2, %entry ], [ %iv_next, %loop_latch ]
  44   %iv.prev = phi i32 [ 1, %entry ], [ %iv, %loop_latch ]
  45   %tmp2 = icmp sgt i32 %iv.prev, -1
  46   br i1 %tmp2, label %loop_header.split.us, label %exit
  47
  48 loop_header.split.us:                   ; preds = %loop_header
  49   br label %inner_loop
  50
  51 inner_loop:                                   ; preds = %inner_loop, %loop_header.split.us
  52   %inner_iv = phi i32 [ 1, %loop_header.split.us ], [ %inner_iv_next, %inner_loop ]
  53   %inner_iv_next = add nuw nsw i32 %inner_iv, 1
  54   %inner_cond = icmp ult i32 %inner_iv_next, 31
  55   br i1 %inner_cond, label %inner_loop, label %range_check_block
  56
  57 exit:                                            ; preds = %loop_latch, %loop_header
  58   ret void
  59
  60 range_check_block:                                          ; preds = %inner_loop
  61   %range_check = icmp slt i32 %iv, 331
  62   br i1 %range_check, label %loop_latch, label %deopt
  63
  64 loop_latch:                                         ; preds = %range_check_block
  65   %iv_next = add i32 %iv, 1
  66   %loop_cond = icmp ult i32 %iv_next, 400
  67   br i1 %loop_cond, label %loop_header, label %exit
  68
  69 deopt:                                          ; preds = %range_check_block
  70   ret void
  71 }
  72
  73 ; Similar to test_01, but here the range check is done against 450. No postloop
  74 ; is required.
  75
  76 define void @test_02() {
  77
  78 ; CHECK-LABEL: test_02
  79 ; CHECK-NOT:     preloop
  80 ; CHECK-NOT:     postloop
  81 ; CHECK:         range_check_block:                                ; preds = %inner_loop
  82 ; CHECK-NEXT:      %range_check = icmp slt i32 %iv, 450
  83 ; CHECK-NEXT:      br i1 true, label %loop_latch
  84 ; CHECK:         loop_latch:                                       ; preds = %range_check_block
  85 ; CHECK-NEXT:      %iv_next = add i32 %iv, 1
  86 ; CHECK-NEXT:      %loop_cond = icmp ult i32 %iv_next, 400
  87 ; CHECK-NEXT:      br i1 %loop_cond, label %loop_header, label %exit
  88
  89 entry:
  90   br label %loop_header
  91
  92 loop_header:                            ; preds = %loop_latch, %entry
  93   %iv = phi i32 [ 2, %entry ], [ %iv_next, %loop_latch ]
  94   %iv.prev = phi i32 [ 1, %entry ], [ %iv, %loop_latch ]
  95   %tmp2 = icmp sgt i32 %iv.prev, -1
  96   br i1 %tmp2, label %loop_header.split.us, label %exit
  97
  98 loop_header.split.us:                   ; preds = %loop_header
  99   br label %inner_loop
 100
 101 inner_loop:                                   ; preds = %inner_loop, %loop_header.split.us
 102   %inner_iv = phi i32 [ 1, %loop_header.split.us ], [ %inner_iv_next, %inner_loop ]
 103   %inner_iv_next = add nuw nsw i32 %inner_iv, 1
 104   %inner_cond = icmp ult i32 %inner_iv_next, 31
 105   br i1 %inner_cond, label %inner_loop, label %range_check_block
 106
 107 exit:                                            ; preds = %loop_latch, %loop_header
 108   ret void
 109
 110 range_check_block:                                          ; preds = %inner_loop
 111   %range_check = icmp slt i32 %iv, 450
 112   br i1 %range_check, label %loop_latch, label %deopt
 113
 114 loop_latch:                                         ; preds = %range_check_block
 115   %iv_next = add i32 %iv, 1
 116   %loop_cond = icmp ult i32 %iv_next, 400
 117   br i1 %loop_cond, label %loop_header, label %exit
 118
 119 deopt:                                          ; preds = %range_check_block
 120   ret void
 121 }
 122
 123 ; Range check is made against 0, so the safe iteration range is empty. IRCE
 124 ; should not apply to the inner loop. The condition %tmp2 can be eliminated.
 125
 126 define void @test_03() {
 127
 128 ; CHECK-LABEL: test_03
 129 ; CHECK-NOT:   preloop
 130 ; CHECK-NOT:   postloop
 131 ; CHECK:         %tmp2 = icmp sgt i32 %iv.prev, -1
 132 ; CHECK-NEXT:    br i1 true, label %loop_header.split.us, label %exit
 133 ; CHECK:       range_check_block:
 134 ; CHECK-NEXT:    %range_check = icmp slt i32 %iv, 0
 135 ; CHECK-NEXT:    br i1 %range_check, label %loop_latch, label %deopt
 136
 137 entry:
 138   br label %loop_header
 139
 140 loop_header:                            ; preds = %loop_latch, %entry
 141   %iv = phi i32 [ 2, %entry ], [ %iv_next, %loop_latch ]
 142   %iv.prev = phi i32 [ 1, %entry ], [ %iv, %loop_latch ]
 143   %tmp2 = icmp sgt i32 %iv.prev, -1
 144   br i1 %tmp2, label %loop_header.split.us, label %exit
 145
 146 loop_header.split.us:                   ; preds = %loop_header
 147   br label %inner_loop
 148
 149 inner_loop:                                   ; preds = %inner_loop, %loop_header.split.us
 150   %inner_iv = phi i32 [ 1, %loop_header.split.us ], [ %inner_iv_next, %inner_loop ]
 151   %inner_iv_next = add nuw nsw i32 %inner_iv, 1
 152   %inner_cond = icmp ult i32 %inner_iv_next, 31
 153   br i1 %inner_cond, label %inner_loop, label %range_check_block
 154
 155 exit:                                            ; preds = %loop_latch, %loop_header
 156   ret void
 157
 158 range_check_block:                                          ; preds = %inner_loop
 159   %range_check = icmp slt i32 %iv, 0
 160   br i1 %range_check, label %loop_latch, label %deopt
 161
 162 loop_latch:                                         ; preds = %range_check_block
 163   %iv_next = add i32 %iv, 1
 164   %loop_cond = icmp ult i32 %iv_next, 400
 165   br i1 %loop_cond, label %loop_header, label %exit
 166
 167 deopt:                                          ; preds = %range_check_block
 168   ret void
 169 }
 170
 171 ; We can also properly eliminate range check against %n which is not always
 172 ; known positive.
 173
 174 define void @test_04(i32* %p) {
 175
 176 ; CHECK-LABEL: test_04
 177 ; CHECK:       entry
 178 ; CHECK-NOT:   preloop
 179 ; CHECK:         %tmp2 = icmp sgt i32 %iv.prev, -1
 180 ; CHECK-NEXT:    br i1 true, label %loop_header.split.us, label %exit
 181 ; CHECK:       range_check_block:
 182 ; CHECK-NEXT:    %range_check = icmp slt i32 %iv, %n
 183 ; CHECK-NEXT:    br i1 true, label %loop_latch, label %deopt
 184 ; CHECK:       postloop:
 185
 186 entry:
 187   %n = load i32, i32* %p
 188   br label %loop_header
 189
 190 loop_header:                            ; preds = %loop_latch, %entry
 191   %iv = phi i32 [ 2, %entry ], [ %iv_next, %loop_latch ]
 192   %iv.prev = phi i32 [ 1, %entry ], [ %iv, %loop_latch ]
 193   %tmp2 = icmp sgt i32 %iv.prev, -1
 194   br i1 %tmp2, label %loop_header.split.us, label %exit
 195
 196 loop_header.split.us:                   ; preds = %loop_header
 197   br label %inner_loop
 198
 199 inner_loop:                                   ; preds = %inner_loop, %loop_header.split.us
 200   %inner_iv = phi i32 [ 1, %loop_header.split.us ], [ %inner_iv_next, %inner_loop ]
 201   %inner_iv_next = add nuw nsw i32 %inner_iv, 1
 202   %inner_cond = icmp ult i32 %inner_iv_next, 31
 203   br i1 %inner_cond, label %inner_loop, label %range_check_block
 204
 205 exit:                                            ; preds = %loop_latch, %loop_header
 206   ret void
 207
 208 range_check_block:                                          ; preds = %inner_loop
 209   %range_check = icmp slt i32 %iv, %n
 210   br i1 %range_check, label %loop_latch, label %deopt
 211
 212 loop_latch:                                         ; preds = %range_check_block
 213   %iv_next = add i32 %iv, 1
 214   %loop_cond = icmp ult i32 %iv_next, 400
 215   br i1 %loop_cond, label %loop_header, label %exit
 216
 217 deopt:                                          ; preds = %range_check_block
 218   ret void
 219 }
 220
 221 ; Same as test_04, but range guarantees that %n is positive. So we can safely
 222 ; intersect ranges (with insertion of postloop).
 223
 224 define void @test_05(i32* %p) {
 225
 226 ; CHECK-LABEL: test_05
 227 ; CHECK-NOT:     preloop
 228 ; CHECK:         entry:
 229 ; CHECK-NEXT:      %n = load i32, i32* %p, !range !
 230 ; CHECK-NEXT:      [[CMP_1:%[^ ]+]] = icmp ugt i32 %n, 2
 231 ; CHECK-NEXT:      %exit.mainloop.at = select i1 [[CMP_1]], i32 %n, i32 2
 232 ; CHECK-NEXT:      [[CMP_2:%[^ ]+]] = icmp ult i32 2, %exit.mainloop.at
 233 ; CHECK-NEXT:      br i1 [[CMP_2]], label %loop_header.preheader, label %main.pseudo.exit
 234 ; CHECK:         range_check_block:                                ; preds = %inner_loop
 235 ; CHECK-NEXT:      %range_check = icmp slt i32 %iv, %n
 236 ; CHECK-NEXT:      br i1 true, label %loop_latch, label %deopt.loopexit2
 237 ; CHECK:         loop_latch:                                       ; preds = %range_check_block
 238 ; CHECK-NEXT:      %iv_next = add i32 %iv, 1
 239 ; CHECK-NEXT:      %loop_cond = icmp ult i32 %iv_next, 400
 240 ; CHECK-NEXT:      [[COND:%[^ ]+]] = icmp ult i32 %iv_next, %exit.mainloop.at
 241 ; CHECK-NEXT:      br i1 [[COND]], label %loop_header, label %main.exit.selector
 242 ; CHECK:         main.exit.selector:                               ; preds = %loop_latch
 243 ; CHECK-NEXT:      %iv_next.lcssa = phi i32 [ %iv_next, %loop_latch ]
 244 ; CHECK-NEXT:      %iv.lcssa = phi i32 [ %iv, %loop_latch ]
 245 ; CHECK-NEXT:      [[MES_COND:%[^ ]+]] = icmp ult i32 %iv_next.lcssa, 400
 246 ; CHECK-NEXT:      br i1 [[MES_COND]], label %main.pseudo.exit, label %exit
 247 ; CHECK:         loop_latch.postloop:                              ; preds = %range_check_block.postloop
 248 ; CHECK-NEXT:      %iv_next.postloop = add i32 %iv.postloop, 1
 249 ; CHECK-NEXT:      %loop_cond.postloop = icmp ult i32 %iv_next.postloop, 400
 250 ; CHECK-NEXT:      br i1 %loop_cond.postloop, label %loop_header.postloop, label %exit.loopexit
 251
 252 entry:
 253   %n = load i32, i32* %p, !range !0
 254   br label %loop_header
 255
 256 loop_header:                            ; preds = %loop_latch, %entry
 257   %iv = phi i32 [ 2, %entry ], [ %iv_next, %loop_latch ]
 258   %iv.prev = phi i32 [ 1, %entry ], [ %iv, %loop_latch ]
 259   %tmp2 = icmp sgt i32 %iv.prev, -1
 260   br i1 %tmp2, label %loop_header.split.us, label %exit
 261
 262 loop_header.split.us:                   ; preds = %loop_header
 263   br label %inner_loop
 264
 265 inner_loop:                                   ; preds = %inner_loop, %loop_header.split.us
 266   %inner_iv = phi i32 [ 1, %loop_header.split.us ], [ %inner_iv_next, %inner_loop ]
 267   %inner_iv_next = add nuw nsw i32 %inner_iv, 1
 268   %inner_cond = icmp ult i32 %inner_iv_next, 31
 269   br i1 %inner_cond, label %inner_loop, label %range_check_block
 270
 271 exit:                                            ; preds = %loop_latch, %loop_header
 272   ret void
 273
 274 range_check_block:                                          ; preds = %inner_loop
 275   %range_check = icmp slt i32 %iv, %n
 276   br i1 %range_check, label %loop_latch, label %deopt
 277
 278 loop_latch:                                         ; preds = %range_check_block
 279   %iv_next = add i32 %iv, 1
 280   %loop_cond = icmp ult i32 %iv_next, 400
 281   br i1 %loop_cond, label %loop_header, label %exit
 282
 283 deopt:                                          ; preds = %range_check_block
 284   ret void
 285 }
 286
 287 !0 = !{i32 0, i32 50}