diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
--- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
@@ -5608,8 +5608,17 @@
 
       // Build vector (integer) scalar operands may need implicit
       // truncation - do this before constant folding.
-      if (ScalarVT.isInteger() && ScalarVT.bitsGT(InSVT))
+      if (ScalarVT.isInteger() && ScalarVT.bitsGT(InSVT)) {
+        // Don't create illegally-typed nodes unless they're constants - if we
+        // fail to constant fold we can't guarantee the (dead) nodes we're
+        // creating will be cleaned up before being visited for legalizatoin.
+        if (NewNodesMustHaveLegalTypes &&
+            ScalarOp.getOpcode() != ISD::Constant &&
+            TLI->getTypeAction(*getContext(), InSVT) !=
+                TargetLowering::TypeLegal)
+          return SDValue();
         ScalarOp = getNode(ISD::TRUNCATE, DL, InSVT, ScalarOp);
+      }
 
       ScalarOps.push_back(ScalarOp);
     }
diff --git a/llvm/test/CodeGen/Mips/msa/i5-b.ll b/llvm/test/CodeGen/Mips/msa/i5-b.ll
--- a/llvm/test/CodeGen/Mips/msa/i5-b.ll
+++ b/llvm/test/CodeGen/Mips/msa/i5-b.ll
@@ -328,7 +328,8 @@
 ; CHECK-NEXT:    addu $1, $2, $25
 ; CHECK-NEXT:    lw $2, %got(llvm_mips_bnegi_b_ARG1)($1)
 ; CHECK-NEXT:    ld.b $w0, 0($2)
-; CHECK-NEXT:    bnegi.b $w0, $w0, 7
+; CHECK-NEXT:    ldi.b $w1, 7
+; CHECK-NEXT:    bneg.b $w0, $w0, $w1
 ; CHECK-NEXT:    lw $1, %got(llvm_mips_bnegi_b_RES)($1)
 ; CHECK-NEXT:    jr $ra
 ; CHECK-NEXT:    st.b $w0, 0($1)
@@ -351,7 +352,8 @@
 ; CHECK-NEXT:    addu $1, $2, $25
 ; CHECK-NEXT:    lw $2, %got(llvm_mips_bnegi_h_ARG1)($1)
 ; CHECK-NEXT:    ld.h $w0, 0($2)
-; CHECK-NEXT:    bnegi.h $w0, $w0, 7
+; CHECK-NEXT:    ldi.h $w1, 7
+; CHECK-NEXT:    bneg.h $w0, $w0, $w1
 ; CHECK-NEXT:    lw $1, %got(llvm_mips_bnegi_h_RES)($1)
 ; CHECK-NEXT:    jr $ra
 ; CHECK-NEXT:    st.h $w0, 0($1)
@@ -420,7 +422,8 @@
 ; CHECK-NEXT:    addu $1, $2, $25
 ; CHECK-NEXT:    lw $2, %got(llvm_mips_bseti_b_ARG1)($1)
 ; CHECK-NEXT:    ld.b $w0, 0($2)
-; CHECK-NEXT:    bseti.b $w0, $w0, 7
+; CHECK-NEXT:    ldi.b $w1, 7
+; CHECK-NEXT:    bset.b $w0, $w0, $w1
 ; CHECK-NEXT:    lw $1, %got(llvm_mips_bseti_b_RES)($1)
 ; CHECK-NEXT:    jr $ra
 ; CHECK-NEXT:    st.b $w0, 0($1)
@@ -443,7 +446,8 @@
 ; CHECK-NEXT:    addu $1, $2, $25
 ; CHECK-NEXT:    lw $2, %got(llvm_mips_bseti_h_ARG1)($1)
 ; CHECK-NEXT:    ld.h $w0, 0($2)
-; CHECK-NEXT:    bseti.h $w0, $w0, 7
+; CHECK-NEXT:    ldi.h $w1, 7
+; CHECK-NEXT:    bset.h $w0, $w0, $w1
 ; CHECK-NEXT:    lw $1, %got(llvm_mips_bseti_h_RES)($1)
 ; CHECK-NEXT:    jr $ra
 ; CHECK-NEXT:    st.h $w0, 0($1)
diff --git a/llvm/test/CodeGen/Mips/msa/immediates.ll b/llvm/test/CodeGen/Mips/msa/immediates.ll
--- a/llvm/test/CodeGen/Mips/msa/immediates.ll
+++ b/llvm/test/CodeGen/Mips/msa/immediates.ll
@@ -184,7 +184,8 @@
 ; MSA-LABEL: bnegi_b:
 ; MSA:       # %bb.0: # %entry
 ; MSA-NEXT:    ld.b $w0, 0($4)
-; MSA-NEXT:    bnegi.b $w0, $w0, 6
+; MSA-NEXT:    ldi.b $w1, 6
+; MSA-NEXT:    bneg.b $w0, $w0, $w1
 ; MSA-NEXT:    jr $ra
 ; MSA-NEXT:    st.b $w0, 0($4)
 ;
@@ -192,7 +193,8 @@
 ; MSA64N32:       # %bb.0: # %entry
 ; MSA64N32-NEXT:    sll $1, $4, 0
 ; MSA64N32-NEXT:    ld.b $w0, 0($1)
-; MSA64N32-NEXT:    bnegi.b $w0, $w0, 6
+; MSA64N32-NEXT:    ldi.b $w1, 6
+; MSA64N32-NEXT:    bneg.b $w0, $w0, $w1
 ; MSA64N32-NEXT:    jr $ra
 ; MSA64N32-NEXT:    st.b $w0, 0($1)
 entry:
@@ -228,7 +230,8 @@
 ; MSA-LABEL: bseti_b:
 ; MSA:       # %bb.0: # %entry
 ; MSA-NEXT:    ld.b $w0, 0($4)
-; MSA-NEXT:    bseti.b $w0, $w0, 5
+; MSA-NEXT:    ldi.b $w1, 5
+; MSA-NEXT:    bset.b $w0, $w0, $w1
 ; MSA-NEXT:    jr $ra
 ; MSA-NEXT:    st.b $w0, 0($4)
 ;
@@ -236,7 +239,8 @@
 ; MSA64N32:       # %bb.0: # %entry
 ; MSA64N32-NEXT:    sll $1, $4, 0
 ; MSA64N32-NEXT:    ld.b $w0, 0($1)
-; MSA64N32-NEXT:    bseti.b $w0, $w0, 5
+; MSA64N32-NEXT:    ldi.b $w1, 5
+; MSA64N32-NEXT:    bset.b $w0, $w0, $w1
 ; MSA64N32-NEXT:    jr $ra
 ; MSA64N32-NEXT:    st.b $w0, 0($1)
 entry:
@@ -1228,7 +1232,8 @@
 ; MSA-LABEL: bnegi_h:
 ; MSA:       # %bb.0: # %entry
 ; MSA-NEXT:    ld.h $w0, 0($4)
-; MSA-NEXT:    bnegi.h $w0, $w0, 14
+; MSA-NEXT:    ldi.h $w1, 14
+; MSA-NEXT:    bneg.h $w0, $w0, $w1
 ; MSA-NEXT:    jr $ra
 ; MSA-NEXT:    st.h $w0, 0($4)
 ;
@@ -1236,7 +1241,8 @@
 ; MSA64N32:       # %bb.0: # %entry
 ; MSA64N32-NEXT:    sll $1, $4, 0
 ; MSA64N32-NEXT:    ld.h $w0, 0($1)
-; MSA64N32-NEXT:    bnegi.h $w0, $w0, 14
+; MSA64N32-NEXT:    ldi.h $w1, 14
+; MSA64N32-NEXT:    bneg.h $w0, $w0, $w1
 ; MSA64N32-NEXT:    jr $ra
 ; MSA64N32-NEXT:    st.h $w0, 0($1)
 entry:
@@ -1250,7 +1256,8 @@
 ; MSA-LABEL: bseti_h:
 ; MSA:       # %bb.0: # %entry
 ; MSA-NEXT:    ld.h $w0, 0($4)
-; MSA-NEXT:    bseti.h $w0, $w0, 15
+; MSA-NEXT:    ldi.h $w1, 15
+; MSA-NEXT:    bset.h $w0, $w0, $w1
 ; MSA-NEXT:    jr $ra
 ; MSA-NEXT:    st.h $w0, 0($4)
 ;
@@ -1258,7 +1265,8 @@
 ; MSA64N32:       # %bb.0: # %entry
 ; MSA64N32-NEXT:    sll $1, $4, 0
 ; MSA64N32-NEXT:    ld.h $w0, 0($1)
-; MSA64N32-NEXT:    bseti.h $w0, $w0, 15
+; MSA64N32-NEXT:    ldi.h $w1, 15
+; MSA64N32-NEXT:    bset.h $w0, $w0, $w1
 ; MSA64N32-NEXT:    jr $ra
 ; MSA64N32-NEXT:    st.h $w0, 0($1)
 entry:
diff --git a/llvm/test/CodeGen/RISCV/rvv/constant-folding-crash.ll b/llvm/test/CodeGen/RISCV/rvv/constant-folding-crash.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/CodeGen/RISCV/rvv/constant-folding-crash.ll
@@ -0,0 +1,85 @@
+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc -mtriple=riscv32 -mattr=+v -riscv-v-vector-bits-min=128 -verify-machineinstrs < %s \
+; RUN:   | FileCheck %s --check-prefix RV32
+; RUN: llc -mtriple=riscv64 -mattr=+v -riscv-v-vector-bits-min=128 -verify-machineinstrs < %s \
+; RUN:   | FileCheck %s --check-prefix RV64
+
+; This used to crash during type legalization, where lowering (v4i1 =
+; BUILD_VECTOR) created a (v4i1 = SETCC v4i8) which during constant-folding
+; created illegally-typed i8 nodes. Ultimately, constant-folding failed and so
+; the new illegal nodes had no uses. However, during a second round of
+; legalization, this same pattern was generated from another BUILD_VECTOR. This
+; meant one of the illegally-typed (i8 = Constant<0>) nodes now had two dead
+; uses. Because the Constant and one of the uses were from round 1, they were
+; further up in the node order than the new second use, so the constant was
+; visited while it wasn't "dead". At the point of visiting the constant, we
+; crashed.
+
+define void @constant_folding_crash(i8* %v54, <4 x <4 x i32>*> %lanes.a, <4 x <4 x i32>*> %lanes.b, <4 x i1> %sel) {
+; RV32-LABEL: constant_folding_crash:
+; RV32:       # %bb.0: # %entry
+; RV32-NEXT:    lw a0, 8(a0)
+; RV32-NEXT:    vmv1r.v v10, v0
+; RV32-NEXT:    andi a0, a0, 1
+; RV32-NEXT:    seqz a0, a0
+; RV32-NEXT:    vsetivli zero, 4, e8, mf4, ta, mu
+; RV32-NEXT:    vmv.v.x v11, a0
+; RV32-NEXT:    vmsne.vi v0, v11, 0
+; RV32-NEXT:    vsetvli zero, zero, e32, m1, ta, mu
+; RV32-NEXT:    vmerge.vvm v8, v9, v8, v0
+; RV32-NEXT:    vsetvli zero, zero, e8, mf4, ta, mu
+; RV32-NEXT:    vmv.v.i v9, 0
+; RV32-NEXT:    vsetvli zero, zero, e32, m1, ta, mu
+; RV32-NEXT:    vmv.x.s a0, v8
+; RV32-NEXT:    vsetivli zero, 4, e8, mf4, ta, mu
+; RV32-NEXT:    vmv1r.v v0, v10
+; RV32-NEXT:    vmerge.vim v8, v9, 1, v0
+; RV32-NEXT:    vmv.x.s a1, v8
+; RV32-NEXT:    andi a1, a1, 1
+; RV32-NEXT:    vmv.v.x v8, a1
+; RV32-NEXT:    vmsne.vi v0, v8, 0
+; RV32-NEXT:    vsetvli zero, zero, e32, m1, ta, mu
+; RV32-NEXT:    vmv.v.i v8, 10
+; RV32-NEXT:    vse32.v v8, (a0), v0.t
+; RV32-NEXT:    ret
+;
+; RV64-LABEL: constant_folding_crash:
+; RV64:       # %bb.0: # %entry
+; RV64-NEXT:    ld a0, 8(a0)
+; RV64-NEXT:    vmv1r.v v12, v0
+; RV64-NEXT:    andi a0, a0, 1
+; RV64-NEXT:    seqz a0, a0
+; RV64-NEXT:    vsetivli zero, 4, e8, mf4, ta, mu
+; RV64-NEXT:    vmv.v.x v13, a0
+; RV64-NEXT:    vmsne.vi v0, v13, 0
+; RV64-NEXT:    vsetvli zero, zero, e64, m2, ta, mu
+; RV64-NEXT:    vmerge.vvm v8, v10, v8, v0
+; RV64-NEXT:    vsetvli zero, zero, e8, mf4, ta, mu
+; RV64-NEXT:    vmv.v.i v10, 0
+; RV64-NEXT:    vsetvli zero, zero, e64, m2, ta, mu
+; RV64-NEXT:    vmv.x.s a0, v8
+; RV64-NEXT:    vsetivli zero, 4, e8, mf4, ta, mu
+; RV64-NEXT:    vmv1r.v v0, v12
+; RV64-NEXT:    vmerge.vim v8, v10, 1, v0
+; RV64-NEXT:    vmv.x.s a1, v8
+; RV64-NEXT:    andi a1, a1, 1
+; RV64-NEXT:    vmv.v.x v8, a1
+; RV64-NEXT:    vmsne.vi v0, v8, 0
+; RV64-NEXT:    vsetvli zero, zero, e32, m1, ta, mu
+; RV64-NEXT:    vmv.v.i v8, 10
+; RV64-NEXT:    vse32.v v8, (a0), v0.t
+; RV64-NEXT:    ret
+entry:
+  %sunkaddr = getelementptr i8, i8* %v54, i64 8
+  %v55 = bitcast i8* %sunkaddr to i64*
+  %v56 = load i64, i64* %v55, align 8
+  %trunc = and i64 %v56, 1
+  %cmp = icmp eq i64 %trunc, 0
+  %ptrs = select i1 %cmp, <4 x <4 x i32>*> %lanes.a, <4 x <4 x i32>*> %lanes.b
+  %v67 = extractelement <4 x <4 x i32>*> %ptrs, i64 0
+  %mask = shufflevector <4 x i1> %sel, <4 x i1> undef, <4 x i32> zeroinitializer
+  call void @llvm.masked.store.v4i32.p0v4i32(<4 x i32> <i32 10, i32 10, i32 10, i32 10>, <4 x i32>* %v67, i32 16, <4 x i1> %mask)
+  ret void
+}
+
+declare void @llvm.masked.store.v4i32.p0v4i32(<4 x i32>, <4 x i32>*, i32, <4 x i1>)
diff --git a/llvm/test/CodeGen/X86/vector-shuffle-v1.ll b/llvm/test/CodeGen/X86/vector-shuffle-v1.ll
--- a/llvm/test/CodeGen/X86/vector-shuffle-v1.ll
+++ b/llvm/test/CodeGen/X86/vector-shuffle-v1.ll
@@ -48,7 +48,8 @@
 ; AVX512F-NEXT:    vpsllq $63, %xmm0, %xmm0
 ; AVX512F-NEXT:    vptestmq %zmm0, %zmm0, %k1
 ; AVX512F-NEXT:    vpternlogq $255, %zmm0, %zmm0, %zmm0 {%k1} {z}
-; AVX512F-NEXT:    vmovdqa {{.*#+}} xmm1 = [18446744073709551615,0]
+; AVX512F-NEXT:    kxnorw %k0, %k0, %k1
+; AVX512F-NEXT:    vpternlogq $255, %zmm1, %zmm1, %zmm1 {%k1} {z}
 ; AVX512F-NEXT:    vpalignr {{.*#+}} xmm0 = xmm0[8,9,10,11,12,13,14,15],xmm1[0,1,2,3,4,5,6,7]
 ; AVX512F-NEXT:    vptestmq %zmm0, %zmm0, %k1
 ; AVX512F-NEXT:    vpternlogq $255, %zmm0, %zmm0, %zmm0 {%k1} {z}
@@ -73,7 +74,7 @@
 ; VL_BW_DQ-NEXT:    vpsllq $63, %xmm0, %xmm0
 ; VL_BW_DQ-NEXT:    vpmovq2m %xmm0, %k0
 ; VL_BW_DQ-NEXT:    vpmovm2q %k0, %xmm0
-; VL_BW_DQ-NEXT:    vmovdqa {{.*#+}} xmm1 = [18446744073709551615,0]
+; VL_BW_DQ-NEXT:    vpcmpeqd %xmm1, %xmm1, %xmm1
 ; VL_BW_DQ-NEXT:    vpalignr {{.*#+}} xmm0 = xmm0[8,9,10,11,12,13,14,15],xmm1[0,1,2,3,4,5,6,7]
 ; VL_BW_DQ-NEXT:    vpmovq2m %xmm0, %k0
 ; VL_BW_DQ-NEXT:    vpmovm2q %k0, %xmm0
@@ -733,10 +734,12 @@
 ; AVX512F-LABEL: shuf8i1__9_6_1_10_3_7_7_1:
 ; AVX512F:       # %bb.0:
 ; AVX512F-NEXT:    kmovw %edi, %k1
-; AVX512F-NEXT:    vpternlogq $255, %zmm0, %zmm0, %zmm0 {%k1} {z}
-; AVX512F-NEXT:    vmovdqa64 {{.*#+}} zmm1 = [9,6,1,0,3,7,7,1]
-; AVX512F-NEXT:    vmovdqa64 {{.*#+}} zmm2 = [18446744073709551615,18446744073709551615,0,0,0,0,0,0]
-; AVX512F-NEXT:    vpermt2q %zmm0, %zmm1, %zmm2
+; AVX512F-NEXT:    movb $3, %al
+; AVX512F-NEXT:    kmovw %eax, %k2
+; AVX512F-NEXT:    vpternlogq $255, %zmm0, %zmm0, %zmm0 {%k2} {z}
+; AVX512F-NEXT:    vpternlogq $255, %zmm1, %zmm1, %zmm1 {%k1} {z}
+; AVX512F-NEXT:    vmovdqa64 {{.*#+}} zmm2 = [9,6,1,0,3,7,7,1]
+; AVX512F-NEXT:    vpermi2q %zmm1, %zmm0, %zmm2
 ; AVX512F-NEXT:    vptestmq %zmm2, %zmm2, %k0
 ; AVX512F-NEXT:    kmovw %k0, %eax
 ; AVX512F-NEXT:    # kill: def $al killed $al killed $eax
@@ -747,10 +750,13 @@
 ; AVX512VL:       # %bb.0:
 ; AVX512VL-NEXT:    kmovw %edi, %k1
 ; AVX512VL-NEXT:    vpcmpeqd %ymm0, %ymm0, %ymm0
+; AVX512VL-NEXT:    movb $3, %al
+; AVX512VL-NEXT:    kmovw %eax, %k2
+; AVX512VL-NEXT:    vmovdqa32 %ymm0, %ymm1 {%k2} {z}
 ; AVX512VL-NEXT:    vmovdqa32 %ymm0, %ymm0 {%k1} {z}
-; AVX512VL-NEXT:    vpshufd {{.*#+}} xmm0 = xmm0[1,1,1,1]
-; AVX512VL-NEXT:    vpblendd {{.*#+}} ymm0 = ymm0[0],mem[1,2,3,4,5,6,7]
-; AVX512VL-NEXT:    vptestmd %ymm0, %ymm0, %k0
+; AVX512VL-NEXT:    vmovdqa {{.*#+}} ymm2 = [9,6,1,0,3,7,7,1]
+; AVX512VL-NEXT:    vpermi2d %ymm0, %ymm1, %ymm2
+; AVX512VL-NEXT:    vptestmd %ymm2, %ymm2, %k0
 ; AVX512VL-NEXT:    kmovw %k0, %eax
 ; AVX512VL-NEXT:    # kill: def $al killed $al killed $eax
 ; AVX512VL-NEXT:    vzeroupper
@@ -759,10 +765,13 @@
 ; VL_BW_DQ-LABEL: shuf8i1__9_6_1_10_3_7_7_1:
 ; VL_BW_DQ:       # %bb.0:
 ; VL_BW_DQ-NEXT:    kmovd %edi, %k0
-; VL_BW_DQ-NEXT:    vpmovm2d %k0, %ymm0
-; VL_BW_DQ-NEXT:    vpshufd {{.*#+}} xmm0 = xmm0[1,1,1,1]
-; VL_BW_DQ-NEXT:    vpblendd {{.*#+}} ymm0 = ymm0[0],mem[1,2,3,4,5,6,7]
-; VL_BW_DQ-NEXT:    vpmovd2m %ymm0, %k0
+; VL_BW_DQ-NEXT:    movb $3, %al
+; VL_BW_DQ-NEXT:    kmovd %eax, %k1
+; VL_BW_DQ-NEXT:    vpmovm2d %k1, %ymm0
+; VL_BW_DQ-NEXT:    vpmovm2d %k0, %ymm1
+; VL_BW_DQ-NEXT:    vmovdqa {{.*#+}} ymm2 = [9,6,1,0,3,7,7,1]
+; VL_BW_DQ-NEXT:    vpermi2d %ymm1, %ymm0, %ymm2
+; VL_BW_DQ-NEXT:    vpmovd2m %ymm2, %k0
 ; VL_BW_DQ-NEXT:    kmovd %k0, %eax
 ; VL_BW_DQ-NEXT:    # kill: def $al killed $al killed $eax
 ; VL_BW_DQ-NEXT:    vzeroupper