llvm/test/CodeGen/X86/divide-by-constant.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
   2 ; RUN: llc < %s -mtriple=i686-pc-linux-gnu | FileCheck %s --check-prefix=X86
   3 ; RUN: llc < %s -mtriple=x86_64-pc-linux-gnu | FileCheck %s --check-prefixes=X64,X64-FAST
   4 ; RUN: llc < %s -mtriple=x86_64-pc-linux-gnu -mattr=idivq-to-divl | FileCheck %s --check-prefixes=X64,X64-SLOW
   5
   6 define zeroext i16 @test1(i16 zeroext %x) nounwind {
   7 ; X86-LABEL: test1:
   8 ; X86:       # %bb.0: # %entry
   9 ; X86-NEXT:    movzwl {{[0-9]+}}(%esp), %eax
  10 ; X86-NEXT:    imull $63551, %eax, %eax # imm = 0xF83F
  11 ; X86-NEXT:    shrl $21, %eax
  12 ; X86-NEXT:    # kill: def $ax killed $ax killed $eax
  13 ; X86-NEXT:    retl
  14 ;
  15 ; X64-LABEL: test1:
  16 ; X64:       # %bb.0: # %entry
  17 ; X64-NEXT:    imull $63551, %edi, %eax # imm = 0xF83F
  18 ; X64-NEXT:    shrl $21, %eax
  19 ; X64-NEXT:    # kill: def $ax killed $ax killed $eax
  20 ; X64-NEXT:    retq
  21 entry:
  22   %div = udiv i16 %x, 33
  23   ret i16 %div
  24 }
  25
  26 define zeroext i16 @test2(i8 signext %x, i16 zeroext %c) nounwind readnone ssp noredzone {
  27 ; X86-LABEL: test2:
  28 ; X86:       # %bb.0: # %entry
  29 ; X86-NEXT:    movzwl {{[0-9]+}}(%esp), %eax
  30 ; X86-NEXT:    imull $43691, %eax, %eax # imm = 0xAAAB
  31 ; X86-NEXT:    shrl $17, %eax
  32 ; X86-NEXT:    # kill: def $ax killed $ax killed $eax
  33 ; X86-NEXT:    retl
  34 ;
  35 ; X64-LABEL: test2:
  36 ; X64:       # %bb.0: # %entry
  37 ; X64-NEXT:    imull $43691, %esi, %eax # imm = 0xAAAB
  38 ; X64-NEXT:    shrl $17, %eax
  39 ; X64-NEXT:    # kill: def $ax killed $ax killed $eax
  40 ; X64-NEXT:    retq
  41 entry:
  42   %div = udiv i16 %c, 3
  43   ret i16 %div
  44
  45 }
  46
  47 define zeroext i8 @test3(i8 zeroext %x, i8 zeroext %c) nounwind readnone ssp noredzone {
  48 ; X86-LABEL: test3:
  49 ; X86:       # %bb.0: # %entry
  50 ; X86-NEXT:    movzbl {{[0-9]+}}(%esp), %eax
  51 ; X86-NEXT:    imull $171, %eax, %eax
  52 ; X86-NEXT:    shrl $9, %eax
  53 ; X86-NEXT:    # kill: def $al killed $al killed $eax
  54 ; X86-NEXT:    retl
  55 ;
  56 ; X64-LABEL: test3:
  57 ; X64:       # %bb.0: # %entry
  58 ; X64-NEXT:    imull $171, %esi, %eax
  59 ; X64-NEXT:    shrl $9, %eax
  60 ; X64-NEXT:    # kill: def $al killed $al killed $eax
  61 ; X64-NEXT:    retq
  62 entry:
  63   %div = udiv i8 %c, 3
  64   ret i8 %div
  65 }
  66
  67 define signext i16 @test4(i16 signext %x) nounwind {
  68 ; X86-LABEL: test4:
  69 ; X86:       # %bb.0: # %entry
  70 ; X86-NEXT:    movswl {{[0-9]+}}(%esp), %eax
  71 ; X86-NEXT:    imull $1986, %eax, %eax # imm = 0x7C2
  72 ; X86-NEXT:    movl %eax, %ecx
  73 ; X86-NEXT:    shrl $31, %ecx
  74 ; X86-NEXT:    shrl $16, %eax
  75 ; X86-NEXT:    addl %ecx, %eax
  76 ; X86-NEXT:    # kill: def $ax killed $ax killed $eax
  77 ; X86-NEXT:    retl
  78 ;
  79 ; X64-LABEL: test4:
  80 ; X64:       # %bb.0: # %entry
  81 ; X64-NEXT:    imull $1986, %edi, %eax # imm = 0x7C2
  82 ; X64-NEXT:    movl %eax, %ecx
  83 ; X64-NEXT:    shrl $31, %ecx
  84 ; X64-NEXT:    shrl $16, %eax
  85 ; X64-NEXT:    addl %ecx, %eax
  86 ; X64-NEXT:    # kill: def $ax killed $ax killed $eax
  87 ; X64-NEXT:    retq
  88 entry:
  89   %div = sdiv i16 %x, 33                ; <i32> [#uses=1]
  90   ret i16 %div
  91 }
  92
  93 define i32 @test5(i32 %A) nounwind {
  94 ; X86-LABEL: test5:
  95 ; X86:       # %bb.0:
  96 ; X86-NEXT:    movl $365384439, %eax # imm = 0x15C752F7
  97 ; X86-NEXT:    mull {{[0-9]+}}(%esp)
  98 ; X86-NEXT:    movl %edx, %eax
  99 ; X86-NEXT:    shrl $27, %eax
 100 ; X86-NEXT:    retl
 101 ;
 102 ; X64-LABEL: test5:
 103 ; X64:       # %bb.0:
 104 ; X64-NEXT:    movl %edi, %eax
 105 ; X64-NEXT:    imulq $365384439, %rax, %rax # imm = 0x15C752F7
 106 ; X64-NEXT:    shrq $59, %rax
 107 ; X64-NEXT:    # kill: def $eax killed $eax killed $rax
 108 ; X64-NEXT:    retq
 109   %tmp1 = udiv i32 %A, 1577682821         ; <i32> [#uses=1]
 110   ret i32 %tmp1
 111 }
 112
 113 define signext i16 @test6(i16 signext %x) nounwind {
 114 ; X86-LABEL: test6:
 115 ; X86:       # %bb.0: # %entry
 116 ; X86-NEXT:    movswl {{[0-9]+}}(%esp), %eax
 117 ; X86-NEXT:    imull $26215, %eax, %eax # imm = 0x6667
 118 ; X86-NEXT:    movl %eax, %ecx
 119 ; X86-NEXT:    shrl $31, %ecx
 120 ; X86-NEXT:    sarl $18, %eax
 121 ; X86-NEXT:    addl %ecx, %eax
 122 ; X86-NEXT:    # kill: def $ax killed $ax killed $eax
 123 ; X86-NEXT:    retl
 124 ;
 125 ; X64-LABEL: test6:
 126 ; X64:       # %bb.0: # %entry
 127 ; X64-NEXT:    imull $26215, %edi, %eax # imm = 0x6667
 128 ; X64-NEXT:    movl %eax, %ecx
 129 ; X64-NEXT:    shrl $31, %ecx
 130 ; X64-NEXT:    sarl $18, %eax
 131 ; X64-NEXT:    addl %ecx, %eax
 132 ; X64-NEXT:    # kill: def $ax killed $ax killed $eax
 133 ; X64-NEXT:    retq
 134 entry:
 135   %div = sdiv i16 %x, 10
 136   ret i16 %div
 137 }
 138
 139 define i32 @test7(i32 %x) nounwind {
 140 ; X86-LABEL: test7:
 141 ; X86:       # %bb.0:
 142 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
 143 ; X86-NEXT:    shrl $2, %eax
 144 ; X86-NEXT:    movl $613566757, %ecx # imm = 0x24924925
 145 ; X86-NEXT:    mull %ecx
 146 ; X86-NEXT:    movl %edx, %eax
 147 ; X86-NEXT:    retl
 148 ;
 149 ; X64-LABEL: test7:
 150 ; X64:       # %bb.0:
 151 ; X64-NEXT:    # kill: def $edi killed $edi def $rdi
 152 ; X64-NEXT:    shrl $2, %edi
 153 ; X64-NEXT:    imulq $613566757, %rdi, %rax # imm = 0x24924925
 154 ; X64-NEXT:    shrq $32, %rax
 155 ; X64-NEXT:    # kill: def $eax killed $eax killed $rax
 156 ; X64-NEXT:    retq
 157   %div = udiv i32 %x, 28
 158   ret i32 %div
 159 }
 160
 161 ; PR13326
 162 define i8 @test8(i8 %x) nounwind {
 163 ; X86-LABEL: test8:
 164 ; X86:       # %bb.0:
 165 ; X86-NEXT:    movzbl {{[0-9]+}}(%esp), %eax
 166 ; X86-NEXT:    shrb %al
 167 ; X86-NEXT:    movzbl %al, %eax
 168 ; X86-NEXT:    imull $211, %eax, %eax
 169 ; X86-NEXT:    shrl $13, %eax
 170 ; X86-NEXT:    # kill: def $al killed $al killed $eax
 171 ; X86-NEXT:    retl
 172 ;
 173 ; X64-LABEL: test8:
 174 ; X64:       # %bb.0:
 175 ; X64-NEXT:    shrb %dil
 176 ; X64-NEXT:    movzbl %dil, %eax
 177 ; X64-NEXT:    imull $211, %eax, %eax
 178 ; X64-NEXT:    shrl $13, %eax
 179 ; X64-NEXT:    # kill: def $al killed $al killed $eax
 180 ; X64-NEXT:    retq
 181   %div = udiv i8 %x, 78
 182   ret i8 %div
 183 }
 184
 185 define i8 @test9(i8 %x) nounwind {
 186 ; X86-LABEL: test9:
 187 ; X86:       # %bb.0:
 188 ; X86-NEXT:    movzbl {{[0-9]+}}(%esp), %eax
 189 ; X86-NEXT:    shrb $2, %al
 190 ; X86-NEXT:    movzbl %al, %eax
 191 ; X86-NEXT:    imull $71, %eax, %eax
 192 ; X86-NEXT:    shrl $11, %eax
 193 ; X86-NEXT:    # kill: def $al killed $al killed $eax
 194 ; X86-NEXT:    retl
 195 ;
 196 ; X64-LABEL: test9:
 197 ; X64:       # %bb.0:
 198 ; X64-NEXT:    shrb $2, %dil
 199 ; X64-NEXT:    movzbl %dil, %eax
 200 ; X64-NEXT:    imull $71, %eax, %eax
 201 ; X64-NEXT:    shrl $11, %eax
 202 ; X64-NEXT:    # kill: def $al killed $al killed $eax
 203 ; X64-NEXT:    retq
 204   %div = udiv i8 %x, 116
 205   ret i8 %div
 206 }
 207
 208 define i32 @testsize1(i32 %x) minsize nounwind {
 209 ; X86-LABEL: testsize1:
 210 ; X86:       # %bb.0: # %entry
 211 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
 212 ; X86-NEXT:    pushl $32
 213 ; X86-NEXT:    popl %ecx
 214 ; X86-NEXT:    cltd
 215 ; X86-NEXT:    idivl %ecx
 216 ; X86-NEXT:    retl
 217 ;
 218 ; X64-LABEL: testsize1:
 219 ; X64:       # %bb.0: # %entry
 220 ; X64-NEXT:    movl %edi, %eax
 221 ; X64-NEXT:    pushq $32
 222 ; X64-NEXT:    popq %rcx
 223 ; X64-NEXT:    cltd
 224 ; X64-NEXT:    idivl %ecx
 225 ; X64-NEXT:    retq
 226 entry:
 227   %div = sdiv i32 %x, 32
 228   ret i32 %div
 229 }
 230
 231 define i32 @testsize2(i32 %x) minsize nounwind {
 232 ; X86-LABEL: testsize2:
 233 ; X86:       # %bb.0: # %entry
 234 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
 235 ; X86-NEXT:    pushl $33
 236 ; X86-NEXT:    popl %ecx
 237 ; X86-NEXT:    cltd
 238 ; X86-NEXT:    idivl %ecx
 239 ; X86-NEXT:    retl
 240 ;
 241 ; X64-LABEL: testsize2:
 242 ; X64:       # %bb.0: # %entry
 243 ; X64-NEXT:    movl %edi, %eax
 244 ; X64-NEXT:    pushq $33
 245 ; X64-NEXT:    popq %rcx
 246 ; X64-NEXT:    cltd
 247 ; X64-NEXT:    idivl %ecx
 248 ; X64-NEXT:    retq
 249 entry:
 250   %div = sdiv i32 %x, 33
 251   ret i32 %div
 252 }
 253
 254 define i32 @testsize3(i32 %x) minsize nounwind {
 255 ; X86-LABEL: testsize3:
 256 ; X86:       # %bb.0: # %entry
 257 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
 258 ; X86-NEXT:    shrl $5, %eax
 259 ; X86-NEXT:    retl
 260 ;
 261 ; X64-LABEL: testsize3:
 262 ; X64:       # %bb.0: # %entry
 263 ; X64-NEXT:    movl %edi, %eax
 264 ; X64-NEXT:    shrl $5, %eax
 265 ; X64-NEXT:    retq
 266 entry:
 267   %div = udiv i32 %x, 32
 268   ret i32 %div
 269 }
 270
 271 define i32 @testsize4(i32 %x) minsize nounwind {
 272 ; X86-LABEL: testsize4:
 273 ; X86:       # %bb.0: # %entry
 274 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
 275 ; X86-NEXT:    pushl $33
 276 ; X86-NEXT:    popl %ecx
 277 ; X86-NEXT:    xorl %edx, %edx
 278 ; X86-NEXT:    divl %ecx
 279 ; X86-NEXT:    retl
 280 ;
 281 ; X64-LABEL: testsize4:
 282 ; X64:       # %bb.0: # %entry
 283 ; X64-NEXT:    movl %edi, %eax
 284 ; X64-NEXT:    pushq $33
 285 ; X64-NEXT:    popq %rcx
 286 ; X64-NEXT:    xorl %edx, %edx
 287 ; X64-NEXT:    divl %ecx
 288 ; X64-NEXT:    retq
 289 entry:
 290   %div = udiv i32 %x, 33
 291   ret i32 %div
 292 }
 293
 294 define i64 @PR23590(i64 %x) nounwind {
 295 ; X86-LABEL: PR23590:
 296 ; X86:       # %bb.0: # %entry
 297 ; X86-NEXT:    subl $12, %esp
 298 ; X86-NEXT:    pushl $0
 299 ; X86-NEXT:    pushl $12345 # imm = 0x3039
 300 ; X86-NEXT:    pushl {{[0-9]+}}(%esp)
 301 ; X86-NEXT:    pushl {{[0-9]+}}(%esp)
 302 ; X86-NEXT:    calll __umoddi3
 303 ; X86-NEXT:    addl $16, %esp
 304 ; X86-NEXT:    pushl $0
 305 ; X86-NEXT:    pushl $7
 306 ; X86-NEXT:    pushl %edx
 307 ; X86-NEXT:    pushl %eax
 308 ; X86-NEXT:    calll __udivdi3
 309 ; X86-NEXT:    addl $28, %esp
 310 ; X86-NEXT:    retl
 311 ;
 312 ; X64-FAST-LABEL: PR23590:
 313 ; X64-FAST:       # %bb.0: # %entry
 314 ; X64-FAST-NEXT:    movabsq $6120523590596543007, %rcx # imm = 0x54F077C718E7C21F
 315 ; X64-FAST-NEXT:    movq %rdi, %rax
 316 ; X64-FAST-NEXT:    mulq %rcx
 317 ; X64-FAST-NEXT:    shrq $12, %rdx
 318 ; X64-FAST-NEXT:    imulq $12345, %rdx, %rax # imm = 0x3039
 319 ; X64-FAST-NEXT:    subq %rax, %rdi
 320 ; X64-FAST-NEXT:    movabsq $2635249153387078803, %rcx # imm = 0x2492492492492493
 321 ; X64-FAST-NEXT:    movq %rdi, %rax
 322 ; X64-FAST-NEXT:    mulq %rcx
 323 ; X64-FAST-NEXT:    movq %rdx, %rax
 324 ; X64-FAST-NEXT:    retq
 325 ;
 326 ; X64-SLOW-LABEL: PR23590:
 327 ; X64-SLOW:       # %bb.0: # %entry
 328 ; X64-SLOW-NEXT:    movabsq $6120523590596543007, %rcx # imm = 0x54F077C718E7C21F
 329 ; X64-SLOW-NEXT:    movq %rdi, %rax
 330 ; X64-SLOW-NEXT:    mulq %rcx
 331 ; X64-SLOW-NEXT:    shrq $12, %rdx
 332 ; X64-SLOW-NEXT:    imulq $12345, %rdx, %rax # imm = 0x3039
 333 ; X64-SLOW-NEXT:    subq %rax, %rdi
 334 ; X64-SLOW-NEXT:    imulq $613566757, %rdi, %rax # imm = 0x24924925
 335 ; X64-SLOW-NEXT:    shrq $32, %rax
 336 ; X64-SLOW-NEXT:    retq
 337 entry:
 338   %rem = urem i64 %x, 12345
 339   %div = udiv i64 %rem, 7
 340   ret i64 %div
 341 }
 342
 343 define { i64, i32 } @PR38622(i64) nounwind {
 344 ; X86-LABEL: PR38622:
 345 ; X86:       # %bb.0:
 346 ; X86-NEXT:    pushl %ebp
 347 ; X86-NEXT:    pushl %ebx
 348 ; X86-NEXT:    pushl %edi
 349 ; X86-NEXT:    pushl %esi
 350 ; X86-NEXT:    subl $12, %esp
 351 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ebx
 352 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ebp
 353 ; X86-NEXT:    pushl $0
 354 ; X86-NEXT:    pushl $-294967296 # imm = 0xEE6B2800
 355 ; X86-NEXT:    pushl %ebp
 356 ; X86-NEXT:    pushl %ebx
 357 ; X86-NEXT:    calll __udivdi3
 358 ; X86-NEXT:    addl $16, %esp
 359 ; X86-NEXT:    movl %eax, %esi
 360 ; X86-NEXT:    movl %edx, %edi
 361 ; X86-NEXT:    pushl $0
 362 ; X86-NEXT:    pushl $-294967296 # imm = 0xEE6B2800
 363 ; X86-NEXT:    pushl %ebp
 364 ; X86-NEXT:    pushl %ebx
 365 ; X86-NEXT:    calll __umoddi3
 366 ; X86-NEXT:    addl $16, %esp
 367 ; X86-NEXT:    movl %eax, %ecx
 368 ; X86-NEXT:    movl %esi, %eax
 369 ; X86-NEXT:    movl %edi, %edx
 370 ; X86-NEXT:    addl $12, %esp
 371 ; X86-NEXT:    popl %esi
 372 ; X86-NEXT:    popl %edi
 373 ; X86-NEXT:    popl %ebx
 374 ; X86-NEXT:    popl %ebp
 375 ; X86-NEXT:    retl
 376 ;
 377 ; X64-LABEL: PR38622:
 378 ; X64:       # %bb.0:
 379 ; X64-NEXT:    movq %rdi, %rax
 380 ; X64-NEXT:    shrq $11, %rax
 381 ; X64-NEXT:    movabsq $4835703278458517, %rcx # imm = 0x112E0BE826D695
 382 ; X64-NEXT:    mulq %rcx
 383 ; X64-NEXT:    movq %rdx, %rax
 384 ; X64-NEXT:    shrq $9, %rax
 385 ; X64-NEXT:    imull $-294967296, %eax, %ecx # imm = 0xEE6B2800
 386 ; X64-NEXT:    subl %ecx, %edi
 387 ; X64-NEXT:    movl %edi, %edx
 388 ; X64-NEXT:    retq
 389   %2 = udiv i64 %0, 4000000000
 390   %3 = urem i64 %0, 4000000000
 391   %4 = trunc i64 %3 to i32
 392   %5 = insertvalue { i64, i32 } undef, i64 %2, 0
 393   %6 = insertvalue { i64, i32 } %5, i32 %4, 1
 394   ret { i64, i32 } %6
 395 }
 396
 397 define { i64, i32 } @PR38622_signed(i64) nounwind {
 398 ; X86-LABEL: PR38622_signed:
 399 ; X86:       # %bb.0:
 400 ; X86-NEXT:    pushl %ebp
 401 ; X86-NEXT:    pushl %ebx
 402 ; X86-NEXT:    pushl %edi
 403 ; X86-NEXT:    pushl %esi
 404 ; X86-NEXT:    subl $12, %esp
 405 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ebx
 406 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ebp
 407 ; X86-NEXT:    pushl $0
 408 ; X86-NEXT:    pushl $-294967296 # imm = 0xEE6B2800
 409 ; X86-NEXT:    pushl %ebp
 410 ; X86-NEXT:    pushl %ebx
 411 ; X86-NEXT:    calll __divdi3
 412 ; X86-NEXT:    addl $16, %esp
 413 ; X86-NEXT:    movl %eax, %esi
 414 ; X86-NEXT:    movl %edx, %edi
 415 ; X86-NEXT:    pushl $0
 416 ; X86-NEXT:    pushl $-294967296 # imm = 0xEE6B2800
 417 ; X86-NEXT:    pushl %ebp
 418 ; X86-NEXT:    pushl %ebx
 419 ; X86-NEXT:    calll __moddi3
 420 ; X86-NEXT:    addl $16, %esp
 421 ; X86-NEXT:    movl %eax, %ecx
 422 ; X86-NEXT:    movl %esi, %eax
 423 ; X86-NEXT:    movl %edi, %edx
 424 ; X86-NEXT:    addl $12, %esp
 425 ; X86-NEXT:    popl %esi
 426 ; X86-NEXT:    popl %edi
 427 ; X86-NEXT:    popl %ebx
 428 ; X86-NEXT:    popl %ebp
 429 ; X86-NEXT:    retl
 430 ;
 431 ; X64-LABEL: PR38622_signed:
 432 ; X64:       # %bb.0:
 433 ; X64-NEXT:    movabsq $1237940039285380275, %rcx # imm = 0x112E0BE826D694B3
 434 ; X64-NEXT:    movq %rdi, %rax
 435 ; X64-NEXT:    imulq %rcx
 436 ; X64-NEXT:    movq %rdx, %rax
 437 ; X64-NEXT:    shrq $63, %rax
 438 ; X64-NEXT:    sarq $28, %rdx
 439 ; X64-NEXT:    addq %rdx, %rax
 440 ; X64-NEXT:    imull $-294967296, %eax, %ecx # imm = 0xEE6B2800
 441 ; X64-NEXT:    subl %ecx, %edi
 442 ; X64-NEXT:    movl %edi, %edx
 443 ; X64-NEXT:    retq
 444   %2 = sdiv i64 %0, 4000000000
 445   %3 = srem i64 %0, 4000000000
 446   %4 = trunc i64 %3 to i32
 447   %5 = insertvalue { i64, i32 } undef, i64 %2, 0
 448   %6 = insertvalue { i64, i32 } %5, i32 %4, 1
 449   ret { i64, i32 } %6
 450 }
 451
 452 define i64 @urem_i64_3(i64 %x) nounwind {
 453 ; X86-LABEL: urem_i64_3:
 454 ; X86:       # %bb.0: # %entry
 455 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 456 ; X86-NEXT:    addl {{[0-9]+}}(%esp), %ecx
 457 ; X86-NEXT:    adcl $0, %ecx
 458 ; X86-NEXT:    movl $-1431655765, %edx # imm = 0xAAAAAAAB
 459 ; X86-NEXT:    movl %ecx, %eax
 460 ; X86-NEXT:    mull %edx
 461 ; X86-NEXT:    shrl %edx
 462 ; X86-NEXT:    leal (%edx,%edx,2), %eax
 463 ; X86-NEXT:    subl %eax, %ecx
 464 ; X86-NEXT:    movl %ecx, %eax
 465 ; X86-NEXT:    xorl %edx, %edx
 466 ; X86-NEXT:    retl
 467 ;
 468 ; X64-LABEL: urem_i64_3:
 469 ; X64:       # %bb.0: # %entry
 470 ; X64-NEXT:    movabsq $-6148914691236517205, %rcx # imm = 0xAAAAAAAAAAAAAAAB
 471 ; X64-NEXT:    movq %rdi, %rax
 472 ; X64-NEXT:    mulq %rcx
 473 ; X64-NEXT:    shrq %rdx
 474 ; X64-NEXT:    leaq (%rdx,%rdx,2), %rax
 475 ; X64-NEXT:    subq %rax, %rdi
 476 ; X64-NEXT:    movq %rdi, %rax
 477 ; X64-NEXT:    retq
 478 entry:
 479   %rem = urem i64 %x, 3
 480   ret i64 %rem
 481 }
 482
 483 define i64 @urem_i64_5(i64 %x) nounwind {
 484 ; X86-LABEL: urem_i64_5:
 485 ; X86:       # %bb.0: # %entry
 486 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 487 ; X86-NEXT:    addl {{[0-9]+}}(%esp), %ecx
 488 ; X86-NEXT:    adcl $0, %ecx
 489 ; X86-NEXT:    movl $-858993459, %edx # imm = 0xCCCCCCCD
 490 ; X86-NEXT:    movl %ecx, %eax
 491 ; X86-NEXT:    mull %edx
 492 ; X86-NEXT:    shrl $2, %edx
 493 ; X86-NEXT:    leal (%edx,%edx,4), %eax
 494 ; X86-NEXT:    subl %eax, %ecx
 495 ; X86-NEXT:    movl %ecx, %eax
 496 ; X86-NEXT:    xorl %edx, %edx
 497 ; X86-NEXT:    retl
 498 ;
 499 ; X64-LABEL: urem_i64_5:
 500 ; X64:       # %bb.0: # %entry
 501 ; X64-NEXT:    movabsq $-3689348814741910323, %rcx # imm = 0xCCCCCCCCCCCCCCCD
 502 ; X64-NEXT:    movq %rdi, %rax
 503 ; X64-NEXT:    mulq %rcx
 504 ; X64-NEXT:    shrq $2, %rdx
 505 ; X64-NEXT:    leaq (%rdx,%rdx,4), %rax
 506 ; X64-NEXT:    subq %rax, %rdi
 507 ; X64-NEXT:    movq %rdi, %rax
 508 ; X64-NEXT:    retq
 509 entry:
 510   %rem = urem i64 %x, 5
 511   ret i64 %rem
 512 }
 513
 514 define i64 @urem_i64_15(i64 %x) nounwind {
 515 ; X86-LABEL: urem_i64_15:
 516 ; X86:       # %bb.0: # %entry
 517 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 518 ; X86-NEXT:    addl {{[0-9]+}}(%esp), %ecx
 519 ; X86-NEXT:    adcl $0, %ecx
 520 ; X86-NEXT:    movl $-2004318071, %edx # imm = 0x88888889
 521 ; X86-NEXT:    movl %ecx, %eax
 522 ; X86-NEXT:    mull %edx
 523 ; X86-NEXT:    shrl $3, %edx
 524 ; X86-NEXT:    leal (%edx,%edx,4), %eax
 525 ; X86-NEXT:    leal (%eax,%eax,2), %eax
 526 ; X86-NEXT:    subl %eax, %ecx
 527 ; X86-NEXT:    movl %ecx, %eax
 528 ; X86-NEXT:    xorl %edx, %edx
 529 ; X86-NEXT:    retl
 530 ;
 531 ; X64-LABEL: urem_i64_15:
 532 ; X64:       # %bb.0: # %entry
 533 ; X64-NEXT:    movabsq $-8608480567731124087, %rcx # imm = 0x8888888888888889
 534 ; X64-NEXT:    movq %rdi, %rax
 535 ; X64-NEXT:    mulq %rcx
 536 ; X64-NEXT:    shrq $3, %rdx
 537 ; X64-NEXT:    leaq (%rdx,%rdx,4), %rax
 538 ; X64-NEXT:    leaq (%rax,%rax,2), %rax
 539 ; X64-NEXT:    subq %rax, %rdi
 540 ; X64-NEXT:    movq %rdi, %rax
 541 ; X64-NEXT:    retq
 542 entry:
 543   %rem = urem i64 %x, 15
 544   ret i64 %rem
 545 }
 546
 547 define i64 @urem_i64_17(i64 %x) nounwind {
 548 ; X86-LABEL: urem_i64_17:
 549 ; X86:       # %bb.0: # %entry
 550 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 551 ; X86-NEXT:    addl {{[0-9]+}}(%esp), %ecx
 552 ; X86-NEXT:    adcl $0, %ecx
 553 ; X86-NEXT:    movl $-252645135, %edx # imm = 0xF0F0F0F1
 554 ; X86-NEXT:    movl %ecx, %eax
 555 ; X86-NEXT:    mull %edx
 556 ; X86-NEXT:    movl %edx, %eax
 557 ; X86-NEXT:    andl $-16, %eax
 558 ; X86-NEXT:    shrl $4, %edx
 559 ; X86-NEXT:    addl %eax, %edx
 560 ; X86-NEXT:    subl %edx, %ecx
 561 ; X86-NEXT:    movl %ecx, %eax
 562 ; X86-NEXT:    xorl %edx, %edx
 563 ; X86-NEXT:    retl
 564 ;
 565 ; X64-LABEL: urem_i64_17:
 566 ; X64:       # %bb.0: # %entry
 567 ; X64-NEXT:    movabsq $-1085102592571150095, %rcx # imm = 0xF0F0F0F0F0F0F0F1
 568 ; X64-NEXT:    movq %rdi, %rax
 569 ; X64-NEXT:    mulq %rcx
 570 ; X64-NEXT:    movq %rdx, %rax
 571 ; X64-NEXT:    andq $-16, %rax
 572 ; X64-NEXT:    shrq $4, %rdx
 573 ; X64-NEXT:    addq %rax, %rdx
 574 ; X64-NEXT:    subq %rdx, %rdi
 575 ; X64-NEXT:    movq %rdi, %rax
 576 ; X64-NEXT:    retq
 577 entry:
 578   %rem = urem i64 %x, 17
 579   ret i64 %rem
 580 }
 581
 582 define i64 @urem_i64_255(i64 %x) nounwind {
 583 ; X86-LABEL: urem_i64_255:
 584 ; X86:       # %bb.0: # %entry
 585 ; X86-NEXT:    pushl %esi
 586 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 587 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %esi
 588 ; X86-NEXT:    movl %ecx, %eax
 589 ; X86-NEXT:    addl %esi, %eax
 590 ; X86-NEXT:    adcl $0, %eax
 591 ; X86-NEXT:    movl $-2139062143, %edx # imm = 0x80808081
 592 ; X86-NEXT:    mull %edx
 593 ; X86-NEXT:    shrl $7, %edx
 594 ; X86-NEXT:    movl %edx, %eax
 595 ; X86-NEXT:    shll $8, %eax
 596 ; X86-NEXT:    subl %eax, %edx
 597 ; X86-NEXT:    addl %esi, %ecx
 598 ; X86-NEXT:    adcl %edx, %ecx
 599 ; X86-NEXT:    movl %ecx, %eax
 600 ; X86-NEXT:    xorl %edx, %edx
 601 ; X86-NEXT:    popl %esi
 602 ; X86-NEXT:    retl
 603 ;
 604 ; X64-LABEL: urem_i64_255:
 605 ; X64:       # %bb.0: # %entry
 606 ; X64-NEXT:    movabsq $-9187201950435737471, %rcx # imm = 0x8080808080808081
 607 ; X64-NEXT:    movq %rdi, %rax
 608 ; X64-NEXT:    mulq %rcx
 609 ; X64-NEXT:    shrq $7, %rdx
 610 ; X64-NEXT:    movq %rdx, %rax
 611 ; X64-NEXT:    shlq $8, %rax
 612 ; X64-NEXT:    subq %rax, %rdx
 613 ; X64-NEXT:    leaq (%rdx,%rdi), %rax
 614 ; X64-NEXT:    retq
 615 entry:
 616   %rem = urem i64 %x, 255
 617   ret i64 %rem
 618 }
 619
 620 define i64 @urem_i64_257(i64 %x) nounwind {
 621 ; X86-LABEL: urem_i64_257:
 622 ; X86:       # %bb.0: # %entry
 623 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 624 ; X86-NEXT:    addl {{[0-9]+}}(%esp), %ecx
 625 ; X86-NEXT:    adcl $0, %ecx
 626 ; X86-NEXT:    movl $-16711935, %edx # imm = 0xFF00FF01
 627 ; X86-NEXT:    movl %ecx, %eax
 628 ; X86-NEXT:    mull %edx
 629 ; X86-NEXT:    movl %edx, %eax
 630 ; X86-NEXT:    andl $-256, %eax
 631 ; X86-NEXT:    shrl $8, %edx
 632 ; X86-NEXT:    addl %eax, %edx
 633 ; X86-NEXT:    subl %edx, %ecx
 634 ; X86-NEXT:    movl %ecx, %eax
 635 ; X86-NEXT:    xorl %edx, %edx
 636 ; X86-NEXT:    retl
 637 ;
 638 ; X64-LABEL: urem_i64_257:
 639 ; X64:       # %bb.0: # %entry
 640 ; X64-NEXT:    movabsq $-71777214294589695, %rcx # imm = 0xFF00FF00FF00FF01
 641 ; X64-NEXT:    movq %rdi, %rax
 642 ; X64-NEXT:    mulq %rcx
 643 ; X64-NEXT:    movq %rdx, %rax
 644 ; X64-NEXT:    andq $-256, %rax
 645 ; X64-NEXT:    shrq $8, %rdx
 646 ; X64-NEXT:    addq %rax, %rdx
 647 ; X64-NEXT:    subq %rdx, %rdi
 648 ; X64-NEXT:    movq %rdi, %rax
 649 ; X64-NEXT:    retq
 650 entry:
 651   %rem = urem i64 %x, 257
 652   ret i64 %rem
 653 }
 654
 655 define i64 @urem_i64_65535(i64 %x) nounwind {
 656 ; X86-LABEL: urem_i64_65535:
 657 ; X86:       # %bb.0: # %entry
 658 ; X86-NEXT:    pushl %esi
 659 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 660 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %esi
 661 ; X86-NEXT:    movl %ecx, %eax
 662 ; X86-NEXT:    addl %esi, %eax
 663 ; X86-NEXT:    adcl $0, %eax
 664 ; X86-NEXT:    movl $-2147450879, %edx # imm = 0x80008001
 665 ; X86-NEXT:    mull %edx
 666 ; X86-NEXT:    shrl $15, %edx
 667 ; X86-NEXT:    movl %edx, %eax
 668 ; X86-NEXT:    shll $16, %eax
 669 ; X86-NEXT:    subl %eax, %edx
 670 ; X86-NEXT:    addl %esi, %ecx
 671 ; X86-NEXT:    adcl %edx, %ecx
 672 ; X86-NEXT:    movl %ecx, %eax
 673 ; X86-NEXT:    xorl %edx, %edx
 674 ; X86-NEXT:    popl %esi
 675 ; X86-NEXT:    retl
 676 ;
 677 ; X64-LABEL: urem_i64_65535:
 678 ; X64:       # %bb.0: # %entry
 679 ; X64-NEXT:    movabsq $-9223231297218904063, %rcx # imm = 0x8000800080008001
 680 ; X64-NEXT:    movq %rdi, %rax
 681 ; X64-NEXT:    mulq %rcx
 682 ; X64-NEXT:    shrq $15, %rdx
 683 ; X64-NEXT:    movq %rdx, %rax
 684 ; X64-NEXT:    shlq $16, %rax
 685 ; X64-NEXT:    subq %rax, %rdx
 686 ; X64-NEXT:    leaq (%rdx,%rdi), %rax
 687 ; X64-NEXT:    retq
 688 entry:
 689   %rem = urem i64 %x, 65535
 690   ret i64 %rem
 691 }
 692
 693 define i64 @urem_i64_65537(i64 %x) nounwind {
 694 ; X86-LABEL: urem_i64_65537:
 695 ; X86:       # %bb.0: # %entry
 696 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 697 ; X86-NEXT:    addl {{[0-9]+}}(%esp), %ecx
 698 ; X86-NEXT:    adcl $0, %ecx
 699 ; X86-NEXT:    movl $-65535, %edx # imm = 0xFFFF0001
 700 ; X86-NEXT:    movl %ecx, %eax
 701 ; X86-NEXT:    mull %edx
 702 ; X86-NEXT:    movl %edx, %eax
 703 ; X86-NEXT:    shrl $16, %eax
 704 ; X86-NEXT:    shldl $16, %edx, %eax
 705 ; X86-NEXT:    subl %eax, %ecx
 706 ; X86-NEXT:    movl %ecx, %eax
 707 ; X86-NEXT:    xorl %edx, %edx
 708 ; X86-NEXT:    retl
 709 ;
 710 ; X64-LABEL: urem_i64_65537:
 711 ; X64:       # %bb.0: # %entry
 712 ; X64-NEXT:    movabsq $-281470681808895, %rcx # imm = 0xFFFF0000FFFF0001
 713 ; X64-NEXT:    movq %rdi, %rax
 714 ; X64-NEXT:    mulq %rcx
 715 ; X64-NEXT:    movq %rdx, %rax
 716 ; X64-NEXT:    andq $-65536, %rax # imm = 0xFFFF0000
 717 ; X64-NEXT:    shrq $16, %rdx
 718 ; X64-NEXT:    addq %rax, %rdx
 719 ; X64-NEXT:    subq %rdx, %rdi
 720 ; X64-NEXT:    movq %rdi, %rax
 721 ; X64-NEXT:    retq
 722 entry:
 723   %rem = urem i64 %x, 65537
 724   ret i64 %rem
 725 }
 726
 727 define i64 @urem_i64_12(i64 %x) nounwind {
 728 ; X86-LABEL: urem_i64_12:
 729 ; X86:       # %bb.0: # %entry
 730 ; X86-NEXT:    pushl %esi
 731 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %esi
 732 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 733 ; X86-NEXT:    movl %ecx, %eax
 734 ; X86-NEXT:    shrl $2, %eax
 735 ; X86-NEXT:    shldl $30, %esi, %ecx
 736 ; X86-NEXT:    addl %eax, %ecx
 737 ; X86-NEXT:    adcl $0, %ecx
 738 ; X86-NEXT:    movl $-1431655765, %edx # imm = 0xAAAAAAAB
 739 ; X86-NEXT:    movl %ecx, %eax
 740 ; X86-NEXT:    mull %edx
 741 ; X86-NEXT:    shrl %edx
 742 ; X86-NEXT:    leal (%edx,%edx,2), %eax
 743 ; X86-NEXT:    subl %eax, %ecx
 744 ; X86-NEXT:    andl $3, %esi
 745 ; X86-NEXT:    leal (%esi,%ecx,4), %eax
 746 ; X86-NEXT:    xorl %edx, %edx
 747 ; X86-NEXT:    popl %esi
 748 ; X86-NEXT:    retl
 749 ;
 750 ; X64-LABEL: urem_i64_12:
 751 ; X64:       # %bb.0: # %entry
 752 ; X64-NEXT:    movabsq $-6148914691236517205, %rcx # imm = 0xAAAAAAAAAAAAAAAB
 753 ; X64-NEXT:    movq %rdi, %rax
 754 ; X64-NEXT:    mulq %rcx
 755 ; X64-NEXT:    shrq %rdx
 756 ; X64-NEXT:    andq $-4, %rdx
 757 ; X64-NEXT:    leaq (%rdx,%rdx,2), %rax
 758 ; X64-NEXT:    subq %rax, %rdi
 759 ; X64-NEXT:    movq %rdi, %rax
 760 ; X64-NEXT:    retq
 761 entry:
 762   %rem = urem i64 %x, 12
 763   ret i64 %rem
 764 }
 765
 766 define i64 @udiv_i64_3(i64 %x) nounwind {
 767 ; X86-LABEL: udiv_i64_3:
 768 ; X86:       # %bb.0: # %entry
 769 ; X86-NEXT:    pushl %ebx
 770 ; X86-NEXT:    pushl %edi
 771 ; X86-NEXT:    pushl %esi
 772 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 773 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %edi
 774 ; X86-NEXT:    movl %ecx, %esi
 775 ; X86-NEXT:    addl %edi, %esi
 776 ; X86-NEXT:    adcl $0, %esi
 777 ; X86-NEXT:    movl $-1431655765, %ebx # imm = 0xAAAAAAAB
 778 ; X86-NEXT:    movl %esi, %eax
 779 ; X86-NEXT:    mull %ebx
 780 ; X86-NEXT:    shrl %edx
 781 ; X86-NEXT:    leal (%edx,%edx,2), %eax
 782 ; X86-NEXT:    subl %eax, %esi
 783 ; X86-NEXT:    subl %esi, %ecx
 784 ; X86-NEXT:    sbbl $0, %edi
 785 ; X86-NEXT:    movl %ecx, %eax
 786 ; X86-NEXT:    mull %ebx
 787 ; X86-NEXT:    imull $-1431655766, %ecx, %ecx # imm = 0xAAAAAAAA
 788 ; X86-NEXT:    addl %ecx, %edx
 789 ; X86-NEXT:    imull $-1431655765, %edi, %ecx # imm = 0xAAAAAAAB
 790 ; X86-NEXT:    addl %ecx, %edx
 791 ; X86-NEXT:    popl %esi
 792 ; X86-NEXT:    popl %edi
 793 ; X86-NEXT:    popl %ebx
 794 ; X86-NEXT:    retl
 795 ;
 796 ; X64-LABEL: udiv_i64_3:
 797 ; X64:       # %bb.0: # %entry
 798 ; X64-NEXT:    movq %rdi, %rax
 799 ; X64-NEXT:    movabsq $-6148914691236517205, %rcx # imm = 0xAAAAAAAAAAAAAAAB
 800 ; X64-NEXT:    mulq %rcx
 801 ; X64-NEXT:    movq %rdx, %rax
 802 ; X64-NEXT:    shrq %rax
 803 ; X64-NEXT:    retq
 804 entry:
 805   %rem = udiv i64 %x, 3
 806   ret i64 %rem
 807 }
 808
 809 define i64 @udiv_i64_5(i64 %x) nounwind {
 810 ; X86-LABEL: udiv_i64_5:
 811 ; X86:       # %bb.0: # %entry
 812 ; X86-NEXT:    pushl %ebx
 813 ; X86-NEXT:    pushl %edi
 814 ; X86-NEXT:    pushl %esi
 815 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 816 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %edi
 817 ; X86-NEXT:    movl %ecx, %esi
 818 ; X86-NEXT:    addl %edi, %esi
 819 ; X86-NEXT:    adcl $0, %esi
 820 ; X86-NEXT:    movl $-858993459, %ebx # imm = 0xCCCCCCCD
 821 ; X86-NEXT:    movl %esi, %eax
 822 ; X86-NEXT:    mull %ebx
 823 ; X86-NEXT:    shrl $2, %edx
 824 ; X86-NEXT:    leal (%edx,%edx,4), %eax
 825 ; X86-NEXT:    subl %eax, %esi
 826 ; X86-NEXT:    subl %esi, %ecx
 827 ; X86-NEXT:    sbbl $0, %edi
 828 ; X86-NEXT:    movl %ecx, %eax
 829 ; X86-NEXT:    mull %ebx
 830 ; X86-NEXT:    imull $-858993460, %ecx, %ecx # imm = 0xCCCCCCCC
 831 ; X86-NEXT:    addl %ecx, %edx
 832 ; X86-NEXT:    imull $-858993459, %edi, %ecx # imm = 0xCCCCCCCD
 833 ; X86-NEXT:    addl %ecx, %edx
 834 ; X86-NEXT:    popl %esi
 835 ; X86-NEXT:    popl %edi
 836 ; X86-NEXT:    popl %ebx
 837 ; X86-NEXT:    retl
 838 ;
 839 ; X64-LABEL: udiv_i64_5:
 840 ; X64:       # %bb.0: # %entry
 841 ; X64-NEXT:    movq %rdi, %rax
 842 ; X64-NEXT:    movabsq $-3689348814741910323, %rcx # imm = 0xCCCCCCCCCCCCCCCD
 843 ; X64-NEXT:    mulq %rcx
 844 ; X64-NEXT:    movq %rdx, %rax
 845 ; X64-NEXT:    shrq $2, %rax
 846 ; X64-NEXT:    retq
 847 entry:
 848   %rem = udiv i64 %x, 5
 849   ret i64 %rem
 850 }
 851
 852 define i64 @udiv_i64_15(i64 %x) nounwind {
 853 ; X86-LABEL: udiv_i64_15:
 854 ; X86:       # %bb.0: # %entry
 855 ; X86-NEXT:    pushl %edi
 856 ; X86-NEXT:    pushl %esi
 857 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 858 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %edi
 859 ; X86-NEXT:    movl %ecx, %esi
 860 ; X86-NEXT:    addl %edi, %esi
 861 ; X86-NEXT:    adcl $0, %esi
 862 ; X86-NEXT:    movl $-2004318071, %edx # imm = 0x88888889
 863 ; X86-NEXT:    movl %esi, %eax
 864 ; X86-NEXT:    mull %edx
 865 ; X86-NEXT:    shrl $3, %edx
 866 ; X86-NEXT:    leal (%edx,%edx,4), %eax
 867 ; X86-NEXT:    leal (%eax,%eax,2), %eax
 868 ; X86-NEXT:    subl %eax, %esi
 869 ; X86-NEXT:    subl %esi, %ecx
 870 ; X86-NEXT:    sbbl $0, %edi
 871 ; X86-NEXT:    movl $-286331153, %edx # imm = 0xEEEEEEEF
 872 ; X86-NEXT:    movl %ecx, %eax
 873 ; X86-NEXT:    mull %edx
 874 ; X86-NEXT:    imull $-286331154, %ecx, %ecx # imm = 0xEEEEEEEE
 875 ; X86-NEXT:    addl %ecx, %edx
 876 ; X86-NEXT:    imull $-286331153, %edi, %ecx # imm = 0xEEEEEEEF
 877 ; X86-NEXT:    addl %ecx, %edx
 878 ; X86-NEXT:    popl %esi
 879 ; X86-NEXT:    popl %edi
 880 ; X86-NEXT:    retl
 881 ;
 882 ; X64-LABEL: udiv_i64_15:
 883 ; X64:       # %bb.0: # %entry
 884 ; X64-NEXT:    movq %rdi, %rax
 885 ; X64-NEXT:    movabsq $-8608480567731124087, %rcx # imm = 0x8888888888888889
 886 ; X64-NEXT:    mulq %rcx
 887 ; X64-NEXT:    movq %rdx, %rax
 888 ; X64-NEXT:    shrq $3, %rax
 889 ; X64-NEXT:    retq
 890 entry:
 891   %rem = udiv i64 %x, 15
 892   ret i64 %rem
 893 }
 894
 895 define i64 @udiv_i64_17(i64 %x) nounwind {
 896 ; X86-LABEL: udiv_i64_17:
 897 ; X86:       # %bb.0: # %entry
 898 ; X86-NEXT:    pushl %ebx
 899 ; X86-NEXT:    pushl %edi
 900 ; X86-NEXT:    pushl %esi
 901 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 902 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %edi
 903 ; X86-NEXT:    movl %ecx, %esi
 904 ; X86-NEXT:    addl %edi, %esi
 905 ; X86-NEXT:    adcl $0, %esi
 906 ; X86-NEXT:    movl $-252645135, %ebx # imm = 0xF0F0F0F1
 907 ; X86-NEXT:    movl %esi, %eax
 908 ; X86-NEXT:    mull %ebx
 909 ; X86-NEXT:    movl %edx, %eax
 910 ; X86-NEXT:    andl $-16, %eax
 911 ; X86-NEXT:    shrl $4, %edx
 912 ; X86-NEXT:    addl %eax, %edx
 913 ; X86-NEXT:    subl %edx, %esi
 914 ; X86-NEXT:    subl %esi, %ecx
 915 ; X86-NEXT:    sbbl $0, %edi
 916 ; X86-NEXT:    movl %ecx, %eax
 917 ; X86-NEXT:    mull %ebx
 918 ; X86-NEXT:    imull $-252645136, %ecx, %ecx # imm = 0xF0F0F0F0
 919 ; X86-NEXT:    addl %ecx, %edx
 920 ; X86-NEXT:    imull $-252645135, %edi, %ecx # imm = 0xF0F0F0F1
 921 ; X86-NEXT:    addl %ecx, %edx
 922 ; X86-NEXT:    popl %esi
 923 ; X86-NEXT:    popl %edi
 924 ; X86-NEXT:    popl %ebx
 925 ; X86-NEXT:    retl
 926 ;
 927 ; X64-LABEL: udiv_i64_17:
 928 ; X64:       # %bb.0: # %entry
 929 ; X64-NEXT:    movq %rdi, %rax
 930 ; X64-NEXT:    movabsq $-1085102592571150095, %rcx # imm = 0xF0F0F0F0F0F0F0F1
 931 ; X64-NEXT:    mulq %rcx
 932 ; X64-NEXT:    movq %rdx, %rax
 933 ; X64-NEXT:    shrq $4, %rax
 934 ; X64-NEXT:    retq
 935 entry:
 936   %rem = udiv i64 %x, 17
 937   ret i64 %rem
 938 }
 939
 940 define i64 @udiv_i64_255(i64 %x) nounwind {
 941 ; X86-LABEL: udiv_i64_255:
 942 ; X86:       # %bb.0: # %entry
 943 ; X86-NEXT:    pushl %esi
 944 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 945 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %esi
 946 ; X86-NEXT:    movl %ecx, %eax
 947 ; X86-NEXT:    addl %esi, %eax
 948 ; X86-NEXT:    adcl $0, %eax
 949 ; X86-NEXT:    movl $-2139062143, %edx # imm = 0x80808081
 950 ; X86-NEXT:    mull %edx
 951 ; X86-NEXT:    shrl $7, %edx
 952 ; X86-NEXT:    movl %edx, %eax
 953 ; X86-NEXT:    shll $8, %eax
 954 ; X86-NEXT:    subl %eax, %edx
 955 ; X86-NEXT:    movl %ecx, %eax
 956 ; X86-NEXT:    addl %esi, %eax
 957 ; X86-NEXT:    adcl %edx, %eax
 958 ; X86-NEXT:    subl %eax, %ecx
 959 ; X86-NEXT:    sbbl $0, %esi
 960 ; X86-NEXT:    movl $-16843009, %edx # imm = 0xFEFEFEFF
 961 ; X86-NEXT:    movl %ecx, %eax
 962 ; X86-NEXT:    mull %edx
 963 ; X86-NEXT:    imull $-16843010, %ecx, %ecx # imm = 0xFEFEFEFE
 964 ; X86-NEXT:    addl %ecx, %edx
 965 ; X86-NEXT:    imull $-16843009, %esi, %ecx # imm = 0xFEFEFEFF
 966 ; X86-NEXT:    addl %ecx, %edx
 967 ; X86-NEXT:    popl %esi
 968 ; X86-NEXT:    retl
 969 ;
 970 ; X64-LABEL: udiv_i64_255:
 971 ; X64:       # %bb.0: # %entry
 972 ; X64-NEXT:    movq %rdi, %rax
 973 ; X64-NEXT:    movabsq $-9187201950435737471, %rcx # imm = 0x8080808080808081
 974 ; X64-NEXT:    mulq %rcx
 975 ; X64-NEXT:    movq %rdx, %rax
 976 ; X64-NEXT:    shrq $7, %rax
 977 ; X64-NEXT:    retq
 978 entry:
 979   %rem = udiv i64 %x, 255
 980   ret i64 %rem
 981 }
 982
 983 define i64 @udiv_i64_257(i64 %x) nounwind {
 984 ; X86-LABEL: udiv_i64_257:
 985 ; X86:       # %bb.0: # %entry
 986 ; X86-NEXT:    pushl %ebx
 987 ; X86-NEXT:    pushl %edi
 988 ; X86-NEXT:    pushl %esi
 989 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 990 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %edi
 991 ; X86-NEXT:    movl %ecx, %esi
 992 ; X86-NEXT:    addl %edi, %esi
 993 ; X86-NEXT:    adcl $0, %esi
 994 ; X86-NEXT:    movl $-16711935, %ebx # imm = 0xFF00FF01
 995 ; X86-NEXT:    movl %esi, %eax
 996 ; X86-NEXT:    mull %ebx
 997 ; X86-NEXT:    movl %edx, %eax
 998 ; X86-NEXT:    andl $-256, %eax
 999 ; X86-NEXT:    shrl $8, %edx
1000 ; X86-NEXT:    addl %eax, %edx
1001 ; X86-NEXT:    subl %edx, %esi
1002 ; X86-NEXT:    subl %esi, %ecx
1003 ; X86-NEXT:    sbbl $0, %edi
1004 ; X86-NEXT:    movl %ecx, %eax
1005 ; X86-NEXT:    mull %ebx
1006 ; X86-NEXT:    imull $-16711936, %ecx, %ecx # imm = 0xFF00FF00
1007 ; X86-NEXT:    addl %ecx, %edx
1008 ; X86-NEXT:    imull $-16711935, %edi, %ecx # imm = 0xFF00FF01
1009 ; X86-NEXT:    addl %ecx, %edx
1010 ; X86-NEXT:    popl %esi
1011 ; X86-NEXT:    popl %edi
1012 ; X86-NEXT:    popl %ebx
1013 ; X86-NEXT:    retl
1014 ;
1015 ; X64-LABEL: udiv_i64_257:
1016 ; X64:       # %bb.0: # %entry
1017 ; X64-NEXT:    movq %rdi, %rax
1018 ; X64-NEXT:    movabsq $-71777214294589695, %rcx # imm = 0xFF00FF00FF00FF01
1019 ; X64-NEXT:    mulq %rcx
1020 ; X64-NEXT:    movq %rdx, %rax
1021 ; X64-NEXT:    shrq $8, %rax
1022 ; X64-NEXT:    retq
1023 entry:
1024   %rem = udiv i64 %x, 257
1025   ret i64 %rem
1026 }
1027
1028 define i64 @udiv_i64_65535(i64 %x) nounwind {
1029 ; X86-LABEL: udiv_i64_65535:
1030 ; X86:       # %bb.0: # %entry
1031 ; X86-NEXT:    pushl %esi
1032 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
1033 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %esi
1034 ; X86-NEXT:    movl %ecx, %eax
1035 ; X86-NEXT:    addl %esi, %eax
1036 ; X86-NEXT:    adcl $0, %eax
1037 ; X86-NEXT:    movl $-2147450879, %edx # imm = 0x80008001
1038 ; X86-NEXT:    mull %edx
1039 ; X86-NEXT:    shrl $15, %edx
1040 ; X86-NEXT:    movl %edx, %eax
1041 ; X86-NEXT:    shll $16, %eax
1042 ; X86-NEXT:    subl %eax, %edx
1043 ; X86-NEXT:    movl %ecx, %eax
1044 ; X86-NEXT:    addl %esi, %eax
1045 ; X86-NEXT:    adcl %edx, %eax
1046 ; X86-NEXT:    subl %eax, %ecx
1047 ; X86-NEXT:    sbbl $0, %esi
1048 ; X86-NEXT:    movl $-65537, %edx # imm = 0xFFFEFFFF
1049 ; X86-NEXT:    movl %ecx, %eax
1050 ; X86-NEXT:    mull %edx
1051 ; X86-NEXT:    imull $-65538, %ecx, %ecx # imm = 0xFFFEFFFE
1052 ; X86-NEXT:    addl %ecx, %edx
1053 ; X86-NEXT:    movl %esi, %ecx
1054 ; X86-NEXT:    shll $16, %ecx
1055 ; X86-NEXT:    addl %esi, %ecx
1056 ; X86-NEXT:    subl %ecx, %edx
1057 ; X86-NEXT:    popl %esi
1058 ; X86-NEXT:    retl
1059 ;
1060 ; X64-LABEL: udiv_i64_65535:
1061 ; X64:       # %bb.0: # %entry
1062 ; X64-NEXT:    movq %rdi, %rax
1063 ; X64-NEXT:    movabsq $-9223231297218904063, %rcx # imm = 0x8000800080008001
1064 ; X64-NEXT:    mulq %rcx
1065 ; X64-NEXT:    movq %rdx, %rax
1066 ; X64-NEXT:    shrq $15, %rax
1067 ; X64-NEXT:    retq
1068 entry:
1069   %rem = udiv i64 %x, 65535
1070   ret i64 %rem
1071 }
1072
1073 define i64 @udiv_i64_65537(i64 %x) nounwind {
1074 ; X86-LABEL: udiv_i64_65537:
1075 ; X86:       # %bb.0: # %entry
1076 ; X86-NEXT:    pushl %ebx
1077 ; X86-NEXT:    pushl %edi
1078 ; X86-NEXT:    pushl %esi
1079 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
1080 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %edi
1081 ; X86-NEXT:    movl %ecx, %esi
1082 ; X86-NEXT:    addl %edi, %esi
1083 ; X86-NEXT:    adcl $0, %esi
1084 ; X86-NEXT:    movl $-65535, %ebx # imm = 0xFFFF0001
1085 ; X86-NEXT:    movl %esi, %eax
1086 ; X86-NEXT:    mull %ebx
1087 ; X86-NEXT:    movl %edx, %eax
1088 ; X86-NEXT:    shrl $16, %eax
1089 ; X86-NEXT:    shldl $16, %edx, %eax
1090 ; X86-NEXT:    subl %eax, %esi
1091 ; X86-NEXT:    subl %esi, %ecx
1092 ; X86-NEXT:    sbbl $0, %edi
1093 ; X86-NEXT:    movl %ecx, %eax
1094 ; X86-NEXT:    mull %ebx
1095 ; X86-NEXT:    shll $16, %ecx
1096 ; X86-NEXT:    subl %ecx, %edx
1097 ; X86-NEXT:    movl %edi, %ecx
1098 ; X86-NEXT:    shll $16, %ecx
1099 ; X86-NEXT:    subl %ecx, %edi
1100 ; X86-NEXT:    addl %edi, %edx
1101 ; X86-NEXT:    popl %esi
1102 ; X86-NEXT:    popl %edi
1103 ; X86-NEXT:    popl %ebx
1104 ; X86-NEXT:    retl
1105 ;
1106 ; X64-LABEL: udiv_i64_65537:
1107 ; X64:       # %bb.0: # %entry
1108 ; X64-NEXT:    movq %rdi, %rax
1109 ; X64-NEXT:    movabsq $-281470681808895, %rcx # imm = 0xFFFF0000FFFF0001
1110 ; X64-NEXT:    mulq %rcx
1111 ; X64-NEXT:    movq %rdx, %rax
1112 ; X64-NEXT:    shrq $16, %rax
1113 ; X64-NEXT:    retq
1114 entry:
1115   %rem = udiv i64 %x, 65537
1116   ret i64 %rem
1117 }
1118
1119 define i64 @udiv_i64_12(i64 %x) nounwind {
1120 ; X86-LABEL: udiv_i64_12:
1121 ; X86:       # %bb.0: # %entry
1122 ; X86-NEXT:    pushl %ebx
1123 ; X86-NEXT:    pushl %edi
1124 ; X86-NEXT:    pushl %esi
1125 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
1126 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %edi
1127 ; X86-NEXT:    shrdl $2, %edi, %ecx
1128 ; X86-NEXT:    shrl $2, %edi
1129 ; X86-NEXT:    movl %ecx, %esi
1130 ; X86-NEXT:    addl %edi, %esi
1131 ; X86-NEXT:    adcl $0, %esi
1132 ; X86-NEXT:    movl $-1431655765, %ebx # imm = 0xAAAAAAAB
1133 ; X86-NEXT:    movl %esi, %eax
1134 ; X86-NEXT:    mull %ebx
1135 ; X86-NEXT:    shrl %edx
1136 ; X86-NEXT:    leal (%edx,%edx,2), %eax
1137 ; X86-NEXT:    subl %eax, %esi
1138 ; X86-NEXT:    subl %esi, %ecx
1139 ; X86-NEXT:    sbbl $0, %edi
1140 ; X86-NEXT:    movl %ecx, %eax
1141 ; X86-NEXT:    mull %ebx
1142 ; X86-NEXT:    imull $-1431655766, %ecx, %ecx # imm = 0xAAAAAAAA
1143 ; X86-NEXT:    addl %ecx, %edx
1144 ; X86-NEXT:    imull $-1431655765, %edi, %ecx # imm = 0xAAAAAAAB
1145 ; X86-NEXT:    addl %ecx, %edx
1146 ; X86-NEXT:    popl %esi
1147 ; X86-NEXT:    popl %edi
1148 ; X86-NEXT:    popl %ebx
1149 ; X86-NEXT:    retl
1150 ;
1151 ; X64-LABEL: udiv_i64_12:
1152 ; X64:       # %bb.0: # %entry
1153 ; X64-NEXT:    movq %rdi, %rax
1154 ; X64-NEXT:    movabsq $-6148914691236517205, %rcx # imm = 0xAAAAAAAAAAAAAAAB
1155 ; X64-NEXT:    mulq %rcx
1156 ; X64-NEXT:    movq %rdx, %rax
1157 ; X64-NEXT:    shrq $3, %rax
1158 ; X64-NEXT:    retq
1159 entry:
1160   %rem = udiv i64 %x, 12
1161   ret i64 %rem
1162 }
1163
1164 ; Make sure we don't inline expand for optsize.
1165 define i64 @urem_i64_3_optsize(i64 %x) nounwind optsize {
1166 ; X86-LABEL: urem_i64_3_optsize:
1167 ; X86:       # %bb.0: # %entry
1168 ; X86-NEXT:    subl $12, %esp
1169 ; X86-NEXT:    pushl $0
1170 ; X86-NEXT:    pushl $3
1171 ; X86-NEXT:    pushl {{[0-9]+}}(%esp)
1172 ; X86-NEXT:    pushl {{[0-9]+}}(%esp)
1173 ; X86-NEXT:    calll __umoddi3
1174 ; X86-NEXT:    addl $28, %esp
1175 ; X86-NEXT:    retl
1176 ;
1177 ; X64-LABEL: urem_i64_3_optsize:
1178 ; X64:       # %bb.0: # %entry
1179 ; X64-NEXT:    movabsq $-6148914691236517205, %rcx # imm = 0xAAAAAAAAAAAAAAAB
1180 ; X64-NEXT:    movq %rdi, %rax
1181 ; X64-NEXT:    mulq %rcx
1182 ; X64-NEXT:    shrq %rdx
1183 ; X64-NEXT:    leaq (%rdx,%rdx,2), %rax
1184 ; X64-NEXT:    subq %rax, %rdi
1185 ; X64-NEXT:    movq %rdi, %rax
1186 ; X64-NEXT:    retq
1187 entry:
1188   %rem = urem i64 %x, 3
1189   ret i64 %rem
1190 }
1191