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}