diff --git a/mlir/include/mlir/IR/SubElementInterfaces.td b/mlir/include/mlir/IR/SubElementInterfaces.td
--- a/mlir/include/mlir/IR/SubElementInterfaces.td
+++ b/mlir/include/mlir/IR/SubElementInterfaces.td
@@ -42,6 +42,11 @@
         would replace the very first attribute given by `walkImmediateSubElements`.
         On success, the new instance with the values replaced is returned. If replacement
         fails, nullptr is returned.
+
+        Note that replacing the sub-elements of mutable types or attributes is
+        not currently supported by the interface. If an implementing type or
+        attribute is mutable, it should return `nullptr` if it has no mechanism
+        for replacing sub elements.
       }], attrOrType, "replaceImmediateSubElements", (ins
         "::llvm::ArrayRef<::mlir::Attribute>":$replAttrs,
         "::llvm::ArrayRef<::mlir::Type>":$replTypes
@@ -106,7 +111,7 @@
     void walkSubTypes(llvm::function_ref<void(mlir::Type)> walkFn) {
       walkSubElements(/*walkAttrsFn=*/[](mlir::Attribute) {}, walkFn);
     }
-    
+
     /// Recursively replace all of the nested sub-attributes using the provided
     /// map function. Returns nullptr in the case of failure.
     }] # attrOrType # [{ replaceSubElements(
diff --git a/mlir/lib/Dialect/LLVMIR/IR/LLVMTypes.cpp b/mlir/lib/Dialect/LLVMIR/IR/LLVMTypes.cpp
--- a/mlir/lib/Dialect/LLVMIR/IR/LLVMTypes.cpp
+++ b/mlir/lib/Dialect/LLVMIR/IR/LLVMTypes.cpp
@@ -698,9 +698,12 @@
 
 Type LLVMStructType::replaceImmediateSubElements(
     ArrayRef<Attribute> replAttrs, ArrayRef<Type> replTypes) const {
-  // TODO: It's not clear how we support replacing sub-elements of mutable
-  // types.
-  return nullptr;
+  if (isIdentified()) {
+    // TODO: It's not clear how we support replacing sub-elements of mutable
+    // types.
+    return nullptr;
+  }
+  return getLiteral(getContext(), replTypes, isPacked());
 }
 
 //===----------------------------------------------------------------------===//
diff --git a/mlir/lib/IR/SubElementInterfaces.cpp b/mlir/lib/IR/SubElementInterfaces.cpp
--- a/mlir/lib/IR/SubElementInterfaces.cpp
+++ b/mlir/lib/IR/SubElementInterfaces.cpp
@@ -93,14 +93,6 @@
 //===----------------------------------------------------------------------===//
 // ReplaceSubElements
 
-/// Return if the given element is mutable.
-static bool isMutable(Attribute attr) {
-  return attr.hasTrait<AttributeTrait::IsMutable>();
-}
-static bool isMutable(Type type) {
-  return type.hasTrait<TypeTrait::IsMutable>();
-}
-
 template <typename InterfaceT, typename T, typename ReplaceSubElementFnT>
 static void updateSubElementImpl(
     T element, function_ref<std::pair<T, WalkResult>(T)> walkFn,
@@ -187,12 +179,6 @@
   if (!*changed)
     return interface;
 
-  // If this element is mutable, we don't support changing its sub elements, the
-  // sub element walk doesn't give us a valid ordering for what we need here. If
-  // we want to support mutable elements, we'll need something more.
-  if (isMutable(interface))
-    return {};
-
   // Use the new elements during the replacement.
   return interface.replaceImmediateSubElements(newAttrs, newTypes);
 }