llvm/test/Transforms/CorrelatedValuePropagation/sdiv.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt < %s -passes=correlated-propagation -S | FileCheck %s
   3
   4 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
   5
   6 define void @test0(i32 %n) {
   7 ; CHECK-LABEL: @test0(
   8 ; CHECK-NEXT:  entry:
   9 ; CHECK-NEXT:    br label [[FOR_COND:%.*]]
  10 ; CHECK:       for.cond:
  11 ; CHECK-NEXT:    [[J_0:%.*]] = phi i32 [ [[N:%.*]], [[ENTRY:%.*]] ], [ [[DIV1:%.*]], [[FOR_BODY:%.*]] ]
  12 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[J_0]], 1
  13 ; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY]], label [[FOR_END:%.*]]
  14 ; CHECK:       for.body:
  15 ; CHECK-NEXT:    [[DIV1]] = udiv i32 [[J_0]], 2
  16 ; CHECK-NEXT:    br label [[FOR_COND]]
  17 ; CHECK:       for.end:
  18 ; CHECK-NEXT:    ret void
  19 ;
  20 entry:
  21   br label %for.cond
  22
  23 for.cond:                                         ; preds = %for.body, %entry
  24   %j.0 = phi i32 [ %n, %entry ], [ %div, %for.body ]
  25   %cmp = icmp sgt i32 %j.0, 1
  26   br i1 %cmp, label %for.body, label %for.end
  27
  28 for.body:                                         ; preds = %for.cond
  29   %div = sdiv i32 %j.0, 2
  30   br label %for.cond
  31
  32 for.end:                                          ; preds = %for.cond
  33   ret void
  34 }
  35
  36 define void @test1(i32 %n) {
  37 ; CHECK-LABEL: @test1(
  38 ; CHECK-NEXT:  entry:
  39 ; CHECK-NEXT:    br label [[FOR_COND:%.*]]
  40 ; CHECK:       for.cond:
  41 ; CHECK-NEXT:    [[J_0:%.*]] = phi i32 [ [[N:%.*]], [[ENTRY:%.*]] ], [ [[DIV:%.*]], [[FOR_BODY:%.*]] ]
  42 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[J_0]], -2
  43 ; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY]], label [[FOR_END:%.*]]
  44 ; CHECK:       for.body:
  45 ; CHECK-NEXT:    [[DIV]] = sdiv i32 [[J_0]], 2
  46 ; CHECK-NEXT:    br label [[FOR_COND]]
  47 ; CHECK:       for.end:
  48 ; CHECK-NEXT:    ret void
  49 ;
  50 entry:
  51   br label %for.cond
  52
  53 for.cond:                                         ; preds = %for.body, %entry
  54   %j.0 = phi i32 [ %n, %entry ], [ %div, %for.body ]
  55   %cmp = icmp sgt i32 %j.0, -2
  56   br i1 %cmp, label %for.body, label %for.end
  57
  58 for.body:                                         ; preds = %for.cond
  59   %div = sdiv i32 %j.0, 2
  60   br label %for.cond
  61
  62 for.end:                                          ; preds = %for.cond
  63   ret void
  64 }
  65
  66 define void @test2(i32 %n) {
  67 ; CHECK-LABEL: @test2(
  68 ; CHECK-NEXT:  entry:
  69 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[N:%.*]], 1
  70 ; CHECK-NEXT:    br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]]
  71 ; CHECK:       bb:
  72 ; CHECK-NEXT:    [[DIV1:%.*]] = udiv i32 [[N]], 2
  73 ; CHECK-NEXT:    br label [[EXIT]]
  74 ; CHECK:       exit:
  75 ; CHECK-NEXT:    ret void
  76 ;
  77 entry:
  78   %cmp = icmp sgt i32 %n, 1
  79   br i1 %cmp, label %bb, label %exit
  80
  81 bb:
  82   %div = sdiv i32 %n, 2
  83   br label %exit
  84
  85 exit:
  86   ret void
  87 }
  88
  89 ; looping case where loop has exactly one block
  90 ; at the point of sdiv, we know that %a is always greater than 0,
  91 ; because of the guard before it, so we can transform it to udiv.
  92 declare void @llvm.experimental.guard(i1,...)
  93 define void @test4(i32 %n) {
  94 ; CHECK-LABEL: @test4(
  95 ; CHECK-NEXT:  entry:
  96 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[N:%.*]], 0
  97 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP:%.*]], label [[EXIT:%.*]]
  98 ; CHECK:       loop:
  99 ; CHECK-NEXT:    [[A:%.*]] = phi i32 [ [[N]], [[ENTRY:%.*]] ], [ [[DIV1:%.*]], [[LOOP]] ]
 100 ; CHECK-NEXT:    [[COND:%.*]] = icmp sgt i32 [[A]], 4
 101 ; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[COND]]) [ "deopt"() ]
 102 ; CHECK-NEXT:    [[DIV1]] = udiv i32 [[A]], 6
 103 ; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[EXIT]]
 104 ; CHECK:       exit:
 105 ; CHECK-NEXT:    ret void
 106 ;
 107 entry:
 108   %cmp = icmp sgt i32 %n, 0
 109   br i1 %cmp, label %loop, label %exit
 110
 111 loop:
 112   %a = phi i32 [ %n, %entry ], [ %div, %loop ]
 113   %cond = icmp sgt i32 %a, 4
 114   call void(i1,...) @llvm.experimental.guard(i1 %cond) [ "deopt"() ]
 115   %div = sdiv i32 %a, 6
 116   br i1 %cond, label %loop, label %exit
 117
 118 exit:
 119   ret void
 120 }
 121
 122 ; same test as above with assume instead of guard.
 123 declare void @llvm.assume(i1)
 124 define void @test5(i32 %n) {
 125 ; CHECK-LABEL: @test5(
 126 ; CHECK-NEXT:  entry:
 127 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[N:%.*]], 0
 128 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP:%.*]], label [[EXIT:%.*]]
 129 ; CHECK:       loop:
 130 ; CHECK-NEXT:    [[A:%.*]] = phi i32 [ [[N]], [[ENTRY:%.*]] ], [ [[DIV1:%.*]], [[LOOP]] ]
 131 ; CHECK-NEXT:    [[COND:%.*]] = icmp samesign ugt i32 [[A]], 4
 132 ; CHECK-NEXT:    call void @llvm.assume(i1 [[COND]])
 133 ; CHECK-NEXT:    [[DIV1]] = udiv i32 [[A]], 6
 134 ; CHECK-NEXT:    [[LOOPCOND:%.*]] = icmp samesign ugt i32 [[DIV1]], 8
 135 ; CHECK-NEXT:    br i1 [[LOOPCOND]], label [[LOOP]], label [[EXIT]]
 136 ; CHECK:       exit:
 137 ; CHECK-NEXT:    ret void
 138 ;
 139 entry:
 140   %cmp = icmp sgt i32 %n, 0
 141   br i1 %cmp, label %loop, label %exit
 142
 143 loop:
 144   %a = phi i32 [ %n, %entry ], [ %div, %loop ]
 145   %cond = icmp sgt i32 %a, 4
 146   call void @llvm.assume(i1 %cond)
 147   %div = sdiv i32 %a, 6
 148   %loopcond = icmp sgt i32 %div, 8
 149   br i1 %loopcond, label %loop, label %exit
 150
 151 exit:
 152   ret void
 153 }
 154
 155 ; Now, let's try various domain combinations for operands.
 156
 157 define i32 @test6_pos_pos(i32 %x, i32 %y) {
 158 ; CHECK-LABEL: @test6_pos_pos(
 159 ; CHECK-NEXT:    [[C0:%.*]] = icmp sge i32 [[X:%.*]], 0
 160 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C0]])
 161 ; CHECK-NEXT:    [[C1:%.*]] = icmp sge i32 [[Y:%.*]], 0
 162 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C1]])
 163 ; CHECK-NEXT:    [[DIV1:%.*]] = udiv i32 [[X]], [[Y]]
 164 ; CHECK-NEXT:    ret i32 [[DIV1]]
 165 ;
 166   %c0 = icmp sge i32 %x, 0
 167   call void @llvm.assume(i1 %c0)
 168   %c1 = icmp sge i32 %y, 0
 169   call void @llvm.assume(i1 %c1)
 170
 171   %div = sdiv i32 %x, %y
 172   ret i32 %div
 173 }
 174 define i32 @test7_pos_neg(i32 %x, i32 %y) {
 175 ; CHECK-LABEL: @test7_pos_neg(
 176 ; CHECK-NEXT:    [[C0:%.*]] = icmp sge i32 [[X:%.*]], 0
 177 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C0]])
 178 ; CHECK-NEXT:    [[C1:%.*]] = icmp sle i32 [[Y:%.*]], 0
 179 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C1]])
 180 ; CHECK-NEXT:    [[Y_NONNEG:%.*]] = sub i32 0, [[Y]]
 181 ; CHECK-NEXT:    [[DIV1:%.*]] = udiv i32 [[X]], [[Y_NONNEG]]
 182 ; CHECK-NEXT:    [[DIV1_NEG:%.*]] = sub i32 0, [[DIV1]]
 183 ; CHECK-NEXT:    ret i32 [[DIV1_NEG]]
 184 ;
 185   %c0 = icmp sge i32 %x, 0
 186   call void @llvm.assume(i1 %c0)
 187   %c1 = icmp sle i32 %y, 0
 188   call void @llvm.assume(i1 %c1)
 189
 190   %div = sdiv i32 %x, %y
 191   ret i32 %div
 192 }
 193 define i32 @test8_neg_pos(i32 %x, i32 %y) {
 194 ; CHECK-LABEL: @test8_neg_pos(
 195 ; CHECK-NEXT:    [[C0:%.*]] = icmp sle i32 [[X:%.*]], 0
 196 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C0]])
 197 ; CHECK-NEXT:    [[C1:%.*]] = icmp sge i32 [[Y:%.*]], 0
 198 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C1]])
 199 ; CHECK-NEXT:    [[X_NONNEG:%.*]] = sub i32 0, [[X]]
 200 ; CHECK-NEXT:    [[DIV1:%.*]] = udiv i32 [[X_NONNEG]], [[Y]]
 201 ; CHECK-NEXT:    [[DIV1_NEG:%.*]] = sub i32 0, [[DIV1]]
 202 ; CHECK-NEXT:    ret i32 [[DIV1_NEG]]
 203 ;
 204   %c0 = icmp sle i32 %x, 0
 205   call void @llvm.assume(i1 %c0)
 206   %c1 = icmp sge i32 %y, 0
 207   call void @llvm.assume(i1 %c1)
 208
 209   %div = sdiv i32 %x, %y
 210   ret i32 %div
 211 }
 212 define i32 @test9_neg_neg(i32 %x, i32 %y) {
 213 ; CHECK-LABEL: @test9_neg_neg(
 214 ; CHECK-NEXT:    [[C0:%.*]] = icmp sle i32 [[X:%.*]], 0
 215 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C0]])
 216 ; CHECK-NEXT:    [[C1:%.*]] = icmp sle i32 [[Y:%.*]], 0
 217 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C1]])
 218 ; CHECK-NEXT:    [[X_NONNEG:%.*]] = sub i32 0, [[X]]
 219 ; CHECK-NEXT:    [[Y_NONNEG:%.*]] = sub i32 0, [[Y]]
 220 ; CHECK-NEXT:    [[DIV1:%.*]] = udiv i32 [[X_NONNEG]], [[Y_NONNEG]]
 221 ; CHECK-NEXT:    ret i32 [[DIV1]]
 222 ;
 223   %c0 = icmp sle i32 %x, 0
 224   call void @llvm.assume(i1 %c0)
 225   %c1 = icmp sle i32 %y, 0
 226   call void @llvm.assume(i1 %c1)
 227
 228   %div = sdiv i32 %x, %y
 229   ret i32 %div
 230 }
 231
 232 ; After making division unsigned, can we narrow it?
 233 define i32 @test10_narrow(i32 %x, i32 %y) {
 234 ; CHECK-LABEL: @test10_narrow(
 235 ; CHECK-NEXT:    [[C0:%.*]] = icmp ult i32 [[X:%.*]], 128
 236 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C0]])
 237 ; CHECK-NEXT:    [[C1:%.*]] = icmp ult i32 [[Y:%.*]], 128
 238 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C1]])
 239 ; CHECK-NEXT:    [[DIV1_LHS_TRUNC:%.*]] = trunc i32 [[X]] to i8
 240 ; CHECK-NEXT:    [[DIV1_RHS_TRUNC:%.*]] = trunc i32 [[Y]] to i8
 241 ; CHECK-NEXT:    [[DIV12:%.*]] = udiv i8 [[DIV1_LHS_TRUNC]], [[DIV1_RHS_TRUNC]]
 242 ; CHECK-NEXT:    [[DIV1_ZEXT:%.*]] = zext i8 [[DIV12]] to i32
 243 ; CHECK-NEXT:    ret i32 [[DIV1_ZEXT]]
 244 ;
 245   %c0 = icmp ult i32 %x, 128
 246   call void @llvm.assume(i1 %c0)
 247   %c1 = icmp ult i32 %y, 128
 248   call void @llvm.assume(i1 %c1)
 249
 250   %div = sdiv i32 %x, %y
 251   ret i32 %div
 252 }
 253
 254 ; Ok, but what about narrowing sdiv in general?
 255
 256 ; If both operands are i15, it's uncontroversial - we can truncate to i16
 257 define i64 @test11_i15_i15(i64 %x, i64 %y) {
 258 ; CHECK-LABEL: @test11_i15_i15(
 259 ; CHECK-NEXT:  entry:
 260 ; CHECK-NEXT:    [[C0:%.*]] = icmp sle i64 [[X:%.*]], 16383
 261 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C0]])
 262 ; CHECK-NEXT:    [[C1:%.*]] = icmp sge i64 [[X]], -16384
 263 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C1]])
 264 ; CHECK-NEXT:    [[C2:%.*]] = icmp sle i64 [[Y:%.*]], 16383
 265 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C2]])
 266 ; CHECK-NEXT:    [[C3:%.*]] = icmp sge i64 [[Y]], -16384
 267 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C3]])
 268 ; CHECK-NEXT:    [[DIV_LHS_TRUNC:%.*]] = trunc i64 [[X]] to i16
 269 ; CHECK-NEXT:    [[DIV_RHS_TRUNC:%.*]] = trunc i64 [[Y]] to i16
 270 ; CHECK-NEXT:    [[DIV1:%.*]] = sdiv i16 [[DIV_LHS_TRUNC]], [[DIV_RHS_TRUNC]]
 271 ; CHECK-NEXT:    [[DIV_SEXT:%.*]] = sext i16 [[DIV1]] to i64
 272 ; CHECK-NEXT:    ret i64 [[DIV_SEXT]]
 273 ;
 274 entry:
 275   %c0 = icmp sle i64 %x, 16383
 276   call void @llvm.assume(i1 %c0)
 277   %c1 = icmp sge i64 %x, -16384
 278   call void @llvm.assume(i1 %c1)
 279
 280   %c2 = icmp sle i64 %y, 16383
 281   call void @llvm.assume(i1 %c2)
 282   %c3 = icmp sge i64 %y, -16384
 283   call void @llvm.assume(i1 %c3)
 284
 285   %div = sdiv i64 %x, %y
 286   ret i64 %div
 287 }
 288
 289 ; But if operands are i16, we can only truncate to i32, because we can't
 290 ; rule out UB of  i16 INT_MIN s/ i16 -1
 291 define i64 @test12_i16_i16(i64 %x, i64 %y) {
 292 ; CHECK-LABEL: @test12_i16_i16(
 293 ; CHECK-NEXT:  entry:
 294 ; CHECK-NEXT:    [[C0:%.*]] = icmp sle i64 [[X:%.*]], 32767
 295 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C0]])
 296 ; CHECK-NEXT:    [[C1:%.*]] = icmp sge i64 [[X]], -32768
 297 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C1]])
 298 ; CHECK-NEXT:    [[C2:%.*]] = icmp sle i64 [[Y:%.*]], 32767
 299 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C2]])
 300 ; CHECK-NEXT:    [[C3:%.*]] = icmp sge i64 [[Y]], -32768
 301 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C3]])
 302 ; CHECK-NEXT:    [[DIV_LHS_TRUNC:%.*]] = trunc i64 [[X]] to i32
 303 ; CHECK-NEXT:    [[DIV_RHS_TRUNC:%.*]] = trunc i64 [[Y]] to i32
 304 ; CHECK-NEXT:    [[DIV1:%.*]] = sdiv i32 [[DIV_LHS_TRUNC]], [[DIV_RHS_TRUNC]]
 305 ; CHECK-NEXT:    [[DIV_SEXT:%.*]] = sext i32 [[DIV1]] to i64
 306 ; CHECK-NEXT:    ret i64 [[DIV_SEXT]]
 307 ;
 308 entry:
 309   %c0 = icmp sle i64 %x, 32767
 310   call void @llvm.assume(i1 %c0)
 311   %c1 = icmp sge i64 %x, -32768
 312   call void @llvm.assume(i1 %c1)
 313
 314   %c2 = icmp sle i64 %y, 32767
 315   call void @llvm.assume(i1 %c2)
 316   %c3 = icmp sge i64 %y, -32768
 317   call void @llvm.assume(i1 %c3)
 318
 319   %div = sdiv i64 %x, %y
 320   ret i64 %div
 321 }
 322
 323 ; But if divident is i16, and divisor is u15, then we know that i16 is UB-safe.
 324 define i64 @test13_i16_u15(i64 %x, i64 %y) {
 325 ; CHECK-LABEL: @test13_i16_u15(
 326 ; CHECK-NEXT:  entry:
 327 ; CHECK-NEXT:    [[C0:%.*]] = icmp sle i64 [[X:%.*]], 32767
 328 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C0]])
 329 ; CHECK-NEXT:    [[C1:%.*]] = icmp sge i64 [[X]], -32768
 330 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C1]])
 331 ; CHECK-NEXT:    [[C2:%.*]] = icmp ule i64 [[Y:%.*]], 32767
 332 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C2]])
 333 ; CHECK-NEXT:    [[DIV_LHS_TRUNC:%.*]] = trunc i64 [[X]] to i16
 334 ; CHECK-NEXT:    [[DIV_RHS_TRUNC:%.*]] = trunc i64 [[Y]] to i16
 335 ; CHECK-NEXT:    [[DIV1:%.*]] = sdiv i16 [[DIV_LHS_TRUNC]], [[DIV_RHS_TRUNC]]
 336 ; CHECK-NEXT:    [[DIV_SEXT:%.*]] = sext i16 [[DIV1]] to i64
 337 ; CHECK-NEXT:    ret i64 [[DIV_SEXT]]
 338 ;
 339 entry:
 340   %c0 = icmp sle i64 %x, 32767
 341   call void @llvm.assume(i1 %c0)
 342   %c1 = icmp sge i64 %x, -32768
 343   call void @llvm.assume(i1 %c1)
 344
 345   %c2 = icmp ule i64 %y, 32767
 346   call void @llvm.assume(i1 %c2)
 347
 348   %div = sdiv i64 %x, %y
 349   ret i64 %div
 350 }
 351
 352 ; And likewise, if we know that if the divident is never i16 INT_MIN,
 353 ; we can truncate to i16.
 354 define i64 @test14_i16safe_i16(i64 %x, i64 %y) {
 355 ; CHECK-LABEL: @test14_i16safe_i16(
 356 ; CHECK-NEXT:  entry:
 357 ; CHECK-NEXT:    [[C0:%.*]] = icmp sle i64 [[X:%.*]], 32767
 358 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C0]])
 359 ; CHECK-NEXT:    [[C1:%.*]] = icmp sgt i64 [[X]], -32768
 360 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C1]])
 361 ; CHECK-NEXT:    [[C2:%.*]] = icmp sle i64 [[Y:%.*]], 32767
 362 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C2]])
 363 ; CHECK-NEXT:    [[C3:%.*]] = icmp sge i64 [[Y]], -32768
 364 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C3]])
 365 ; CHECK-NEXT:    [[DIV_LHS_TRUNC:%.*]] = trunc i64 [[X]] to i16
 366 ; CHECK-NEXT:    [[DIV_RHS_TRUNC:%.*]] = trunc i64 [[Y]] to i16
 367 ; CHECK-NEXT:    [[DIV1:%.*]] = sdiv i16 [[DIV_LHS_TRUNC]], [[DIV_RHS_TRUNC]]
 368 ; CHECK-NEXT:    [[DIV_SEXT:%.*]] = sext i16 [[DIV1]] to i64
 369 ; CHECK-NEXT:    ret i64 [[DIV_SEXT]]
 370 ;
 371 entry:
 372   %c0 = icmp sle i64 %x, 32767
 373   call void @llvm.assume(i1 %c0)
 374   %c1 = icmp sgt i64 %x, -32768
 375   call void @llvm.assume(i1 %c1)
 376
 377   %c2 = icmp sle i64 %y, 32767
 378   call void @llvm.assume(i1 %c2)
 379   %c3 = icmp sge i64 %y, -32768
 380   call void @llvm.assume(i1 %c3)
 381
 382   %div = sdiv i64 %x, %y
 383   ret i64 %div
 384 }
 385
 386 ; Of course, both of the conditions can happen at once.
 387 define i64 @test15_i16safe_u15(i64 %x, i64 %y) {
 388 ; CHECK-LABEL: @test15_i16safe_u15(
 389 ; CHECK-NEXT:  entry:
 390 ; CHECK-NEXT:    [[C0:%.*]] = icmp sle i64 [[X:%.*]], 32767
 391 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C0]])
 392 ; CHECK-NEXT:    [[C1:%.*]] = icmp sgt i64 [[X]], -32768
 393 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C1]])
 394 ; CHECK-NEXT:    [[C2:%.*]] = icmp ule i64 [[Y:%.*]], 32767
 395 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C2]])
 396 ; CHECK-NEXT:    [[DIV_LHS_TRUNC:%.*]] = trunc i64 [[X]] to i16
 397 ; CHECK-NEXT:    [[DIV_RHS_TRUNC:%.*]] = trunc i64 [[Y]] to i16
 398 ; CHECK-NEXT:    [[DIV1:%.*]] = sdiv i16 [[DIV_LHS_TRUNC]], [[DIV_RHS_TRUNC]]
 399 ; CHECK-NEXT:    [[DIV_SEXT:%.*]] = sext i16 [[DIV1]] to i64
 400 ; CHECK-NEXT:    ret i64 [[DIV_SEXT]]
 401 ;
 402 entry:
 403   %c0 = icmp sle i64 %x, 32767
 404   call void @llvm.assume(i1 %c0)
 405   %c1 = icmp sgt i64 %x, -32768
 406   call void @llvm.assume(i1 %c1)
 407
 408   %c2 = icmp ule i64 %y, 32767
 409   call void @llvm.assume(i1 %c2)
 410
 411   %div = sdiv i64 %x, %y
 412   ret i64 %div
 413 }
 414
 415 ; We at most truncate to i8
 416 define i64 @test16_i4_i4(i64 %x, i64 %y) {
 417 ; CHECK-LABEL: @test16_i4_i4(
 418 ; CHECK-NEXT:  entry:
 419 ; CHECK-NEXT:    [[C0:%.*]] = icmp sle i64 [[X:%.*]], 3
 420 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C0]])
 421 ; CHECK-NEXT:    [[C1:%.*]] = icmp sge i64 [[X]], -4
 422 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C1]])
 423 ; CHECK-NEXT:    [[C2:%.*]] = icmp sle i64 [[Y:%.*]], 3
 424 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C2]])
 425 ; CHECK-NEXT:    [[C3:%.*]] = icmp sge i64 [[Y]], -4
 426 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C3]])
 427 ; CHECK-NEXT:    [[DIV_LHS_TRUNC:%.*]] = trunc i64 [[X]] to i8
 428 ; CHECK-NEXT:    [[DIV_RHS_TRUNC:%.*]] = trunc i64 [[Y]] to i8
 429 ; CHECK-NEXT:    [[DIV1:%.*]] = sdiv i8 [[DIV_LHS_TRUNC]], [[DIV_RHS_TRUNC]]
 430 ; CHECK-NEXT:    [[DIV_SEXT:%.*]] = sext i8 [[DIV1]] to i64
 431 ; CHECK-NEXT:    ret i64 [[DIV_SEXT]]
 432 ;
 433 entry:
 434   %c0 = icmp sle i64 %x, 3
 435   call void @llvm.assume(i1 %c0)
 436   %c1 = icmp sge i64 %x, -4
 437   call void @llvm.assume(i1 %c1)
 438
 439   %c2 = icmp sle i64 %y, 3
 440   call void @llvm.assume(i1 %c2)
 441   %c3 = icmp sge i64 %y, -4
 442   call void @llvm.assume(i1 %c3)
 443
 444   %div = sdiv i64 %x, %y
 445   ret i64 %div
 446 }
 447
 448 ; And we round up to the powers of two
 449 define i64 @test17_i9_i9(i64 %x, i64 %y) {
 450 ; CHECK-LABEL: @test17_i9_i9(
 451 ; CHECK-NEXT:  entry:
 452 ; CHECK-NEXT:    [[C0:%.*]] = icmp sle i64 [[X:%.*]], 255
 453 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C0]])
 454 ; CHECK-NEXT:    [[C1:%.*]] = icmp sge i64 [[X]], -256
 455 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C1]])
 456 ; CHECK-NEXT:    [[C2:%.*]] = icmp sle i64 [[Y:%.*]], 255
 457 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C2]])
 458 ; CHECK-NEXT:    [[C3:%.*]] = icmp sge i64 [[Y]], -256
 459 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C3]])
 460 ; CHECK-NEXT:    [[DIV_LHS_TRUNC:%.*]] = trunc i64 [[X]] to i16
 461 ; CHECK-NEXT:    [[DIV_RHS_TRUNC:%.*]] = trunc i64 [[Y]] to i16
 462 ; CHECK-NEXT:    [[DIV1:%.*]] = sdiv i16 [[DIV_LHS_TRUNC]], [[DIV_RHS_TRUNC]]
 463 ; CHECK-NEXT:    [[DIV_SEXT:%.*]] = sext i16 [[DIV1]] to i64
 464 ; CHECK-NEXT:    ret i64 [[DIV_SEXT]]
 465 ;
 466 entry:
 467   %c0 = icmp sle i64 %x, 255
 468   call void @llvm.assume(i1 %c0)
 469   %c1 = icmp sge i64 %x, -256
 470   call void @llvm.assume(i1 %c1)
 471
 472   %c2 = icmp sle i64 %y, 255
 473   call void @llvm.assume(i1 %c2)
 474   %c3 = icmp sge i64 %y, -256
 475   call void @llvm.assume(i1 %c3)
 476
 477   %div = sdiv i64 %x, %y
 478   ret i64 %div
 479 }
 480
 481 ; Don't widen the operation to the next power of two if it wasn't a power of two.
 482 define i9 @test18_i9_i9(i9 %x, i9 %y) {
 483 ; CHECK-LABEL: @test18_i9_i9(
 484 ; CHECK-NEXT:  entry:
 485 ; CHECK-NEXT:    [[C0:%.*]] = icmp sle i9 [[X:%.*]], 255
 486 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C0]])
 487 ; CHECK-NEXT:    [[C1:%.*]] = icmp sge i9 [[X]], -256
 488 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C1]])
 489 ; CHECK-NEXT:    [[C2:%.*]] = icmp sle i9 [[Y:%.*]], 255
 490 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C2]])
 491 ; CHECK-NEXT:    [[C3:%.*]] = icmp sge i9 [[Y]], -256
 492 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C3]])
 493 ; CHECK-NEXT:    [[DIV:%.*]] = sdiv i9 [[X]], [[Y]]
 494 ; CHECK-NEXT:    ret i9 [[DIV]]
 495 ;
 496 entry:
 497   %c0 = icmp sle i9 %x, 255
 498   call void @llvm.assume(i1 %c0)
 499   %c1 = icmp sge i9 %x, -256
 500   call void @llvm.assume(i1 %c1)
 501
 502   %c2 = icmp sle i9 %y, 255
 503   call void @llvm.assume(i1 %c2)
 504   %c3 = icmp sge i9 %y, -256
 505   call void @llvm.assume(i1 %c3)
 506
 507   %div = sdiv i9 %x, %y
 508   ret i9 %div
 509 }
 510 define i10 @test19_i10_i10(i10 %x, i10 %y) {
 511 ; CHECK-LABEL: @test19_i10_i10(
 512 ; CHECK-NEXT:  entry:
 513 ; CHECK-NEXT:    [[C0:%.*]] = icmp sle i10 [[X:%.*]], 255
 514 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C0]])
 515 ; CHECK-NEXT:    [[C1:%.*]] = icmp sge i10 [[X]], -256
 516 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C1]])
 517 ; CHECK-NEXT:    [[C2:%.*]] = icmp sle i10 [[Y:%.*]], 255
 518 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C2]])
 519 ; CHECK-NEXT:    [[C3:%.*]] = icmp sge i10 [[Y]], -256
 520 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C3]])
 521 ; CHECK-NEXT:    [[DIV:%.*]] = sdiv i10 [[X]], [[Y]]
 522 ; CHECK-NEXT:    ret i10 [[DIV]]
 523 ;
 524 entry:
 525   %c0 = icmp sle i10 %x, 255
 526   call void @llvm.assume(i1 %c0)
 527   %c1 = icmp sge i10 %x, -256
 528   call void @llvm.assume(i1 %c1)
 529
 530   %c2 = icmp sle i10 %y, 255
 531   call void @llvm.assume(i1 %c2)
 532   %c3 = icmp sge i10 %y, -256
 533   call void @llvm.assume(i1 %c3)
 534
 535   %div = sdiv i10 %x, %y
 536   ret i10 %div
 537 }
 538
 539 ; Note that we need to take the maximal bitwidth, in which both of the operands are representable!
 540 define i64 @test20_i16_i18(i64 %x, i64 %y) {
 541 ; CHECK-LABEL: @test20_i16_i18(
 542 ; CHECK-NEXT:  entry:
 543 ; CHECK-NEXT:    [[C0:%.*]] = icmp sle i64 [[X:%.*]], 16383
 544 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C0]])
 545 ; CHECK-NEXT:    [[C1:%.*]] = icmp sge i64 [[X]], -16384
 546 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C1]])
 547 ; CHECK-NEXT:    [[C2:%.*]] = icmp sle i64 [[Y:%.*]], 65535
 548 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C2]])
 549 ; CHECK-NEXT:    [[C3:%.*]] = icmp sge i64 [[Y]], -65536
 550 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C3]])
 551 ; CHECK-NEXT:    [[DIV_LHS_TRUNC:%.*]] = trunc i64 [[X]] to i32
 552 ; CHECK-NEXT:    [[DIV_RHS_TRUNC:%.*]] = trunc i64 [[Y]] to i32
 553 ; CHECK-NEXT:    [[DIV1:%.*]] = sdiv i32 [[DIV_LHS_TRUNC]], [[DIV_RHS_TRUNC]]
 554 ; CHECK-NEXT:    [[DIV_SEXT:%.*]] = sext i32 [[DIV1]] to i64
 555 ; CHECK-NEXT:    ret i64 [[DIV_SEXT]]
 556 ;
 557 entry:
 558   %c0 = icmp sle i64 %x, 16383
 559   call void @llvm.assume(i1 %c0)
 560   %c1 = icmp sge i64 %x, -16384
 561   call void @llvm.assume(i1 %c1)
 562
 563   %c2 = icmp sle i64 %y, 65535
 564   call void @llvm.assume(i1 %c2)
 565   %c3 = icmp sge i64 %y, -65536
 566   call void @llvm.assume(i1 %c3)
 567
 568   %div = sdiv i64 %x, %y
 569   ret i64 %div
 570 }
 571 define i64 @test21_i18_i16(i64 %x, i64 %y) {
 572 ; CHECK-LABEL: @test21_i18_i16(
 573 ; CHECK-NEXT:  entry:
 574 ; CHECK-NEXT:    [[C0:%.*]] = icmp sle i64 [[X:%.*]], 65535
 575 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C0]])
 576 ; CHECK-NEXT:    [[C1:%.*]] = icmp sge i64 [[X]], -65536
 577 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C1]])
 578 ; CHECK-NEXT:    [[C2:%.*]] = icmp sle i64 [[Y:%.*]], 16383
 579 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C2]])
 580 ; CHECK-NEXT:    [[C3:%.*]] = icmp sge i64 [[Y]], -16384
 581 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C3]])
 582 ; CHECK-NEXT:    [[DIV_LHS_TRUNC:%.*]] = trunc i64 [[X]] to i32
 583 ; CHECK-NEXT:    [[DIV_RHS_TRUNC:%.*]] = trunc i64 [[Y]] to i32
 584 ; CHECK-NEXT:    [[DIV1:%.*]] = sdiv i32 [[DIV_LHS_TRUNC]], [[DIV_RHS_TRUNC]]
 585 ; CHECK-NEXT:    [[DIV_SEXT:%.*]] = sext i32 [[DIV1]] to i64
 586 ; CHECK-NEXT:    ret i64 [[DIV_SEXT]]
 587 ;
 588 entry:
 589   %c0 = icmp sle i64 %x, 65535
 590   call void @llvm.assume(i1 %c0)
 591   %c1 = icmp sge i64 %x, -65536
 592   call void @llvm.assume(i1 %c1)
 593
 594   %c2 = icmp sle i64 %y, 16383
 595   call void @llvm.assume(i1 %c2)
 596   %c3 = icmp sge i64 %y, -16384
 597   call void @llvm.assume(i1 %c3)
 598
 599   %div = sdiv i64 %x, %y
 600   ret i64 %div
 601 }
 602
 603 ; Ensure that we preserve exact-ness
 604 define i64 @test22_i16_i16(i64 %x, i64 %y) {
 605 ; CHECK-LABEL: @test22_i16_i16(
 606 ; CHECK-NEXT:  entry:
 607 ; CHECK-NEXT:    [[C0:%.*]] = icmp sle i64 [[X:%.*]], 32767
 608 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C0]])
 609 ; CHECK-NEXT:    [[C1:%.*]] = icmp sge i64 [[X]], -32768
 610 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C1]])
 611 ; CHECK-NEXT:    [[C2:%.*]] = icmp sle i64 [[Y:%.*]], 32767
 612 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C2]])
 613 ; CHECK-NEXT:    [[C3:%.*]] = icmp sge i64 [[Y]], -32768
 614 ; CHECK-NEXT:    call void @llvm.assume(i1 [[C3]])
 615 ; CHECK-NEXT:    [[DIV_LHS_TRUNC:%.*]] = trunc i64 [[X]] to i32
 616 ; CHECK-NEXT:    [[DIV_RHS_TRUNC:%.*]] = trunc i64 [[Y]] to i32
 617 ; CHECK-NEXT:    [[DIV1:%.*]] = sdiv exact i32 [[DIV_LHS_TRUNC]], [[DIV_RHS_TRUNC]]
 618 ; CHECK-NEXT:    [[DIV_SEXT:%.*]] = sext i32 [[DIV1]] to i64
 619 ; CHECK-NEXT:    ret i64 [[DIV_SEXT]]
 620 ;
 621 entry:
 622   %c0 = icmp sle i64 %x, 32767
 623   call void @llvm.assume(i1 %c0)
 624   %c1 = icmp sge i64 %x, -32768
 625   call void @llvm.assume(i1 %c1)
 626
 627   %c2 = icmp sle i64 %y, 32767
 628   call void @llvm.assume(i1 %c2)
 629   %c3 = icmp sge i64 %y, -32768
 630   call void @llvm.assume(i1 %c3)
 631
 632   %div = sdiv exact i64 %x, %y
 633   ret i64 %div
 634 }
 635
 636 define void @sdiv_zero(ptr %p, i32 %arg) {
 637 ; CHECK-LABEL: @sdiv_zero(
 638 ; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[ARG:%.*]], 5
 639 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[ADD]], 11
 640 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP]])
 641 ; CHECK-NEXT:    store i32 0, ptr [[P:%.*]], align 4
 642 ; CHECK-NEXT:    ret void
 643 ;
 644   %add = add i32 %arg, 5
 645   %cmp = icmp ult i32 %add, 11
 646   call void @llvm.assume(i1 %cmp)
 647   %div = sdiv i32 %arg, 6
 648   store i32 %div, ptr %p
 649   ret void
 650 }
 651
 652 define void @sdiv_not_zero(ptr %p, i32 %arg) {
 653 ; CHECK-LABEL: @sdiv_not_zero(
 654 ; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[ARG:%.*]], 5
 655 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[ADD]], 12
 656 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP]])
 657 ; CHECK-NEXT:    [[DIV_LHS_TRUNC:%.*]] = trunc i32 [[ARG]] to i8
 658 ; CHECK-NEXT:    [[DIV1:%.*]] = sdiv i8 [[DIV_LHS_TRUNC]], 6
 659 ; CHECK-NEXT:    [[DIV_SEXT:%.*]] = sext i8 [[DIV1]] to i32
 660 ; CHECK-NEXT:    store i32 [[DIV_SEXT]], ptr [[P:%.*]], align 4
 661 ; CHECK-NEXT:    ret void
 662 ;
 663   %add = add i32 %arg, 5
 664   %cmp = icmp ult i32 %add, 12
 665   call void @llvm.assume(i1 %cmp)
 666   %div = sdiv i32 %arg, 6
 667   store i32 %div, ptr %p
 668   ret void
 669 }
 670
 671 define void @sdiv_pos(ptr %p, i32 %arg) {
 672 ; CHECK-LABEL: @sdiv_pos(
 673 ; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[ARG:%.*]], -12
 674 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[ADD]], 6
 675 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP]])
 676 ; CHECK-NEXT:    store i32 2, ptr [[P:%.*]], align 4
 677 ; CHECK-NEXT:    ret void
 678 ;
 679   %add = add i32 %arg, -12
 680   %cmp = icmp ult i32 %add, 6
 681   call void @llvm.assume(i1 %cmp)
 682   %div = sdiv i32 %arg, 6
 683   store i32 %div, ptr %p
 684   ret void
 685 }
 686
 687 define void @sdiv_neg(ptr %p, i32 %arg) {
 688 ; CHECK-LABEL: @sdiv_neg(
 689 ; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[ARG:%.*]], 17
 690 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[ADD]], 6
 691 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP]])
 692 ; CHECK-NEXT:    store i32 -2, ptr [[P:%.*]], align 4
 693 ; CHECK-NEXT:    ret void
 694 ;
 695   %add = add i32 %arg, 17
 696   %cmp = icmp ult i32 %add, 6
 697   call void @llvm.assume(i1 %cmp)
 698   %div = sdiv i32 %arg, 6
 699   store i32 %div, ptr %p
 700   ret void
 701 }