diff --git a/source/opt/instruction.cpp b/source/opt/instruction.cpp
index 19f6fff..126848e 100644
--- a/source/opt/instruction.cpp
+++ b/source/opt/instruction.cpp
@@ -623,7 +623,19 @@
     return false;
   }
   Instruction* type = context()->get_def_use_mgr()->GetDef(type_id());
-  return folder.IsFoldableType(type);
+  if (!folder.IsFoldableType(type)) {
+    return false;
+  }
+
+  // Even if the type of the instruction is foldable, its operands may not be
+  // foldable (e.g., comparisons of 64bit types).  Check that all operand types
+  // are foldable before accepting the instruction.
+  return WhileEachInOperand([&folder, this](const uint32_t* op_id) {
+    Instruction* def_inst = context()->get_def_use_mgr()->GetDef(*op_id);
+    Instruction* def_inst_type =
+        context()->get_def_use_mgr()->GetDef(def_inst->type_id());
+    return folder.IsFoldableType(def_inst_type);
+  });
 }
 
 bool Instruction::IsFloatingPointFoldingAllowed() const {
diff --git a/test/opt/fold_test.cpp b/test/opt/fold_test.cpp
index db01924..beb26f2 100644
--- a/test/opt/fold_test.cpp
+++ b/test/opt/fold_test.cpp
@@ -3297,7 +3297,16 @@
             "%2 = OpIMul %int %3 %int_1\n" +
             "OpReturn\n" +
             "OpFunctionEnd",
-        2, 3)
+        2, 3),
+    // Test case 42: Don't fold comparisons of 64-bit types
+    // (https://github.com/KhronosGroup/SPIRV-Tools/issues/3343).
+    InstructionFoldingCase<uint32_t>(
+        Header() + "%main = OpFunction %void None %void_func\n" +
+          "%main_lab = OpLabel\n" +
+          "%2 = OpSLessThan %bool %long_0 %long_2\n" +
+          "OpReturn\n" +
+          "OpFunctionEnd",
+        2, 0)
 ));
 
 INSTANTIATE_TEST_SUITE_P(CompositeExtractFoldingTest, GeneralInstructionFoldingTest,