diff --git a/llvm/tools/llvm-exegesis/lib/ParallelSnippetGenerator.cpp b/llvm/tools/llvm-exegesis/lib/ParallelSnippetGenerator.cpp
--- a/llvm/tools/llvm-exegesis/lib/ParallelSnippetGenerator.cpp
+++ b/llvm/tools/llvm-exegesis/lib/ParallelSnippetGenerator.cpp
@@ -186,25 +186,59 @@
     return getSingleton(std::move(CT));
   }
   // No tied variables, we pick random values for defs.
+
+  // We don't want to accidentally serialize the instruction,
+  // so we must be sure that we don't pick a def that is an implicit use,
+  // or a use that is an implicit def, so record implicit regs now.
+  BitVector ImplicitUses(State.getRegInfo().getNumRegs());
+  BitVector ImplicitDefs(State.getRegInfo().getNumRegs());
+  for (const auto &Op : Instr.Operands) {
+    if (Op.isReg() && Op.isImplicit() && !Op.isMemory()) {
+      assert(Op.isImplicitReg() && "Not an implicit register operand?");
+      if (Op.isUse())
+        ImplicitUses.set(Op.getImplicitReg());
+      else {
+        assert(Op.isDef() && "Not a use and not a def?");
+        ImplicitDefs.set(Op.getImplicitReg());
+      }
+    }
+  }
+  const auto ImplicitUseAliases =
+      getAliasedBits(State.getRegInfo(), ImplicitUses);
+  const auto ImplicitDefAliases =
+      getAliasedBits(State.getRegInfo(), ImplicitDefs);
   BitVector Defs(State.getRegInfo().getNumRegs());
   for (const auto &Op : Instr.Operands) {
     if (Op.isReg() && Op.isExplicit() && Op.isDef() && !Op.isMemory()) {
       auto PossibleRegisters = Op.getRegisterAliasing().sourceBits();
-      // Do not use forbidden registers.
+      // Do not use forbidden registers and regs that are implicitly used.
+      // Note that we don't try to avoid using implicit defs explicitly.
       remove(PossibleRegisters, ForbiddenRegisters);
-      assert(PossibleRegisters.any() && "No register left to choose from");
+      remove(PossibleRegisters, ImplicitUseAliases);
+      if (!PossibleRegisters.any())
+        return make_error<StringError>(
+            Twine("no available registers:\ncandidates:\n")
+                .concat(debugString(State.getRegInfo(),
+                                    Op.getRegisterAliasing().sourceBits()))
+                .concat("\nforbidden:\n")
+                .concat(debugString(State.getRegInfo(), ForbiddenRegisters))
+                .concat("\nimplicit use:\n")
+                .concat(debugString(State.getRegInfo(), ImplicitUseAliases)),
+            inconvertibleErrorCode());
       const auto RandomReg = randomBit(PossibleRegisters);
       Defs.set(RandomReg);
       Variant.getValueFor(Op) = MCOperand::createReg(RandomReg);
     }
   }
   // And pick random use values that are not reserved and don't alias with defs.
+  // Note that we don't try to avoid using implicit uses explicitly.
   const auto DefAliases = getAliasedBits(State.getRegInfo(), Defs);
   for (const auto &Op : Instr.Operands) {
     if (Op.isReg() && Op.isExplicit() && Op.isUse() && !Op.isMemory()) {
       auto PossibleRegisters = Op.getRegisterAliasing().sourceBits();
       remove(PossibleRegisters, ForbiddenRegisters);
       remove(PossibleRegisters, DefAliases);
+      remove(PossibleRegisters, ImplicitDefAliases);
       assert(PossibleRegisters.any() && "No register left to choose from");
       const auto RandomReg = randomBit(PossibleRegisters);
       Variant.getValueFor(Op) = MCOperand::createReg(RandomReg);
diff --git a/llvm/unittests/tools/llvm-exegesis/X86/SnippetGeneratorTest.cpp b/llvm/unittests/tools/llvm-exegesis/X86/SnippetGeneratorTest.cpp
--- a/llvm/unittests/tools/llvm-exegesis/X86/SnippetGeneratorTest.cpp
+++ b/llvm/unittests/tools/llvm-exegesis/X86/SnippetGeneratorTest.cpp
@@ -154,29 +154,6 @@
   consumeError(std::move(Error));
 }
 
-TEST_F(X86SerialSnippetGeneratorTest,
-       AvoidSerializingThroughImplicitRegisters) {
-  // MULX32rr implicitly uses EDX. We should not select that register to avoid
-  // serialization.
-  const unsigned Opcode = X86::MULX32rr;
-  randomGenerator().seed(0); // Initialize seed.
-  const Instruction &Instr = State.getIC().getInstr(Opcode);
-  // Forbid all registers but RDX/EDX/DX/DH/DL. The only option would be to
-  // choose that register, but that would serialize the instruction, so we
-  // should be returning an error.
-  auto AllRegisters = State.getRATC().emptyRegisters();
-  AllRegisters.flip();
-  AllRegisters.reset(X86::RDX);
-  AllRegisters.reset(X86::EDX);
-  AllRegisters.reset(X86::DX);
-  AllRegisters.reset(X86::DH);
-  AllRegisters.reset(X86::DL);
-  auto Error =
-      Generator.generateCodeTemplates(&Instr, AllRegisters).takeError();
-  // FIXME: EXPECT_TRUE + consumeError(std::move(Error)).
-  EXPECT_FALSE((bool)Error);
-}
-
 TEST_F(X86SerialSnippetGeneratorTest, DependencyThroughOtherOpcode) {
   // - CMP64rr
   // - Op0 Explicit Use RegClass(GR64)
@@ -385,6 +362,29 @@
               testing::HasSubstr("no available registers"));
 }
 
+TEST_F(X86ParallelSnippetGeneratorTest,
+       AvoidSerializingThroughImplicitRegisters) {
+  // MULX32rr implicitly uses EDX. We should not select that register to avoid
+  // serialization.
+  const unsigned Opcode = X86::MULX32rr;
+  randomGenerator().seed(0); // Initialize seed.
+  const Instruction &Instr = State.getIC().getInstr(Opcode);
+  // Forbid all registers but RDX/EDX/DX/DH/DL. The only option would be to
+  // choose that register, but that would serialize the instruction, so we
+  // should be returning an error.
+  auto AllRegisters = State.getRATC().emptyRegisters();
+  AllRegisters.flip();
+  AllRegisters.reset(X86::RDX);
+  AllRegisters.reset(X86::EDX);
+  AllRegisters.reset(X86::DX);
+  AllRegisters.reset(X86::DH);
+  AllRegisters.reset(X86::DL);
+  auto Err = Generator.generateCodeTemplates(&Instr, AllRegisters);
+  EXPECT_FALSE((bool)Err);
+  EXPECT_THAT(toString(Err.takeError()),
+              testing::HasSubstr("no available registers"));
+}
+
 class X86FakeSnippetGenerator : public SnippetGenerator {
 public:
   X86FakeSnippetGenerator(const LLVMState &State, const Options &Opts)