Index: mlir/lib/Target/LLVMIR/ConvertFromLLVMIR.cpp
===================================================================
--- mlir/lib/Target/LLVMIR/ConvertFromLLVMIR.cpp
+++ mlir/lib/Target/LLVMIR/ConvertFromLLVMIR.cpp
@@ -170,6 +170,8 @@
   /// Imports GV as a GlobalOp, creating it if it doesn't exist.
   GlobalOp processGlobal(llvm::GlobalVariable *gv);
 
+  ~Importer();
+
 private:
   /// Returns personality of `f` as a FlatSymbolRefAttr.
   FlatSymbolRefAttr getPersonalityAsAttr(llvm::Function *f);
@@ -241,9 +243,20 @@
   Location unknownLoc;
   /// The stateful type translator (contains named structs).
   LLVM::TypeFromLLVMIRTranslator typeTranslator;
+  /// Values that will be removed after the translation is finished.
+  /// These are usually llvm::Instruction generated on-the-fly from
+  /// llvm::ConstantExpr::getAsInstruction.
+  SmallPtrSet<llvm::Value *, 2> cleanupValues;
 };
 } // namespace
 
+Importer::~Importer() {
+  for (auto *V : cleanupValues) {
+    if (V)
+      V->deleteValue();
+  }
+}
+
 Location Importer::processDebugLoc(const llvm::DebugLoc &loc,
                                    llvm::Instruction *inst) {
   if (!loc && inst) {
@@ -487,9 +500,16 @@
       return nullptr;
     assert(instMap.count(i));
 
-    // Remove this zombie LLVM instruction now, leaving us only with the MLIR
-    // op.
-    i->deleteValue();
+    // Eventually we need to delete `i`, but not right now. Because
+    // llvm::ConstantExpr::getAsInstruction created a new Instruction
+    // every time it is called. If we delete `i` right now, the next time
+    // getAsInstruction is called, it might allocate an Instruction that
+    // has the exact same memory address as the one we just deleted!
+    // This will become a problem because instMap is indexed by llvm::Value*,
+    // thus the aforementioned double booking issue will make processInstruction
+    // falsely believe that the new Instruction has been processed before
+    // and raised an assertion error.
+    cleanupValues.insert(i);
     return instMap[c] = instMap[i];
   }
   if (auto *ue = dyn_cast<llvm::UndefValue>(c)) {
Index: mlir/test/Target/LLVMIR/Import/deferred-delete.ll
===================================================================
--- /dev/null
+++ mlir/test/Target/LLVMIR/Import/deferred-delete.ll
@@ -0,0 +1,31 @@
+; RUN: mlir-translate --import-llvm %s | FileCheck %s
+; REQUIRES: asserts
+
+; This test is primarily used to make sure an assertion is not triggered.
+; Thus, we only wrote minimum level of checks.
+
+%my_struct = type {i32, i8*}
+; CHECK: llvm.mlir.constant(3 : i32) : i32
+; CHECK: llvm.mlir.constant(2 : i32) : i32
+; CHECK: llvm.mlir.addressof @str1 : !llvm.ptr<array<5 x i8>>
+; CHECK: llvm.getelementptr
+; CHECK: llvm.mlir.constant(7 : i32) : i32
+; CHECK: llvm.mlir.undef : !llvm.struct<"my_struct", (i32, ptr<i8>)>
+; CHECK: llvm.insertvalue
+; CHECK: llvm.insertvalue
+; CHECK: llvm.mlir.constant(1 : i32) : i32
+; CHECK: llvm.mlir.constant(0 : i32) : i32
+; CHECK: llvm.mlir.addressof @str0 : !llvm.ptr<array<5 x i8>>
+; CHECK: llvm.getelementptr
+; CHECK: llvm.mlir.constant(8 : i32) : i32
+; CHECK: llvm.mlir.undef : !llvm.struct<"my_struct", (i32, ptr<i8>)>
+; CHECK: llvm.insertvalue
+; CHECK: llvm.insertvalue
+; CHECK: llvm.mlir.undef : !llvm.array<2 x struct<"my_struct", (i32, ptr<i8>)>>
+; CHECK: llvm.insertvalue
+; CHECK: llvm.insertvalue
+; CHECK: llvm.return
+@str0 = private unnamed_addr constant [5 x i8] c"aaaa\00"
+@str1 = private unnamed_addr constant [5 x i8] c"bbbb\00"
+@g = global [2 x %my_struct] [%my_struct {i32 8, i8* getelementptr ([5 x i8], [5 x i8]* @str0, i32 0, i32 1)}, %my_struct {i32 7, i8* getelementptr ([5 x i8], [5 x i8]* @str1, i32 2, i32 3)}]
+