diff --git a/llvm/lib/CodeGen/CalcSpillWeights.cpp b/llvm/lib/CodeGen/CalcSpillWeights.cpp
--- a/llvm/lib/CodeGen/CalcSpillWeights.cpp
+++ b/llvm/lib/CodeGen/CalcSpillWeights.cpp
@@ -209,6 +209,11 @@
        I != E;) {
     MachineInstr *mi = &*(I++);
 
+    if (mi->getOpcode() == TargetOpcode::INLINEASM_BR) {
+      li.markNotSpillable();
+      return -1.0;
+    }
+
     // For local split artifacts, we are interested only in instructions between
     // the expected start and end of the range.
     SlotIndex si = LIS.getInstructionIndex(*mi);
diff --git a/llvm/test/CodeGen/X86/callbr-asm-regalloc.ll b/llvm/test/CodeGen/X86/callbr-asm-regalloc.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/CodeGen/X86/callbr-asm-regalloc.ll
@@ -0,0 +1,96 @@
+; Test that the greedy register allocator emits MachineInstrs that pass
+; verification. Previously, the callbr was being lowered to an INLINEASM_BR
+; with a non-terminator register spill which violated the MachineVerifier
+; invariant that all MachineInstrs post the first Terminal MachineInstr were
+; also Terminal. The unexpected spill looked like:
+; MOV32mr %stack.0, 1, $noreg, 0, $noreg, %44:gr32 :: (store 4 into %stack.0)
+
+; RUN: llc -regalloc=greedy -stop-after=greedy -verify-regalloc < %s
+
+%struct.d = type { i8* }
+%struct.b = type {}
+
+@j = dso_local local_unnamed_addr global i32 0, align 4
+@i = dso_local local_unnamed_addr global i32 0, align 4
+@h = dso_local local_unnamed_addr global i32 0, align 4
+@g = dso_local local_unnamed_addr global i32 0, align 4
+
+define dso_local i32 @cmsghdr_from_user_compat_to_kern(%struct.d* %0) #0 {
+  br label %2
+
+2:                                                ; preds = %1, %9
+  %3 = phi i32 [ %14, %9 ], [ undef, %1 ]
+  %4 = load i32, i32* @j, align 4
+  %5 = load i32, i32* @i, align 4
+  %6 = icmp eq i32 %5, 0
+  br i1 %6, label %7, label %44
+
+7:                                                ; preds = %2
+  %8 = icmp eq i32 %4, 0
+  br i1 %8, label %44, label %9
+
+9:                                                ; preds = %7
+  %10 = zext i32 %4 to i64
+  %11 = add nuw nsw i64 %10, 1
+  %12 = and i64 %11, 8589934590
+  %13 = trunc i64 %12 to i32
+  store i32 %13, i32* @h, align 4
+  %14 = tail call i32 @f(%struct.d* %0, i32 %3, i32 %4) #3
+  %15 = icmp eq i32 %14, 0
+  br i1 %15, label %16, label %2
+
+16:                                               ; preds = %9
+  %17 = icmp eq i64 %12, 0
+  br i1 %17, label %18, label %44
+
+18:                                               ; preds = %16
+  %19 = icmp eq %struct.d* %0, null
+  br i1 %19, label %44, label %20
+
+20:                                               ; preds = %18
+  %21 = bitcast %struct.d* %0 to i64*
+  %22 = load i64, i64* %21, align 8
+  %23 = trunc i64 %22 to i32
+  %24 = icmp eq i32 %23, 0
+  br i1 %24, label %44, label %25, !prof !0
+
+25:                                               ; preds = %20, %38
+  %26 = phi i32 [ %42, %38 ], [ %23, %20 ]
+  %27 = phi i64 [ %41, %38 ], [ 0, %20 ]
+  %28 = callbr i32 asm "1:\09mov $1,$0\0A .pushsection \22__ex_table\22,\22a\22\0A .long 1b - .\0A .long ${2:l} - .\0A .long 0 - .\0A .popsection\0A", "=r,*m,X,~{dirflag},~{fpsr},~{flags}"(%struct.b* null, i8* blockaddress(@cmsghdr_from_user_compat_to_kern, %29)) #4
+          to label %31 [label %29]
+
+29:                                               ; preds = %25
+  %30 = tail call i32 @a() #3
+  br label %44
+
+31:                                               ; preds = %25
+  %32 = zext i32 %28 to i64
+  %33 = shl i64 %27, 32
+  %34 = ashr exact i64 %33, 32
+  %35 = inttoptr i64 %34 to i32*
+  %36 = tail call i32 @c(i32* %35, i64 %32) #3
+  %37 = icmp eq i32 %36, 0
+  br i1 %37, label %38, label %44
+
+38:                                               ; preds = %31
+  %39 = add nuw nsw i64 %32, 8
+  %40 = and i64 %39, 8589934590
+  %41 = add nsw i64 %40, %34
+  %42 = tail call i32 @f(%struct.d* nonnull %0, i32 %26, i32 %28) #3
+  %43 = icmp eq i32 %42, 0
+  br i1 %43, label %44, label %25, !prof !0
+
+44:                                               ; preds = %7, %2, %31, %38, %18, %20, %29, %16
+  %45 = phi i32 [ -22, %16 ], [ undef, %29 ], [ undef, %20 ], [ undef, %18 ], [ undef, %38 ], [ undef, %31 ], [ -22, %7 ], [ 4, %2 ]
+  ret i32 %45
+}
+
+declare dso_local i32 @f(%struct.d*, i32, i32) local_unnamed_addr #1
+declare dso_local i32 @a() local_unnamed_addr #1
+declare dso_local i32 @c(i32*, i64) local_unnamed_addr #1
+define dso_local i32 @put_cmsg_compat() local_unnamed_addr #2 {
+  ret i32 undef
+}
+
+!0 = !{!"branch_weights", i32 2146410443, i32 1073205}
diff --git a/llvm/test/CodeGen/X86/callbr-asm-regalloc.mir b/llvm/test/CodeGen/X86/callbr-asm-regalloc.mir
new file mode 100644
--- /dev/null
+++ b/llvm/test/CodeGen/X86/callbr-asm-regalloc.mir
@@ -0,0 +1,337 @@
+# RUN: llc -run-pass=greedy -regalloc=greedy -verify-regalloc %s
+# Dumped via:
+# $ llc -stop-after=twoaddressinstruction -simplify-mir \
+#    -o callbr-asm-regalloc.mir llvm/test/CodeGen/X86/callbr-asm-regalloc.ll
+--- |
+  ; ModuleID = 'llvm/test/CodeGen/X86/callbr-asm-regalloc.ll'
+  source_filename = "llvm/test/CodeGen/X86/callbr-asm-regalloc.ll"
+  target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+  
+  %struct.d = type { i8* }
+  %struct.b = type {}
+  
+  @j = dso_local local_unnamed_addr global i32 0, align 4
+  @i = dso_local local_unnamed_addr global i32 0, align 4
+  @h = dso_local local_unnamed_addr global i32 0, align 4
+  @g = dso_local local_unnamed_addr global i32 0, align 4
+  
+  define dso_local i32 @cmsghdr_from_user_compat_to_kern(%struct.d* %0) {
+    %const = bitcast i64 8589934590 to i64
+    br label %2
+  
+  2:                                                ; preds = %11, %1
+    %3 = phi i32 [ %16, %11 ], [ undef, %1 ]
+    %4 = load i32, i32* @j, align 4
+    %5 = zext i32 %4 to i64
+    %6 = load i32, i32* @i, align 4
+    %7 = icmp eq i32 %6, 0
+    br i1 %7, label %8, label %46
+  
+  8:                                                ; preds = %2
+    %9 = trunc i64 %5 to i32
+    %10 = icmp eq i32 %9, 0
+    br i1 %10, label %46, label %11
+  
+  11:                                               ; preds = %8
+    %12 = trunc i64 %5 to i32
+    %13 = add nuw nsw i64 %5, 1
+    %14 = and i64 %13, %const
+    %15 = trunc i64 %14 to i32
+    store i32 %15, i32* @h, align 4
+    %16 = tail call i32 @f(%struct.d* %0, i32 %3, i32 %12)
+    %17 = icmp eq i32 %16, 0
+    br i1 %17, label %18, label %2
+  
+  18:                                               ; preds = %11
+    %19 = icmp eq i64 %14, 0
+    br i1 %19, label %20, label %46
+  
+  20:                                               ; preds = %18
+    %21 = icmp eq %struct.d* %0, null
+    br i1 %21, label %46, label %22
+  
+  22:                                               ; preds = %20
+    %23 = bitcast %struct.d* %0 to i64*
+    %24 = load i64, i64* %23, align 8
+    %25 = trunc i64 %24 to i32
+    %26 = icmp eq i32 %25, 0
+    br i1 %26, label %46, label %.preheader, !prof !0
+  
+  .preheader:                                       ; preds = %22
+    br label %27
+  
+  27:                                               ; preds = %.preheader, %40
+    %28 = phi i32 [ %44, %40 ], [ %25, %.preheader ]
+    %29 = phi i64 [ %43, %40 ], [ 0, %.preheader ]
+    %30 = callbr i32 asm "1:\09mov $1,$0\0A .pushsection \22__ex_table\22,\22a\22\0A .long 1b - .\0A .long ${2:l} - .\0A .long 0 - .\0A .popsection\0A", "=r,*m,X,~{dirflag},~{fpsr},~{flags}"(%struct.b* null, i8* blockaddress(@cmsghdr_from_user_compat_to_kern, %31))
+            to label %33 [label %31]
+  
+  31:                                               ; preds = %27
+    %32 = tail call i32 @a()
+    br label %46
+  
+  33:                                               ; preds = %27
+    %34 = zext i32 %30 to i64
+    %35 = shl i64 %29, 32
+    %36 = ashr exact i64 %35, 32
+    %37 = inttoptr i64 %36 to i32*
+    %38 = tail call i32 @c(i32* %37, i64 %34)
+    %39 = icmp eq i32 %38, 0
+    br i1 %39, label %40, label %46
+  
+  40:                                               ; preds = %33
+    %41 = add nuw nsw i64 %34, 8
+    %42 = and i64 %41, %const
+    %43 = add nsw i64 %42, %36
+    %44 = tail call i32 @f(%struct.d* nonnull %0, i32 %28, i32 %30)
+    %45 = icmp eq i32 %44, 0
+    br i1 %45, label %46, label %27, !prof !0
+  
+  46:                                               ; preds = %8, %2, %40, %33, %31, %22, %20, %18
+    %47 = phi i32 [ -22, %18 ], [ undef, %31 ], [ undef, %22 ], [ undef, %20 ], [ undef, %33 ], [ undef, %40 ], [ 4, %2 ], [ -22, %8 ]
+    ret i32 %47
+  }
+  
+  declare dso_local i32 @f(%struct.d*, i32, i32) local_unnamed_addr
+  
+  declare dso_local i32 @a() local_unnamed_addr
+  
+  declare dso_local i32 @c(i32*, i64) local_unnamed_addr
+  
+  define dso_local i32 @put_cmsg_compat() local_unnamed_addr {
+    ret i32 undef
+  }
+  
+  ; Function Attrs: nounwind
+  declare void @llvm.stackprotector(i8*, i8**) #0
+  
+  attributes #0 = { nounwind }
+  
+  !0 = !{!"branch_weights", i32 2146410443, i32 1073205}
+
+...
+---
+name:            cmsghdr_from_user_compat_to_kern
+alignment:       16
+tracksRegLiveness: true
+registers:
+  - { id: 0, class: gr64 }
+  - { id: 1, class: gr32 }
+  - { id: 2, class: gr64 }
+  - { id: 3, class: gr64 }
+  - { id: 4, class: gr32 }
+  - { id: 5, class: gr32 }
+  - { id: 6, class: gr32 }
+  - { id: 7, class: gr64 }
+  - { id: 8, class: gr32 }
+  - { id: 9, class: gr64 }
+  - { id: 10, class: gr64 }
+  - { id: 11, class: gr64 }
+  - { id: 12, class: gr32 }
+  - { id: 13, class: gr32 }
+  - { id: 14, class: gr64 }
+  - { id: 15, class: gr32 }
+  - { id: 16, class: gr32 }
+  - { id: 17, class: gr32 }
+  - { id: 18, class: gr32 }
+  - { id: 19, class: gr32 }
+  - { id: 20, class: gr32 }
+  - { id: 21, class: gr64 }
+  - { id: 22, class: gr32 }
+  - { id: 23, class: gr32 }
+  - { id: 24, class: gr32 }
+  - { id: 25, class: gr32 }
+  - { id: 26, class: gr32 }
+  - { id: 27, class: gr64 }
+  - { id: 28, class: gr32 }
+  - { id: 29, class: gr32 }
+  - { id: 30, class: gr32 }
+  - { id: 31, class: gr32 }
+  - { id: 32, class: gr32 }
+  - { id: 33, class: gr32 }
+  - { id: 34, class: gr32 }
+  - { id: 35, class: gr32 }
+  - { id: 36, class: gr32 }
+  - { id: 37, class: gr64 }
+  - { id: 38, class: gr64 }
+  - { id: 39, class: gr32 }
+  - { id: 40, class: gr32 }
+  - { id: 41, class: gr32 }
+  - { id: 42, class: gr64 }
+  - { id: 43, class: gr32 }
+liveins:
+  - { reg: '$rdi', virtual-reg: '%14' }
+frameInfo:
+  maxAlignment:    1
+  hasCalls:        true
+machineFunctionInfo: {}
+body:             |
+  bb.0 (%ir-block.1):
+    liveins: $rdi
+  
+    %14:gr64 = COPY killed $rdi
+    %0:gr64 = MOV64ri 8589934590
+    %40:gr32 = IMPLICIT_DEF
+  
+  bb.1 (%ir-block.2):
+    successors: %bb.3(0x7c000000), %bb.2(0x04000000)
+  
+    %1:gr32 = COPY killed %40
+    CMP32mi8 $rip, 1, $noreg, @i, $noreg, 0, implicit-def $eflags :: (dereferenceable load 4 from @i)
+    JCC_1 %bb.3, 4, implicit killed $eflags
+  
+  bb.2:
+    %16:gr32 = MOV32ri 4
+    %43:gr32 = COPY killed %16
+    JMP_1 %bb.15
+  
+  bb.3 (%ir-block.8):
+    successors: %bb.16(0x04000000), %bb.4(0x7c000000)
+  
+    %17:gr32 = MOV32rm $rip, 1, $noreg, @j, $noreg :: (dereferenceable load 4 from @j)
+    %2:gr64 = SUBREG_TO_REG 0, killed %17, %subreg.sub_32bit
+    %19:gr32 = COPY %2.sub_32bit
+    %18:gr32 = MOV32ri -22
+    TEST32rr killed %19, %19, implicit-def $eflags
+    JCC_1 %bb.4, 5, implicit killed $eflags
+  
+  bb.16:
+    %43:gr32 = COPY killed %18
+    JMP_1 %bb.15
+  
+  bb.4 (%ir-block.11):
+    successors: %bb.5(0x04000000), %bb.1(0x7c000000)
+  
+    %20:gr32 = COPY %2.sub_32bit
+    %21:gr64 = COPY killed %2
+    %21:gr64 = nuw nsw INC64r %21, implicit-def dead $eflags
+    %3:gr64 = COPY killed %21
+    %3:gr64 = AND64rr %3, %0, implicit-def dead $eflags
+    %22:gr32 = COPY %3.sub_32bit
+    MOV32mr $rip, 1, $noreg, @h, $noreg, killed %22 :: (store 4 into @h)
+    ADJCALLSTACKDOWN64 0, 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp
+    $rdi = COPY %14
+    $esi = COPY killed %1
+    $edx = COPY killed %20
+    CALL64pcrel32 @f, csr_64, implicit $rsp, implicit $ssp, implicit killed $rdi, implicit killed $esi, implicit killed $edx, implicit-def $rsp, implicit-def $ssp, implicit-def $eax
+    ADJCALLSTACKUP64 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp
+    %23:gr32 = COPY killed $eax
+    %4:gr32 = COPY %23
+    TEST32rr killed %23, %23, implicit-def $eflags
+    %40:gr32 = COPY killed %4
+    JCC_1 %bb.1, 5, implicit killed $eflags
+    JMP_1 %bb.5
+  
+  bb.5 (%ir-block.18):
+    successors: %bb.6(0x30000000), %bb.15(0x50000000)
+  
+    TEST64rr killed %3, %3, implicit-def $eflags
+    %43:gr32 = COPY killed %18
+    JCC_1 %bb.15, 5, implicit killed $eflags
+    JMP_1 %bb.6
+  
+  bb.6 (%ir-block.20):
+    successors: %bb.7(0x30000000), %bb.8(0x50000000)
+  
+    TEST64rr %14, %14, implicit-def $eflags
+    JCC_1 %bb.8, 5, implicit killed $eflags
+  
+  bb.7:
+    %43:gr32 = IMPLICIT_DEF
+    JMP_1 %bb.15
+  
+  bb.8 (%ir-block.22):
+    successors: %bb.15(0x7fef9fcb), %bb.9(0x00106035)
+  
+    %5:gr32 = MOV32rm %14, 1, $noreg, 0, $noreg :: (load 4 from %ir.23, align 8)
+    TEST32rr %5, %5, implicit-def $eflags
+    %43:gr32 = IMPLICIT_DEF
+    JCC_1 %bb.15, 4, implicit killed $eflags
+    JMP_1 %bb.9
+  
+  bb.9..preheader:
+    %28:gr32 = MOV32r0 implicit-def dead $eflags
+    %27:gr64 = SUBREG_TO_REG 0, killed %28, %subreg.sub_32bit
+    %41:gr32 = COPY killed %5
+    %42:gr64 = COPY killed %27
+  
+  bb.10 (%ir-block.27):
+    successors: %bb.12(0x00000000), %bb.11(0x80000000)
+  
+    %7:gr64 = COPY killed %42
+    %6:gr32 = COPY killed %41
+    INLINEASM_BR &"1:\09mov $1,$0\0A .pushsection \22__ex_table\22,\22a\22\0A .long 1b - .\0A .long ${2:l} - .\0A .long 0 - .\0A .popsection\0A", 8, 2228234, def %29, 196654, $noreg, 1, $noreg, 0, $noreg, 13, blockaddress(@cmsghdr_from_user_compat_to_kern, %ir-block.31), 12, implicit-def dead early-clobber $df, 12, implicit-def early-clobber $fpsw, 12, implicit-def dead early-clobber $eflags
+  
+  bb.11 (%ir-block.27):
+    %8:gr32 = COPY %29
+    JMP_1 %bb.13
+  
+  bb.12 (%ir-block.31, address-taken):
+    ADJCALLSTACKDOWN64 0, 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp
+    CALL64pcrel32 @a, csr_64, implicit $rsp, implicit $ssp, implicit-def $rsp, implicit-def $ssp, implicit-def dead $eax
+    ADJCALLSTACKUP64 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp
+    %43:gr32 = IMPLICIT_DEF
+    JMP_1 %bb.15
+  
+  bb.13 (%ir-block.33):
+    successors: %bb.14(0x7c000000), %bb.15(0x04000000)
+  
+    %33:gr32 = MOV32rr killed %29
+    %9:gr64 = SUBREG_TO_REG 0, killed %33, %subreg.sub_32bit
+    %34:gr32 = COPY killed %7.sub_32bit
+    %10:gr64 = MOVSX64rr32 killed %34
+    ADJCALLSTACKDOWN64 0, 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp
+    $rdi = COPY %10
+    $rsi = COPY %9
+    CALL64pcrel32 @c, csr_64, implicit $rsp, implicit $ssp, implicit killed $rdi, implicit killed $rsi, implicit-def $rsp, implicit-def $ssp, implicit-def $eax
+    ADJCALLSTACKUP64 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp
+    %35:gr32 = COPY killed $eax
+    TEST32rr killed %35, %35, implicit-def $eflags
+    %43:gr32 = IMPLICIT_DEF
+    JCC_1 %bb.15, 5, implicit killed $eflags
+    JMP_1 %bb.14
+  
+  bb.14 (%ir-block.40):
+    successors: %bb.15(0x7fef9fcb), %bb.10(0x00106035)
+  
+    %37:gr64 = COPY killed %9
+    %37:gr64 = nuw nsw ADD64ri8 %37, 8, implicit-def dead $eflags
+    %38:gr64 = COPY killed %37
+    %38:gr64 = AND64rr %38, %0, implicit-def dead $eflags
+    %11:gr64 = COPY killed %38
+    %11:gr64 = nsw ADD64rr %11, killed %10, implicit-def dead $eflags
+    ADJCALLSTACKDOWN64 0, 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp
+    $rdi = COPY %14
+    $esi = COPY killed %6
+    $edx = COPY killed %8
+    CALL64pcrel32 @f, csr_64, implicit $rsp, implicit $ssp, implicit killed $rdi, implicit killed $esi, implicit killed $edx, implicit-def $rsp, implicit-def $ssp, implicit-def $eax
+    ADJCALLSTACKUP64 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp
+    %39:gr32 = COPY killed $eax
+    %12:gr32 = COPY %39
+    TEST32rr killed %39, %39, implicit-def $eflags
+    %41:gr32 = COPY killed %12
+    %42:gr64 = COPY killed %11
+    %43:gr32 = IMPLICIT_DEF
+    JCC_1 %bb.10, 5, implicit killed $eflags
+    JMP_1 %bb.15
+  
+  bb.15 (%ir-block.46):
+    %13:gr32 = COPY killed %43
+    $eax = COPY killed %13
+    RET 0, killed $eax
+
+...
+---
+name:            put_cmsg_compat
+alignment:       16
+tracksRegLiveness: true
+registers:
+  - { id: 0, class: gr32 }
+frameInfo:
+  maxAlignment:    1
+machineFunctionInfo: {}
+body:             |
+  bb.0 (%ir-block.0):
+    RET 0, undef $eax
+
+...