llvm/test/CodeGen/X86/addcarry.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
   2 ; RUN: llc < %s -mtriple=x86_64-unknown | FileCheck %s
   3
   4 declare { i8, i64 } @llvm.x86.addcarry.64(i8, i64, i64)
   5 declare { i64, i1 } @llvm.uadd.with.overflow.i64(i64, i64) #1
   6 declare { i64, i1 } @llvm.usub.with.overflow.i64(i64, i64) #1
   7 declare { i128, i1 } @llvm.sadd.with.overflow.i128(i128, i128)
   8
   9 define i128 @add128(i128 %a, i128 %b) nounwind {
  10 ; CHECK-LABEL: add128:
  11 ; CHECK:       # %bb.0: # %entry
  12 ; CHECK-NEXT:    movq %rdi, %rax
  13 ; CHECK-NEXT:    addq %rdx, %rax
  14 ; CHECK-NEXT:    adcq %rcx, %rsi
  15 ; CHECK-NEXT:    movq %rsi, %rdx
  16 ; CHECK-NEXT:    retq
  17 entry:
  18   %0 = add i128 %a, %b
  19   ret i128 %0
  20 }
  21
  22 define void @add128_rmw(ptr %a, i128 %b) nounwind {
  23 ; CHECK-LABEL: add128_rmw:
  24 ; CHECK:       # %bb.0: # %entry
  25 ; CHECK-NEXT:    addq %rsi, (%rdi)
  26 ; CHECK-NEXT:    adcq %rdx, 8(%rdi)
  27 ; CHECK-NEXT:    retq
  28 entry:
  29   %0 = load i128, ptr %a
  30   %1 = add i128 %0, %b
  31   store i128 %1, ptr %a
  32   ret void
  33 }
  34
  35 define void @add128_rmw2(i128 %a, ptr %b) nounwind {
  36 ; CHECK-LABEL: add128_rmw2:
  37 ; CHECK:       # %bb.0: # %entry
  38 ; CHECK-NEXT:    addq %rdi, (%rdx)
  39 ; CHECK-NEXT:    adcq %rsi, 8(%rdx)
  40 ; CHECK-NEXT:    retq
  41 entry:
  42   %0 = load i128, ptr %b
  43   %1 = add i128 %a, %0
  44   store i128 %1, ptr %b
  45   ret void
  46 }
  47
  48 define i256 @add256(i256 %a, i256 %b) nounwind {
  49 ; CHECK-LABEL: add256:
  50 ; CHECK:       # %bb.0: # %entry
  51 ; CHECK-NEXT:    movq %rdi, %rax
  52 ; CHECK-NEXT:    addq {{[0-9]+}}(%rsp), %rsi
  53 ; CHECK-NEXT:    adcq {{[0-9]+}}(%rsp), %rdx
  54 ; CHECK-NEXT:    adcq {{[0-9]+}}(%rsp), %rcx
  55 ; CHECK-NEXT:    adcq {{[0-9]+}}(%rsp), %r8
  56 ; CHECK-NEXT:    movq %rcx, 16(%rdi)
  57 ; CHECK-NEXT:    movq %rdx, 8(%rdi)
  58 ; CHECK-NEXT:    movq %rsi, (%rdi)
  59 ; CHECK-NEXT:    movq %r8, 24(%rdi)
  60 ; CHECK-NEXT:    retq
  61 entry:
  62   %0 = add i256 %a, %b
  63   ret i256 %0
  64 }
  65
  66 define void @add256_rmw(ptr %a, i256 %b) nounwind {
  67 ; CHECK-LABEL: add256_rmw:
  68 ; CHECK:       # %bb.0: # %entry
  69 ; CHECK-NEXT:    addq %rsi, (%rdi)
  70 ; CHECK-NEXT:    adcq %rdx, 8(%rdi)
  71 ; CHECK-NEXT:    adcq %rcx, 16(%rdi)
  72 ; CHECK-NEXT:    adcq %r8, 24(%rdi)
  73 ; CHECK-NEXT:    retq
  74 entry:
  75   %0 = load i256, ptr %a
  76   %1 = add i256 %0, %b
  77   store i256 %1, ptr %a
  78   ret void
  79 }
  80
  81 define void @add256_rmw2(i256 %a, ptr %b) nounwind {
  82 ; CHECK-LABEL: add256_rmw2:
  83 ; CHECK:       # %bb.0: # %entry
  84 ; CHECK-NEXT:    addq %rdi, (%r8)
  85 ; CHECK-NEXT:    adcq %rsi, 8(%r8)
  86 ; CHECK-NEXT:    adcq %rdx, 16(%r8)
  87 ; CHECK-NEXT:    adcq %rcx, 24(%r8)
  88 ; CHECK-NEXT:    retq
  89 entry:
  90   %0 = load i256, ptr %b
  91   %1 = add i256 %a, %0
  92   store i256 %1, ptr %b
  93   ret void
  94 }
  95
  96 define void @a(ptr nocapture %s, ptr nocapture %t, i64 %a, i64 %b, i64 %c) nounwind {
  97 ; CHECK-LABEL: a:
  98 ; CHECK:       # %bb.0: # %entry
  99 ; CHECK-NEXT:    addq %rcx, %rdx
 100 ; CHECK-NEXT:    adcq $0, %r8
 101 ; CHECK-NEXT:    movq %r8, (%rdi)
 102 ; CHECK-NEXT:    movq %rdx, (%rsi)
 103 ; CHECK-NEXT:    retq
 104 entry:
 105  %0 = zext i64 %a to i128
 106  %1 = zext i64 %b to i128
 107  %2 = add i128 %1, %0
 108  %3 = zext i64 %c to i128
 109  %4 = shl i128 %3, 64
 110  %5 = add i128 %4, %2
 111  %6 = lshr i128 %5, 64
 112  %7 = trunc i128 %6 to i64
 113  store i64 %7, ptr %s, align 8
 114  %8 = trunc i128 %2 to i64
 115  store i64 %8, ptr %t, align 8
 116  ret void
 117 }
 118
 119 define void @b(ptr nocapture %r, i64 %a, i64 %b, i32 %c) nounwind {
 120 ; CHECK-LABEL: b:
 121 ; CHECK:       # %bb.0: # %entry
 122 ; CHECK-NEXT:    addq %rdx, %rsi
 123 ; CHECK-NEXT:    adcl $0, %ecx
 124 ; CHECK-NEXT:    movl %ecx, (%rdi)
 125 ; CHECK-NEXT:    retq
 126 entry:
 127  %0 = zext i64 %a to i128
 128  %1 = zext i64 %b to i128
 129  %2 = zext i32 %c to i128
 130  %3 = add i128 %1, %0
 131  %4 = lshr i128 %3, 64
 132  %5 = add i128 %4, %2
 133  %6 = trunc i128 %5 to i32
 134  store i32 %6, ptr %r, align 4
 135  ret void
 136 }
 137
 138 define void @c(ptr nocapture %r, i64 %a, i64 %b, i16 %c) nounwind {
 139 ; CHECK-LABEL: c:
 140 ; CHECK:       # %bb.0: # %entry
 141 ; CHECK-NEXT:    addq %rdx, %rsi
 142 ; CHECK-NEXT:    adcw $0, %cx
 143 ; CHECK-NEXT:    movw %cx, (%rdi)
 144 ; CHECK-NEXT:    retq
 145 entry:
 146  %0 = zext i64 %a to i128
 147  %1 = zext i64 %b to i128
 148  %2 = zext i16 %c to i128
 149  %3 = add i128 %1, %0
 150  %4 = lshr i128 %3, 64
 151  %5 = add i128 %4, %2
 152  %6 = trunc i128 %5 to i16
 153  store i16 %6, ptr %r, align 4
 154  ret void
 155 }
 156
 157 define void @d(ptr nocapture %r, i64 %a, i64 %b, i8 %c) nounwind {
 158 ; CHECK-LABEL: d:
 159 ; CHECK:       # %bb.0: # %entry
 160 ; CHECK-NEXT:    addq %rdx, %rsi
 161 ; CHECK-NEXT:    adcb $0, %cl
 162 ; CHECK-NEXT:    movb %cl, (%rdi)
 163 ; CHECK-NEXT:    retq
 164 entry:
 165  %0 = zext i64 %a to i128
 166  %1 = zext i64 %b to i128
 167  %2 = zext i8 %c to i128
 168  %3 = add i128 %1, %0
 169  %4 = lshr i128 %3, 64
 170  %5 = add i128 %4, %2
 171  %6 = trunc i128 %5 to i8
 172  store i8 %6, ptr %r, align 4
 173  ret void
 174 }
 175
 176 define i8 @e(ptr nocapture %a, i32 %b) nounwind {
 177 ; CHECK-LABEL: e:
 178 ; CHECK:       # %bb.0:
 179 ; CHECK-NEXT:    # kill: def $esi killed $esi def $rsi
 180 ; CHECK-NEXT:    movl (%rdi), %ecx
 181 ; CHECK-NEXT:    leal (%rsi,%rcx), %edx
 182 ; CHECK-NEXT:    addl %esi, %edx
 183 ; CHECK-NEXT:    setb %al
 184 ; CHECK-NEXT:    addl %ecx, %esi
 185 ; CHECK-NEXT:    movl %edx, (%rdi)
 186 ; CHECK-NEXT:    adcb $0, %al
 187 ; CHECK-NEXT:    retq
 188   %1 = load i32, ptr %a, align 4
 189   %2 = add i32 %1, %b
 190   %3 = icmp ult i32 %2, %b
 191   %4 = zext i1 %3 to i8
 192   %5 = add i32 %2, %b
 193   store i32 %5, ptr %a, align 4
 194   %6 = icmp ult i32 %5, %b
 195   %7 = zext i1 %6 to i8
 196   %8 = add nuw nsw i8 %7, %4
 197   ret i8 %8
 198 }
 199
 200 %scalar = type { [4 x i64] }
 201
 202 define %scalar @pr31719(ptr nocapture readonly %this, %scalar %arg.b) nounwind {
 203 ; CHECK-LABEL: pr31719:
 204 ; CHECK:       # %bb.0: # %entry
 205 ; CHECK-NEXT:    movq %rdi, %rax
 206 ; CHECK-NEXT:    addq (%rsi), %rdx
 207 ; CHECK-NEXT:    adcq 8(%rsi), %rcx
 208 ; CHECK-NEXT:    adcq 16(%rsi), %r8
 209 ; CHECK-NEXT:    adcq 24(%rsi), %r9
 210 ; CHECK-NEXT:    movq %rdx, (%rdi)
 211 ; CHECK-NEXT:    movq %rcx, 8(%rdi)
 212 ; CHECK-NEXT:    movq %r8, 16(%rdi)
 213 ; CHECK-NEXT:    movq %r9, 24(%rdi)
 214 ; CHECK-NEXT:    retq
 215 entry:
 216   %0 = extractvalue %scalar %arg.b, 0
 217   %.elt = extractvalue [4 x i64] %0, 0
 218   %.elt24 = extractvalue [4 x i64] %0, 1
 219   %.elt26 = extractvalue [4 x i64] %0, 2
 220   %.elt28 = extractvalue [4 x i64] %0, 3
 221   %1 = load i64, ptr %this, align 8
 222   %2 = zext i64 %1 to i128
 223   %3 = zext i64 %.elt to i128
 224   %4 = add nuw nsw i128 %2, %3
 225   %5 = trunc i128 %4 to i64
 226   %6 = lshr i128 %4, 64
 227   %7 = getelementptr inbounds %scalar , ptr %this, i64 0, i32 0, i64 1
 228   %8 = load i64, ptr %7, align 8
 229   %9 = zext i64 %8 to i128
 230   %10 = zext i64 %.elt24 to i128
 231   %11 = add nuw nsw i128 %9, %10
 232   %12 = add nuw nsw i128 %11, %6
 233   %13 = trunc i128 %12 to i64
 234   %14 = lshr i128 %12, 64
 235   %15 = getelementptr inbounds %scalar , ptr %this, i64 0, i32 0, i64 2
 236   %16 = load i64, ptr %15, align 8
 237   %17 = zext i64 %16 to i128
 238   %18 = zext i64 %.elt26 to i128
 239   %19 = add nuw nsw i128 %17, %18
 240   %20 = add nuw nsw i128 %19, %14
 241   %21 = trunc i128 %20 to i64
 242   %22 = lshr i128 %20, 64
 243   %23 = getelementptr inbounds %scalar , ptr %this, i64 0, i32 0, i64 3
 244   %24 = load i64, ptr %23, align 8
 245   %25 = zext i64 %24 to i128
 246   %26 = zext i64 %.elt28 to i128
 247   %27 = add nuw nsw i128 %25, %26
 248   %28 = add nuw nsw i128 %27, %22
 249   %29 = trunc i128 %28 to i64
 250   %30 = insertvalue [4 x i64] undef, i64 %5, 0
 251   %31 = insertvalue [4 x i64] %30, i64 %13, 1
 252   %32 = insertvalue [4 x i64] %31, i64 %21, 2
 253   %33 = insertvalue [4 x i64] %32, i64 %29, 3
 254   %34 = insertvalue %scalar undef, [4 x i64] %33, 0
 255   ret %scalar %34
 256 }
 257
 258 %accumulator= type { i64, i64, i32 }
 259
 260 define void @muladd(ptr nocapture %this, i64 %arg.a, i64 %arg.b) nounwind {
 261 ; CHECK-LABEL: muladd:
 262 ; CHECK:       # %bb.0: # %entry
 263 ; CHECK-NEXT:    movq %rdx, %rax
 264 ; CHECK-NEXT:    mulq %rsi
 265 ; CHECK-NEXT:    addq %rax, (%rdi)
 266 ; CHECK-NEXT:    adcq %rdx, 8(%rdi)
 267 ; CHECK-NEXT:    adcl $0, 16(%rdi)
 268 ; CHECK-NEXT:    retq
 269 entry:
 270   %0 = zext i64 %arg.a to i128
 271   %1 = zext i64 %arg.b to i128
 272   %2 = mul nuw i128 %1, %0
 273   %3 = load i64, ptr %this, align 8
 274   %4 = zext i64 %3 to i128
 275   %5 = add i128 %4, %2
 276   %6 = trunc i128 %5 to i64
 277   store i64 %6, ptr %this, align 8
 278   %7 = lshr i128 %5, 64
 279   %8 = getelementptr inbounds %accumulator, ptr %this, i64 0, i32 1
 280   %9 = load i64, ptr %8, align 8
 281   %10 = zext i64 %9 to i128
 282   %11 = add nuw nsw i128 %7, %10
 283   %12 = trunc i128 %11 to i64
 284   store i64 %12, ptr %8, align 8
 285   %13 = lshr i128 %11, 64
 286   %14 = getelementptr inbounds %accumulator, ptr %this, i64 0, i32 2
 287   %15 = load i32, ptr %14, align 4
 288   %16 = zext i32 %15 to i128
 289   %17 = add nuw nsw i128 %13, %16
 290   %18 = trunc i128 %17 to i32
 291   store i32 %18, ptr %14, align 4
 292   ret void
 293 }
 294
 295 define i64 @shiftadd(i64 %a, i64 %b, i64 %c, i64 %d) nounwind {
 296 ; CHECK-LABEL: shiftadd:
 297 ; CHECK:       # %bb.0: # %entry
 298 ; CHECK-NEXT:    movq %rdx, %rax
 299 ; CHECK-NEXT:    addq %rsi, %rdi
 300 ; CHECK-NEXT:    adcq %rcx, %rax
 301 ; CHECK-NEXT:    retq
 302 entry:
 303   %0 = zext i64 %a to i128
 304   %1 = zext i64 %b to i128
 305   %2 = add i128 %0, %1
 306   %3 = lshr i128 %2, 64
 307   %4 = trunc i128 %3 to i64
 308   %5 = add i64 %c, %d
 309   %6 = add i64 %4, %5
 310   ret i64 %6
 311 }
 312
 313 %S = type { [4 x i64] }
 314
 315 define %S @readd(ptr nocapture readonly %this, %S %arg.b) nounwind {
 316 ; CHECK-LABEL: readd:
 317 ; CHECK:       # %bb.0: # %entry
 318 ; CHECK-NEXT:    movq %rdi, %rax
 319 ; CHECK-NEXT:    addq (%rsi), %rdx
 320 ; CHECK-NEXT:    movq 8(%rsi), %rdi
 321 ; CHECK-NEXT:    adcq $0, %rdi
 322 ; CHECK-NEXT:    setb %r10b
 323 ; CHECK-NEXT:    movzbl %r10b, %r10d
 324 ; CHECK-NEXT:    addq %rcx, %rdi
 325 ; CHECK-NEXT:    adcq 16(%rsi), %r10
 326 ; CHECK-NEXT:    setb %cl
 327 ; CHECK-NEXT:    movzbl %cl, %ecx
 328 ; CHECK-NEXT:    addq %r8, %r10
 329 ; CHECK-NEXT:    adcq 24(%rsi), %rcx
 330 ; CHECK-NEXT:    addq %r9, %rcx
 331 ; CHECK-NEXT:    movq %rdx, (%rax)
 332 ; CHECK-NEXT:    movq %rdi, 8(%rax)
 333 ; CHECK-NEXT:    movq %r10, 16(%rax)
 334 ; CHECK-NEXT:    movq %rcx, 24(%rax)
 335 ; CHECK-NEXT:    retq
 336 entry:
 337   %0 = extractvalue %S %arg.b, 0
 338   %.elt6 = extractvalue [4 x i64] %0, 1
 339   %.elt8 = extractvalue [4 x i64] %0, 2
 340   %.elt10 = extractvalue [4 x i64] %0, 3
 341   %.elt = extractvalue [4 x i64] %0, 0
 342   %1 = load i64, ptr %this, align 8
 343   %2 = zext i64 %1 to i128
 344   %3 = zext i64 %.elt to i128
 345   %4 = add nuw nsw i128 %2, %3
 346   %5 = trunc i128 %4 to i64
 347   %6 = lshr i128 %4, 64
 348   %7 = getelementptr inbounds %S, ptr %this, i64 0, i32 0, i64 1
 349   %8 = load i64, ptr %7, align 8
 350   %9 = zext i64 %8 to i128
 351   %10 = add nuw nsw i128 %6, %9
 352   %11 = zext i64 %.elt6 to i128
 353   %12 = add nuw nsw i128 %10, %11
 354   %13 = trunc i128 %12 to i64
 355   %14 = lshr i128 %12, 64
 356   %15 = getelementptr inbounds %S, ptr %this, i64 0, i32 0, i64 2
 357   %16 = load i64, ptr %15, align 8
 358   %17 = zext i64 %16 to i128
 359   %18 = add nuw nsw i128 %14, %17
 360   %19 = zext i64 %.elt8 to i128
 361   %20 = add nuw nsw i128 %18, %19
 362   %21 = lshr i128 %20, 64
 363   %22 = trunc i128 %20 to i64
 364   %23 = getelementptr inbounds %S, ptr %this, i64 0,i32 0, i64 3
 365   %24 = load i64, ptr %23, align 8
 366   %25 = zext i64 %24 to i128
 367   %26 = add nuw nsw i128 %21, %25
 368   %27 = zext i64 %.elt10 to i128
 369   %28 = add nuw nsw i128 %26, %27
 370   %29 = trunc i128 %28 to i64
 371   %30 = insertvalue [4 x i64] undef, i64 %5, 0
 372   %31 = insertvalue [4 x i64] %30, i64 %13, 1
 373   %32 = insertvalue [4 x i64] %31, i64 %22, 2
 374   %33 = insertvalue [4 x i64] %32, i64 %29, 3
 375   %34 = insertvalue %S undef, [4 x i64] %33, 0
 376   ret %S %34
 377 }
 378
 379 define i128 @addcarry1_not(i128 %n) nounwind {
 380 ; CHECK-LABEL: addcarry1_not:
 381 ; CHECK:       # %bb.0:
 382 ; CHECK-NEXT:    movq %rdi, %rax
 383 ; CHECK-NEXT:    xorl %edx, %edx
 384 ; CHECK-NEXT:    negq %rax
 385 ; CHECK-NEXT:    sbbq %rsi, %rdx
 386 ; CHECK-NEXT:    retq
 387   %1 = xor i128 %n, -1
 388   %2 = add i128 %1, 1
 389   ret i128 %2
 390 }
 391
 392 define { i128, i1 } @saddo_not_1(i128 %x) nounwind {
 393 ; CHECK-LABEL: saddo_not_1:
 394 ; CHECK:       # %bb.0:
 395 ; CHECK-NEXT:    movq %rdi, %rax
 396 ; CHECK-NEXT:    xorl %edx, %edx
 397 ; CHECK-NEXT:    negq %rax
 398 ; CHECK-NEXT:    sbbq %rsi, %rdx
 399 ; CHECK-NEXT:    seto %cl
 400 ; CHECK-NEXT:    retq
 401   %not = xor i128 %x, -1
 402   %r = call { i128, i1 } @llvm.sadd.with.overflow.i128(i128 %not, i128 1)
 403   ret { i128, i1 } %r
 404 }
 405
 406 define { i128, i1 } @saddo_carry_not_1(i128 %x) nounwind {
 407 ; CHECK-LABEL: saddo_carry_not_1:
 408 ; CHECK:       # %bb.0:
 409 ; CHECK-NEXT:    movq %rdi, %rax
 410 ; CHECK-NEXT:    negq %rax
 411 ; CHECK-NEXT:    movl $1, %edx
 412 ; CHECK-NEXT:    sbbq %rsi, %rdx
 413 ; CHECK-NEXT:    seto %cl
 414 ; CHECK-NEXT:    retq
 415   %not = xor i128 %x, -1
 416   %r = call { i128, i1 } @llvm.sadd.with.overflow.i128(i128 %not, i128 u0x10000000000000001)
 417   ret { i128, i1 } %r
 418 }
 419
 420 define i128 @addcarry_to_subcarry(i64 %a, i64 %b) nounwind {
 421 ; CHECK-LABEL: addcarry_to_subcarry:
 422 ; CHECK:       # %bb.0:
 423 ; CHECK-NEXT:    movq %rdi, %rax
 424 ; CHECK-NEXT:    cmpq %rsi, %rdi
 425 ; CHECK-NEXT:    notq %rsi
 426 ; CHECK-NEXT:    setae %cl
 427 ; CHECK-NEXT:    addb $-1, %cl
 428 ; CHECK-NEXT:    adcq $0, %rax
 429 ; CHECK-NEXT:    setb %cl
 430 ; CHECK-NEXT:    movzbl %cl, %edx
 431 ; CHECK-NEXT:    addq %rsi, %rax
 432 ; CHECK-NEXT:    adcq $0, %rdx
 433 ; CHECK-NEXT:    retq
 434   %notb = xor i64 %b, -1
 435   %notb128 = zext i64 %notb to i128
 436   %a128 = zext i64 %a to i128
 437   %sum1 = add i128 %a128, 1
 438   %sub1 = add i128 %sum1, %notb128
 439   %hi = lshr i128 %sub1, 64
 440   %sum2 = add i128 %hi, %a128
 441   %sub2 = add i128 %sum2, %notb128
 442   ret i128 %sub2
 443 }
 444
 445 ; basic test for combineCarryDiamond()
 446 define { i64, i64, i1 } @addcarry_2x64(i64 %x0, i64 %x1, i64 %y0, i64 %y1) nounwind {
 447 ; CHECK-LABEL: addcarry_2x64:
 448 ; CHECK:       # %bb.0:
 449 ; CHECK-NEXT:    movq %rdi, %rax
 450 ; CHECK-NEXT:    addq %rdx, %rax
 451 ; CHECK-NEXT:    adcq %rcx, %rsi
 452 ; CHECK-NEXT:    setb %cl
 453 ; CHECK-NEXT:    movq %rsi, %rdx
 454 ; CHECK-NEXT:    retq
 455   %t0 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %x0, i64 %y0)
 456   %s0 = extractvalue { i64, i1 } %t0, 0
 457   %k0 = extractvalue { i64, i1 } %t0, 1
 458
 459   %t1 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %x1, i64 %y1)
 460   %s1 = extractvalue { i64, i1 } %t1, 0
 461   %k1 = extractvalue { i64, i1 } %t1, 1
 462
 463   %zk0 = zext i1 %k0 to i64
 464   %t2 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %s1, i64 %zk0)
 465   %s2 = extractvalue { i64, i1 } %t2, 0
 466   %k2 = extractvalue { i64, i1 } %t2, 1
 467   %k = or i1 %k1, %k2
 468
 469   %r0 = insertvalue { i64, i64, i1 } poison, i64 %s0, 0
 470   %r1 = insertvalue { i64, i64, i1 } %r0, i64 %s2, 1
 471   %r = insertvalue { i64, i64, i1 } %r1, i1 %k, 2
 472   ret { i64, i64, i1 } %r
 473 }
 474
 475 ; basic test for combineCarryDiamond() with carries behind zext/and/trunc
 476 define { i64, i64, i1 } @addcarry_hidden_2x64(i64 %x0, i64 %x1, i64 %y0, i64 %y1) nounwind {
 477 ; CHECK-LABEL: addcarry_hidden_2x64:
 478 ; CHECK:       # %bb.0:
 479 ; CHECK-NEXT:    movq %rdi, %rax
 480 ; CHECK-NEXT:    addq %rdx, %rax
 481 ; CHECK-NEXT:    adcq %rcx, %rsi
 482 ; CHECK-NEXT:    setb %cl
 483 ; CHECK-NEXT:    movq %rsi, %rdx
 484 ; CHECK-NEXT:    retq
 485   %t0 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %x0, i64 %y0)
 486   %s0 = extractvalue { i64, i1 } %t0, 0
 487   %k0 = extractvalue { i64, i1 } %t0, 1
 488
 489   %t1 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %x1, i64 %y1)
 490   %s1 = extractvalue { i64, i1 } %t1, 0
 491   %k1 = extractvalue { i64, i1 } %t1, 1
 492   %k1i8 = zext i1 %k1 to i8
 493   %k1and = and i8 %k1i8, 1
 494   %k1hidden = trunc i8 %k1and to i1
 495
 496   %zk0 = zext i1 %k0 to i64
 497   %t2 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %s1, i64 %zk0)
 498   %s2 = extractvalue { i64, i1 } %t2, 0
 499   %k2 = extractvalue { i64, i1 } %t2, 1
 500
 501   %k = or i1 %k1hidden, %k2
 502
 503   %r0 = insertvalue { i64, i64, i1 } poison, i64 %s0, 0
 504   %r1 = insertvalue { i64, i64, i1 } %r0, i64 %s2, 1
 505   %r = insertvalue { i64, i64, i1 } %r1, i1 %k, 2
 506   ret { i64, i64, i1 } %r
 507 }
 508
 509 ; basic test for combineCarryDiamond() with carries behind zext/and/trunc
 510 define { i64, i64, i1 } @addcarry_hidden2_2x64(i64 %x0, i64 %x1, i64 %y0, i64 %y1) nounwind {
 511 ; CHECK-LABEL: addcarry_hidden2_2x64:
 512 ; CHECK:       # %bb.0:
 513 ; CHECK-NEXT:    movq %rdi, %rax
 514 ; CHECK-NEXT:    addq %rdx, %rax
 515 ; CHECK-NEXT:    adcq %rcx, %rsi
 516 ; CHECK-NEXT:    setb %cl
 517 ; CHECK-NEXT:    movq %rsi, %rdx
 518 ; CHECK-NEXT:    retq
 519   %t0 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %x0, i64 %y0)
 520   %s0 = extractvalue { i64, i1 } %t0, 0
 521   %k0 = extractvalue { i64, i1 } %t0, 1
 522
 523   %t1 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %x1, i64 %y1)
 524   %s1 = extractvalue { i64, i1 } %t1, 0
 525   %k1 = extractvalue { i64, i1 } %t1, 1
 526
 527   %zk0 = zext i1 %k0 to i64
 528   %t2 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %s1, i64 %zk0)
 529   %s2 = extractvalue { i64, i1 } %t2, 0
 530   %k2 = extractvalue { i64, i1 } %t2, 1
 531   %k2i8 = zext i1 %k2 to i8
 532   %k2and = and i8 %k2i8, 1
 533   %k2hidden = trunc i8 %k2and to i1
 534
 535   %k = or i1 %k1, %k2hidden
 536
 537   %r0 = insertvalue { i64, i64, i1 } poison, i64 %s0, 0
 538   %r1 = insertvalue { i64, i64, i1 } %r0, i64 %s2, 1
 539   %r = insertvalue { i64, i64, i1 } %r1, i1 %k, 2
 540   ret { i64, i64, i1 } %r
 541 }
 542
 543 ; basic test for combineCarryDiamond() with or operands reversed
 544 define { i64, i64, i1 } @addcarry_2x64_or_reversed(i64 %x0, i64 %x1, i64 %y0, i64 %y1) nounwind {
 545 ; CHECK-LABEL: addcarry_2x64_or_reversed:
 546 ; CHECK:       # %bb.0:
 547 ; CHECK-NEXT:    movq %rdi, %rax
 548 ; CHECK-NEXT:    addq %rdx, %rax
 549 ; CHECK-NEXT:    adcq %rcx, %rsi
 550 ; CHECK-NEXT:    setb %cl
 551 ; CHECK-NEXT:    movq %rsi, %rdx
 552 ; CHECK-NEXT:    retq
 553   %t0 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %x0, i64 %y0)
 554   %s0 = extractvalue { i64, i1 } %t0, 0
 555   %k0 = extractvalue { i64, i1 } %t0, 1
 556
 557   %t1 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %x1, i64 %y1)
 558   %s1 = extractvalue { i64, i1 } %t1, 0
 559   %k1 = extractvalue { i64, i1 } %t1, 1
 560
 561   %zk0 = zext i1 %k0 to i64
 562   %t2 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %zk0, i64 %s1)  ; reversed
 563   %s2 = extractvalue { i64, i1 } %t2, 0
 564   %k2 = extractvalue { i64, i1 } %t2, 1
 565   %k = or i1 %k2, %k1  ; reverse natural order of operands
 566
 567   %r0 = insertvalue { i64, i64, i1 } poison, i64 %s0, 0
 568   %r1 = insertvalue { i64, i64, i1 } %r0, i64 %s2, 1
 569   %r = insertvalue { i64, i64, i1 } %r1, i1 %k, 2
 570   ret { i64, i64, i1 } %r
 571 }
 572
 573 ; basic test for combineCarryDiamond() with xor operands reversed
 574 define { i64, i64, i1 } @addcarry_2x64_xor_reversed(i64 %x0, i64 %x1, i64 %y0, i64 %y1) nounwind {
 575 ; CHECK-LABEL: addcarry_2x64_xor_reversed:
 576 ; CHECK:       # %bb.0:
 577 ; CHECK-NEXT:    movq %rdi, %rax
 578 ; CHECK-NEXT:    addq %rdx, %rax
 579 ; CHECK-NEXT:    adcq %rcx, %rsi
 580 ; CHECK-NEXT:    setb %cl
 581 ; CHECK-NEXT:    movq %rsi, %rdx
 582 ; CHECK-NEXT:    retq
 583   %t0 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %x0, i64 %y0)
 584   %s0 = extractvalue { i64, i1 } %t0, 0
 585   %k0 = extractvalue { i64, i1 } %t0, 1
 586
 587   %t1 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %x1, i64 %y1)
 588   %s1 = extractvalue { i64, i1 } %t1, 0
 589   %k1 = extractvalue { i64, i1 } %t1, 1
 590
 591   %zk0 = zext i1 %k0 to i64
 592   %t2 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %s1, i64 %zk0)
 593   %s2 = extractvalue { i64, i1 } %t2, 0
 594   %k2 = extractvalue { i64, i1 } %t2, 1
 595   %k = xor i1 %k2, %k1  ; reverse natural order of operands
 596
 597   %r0 = insertvalue { i64, i64, i1 } poison, i64 %s0, 0
 598   %r1 = insertvalue { i64, i64, i1 } %r0, i64 %s2, 1
 599   %r = insertvalue { i64, i64, i1 } %r1, i1 %k, 2
 600   ret { i64, i64, i1 } %r
 601 }
 602
 603 ; basic test for combineCarryDiamond() with and operands reversed
 604 define { i64, i64, i1 } @addcarry_2x64_and_reversed(i64 %x0, i64 %x1, i64 %y0, i64 %y1) nounwind {
 605 ; CHECK-LABEL: addcarry_2x64_and_reversed:
 606 ; CHECK:       # %bb.0:
 607 ; CHECK-NEXT:    movq %rdi, %rax
 608 ; CHECK-NEXT:    addq %rdx, %rax
 609 ; CHECK-NEXT:    adcq %rcx, %rsi
 610 ; CHECK-NEXT:    movq %rsi, %rdx
 611 ; CHECK-NEXT:    xorl %ecx, %ecx
 612 ; CHECK-NEXT:    retq
 613   %t0 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %x0, i64 %y0)
 614   %s0 = extractvalue { i64, i1 } %t0, 0
 615   %k0 = extractvalue { i64, i1 } %t0, 1
 616
 617   %t1 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %x1, i64 %y1)
 618   %s1 = extractvalue { i64, i1 } %t1, 0
 619   %k1 = extractvalue { i64, i1 } %t1, 1
 620
 621   %zk0 = zext i1 %k0 to i64
 622   %t2 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %s1, i64 %zk0)
 623   %s2 = extractvalue { i64, i1 } %t2, 0
 624   %k2 = extractvalue { i64, i1 } %t2, 1
 625   %k = and i1 %k2, %k1  ; reverse natural order of operands
 626
 627   %r0 = insertvalue { i64, i64, i1 } poison, i64 %s0, 0
 628   %r1 = insertvalue { i64, i64, i1 } %r0, i64 %s2, 1
 629   %r = insertvalue { i64, i64, i1 } %r1, i1 %k, 2
 630   ret { i64, i64, i1 } %r
 631 }
 632
 633 ; basic test for combineCarryDiamond() with add operands reversed
 634 define { i64, i64, i1 } @addcarry_2x64_add_reversed(i64 %x0, i64 %x1, i64 %y0, i64 %y1) nounwind {
 635 ; CHECK-LABEL: addcarry_2x64_add_reversed:
 636 ; CHECK:       # %bb.0:
 637 ; CHECK-NEXT:    movq %rdi, %rax
 638 ; CHECK-NEXT:    addq %rdx, %rax
 639 ; CHECK-NEXT:    adcq %rcx, %rsi
 640 ; CHECK-NEXT:    setb %cl
 641 ; CHECK-NEXT:    movq %rsi, %rdx
 642 ; CHECK-NEXT:    retq
 643   %t0 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %x0, i64 %y0)
 644   %s0 = extractvalue { i64, i1 } %t0, 0
 645   %k0 = extractvalue { i64, i1 } %t0, 1
 646
 647   %t1 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %x1, i64 %y1)
 648   %s1 = extractvalue { i64, i1 } %t1, 0
 649   %k1 = extractvalue { i64, i1 } %t1, 1
 650
 651   %zk0 = zext i1 %k0 to i64
 652   %t2 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %s1, i64 %zk0)
 653   %s2 = extractvalue { i64, i1 } %t2, 0
 654   %k2 = extractvalue { i64, i1 } %t2, 1
 655   %k = add i1 %k2, %k1  ; reverse natural order of operands
 656
 657   %r0 = insertvalue { i64, i64, i1 } poison, i64 %s0, 0
 658   %r1 = insertvalue { i64, i64, i1 } %r0, i64 %s2, 1
 659   %r = insertvalue { i64, i64, i1 } %r1, i1 %k, 2
 660   ret { i64, i64, i1 } %r
 661 }
 662
 663 ; Here %carryin is considered as valid carry flag for combining into ADDCARRY
 664 ; although %carryin does not come from any carry-producing instruction.
 665 define { i64, i1 } @addcarry_fake_carry(i64 %a, i64 %b, i1 %carryin) nounwind {
 666 ; CHECK-LABEL: addcarry_fake_carry:
 667 ; CHECK:       # %bb.0:
 668 ; CHECK-NEXT:    movq %rdi, %rax
 669 ; CHECK-NEXT:    btl $0, %edx
 670 ; CHECK-NEXT:    adcq %rsi, %rax
 671 ; CHECK-NEXT:    setb %dl
 672 ; CHECK-NEXT:    retq
 673   %t1 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %a, i64 %b)
 674   %partial = extractvalue { i64, i1 } %t1, 0
 675   %k1 = extractvalue { i64, i1 } %t1, 1
 676
 677   %zcarryin = zext i1 %carryin to i64
 678   %sum = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %partial, i64 %zcarryin)
 679   %k2 = extractvalue { i64, i1 } %sum, 1
 680
 681   %carryout = or i1 %k1, %k2
 682
 683   %ret = insertvalue { i64, i1 } %sum, i1 %carryout, 1
 684   ret { i64, i1 } %ret
 685 }
 686
 687 ; negative test: %carryin does not look like carry
 688 define { i64, i1 } @addcarry_carry_not_zext(i64 %a, i64 %b, i64 %carryin) nounwind {
 689 ; CHECK-LABEL: addcarry_carry_not_zext:
 690 ; CHECK:       # %bb.0:
 691 ; CHECK-NEXT:    movq %rdi, %rax
 692 ; CHECK-NEXT:    addq %rsi, %rax
 693 ; CHECK-NEXT:    setb %cl
 694 ; CHECK-NEXT:    addq %rdx, %rax
 695 ; CHECK-NEXT:    setb %dl
 696 ; CHECK-NEXT:    orb %cl, %dl
 697 ; CHECK-NEXT:    retq
 698   %t1 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %a, i64 %b)
 699   %partial = extractvalue { i64, i1 } %t1, 0
 700   %k1 = extractvalue { i64, i1 } %t1, 1
 701
 702   %sum = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %partial, i64 %carryin)
 703   %k2 = extractvalue { i64, i1 } %sum, 1
 704
 705   %carryout = or i1 %k1, %k2
 706
 707   %ret = insertvalue { i64, i1 } %sum, i1 %carryout, 1
 708   ret { i64, i1 } %ret
 709 }
 710
 711 ; negative test: %carryin does not look like carry
 712 define { i64, i1 } @addcarry_carry_not_i1(i64 %a, i64 %b, i8 %carryin) nounwind {
 713 ; CHECK-LABEL: addcarry_carry_not_i1:
 714 ; CHECK:       # %bb.0:
 715 ; CHECK-NEXT:    addq %rsi, %rdi
 716 ; CHECK-NEXT:    setb %cl
 717 ; CHECK-NEXT:    movzbl %dl, %eax
 718 ; CHECK-NEXT:    addq %rdi, %rax
 719 ; CHECK-NEXT:    setb %dl
 720 ; CHECK-NEXT:    orb %cl, %dl
 721 ; CHECK-NEXT:    retq
 722   %t1 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %a, i64 %b)
 723   %partial = extractvalue { i64, i1 } %t1, 0
 724   %k1 = extractvalue { i64, i1 } %t1, 1
 725
 726   %zcarryin = zext i8 %carryin to i64
 727   %sum = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %partial, i64 %zcarryin)
 728   %k2 = extractvalue { i64, i1 } %sum, 1
 729
 730   %carryout = or i1 %k1, %k2
 731
 732   %ret = insertvalue { i64, i1 } %sum, i1 %carryout, 1
 733   ret { i64, i1 } %ret
 734 }
 735
 736 ; Check that we can reconstruct a carry if it is masked.
 737 define { i64, i1 } @addcarry_carry_and_1(i64 %a, i64 %b, i64 %carryin) nounwind {
 738 ; CHECK-LABEL: addcarry_carry_and_1:
 739 ; CHECK:       # %bb.0:
 740 ; CHECK-NEXT:    movq %rdi, %rax
 741 ; CHECK-NEXT:    btl $0, %edx
 742 ; CHECK-NEXT:    adcq %rsi, %rax
 743 ; CHECK-NEXT:    setb %dl
 744 ; CHECK-NEXT:    retq
 745   %t1 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %a, i64 %b)
 746   %partial = extractvalue { i64, i1 } %t1, 0
 747   %k1 = extractvalue { i64, i1 } %t1, 1
 748
 749   %mcarryin = and i64 %carryin, 1
 750   %sum = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %partial, i64 %mcarryin)
 751   %k2 = extractvalue { i64, i1 } %sum, 1
 752
 753   %carryout = or i1 %k1, %k2
 754
 755   %ret = insertvalue { i64, i1 } %sum, i1 %carryout, 1
 756   ret { i64, i1 } %ret
 757 }
 758
 759 ; negative test for combineCarryDiamond(): uaddo mixed with usubo
 760 define { i64, i64, i1 } @addcarry_mixed_2x64(i64 %x0, i64 %x1, i64 %y0, i64 %y1) nounwind {
 761 ; CHECK-LABEL: addcarry_mixed_2x64:
 762 ; CHECK:       # %bb.0:
 763 ; CHECK-NEXT:    movq %rdi, %rax
 764 ; CHECK-NEXT:    addq %rcx, %rsi
 765 ; CHECK-NEXT:    setb %dil
 766 ; CHECK-NEXT:    addq %rdx, %rax
 767 ; CHECK-NEXT:    sbbq $0, %rsi
 768 ; CHECK-NEXT:    setb %cl
 769 ; CHECK-NEXT:    orb %dil, %cl
 770 ; CHECK-NEXT:    movq %rsi, %rdx
 771 ; CHECK-NEXT:    retq
 772   %t0 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %x0, i64 %y0)
 773   %s0 = extractvalue { i64, i1 } %t0, 0
 774   %k0 = extractvalue { i64, i1 } %t0, 1
 775
 776   %t1 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %x1, i64 %y1)
 777   %s1 = extractvalue { i64, i1 } %t1, 0
 778   %k1 = extractvalue { i64, i1 } %t1, 1
 779
 780   %zk0 = zext i1 %k0 to i64
 781   %t2 = call { i64, i1 } @llvm.usub.with.overflow.i64(i64 %s1, i64 %zk0)
 782   %s2 = extractvalue { i64, i1 } %t2, 0
 783   %k2 = extractvalue { i64, i1 } %t2, 1
 784   %k = or i1 %k1, %k2
 785
 786   %r0 = insertvalue { i64, i64, i1 } poison, i64 %s0, 0
 787   %r1 = insertvalue { i64, i64, i1 } %r0, i64 %s2, 1
 788   %r = insertvalue { i64, i64, i1 } %r1, i1 %k, 2
 789   ret { i64, i64, i1 } %r
 790 }
 791
 792 %struct.U320 = type { [5 x i64] }
 793
 794 define i32 @add_U320_without_i128_add(ptr nocapture dereferenceable(40) %0, i64 %1, i64 %2, i64 %3, i64 %4, i64 %5) nounwind {
 795 ; CHECK-LABEL: add_U320_without_i128_add:
 796 ; CHECK:       # %bb.0:
 797 ; CHECK-NEXT:    movq 16(%rdi), %rax
 798 ; CHECK-NEXT:    movq 24(%rdi), %r10
 799 ; CHECK-NEXT:    movq 32(%rdi), %r11
 800 ; CHECK-NEXT:    addq %rsi, (%rdi)
 801 ; CHECK-NEXT:    adcq %rdx, 8(%rdi)
 802 ; CHECK-NEXT:    movq %rax, %rdx
 803 ; CHECK-NEXT:    adcq %rcx, %rdx
 804 ; CHECK-NEXT:    addq %rcx, %rax
 805 ; CHECK-NEXT:    movq %r10, %rcx
 806 ; CHECK-NEXT:    adcq %r8, %rcx
 807 ; CHECK-NEXT:    cmpq %rax, %rdx
 808 ; CHECK-NEXT:    adcq $0, %rcx
 809 ; CHECK-NEXT:    leaq (%r11,%r9), %rsi
 810 ; CHECK-NEXT:    addq %r8, %r10
 811 ; CHECK-NEXT:    movq %r11, %r8
 812 ; CHECK-NEXT:    adcq %r9, %r8
 813 ; CHECK-NEXT:    cmpq %r10, %rcx
 814 ; CHECK-NEXT:    adcq $0, %r8
 815 ; CHECK-NEXT:    xorl %eax, %eax
 816 ; CHECK-NEXT:    cmpq %rsi, %r8
 817 ; CHECK-NEXT:    setb %al
 818 ; CHECK-NEXT:    addq %r9, %r11
 819 ; CHECK-NEXT:    movq %rdx, 16(%rdi)
 820 ; CHECK-NEXT:    movq %rcx, 24(%rdi)
 821 ; CHECK-NEXT:    movq %r8, 32(%rdi)
 822 ; CHECK-NEXT:    adcl $0, %eax
 823 ; CHECK-NEXT:    retq
 824   %7 = load i64, ptr %0, align 8
 825   %8 = getelementptr inbounds %struct.U320, ptr %0, i64 0, i32 0, i64 1
 826   %9 = load i64, ptr %8, align 8
 827   %10 = getelementptr inbounds %struct.U320, ptr %0, i64 0, i32 0, i64 2
 828   %11 = load i64, ptr %10, align 8
 829   %12 = getelementptr inbounds %struct.U320, ptr %0, i64 0, i32 0, i64 3
 830   %13 = load i64, ptr %12, align 8
 831   %14 = getelementptr inbounds %struct.U320, ptr %0, i64 0, i32 0, i64 4
 832   %15 = load i64, ptr %14, align 8
 833   %16 = add i64 %7, %1
 834   %17 = add i64 %9, %2
 835   %18 = icmp ult i64 %16, %1
 836   %19 = zext i1 %18 to i64
 837   %20 = add i64 %17, %19
 838   %21 = add i64 %11, %3
 839   %22 = icmp ult i64 %17, %9
 840   %23 = zext i1 %22 to i64
 841   %24 = icmp ult i64 %20, %17
 842   %25 = zext i1 %24 to i64
 843   %26 = add i64 %21, %23
 844   %27 = add i64 %26, %25
 845   %28 = add i64 %13, %4
 846   %29 = icmp ult i64 %21, %11
 847   %30 = zext i1 %29 to i64
 848   %31 = icmp ult i64 %27, %21
 849   %32 = zext i1 %31 to i64
 850   %33 = add i64 %28, %30
 851   %34 = add i64 %33, %32
 852   %35 = add i64 %15, %5
 853   %36 = icmp ult i64 %28, %13
 854   %37 = zext i1 %36 to i64
 855   %38 = icmp ult i64 %34, %28
 856   %39 = zext i1 %38 to i64
 857   %40 = add i64 %35, %37
 858   %41 = add i64 %40, %39
 859   store i64 %16, ptr %0, align 8
 860   store i64 %20, ptr %8, align 8
 861   store i64 %27, ptr %10, align 8
 862   store i64 %34, ptr %12, align 8
 863   store i64 %41, ptr %14, align 8
 864   %42 = icmp ult i64 %35, %15
 865   %43 = zext i1 %42 to i32
 866   %44 = icmp ult i64 %41, %35
 867   %45 = zext i1 %44 to i32
 868   %46 = add nuw nsw i32 %45, %43
 869   ret i32 %46
 870 }
 871
 872 define i32 @add_U320_without_i128_or(ptr nocapture dereferenceable(40) %0, i64 %1, i64 %2, i64 %3, i64 %4, i64 %5) nounwind {
 873 ; CHECK-LABEL: add_U320_without_i128_or:
 874 ; CHECK:       # %bb.0:
 875 ; CHECK-NEXT:    addq %rsi, (%rdi)
 876 ; CHECK-NEXT:    adcq %rdx, 8(%rdi)
 877 ; CHECK-NEXT:    adcq %rcx, 16(%rdi)
 878 ; CHECK-NEXT:    adcq %r8, 24(%rdi)
 879 ; CHECK-NEXT:    adcq %r9, 32(%rdi)
 880 ; CHECK-NEXT:    setb %al
 881 ; CHECK-NEXT:    movzbl %al, %eax
 882 ; CHECK-NEXT:    retq
 883   %7 = load i64, ptr %0, align 8
 884   %8 = getelementptr inbounds %struct.U320, ptr %0, i64 0, i32 0, i64 1
 885   %9 = load i64, ptr %8, align 8
 886   %10 = getelementptr inbounds %struct.U320, ptr %0, i64 0, i32 0, i64 2
 887   %11 = load i64, ptr %10, align 8
 888   %12 = getelementptr inbounds %struct.U320, ptr %0, i64 0, i32 0, i64 3
 889   %13 = load i64, ptr %12, align 8
 890   %14 = getelementptr inbounds %struct.U320, ptr %0, i64 0, i32 0, i64 4
 891   %15 = load i64, ptr %14, align 8
 892   %16 = add i64 %7, %1
 893   %17 = add i64 %9, %2
 894   %18 = icmp ult i64 %16, %1
 895   %19 = zext i1 %18 to i64
 896   %20 = add i64 %17, %19
 897   %21 = add i64 %11, %3
 898   %22 = icmp ult i64 %17, %9
 899   %23 = icmp ult i64 %20, %17
 900   %24 = or i1 %22, %23
 901   %25 = zext i1 %24 to i64
 902   %26 = add i64 %21, %25
 903   %27 = add i64 %13, %4
 904   %28 = icmp ult i64 %21, %11
 905   %29 = icmp ult i64 %26, %21
 906   %30 = or i1 %28, %29
 907   %31 = zext i1 %30 to i64
 908   %32 = add i64 %27, %31
 909   %33 = add i64 %15, %5
 910   %34 = icmp ult i64 %27, %13
 911   %35 = icmp ult i64 %32, %27
 912   %36 = or i1 %34, %35
 913   %37 = zext i1 %36 to i64
 914   %38 = add i64 %33, %37
 915   store i64 %16, ptr %0, align 8
 916   store i64 %20, ptr %8, align 8
 917   store i64 %26, ptr %10, align 8
 918   store i64 %32, ptr %12, align 8
 919   store i64 %38, ptr %14, align 8
 920   %39 = icmp ult i64 %33, %15
 921   %40 = icmp ult i64 %38, %33
 922   %41 = or i1 %39, %40
 923   %42 = zext i1 %41 to i32
 924   ret i32 %42
 925 }
 926
 927 define i32 @add_U320_without_i128_xor(ptr nocapture dereferenceable(40) %0, i64 %1, i64 %2, i64 %3, i64 %4, i64 %5) nounwind {
 928 ; CHECK-LABEL: add_U320_without_i128_xor:
 929 ; CHECK:       # %bb.0:
 930 ; CHECK-NEXT:    addq %rsi, (%rdi)
 931 ; CHECK-NEXT:    adcq %rdx, 8(%rdi)
 932 ; CHECK-NEXT:    adcq %rcx, 16(%rdi)
 933 ; CHECK-NEXT:    adcq %r8, 24(%rdi)
 934 ; CHECK-NEXT:    adcq %r9, 32(%rdi)
 935 ; CHECK-NEXT:    setb %al
 936 ; CHECK-NEXT:    movzbl %al, %eax
 937 ; CHECK-NEXT:    retq
 938   %7 = load i64, ptr %0, align 8
 939   %8 = getelementptr inbounds %struct.U320, ptr %0, i64 0, i32 0, i64 1
 940   %9 = load i64, ptr %8, align 8
 941   %10 = getelementptr inbounds %struct.U320, ptr %0, i64 0, i32 0, i64 2
 942   %11 = load i64, ptr %10, align 8
 943   %12 = getelementptr inbounds %struct.U320, ptr %0, i64 0, i32 0, i64 3
 944   %13 = load i64, ptr %12, align 8
 945   %14 = getelementptr inbounds %struct.U320, ptr %0, i64 0, i32 0, i64 4
 946   %15 = load i64, ptr %14, align 8
 947   %16 = add i64 %7, %1
 948   %17 = add i64 %9, %2
 949   %18 = icmp ult i64 %16, %1
 950   %19 = zext i1 %18 to i64
 951   %20 = add i64 %17, %19
 952   %21 = add i64 %11, %3
 953   %22 = icmp ult i64 %17, %9
 954   %23 = icmp ult i64 %20, %17
 955   %24 = xor i1 %22, %23
 956   %25 = zext i1 %24 to i64
 957   %26 = add i64 %21, %25
 958   %27 = add i64 %13, %4
 959   %28 = icmp ult i64 %21, %11
 960   %29 = icmp ult i64 %26, %21
 961   %30 = xor i1 %28, %29
 962   %31 = zext i1 %30 to i64
 963   %32 = add i64 %27, %31
 964   %33 = add i64 %15, %5
 965   %34 = icmp ult i64 %27, %13
 966   %35 = icmp ult i64 %32, %27
 967   %36 = xor i1 %34, %35
 968   %37 = zext i1 %36 to i64
 969   %38 = add i64 %33, %37
 970   store i64 %16, ptr %0, align 8
 971   store i64 %20, ptr %8, align 8
 972   store i64 %26, ptr %10, align 8
 973   store i64 %32, ptr %12, align 8
 974   store i64 %38, ptr %14, align 8
 975   %39 = icmp ult i64 %33, %15
 976   %40 = icmp ult i64 %38, %33
 977   %41 = xor i1 %39, %40
 978   %42 = zext i1 %41 to i32
 979   ret i32 %42
 980 }
 981
 982 ; Either the primary addition can overflow or the addition of the carry, but
 983 ; they cannot both overflow.
 984 define i32 @bogus_add_U320_without_i128_and(ptr nocapture dereferenceable(40) %0, i64 %1, i64 %2, i64 %3, i64 %4, i64 %5) nounwind {
 985 ; CHECK-LABEL: bogus_add_U320_without_i128_and:
 986 ; CHECK:       # %bb.0:
 987 ; CHECK-NEXT:    addq %rsi, (%rdi)
 988 ; CHECK-NEXT:    adcq %rdx, 8(%rdi)
 989 ; CHECK-NEXT:    addq %rcx, 16(%rdi)
 990 ; CHECK-NEXT:    addq %r8, 24(%rdi)
 991 ; CHECK-NEXT:    addq %r9, 32(%rdi)
 992 ; CHECK-NEXT:    xorl %eax, %eax
 993 ; CHECK-NEXT:    retq
 994   %7 = load i64, ptr %0, align 8
 995   %8 = getelementptr inbounds %struct.U320, ptr %0, i64 0, i32 0, i64 1
 996   %9 = load i64, ptr %8, align 8
 997   %10 = getelementptr inbounds %struct.U320, ptr %0, i64 0, i32 0, i64 2
 998   %11 = load i64, ptr %10, align 8
 999   %12 = getelementptr inbounds %struct.U320, ptr %0, i64 0, i32 0, i64 3
1000   %13 = load i64, ptr %12, align 8
1001   %14 = getelementptr inbounds %struct.U320, ptr %0, i64 0, i32 0, i64 4
1002   %15 = load i64, ptr %14, align 8
1003   %16 = add i64 %7, %1
1004   %17 = add i64 %9, %2
1005   %18 = icmp ult i64 %16, %1
1006   %19 = zext i1 %18 to i64
1007   %20 = add i64 %17, %19
1008   %21 = add i64 %11, %3
1009   %22 = icmp ult i64 %17, %9
1010   %23 = icmp ult i64 %20, %17
1011   %24 = and i1 %22, %23
1012   %25 = zext i1 %24 to i64
1013   %26 = add i64 %21, %25
1014   %27 = add i64 %13, %4
1015   %28 = icmp ult i64 %21, %11
1016   %29 = icmp ult i64 %26, %21
1017   %30 = and i1 %28, %29
1018   %31 = zext i1 %30 to i64
1019   %32 = add i64 %27, %31
1020   %33 = add i64 %15, %5
1021   %34 = icmp ult i64 %27, %13
1022   %35 = icmp ult i64 %32, %27
1023   %36 = and i1 %34, %35
1024   %37 = zext i1 %36 to i64
1025   %38 = add i64 %33, %37
1026   store i64 %16, ptr %0, align 8
1027   store i64 %20, ptr %8, align 8
1028   store i64 %26, ptr %10, align 8
1029   store i64 %32, ptr %12, align 8
1030   store i64 %38, ptr %14, align 8
1031   %39 = icmp ult i64 %33, %15
1032   %40 = icmp ult i64 %38, %33
1033   %41 = and i1 %39, %40
1034   %42 = zext i1 %41 to i32
1035   ret i32 %42
1036 }
1037
1038 define void @add_U320_without_i128_or_no_ret(ptr nocapture dereferenceable(40) %0, i64 %1, i64 %2, i64 %3, i64 %4, i64 %5) nounwind {
1039 ; CHECK-LABEL: add_U320_without_i128_or_no_ret:
1040 ; CHECK:       # %bb.0:
1041 ; CHECK-NEXT:    addq %rsi, (%rdi)
1042 ; CHECK-NEXT:    adcq %rdx, 8(%rdi)
1043 ; CHECK-NEXT:    adcq %rcx, 16(%rdi)
1044 ; CHECK-NEXT:    adcq %r8, 24(%rdi)
1045 ; CHECK-NEXT:    adcq %r9, 32(%rdi)
1046 ; CHECK-NEXT:    retq
1047   %7 = load i64, ptr %0, align 8
1048   %8 = getelementptr inbounds %struct.U320, ptr %0, i64 0, i32 0, i64 1
1049   %9 = load i64, ptr %8, align 8
1050   %10 = getelementptr inbounds %struct.U320, ptr %0, i64 0, i32 0, i64 2
1051   %11 = load i64, ptr %10, align 8
1052   %12 = getelementptr inbounds %struct.U320, ptr %0, i64 0, i32 0, i64 3
1053   %13 = load i64, ptr %12, align 8
1054   %14 = getelementptr inbounds %struct.U320, ptr %0, i64 0, i32 0, i64 4
1055   %15 = load i64, ptr %14, align 8
1056   %16 = add i64 %7, %1
1057   %17 = add i64 %9, %2
1058   %18 = icmp ult i64 %16, %1
1059   %19 = zext i1 %18 to i64
1060   %20 = add i64 %17, %19
1061   %21 = add i64 %11, %3
1062   %22 = icmp ult i64 %17, %9
1063   %23 = icmp ult i64 %20, %17
1064   %24 = or i1 %22, %23
1065   %25 = zext i1 %24 to i64
1066   %26 = add i64 %21, %25
1067   %27 = add i64 %13, %4
1068   %28 = icmp ult i64 %21, %11
1069   %29 = icmp ult i64 %26, %21
1070   %30 = or i1 %28, %29
1071   %31 = zext i1 %30 to i64
1072   %32 = add i64 %27, %31
1073   %33 = add i64 %15, %5
1074   %34 = icmp ult i64 %27, %13
1075   %35 = icmp ult i64 %32, %27
1076   %36 = or i1 %34, %35
1077   %37 = zext i1 %36 to i64
1078   %38 = add i64 %33, %37
1079   store i64 %16, ptr %0, align 8
1080   store i64 %20, ptr %8, align 8
1081   store i64 %26, ptr %10, align 8
1082   store i64 %32, ptr %12, align 8
1083   store i64 %38, ptr %14, align 8
1084   ret void
1085 }
1086
1087 define i32 @add_U320_uaddo(ptr nocapture dereferenceable(40) %0, i64 %1, i64 %2, i64 %3, i64 %4, i64 %5) nounwind {
1088 ; CHECK-LABEL: add_U320_uaddo:
1089 ; CHECK:       # %bb.0:
1090 ; CHECK-NEXT:    addq %rsi, (%rdi)
1091 ; CHECK-NEXT:    adcq %rdx, 8(%rdi)
1092 ; CHECK-NEXT:    adcq %rcx, 16(%rdi)
1093 ; CHECK-NEXT:    adcq %r8, 24(%rdi)
1094 ; CHECK-NEXT:    adcq %r9, 32(%rdi)
1095 ; CHECK-NEXT:    setb %al
1096 ; CHECK-NEXT:    movzbl %al, %eax
1097 ; CHECK-NEXT:    retq
1098   %7 = load i64, ptr %0, align 8
1099   %8 = getelementptr inbounds %struct.U320, ptr %0, i64 0, i32 0, i64 1
1100   %9 = load i64, ptr %8, align 8
1101   %10 = getelementptr inbounds %struct.U320, ptr %0, i64 0, i32 0, i64 2
1102   %11 = load i64, ptr %10, align 8
1103   %12 = getelementptr inbounds %struct.U320, ptr %0, i64 0, i32 0, i64 3
1104   %13 = load i64, ptr %12, align 8
1105   %14 = getelementptr inbounds %struct.U320, ptr %0, i64 0, i32 0, i64 4
1106   %15 = load i64, ptr %14, align 8
1107   %16 = tail call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %7, i64 %1)
1108   %17 = extractvalue { i64, i1 } %16, 1
1109   %18 = extractvalue { i64, i1 } %16, 0
1110   %19 = zext i1 %17 to i64
1111   %20 = tail call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %9, i64 %2)
1112   %21 = extractvalue { i64, i1 } %20, 1
1113   %22 = extractvalue { i64, i1 } %20, 0
1114   %23 = tail call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %22, i64 %19)
1115   %24 = extractvalue { i64, i1 } %23, 1
1116   %25 = extractvalue { i64, i1 } %23, 0
1117   %26 = or i1 %21, %24
1118   %27 = zext i1 %26 to i64
1119   %28 = tail call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %11, i64 %3)
1120   %29 = extractvalue { i64, i1 } %28, 1
1121   %30 = extractvalue { i64, i1 } %28, 0
1122   %31 = tail call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %30, i64 %27)
1123   %32 = extractvalue { i64, i1 } %31, 1
1124   %33 = extractvalue { i64, i1 } %31, 0
1125   %34 = or i1 %29, %32
1126   %35 = zext i1 %34 to i64
1127   %36 = tail call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %13, i64 %4)
1128   %37 = extractvalue { i64, i1 } %36, 1
1129   %38 = extractvalue { i64, i1 } %36, 0
1130   %39 = tail call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %38, i64 %35)
1131   %40 = extractvalue { i64, i1 } %39, 1
1132   %41 = extractvalue { i64, i1 } %39, 0
1133   %42 = or i1 %37, %40
1134   %43 = zext i1 %42 to i64
1135   %44 = tail call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %15, i64 %5)
1136   %45 = extractvalue { i64, i1 } %44, 1
1137   %46 = extractvalue { i64, i1 } %44, 0
1138   %47 = tail call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %46, i64 %43)
1139   %48 = extractvalue { i64, i1 } %47, 1
1140   %49 = extractvalue { i64, i1 } %47, 0
1141   %50 = or i1 %45, %48
1142   store i64 %18, ptr %0, align 8
1143   store i64 %25, ptr %8, align 8
1144   store i64 %33, ptr %10, align 8
1145   store i64 %41, ptr %12, align 8
1146   store i64 %49, ptr %14, align 8
1147   %51 = zext i1 %50 to i32
1148   ret i32 %51
1149 }
1150
1151 %struct.U192 = type { [3 x i64] }
1152
1153 define void @PR39464(ptr noalias nocapture sret(%struct.U192) %0, ptr nocapture readonly dereferenceable(24) %1, ptr nocapture readonly dereferenceable(24) %2) nounwind {
1154 ; CHECK-LABEL: PR39464:
1155 ; CHECK:       # %bb.0:
1156 ; CHECK-NEXT:    movq %rdi, %rax
1157 ; CHECK-NEXT:    movq (%rsi), %rcx
1158 ; CHECK-NEXT:    addq (%rdx), %rcx
1159 ; CHECK-NEXT:    movq %rcx, (%rdi)
1160 ; CHECK-NEXT:    movq 8(%rsi), %rcx
1161 ; CHECK-NEXT:    adcq 8(%rdx), %rcx
1162 ; CHECK-NEXT:    movq %rcx, 8(%rdi)
1163 ; CHECK-NEXT:    movq 16(%rsi), %rcx
1164 ; CHECK-NEXT:    adcq 16(%rdx), %rcx
1165 ; CHECK-NEXT:    movq %rcx, 16(%rdi)
1166 ; CHECK-NEXT:    retq
1167   %4 = load i64, ptr %1, align 8
1168   %5 = load i64, ptr %2, align 8
1169   %6 = tail call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %4, i64 %5)
1170   %7 = extractvalue { i64, i1 } %6, 1
1171   %8 = extractvalue { i64, i1 } %6, 0
1172   %9 = zext i1 %7 to i64
1173   store i64 %8, ptr %0, align 8
1174   %10 = getelementptr inbounds %struct.U192, ptr %1, i64 0, i32 0, i64 1
1175   %11 = load i64, ptr %10, align 8
1176   %12 = getelementptr inbounds %struct.U192, ptr %2, i64 0, i32 0, i64 1
1177   %13 = load i64, ptr %12, align 8
1178   %14 = tail call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %11, i64 %13)
1179   %15 = extractvalue { i64, i1 } %14, 1
1180   %16 = extractvalue { i64, i1 } %14, 0
1181   %17 = tail call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %16, i64 %9)
1182   %18 = extractvalue { i64, i1 } %17, 1
1183   %19 = extractvalue { i64, i1 } %17, 0
1184   %20 = or i1 %15, %18
1185   %21 = zext i1 %20 to i64
1186   %22 = getelementptr inbounds %struct.U192, ptr %0, i64 0, i32 0, i64 1
1187   store i64 %19, ptr %22, align 8
1188   %23 = getelementptr inbounds %struct.U192, ptr %1, i64 0, i32 0, i64 2
1189   %24 = load i64, ptr %23, align 8
1190   %25 = getelementptr inbounds %struct.U192, ptr %2, i64 0, i32 0, i64 2
1191   %26 = load i64, ptr %25, align 8
1192   %27 = add i64 %24, %26
1193   %28 = add i64 %27, %21
1194   %29 = getelementptr inbounds %struct.U192, ptr %0, i64 0, i32 0, i64 2
1195   store i64 %28, ptr %29, align 8
1196   ret void
1197 }
1198
1199
1200 %uint128 = type { i64, i64 }
1201
1202 define zeroext i1 @uaddo_U128_without_i128_or(i64 %0, i64 %1, i64 %2, i64 %3, ptr nocapture %4) nounwind {
1203 ; CHECK-LABEL: uaddo_U128_without_i128_or:
1204 ; CHECK:       # %bb.0:
1205 ; CHECK-NEXT:    addq %rdx, %rdi
1206 ; CHECK-NEXT:    adcq %rcx, %rsi
1207 ; CHECK-NEXT:    setb %al
1208 ; CHECK-NEXT:    movq %rsi, (%r8)
1209 ; CHECK-NEXT:    movq %rdi, 8(%r8)
1210 ; CHECK-NEXT:    retq
1211   %6 = add i64 %2, %0
1212   %7 = icmp ult i64 %6, %0
1213   %8 = add i64 %3, %1
1214   %9 = icmp ult i64 %8, %1
1215   %10 = zext i1 %7 to i64
1216   %11 = add i64 %8, %10
1217   %12 = icmp ult i64 %11, %8
1218   %13 = or i1 %9, %12
1219   store i64 %11, ptr %4, align 8
1220   %14 = getelementptr inbounds %uint128, ptr %4, i64 0, i32 1
1221   store i64 %6, ptr %14, align 8
1222   ret i1 %13
1223 }
1224
1225
1226 %uint192 = type { i64, i64, i64 }
1227
1228 define void @add_U192_without_i128_or(ptr sret(%uint192) %0, i64 %1, i64 %2, i64 %3, i64 %4, i64 %5, i64 %6) nounwind {
1229 ; CHECK-LABEL: add_U192_without_i128_or:
1230 ; CHECK:       # %bb.0:
1231 ; CHECK-NEXT:    movq %rdi, %rax
1232 ; CHECK-NEXT:    addq %r8, %rsi
1233 ; CHECK-NEXT:    adcq %r9, %rdx
1234 ; CHECK-NEXT:    adcq {{[0-9]+}}(%rsp), %rcx
1235 ; CHECK-NEXT:    movq %rcx, (%rdi)
1236 ; CHECK-NEXT:    movq %rdx, 8(%rdi)
1237 ; CHECK-NEXT:    movq %rsi, 16(%rdi)
1238 ; CHECK-NEXT:    retq
1239   %8 = add i64 %4, %1
1240   %9 = icmp ult i64 %8, %1
1241   %10 = add i64 %5, %2
1242   %11 = icmp ult i64 %10, %2
1243   %12 = zext i1 %9 to i64
1244   %13 = add i64 %10, %12
1245   %14 = icmp ult i64 %13, %10
1246   %15 = or i1 %11, %14
1247   %16 = add i64 %6, %3
1248   %17 = zext i1 %15 to i64
1249   %18 = add i64 %16, %17
1250   store i64 %18, ptr %0, align 8
1251   %19 = getelementptr inbounds %uint192, ptr %0, i64 0, i32 1
1252   store i64 %13, ptr %19, align 8
1253   %20 = getelementptr inbounds %uint192, ptr %0, i64 0, i32 2
1254   store i64 %8, ptr %20, align 8
1255   ret void
1256 }
1257
1258
1259 %uint256 = type { %uint128, %uint128 }
1260
1261 ; Classic unrolled 256-bit addition implementation using i64 as the word type.
1262 ; It starts by adding least significant words and propagates carry to additions of the higher words.
1263 define void @add_U256_without_i128_or_by_i64_words(ptr sret(%uint256) %0, ptr %1, ptr %2) nounwind {
1264 ; CHECK-LABEL: add_U256_without_i128_or_by_i64_words:
1265 ; CHECK:       # %bb.0:
1266 ; CHECK-NEXT:    movq %rdi, %rax
1267 ; CHECK-NEXT:    movq (%rdx), %rcx
1268 ; CHECK-NEXT:    movq 8(%rdx), %rdi
1269 ; CHECK-NEXT:    addq (%rsi), %rcx
1270 ; CHECK-NEXT:    adcq 8(%rsi), %rdi
1271 ; CHECK-NEXT:    movq 16(%rdx), %r8
1272 ; CHECK-NEXT:    adcq 16(%rsi), %r8
1273 ; CHECK-NEXT:    movq 24(%rdx), %rdx
1274 ; CHECK-NEXT:    adcq 24(%rsi), %rdx
1275 ; CHECK-NEXT:    movq %rdx, (%rax)
1276 ; CHECK-NEXT:    movq %r8, 8(%rax)
1277 ; CHECK-NEXT:    movq %rdi, 16(%rax)
1278 ; CHECK-NEXT:    movq %rcx, 24(%rax)
1279 ; CHECK-NEXT:    retq
1280   %4 = load i64, ptr %1, align 8
1281   %5 = load i64, ptr %2, align 8
1282   %6 = add i64 %5, %4
1283   %7 = icmp ult i64 %6, %4
1284   %8 = getelementptr inbounds %uint256, ptr %1, i64 0, i32 0, i32 1
1285   %9 = load i64, ptr %8, align 8
1286   %10 = getelementptr inbounds %uint256, ptr %2, i64 0, i32 0, i32 1
1287   %11 = load i64, ptr %10, align 8
1288   %12 = add i64 %11, %9
1289   %13 = icmp ult i64 %12, %9
1290   %14 = zext i1 %7 to i64
1291   %15 = add i64 %12, %14
1292   %16 = icmp ult i64 %15, %14
1293   %17 = or i1 %13, %16
1294   %18 = getelementptr inbounds %uint256, ptr %1, i64 0, i32 1, i32 0
1295   %19 = load i64, ptr %18, align 8
1296   %20 = getelementptr inbounds %uint256, ptr %2, i64 0, i32 1, i32 0
1297   %21 = load i64, ptr %20, align 8
1298   %22 = add i64 %21, %19
1299   %23 = icmp ult i64 %22, %19
1300   %24 = zext i1 %17 to i64
1301   %25 = add i64 %22, %24
1302   %26 = icmp ult i64 %25, %24
1303   %27 = or i1 %23, %26
1304   %28 = getelementptr inbounds %uint256, ptr %1, i64 0, i32 1, i32 1
1305   %29 = load i64, ptr %28, align 8
1306   %30 = getelementptr inbounds %uint256, ptr %2, i64 0, i32 1, i32 1
1307   %31 = load i64, ptr %30, align 8
1308   %32 = add i64 %31, %29
1309   %33 = zext i1 %27 to i64
1310   %34 = add i64 %32, %33
1311   store i64 %34, ptr %0, align 8
1312   %35 = getelementptr inbounds %uint256, ptr %0, i64 0, i32 0, i32 1
1313   store i64 %25, ptr %35, align 8
1314   %36 = getelementptr inbounds %uint256, ptr %0, i64 0, i32 1, i32 0
1315   store i64 %15, ptr %36, align 8
1316   %37 = getelementptr inbounds %uint256, ptr %0, i64 0, i32 1, i32 1
1317   store i64 %6, ptr %37, align 8
1318   ret void
1319 }
1320
1321 ; The 256-bit addition implementation using two inlined uaddo procedures for U128 type { i64, i64 }.
1322 ; This is similar to how LLVM legalize types in CodeGen.
1323 define void @add_U256_without_i128_or_recursive(ptr sret(%uint256) %0, ptr %1, ptr %2) nounwind {
1324 ; CHECK-LABEL: add_U256_without_i128_or_recursive:
1325 ; CHECK:       # %bb.0:
1326 ; CHECK-NEXT:    movq %rdi, %rax
1327 ; CHECK-NEXT:    movq (%rdx), %rcx
1328 ; CHECK-NEXT:    movq 8(%rdx), %rdi
1329 ; CHECK-NEXT:    addq (%rsi), %rcx
1330 ; CHECK-NEXT:    adcq 8(%rsi), %rdi
1331 ; CHECK-NEXT:    movq 16(%rdx), %r8
1332 ; CHECK-NEXT:    movq 24(%rdx), %rdx
1333 ; CHECK-NEXT:    adcq 16(%rsi), %r8
1334 ; CHECK-NEXT:    adcq 24(%rsi), %rdx
1335 ; CHECK-NEXT:    movq %rcx, (%rax)
1336 ; CHECK-NEXT:    movq %rdi, 8(%rax)
1337 ; CHECK-NEXT:    movq %r8, 16(%rax)
1338 ; CHECK-NEXT:    movq %rdx, 24(%rax)
1339 ; CHECK-NEXT:    retq
1340   %4 = load i64, ptr %1, align 8
1341   %5 = getelementptr inbounds %uint256, ptr %1, i64 0, i32 0, i32 1
1342   %6 = load i64, ptr %5, align 8
1343   %7 = load i64, ptr %2, align 8
1344   %8 = getelementptr inbounds %uint256, ptr %2, i64 0, i32 0, i32 1
1345   %9 = load i64, ptr %8, align 8
1346   %10 = add i64 %7, %4
1347   %11 = icmp ult i64 %10, %4
1348   %12 = add i64 %9, %6
1349   %13 = icmp ult i64 %12, %6
1350   %14 = zext i1 %11 to i64
1351   %15 = add i64 %12, %14
1352   %16 = icmp ult i64 %15, %12
1353   %17 = or i1 %13, %16
1354   %18 = getelementptr inbounds %uint256, ptr %1, i64 0, i32 1, i32 0
1355   %19 = load i64, ptr %18, align 8
1356   %20 = getelementptr inbounds %uint256, ptr %1, i64 0, i32 1, i32 1
1357   %21 = load i64, ptr %20, align 8
1358   %22 = getelementptr inbounds %uint256, ptr %2, i64 0, i32 1, i32 0
1359   %23 = load i64, ptr %22, align 8
1360   %24 = getelementptr inbounds %uint256, ptr %2, i64 0, i32 1, i32 1
1361   %25 = load i64, ptr %24, align 8
1362   %26 = add i64 %23, %19
1363   %27 = icmp ult i64 %26, %19
1364   %28 = add i64 %25, %21
1365   %29 = zext i1 %27 to i64
1366   %30 = add i64 %28, %29
1367   %31 = zext i1 %17 to i64
1368   %32 = add i64 %26, %31
1369   %33 = icmp ult i64 %32, %26
1370   %34 = zext i1 %33 to i64
1371   %35 = add i64 %30, %34
1372   store i64 %10, ptr %0, align 8
1373   %36 = getelementptr inbounds %uint256, ptr %0, i64 0, i32 0, i32 1
1374   store i64 %15, ptr %36, align 8
1375   %37 = getelementptr inbounds %uint256, ptr %0, i64 0, i32 1, i32 0
1376   store i64 %32, ptr %37, align 8
1377   %38 = getelementptr inbounds %uint256, ptr %0, i64 0, i32 1, i32 1
1378   store i64 %35, ptr %38, align 8
1379   ret void
1380 }
1381
1382 define i32 @addcarry_ult(i32 %a, i32 %b, i32 %x, i32 %y) nounwind {
1383 ; CHECK-LABEL: addcarry_ult:
1384 ; CHECK:       # %bb.0:
1385 ; CHECK-NEXT:    movl %edi, %eax
1386 ; CHECK-NEXT:    cmpl %ecx, %edx
1387 ; CHECK-NEXT:    adcl %esi, %eax
1388 ; CHECK-NEXT:    retq
1389   %s = add i32 %a, %b
1390   %k = icmp ult i32 %x, %y
1391   %z = zext i1 %k to i32
1392   %r = add i32 %s, %z
1393   ret i32 %r
1394 }
1395
1396 define i32 @addcarry_ugt(i32 %a, i32 %b, i32 %x, i32 %y) nounwind {
1397 ; CHECK-LABEL: addcarry_ugt:
1398 ; CHECK:       # %bb.0:
1399 ; CHECK-NEXT:    movl %edi, %eax
1400 ; CHECK-NEXT:    cmpl %edx, %ecx
1401 ; CHECK-NEXT:    adcl %esi, %eax
1402 ; CHECK-NEXT:    retq
1403   %s = add i32 %a, %b
1404   %k = icmp ugt i32 %x, %y
1405   %z = zext i1 %k to i32
1406   %r = add i32 %s, %z
1407   ret i32 %r
1408 }
1409
1410 define i32 @addcarry_ule(i32 %a, i32 %b, i32 %x, i32 %y) nounwind {
1411 ; CHECK-LABEL: addcarry_ule:
1412 ; CHECK:       # %bb.0:
1413 ; CHECK-NEXT:    # kill: def $esi killed $esi def $rsi
1414 ; CHECK-NEXT:    # kill: def $edi killed $edi def $rdi
1415 ; CHECK-NEXT:    leal (%rdi,%rsi), %eax
1416 ; CHECK-NEXT:    cmpl %edx, %ecx
1417 ; CHECK-NEXT:    sbbl $-1, %eax
1418 ; CHECK-NEXT:    retq
1419   %s = add i32 %a, %b
1420   %k = icmp ule i32 %x, %y
1421   %z = zext i1 %k to i32
1422   %r = add i32 %s, %z
1423   ret i32 %r
1424 }
1425
1426 define i32 @addcarry_uge(i32 %a, i32 %b, i32 %x, i32 %y) nounwind {
1427 ; CHECK-LABEL: addcarry_uge:
1428 ; CHECK:       # %bb.0:
1429 ; CHECK-NEXT:    # kill: def $esi killed $esi def $rsi
1430 ; CHECK-NEXT:    # kill: def $edi killed $edi def $rdi
1431 ; CHECK-NEXT:    leal (%rdi,%rsi), %eax
1432 ; CHECK-NEXT:    cmpl %ecx, %edx
1433 ; CHECK-NEXT:    sbbl $-1, %eax
1434 ; CHECK-NEXT:    retq
1435   %s = add i32 %a, %b
1436   %k = icmp uge i32 %x, %y
1437   %z = zext i1 %k to i32
1438   %r = add i32 %s, %z
1439   ret i32 %r
1440 }
1441
1442 define { i64, i64 } @addcarry_commutative_1(i64 %x0, i64 %x1, i64 %y0, i64 %y1) nounwind {
1443 ; CHECK-LABEL: addcarry_commutative_1:
1444 ; CHECK:       # %bb.0:
1445 ; CHECK-NEXT:    movq %rsi, %rax
1446 ; CHECK-NEXT:    addq %rdx, %rdi
1447 ; CHECK-NEXT:    adcq %rcx, %rax
1448 ; CHECK-NEXT:    movq %rax, %rdx
1449 ; CHECK-NEXT:    retq
1450   %z0 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %x0, i64 %y0)
1451   %k0 = extractvalue { i64, i1 } %z0, 1
1452   %k0z = zext i1 %k0 to i64
1453
1454   %t1s = add i64 %x1, %y1
1455   %z1s = add i64 %t1s, %k0z
1456
1457   ; same as the above, but args swapped
1458   %a1s = add i64 %y1, %x1
1459   %b1s = add i64 %a1s, %k0z
1460
1461   %r0 = insertvalue { i64, i64 } poison, i64 %z1s, 0
1462   %r1 = insertvalue { i64, i64 } %r0, i64 %b1s, 1
1463   ret { i64, i64 } %r1
1464 }
1465
1466 define { i64, i64 } @addcarry_commutative_2(i64 %x0, i64 %x1, i64 %y0, i64 %y1) nounwind {
1467 ; CHECK-LABEL: addcarry_commutative_2:
1468 ; CHECK:       # %bb.0:
1469 ; CHECK-NEXT:    movq %rsi, %rax
1470 ; CHECK-NEXT:    addq %rdx, %rdi
1471 ; CHECK-NEXT:    adcq %rcx, %rax
1472 ; CHECK-NEXT:    movq %rax, %rdx
1473 ; CHECK-NEXT:    retq
1474   %z0 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %x0, i64 %y0)
1475   %k0 = extractvalue { i64, i1 } %z0, 1
1476   %k0z = zext i1 %k0 to i64
1477
1478   %t1 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %x1, i64 %y1)
1479   %t1s = extractvalue { i64, i1 } %t1, 0
1480   %z1 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %t1s, i64 %k0z)
1481   %z1s = extractvalue { i64, i1 } %z1, 0
1482
1483   ; same as the above, but args swapped
1484   %a1 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %y1, i64 %x1)
1485   %a1s = extractvalue { i64, i1 } %a1, 0
1486   %b1 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %a1s, i64 %k0z)
1487   %b1s = extractvalue { i64, i1 } %b1, 0
1488
1489   %r0 = insertvalue { i64, i64 } poison, i64 %z1s, 0
1490   %r1 = insertvalue { i64, i64 } %r0, i64 %b1s, 1
1491   ret { i64, i64 } %r1
1492 }