diff --git a/src/reader/spirv/parser.cc b/src/reader/spirv/parser.cc
index eabdc4b..0191387 100644
--- a/src/reader/spirv/parser.cc
+++ b/src/reader/spirv/parser.cc
@@ -52,7 +52,7 @@
 
   // If the generated program contains matrices with a custom MatrixStride
   // attribute then we need to decompose these into an array of vectors
-  if (transform::DecomposeStridedMatrix::ShouldRun(&program)) {
+  if (transform::DecomposeStridedMatrix().ShouldRun(&program)) {
     transform::Manager manager;
     manager.Add<transform::Unshadow>();
     manager.Add<transform::SimplifyPointers>();
diff --git a/src/transform/add_empty_entry_point.cc b/src/transform/add_empty_entry_point.cc
index a9f057e..cbc7e0c 100644
--- a/src/transform/add_empty_entry_point.cc
+++ b/src/transform/add_empty_entry_point.cc
@@ -27,7 +27,9 @@
 
 AddEmptyEntryPoint::~AddEmptyEntryPoint() = default;
 
-void AddEmptyEntryPoint::Run(CloneContext& ctx, const DataMap&, DataMap&) {
+void AddEmptyEntryPoint::Run(CloneContext& ctx,
+                             const DataMap&,
+                             DataMap&) const {
   for (auto* func : ctx.src->AST().Functions()) {
     if (func->IsEntryPoint()) {
       ctx.Clone();
diff --git a/src/transform/add_empty_entry_point.h b/src/transform/add_empty_entry_point.h
index dc65a0b..e955080 100644
--- a/src/transform/add_empty_entry_point.h
+++ b/src/transform/add_empty_entry_point.h
@@ -35,7 +35,9 @@
   /// ProgramBuilder
   /// @param inputs optional extra transform-specific input data
   /// @param outputs optional extra transform-specific output data
-  void Run(CloneContext& ctx, const DataMap& inputs, DataMap& outputs) override;
+  void Run(CloneContext& ctx,
+           const DataMap& inputs,
+           DataMap& outputs) const override;
 };
 
 }  // namespace transform
diff --git a/src/transform/add_spirv_block_decoration.cc b/src/transform/add_spirv_block_decoration.cc
index 3995c83..1bb9f85 100644
--- a/src/transform/add_spirv_block_decoration.cc
+++ b/src/transform/add_spirv_block_decoration.cc
@@ -33,7 +33,9 @@
 
 AddSpirvBlockDecoration::~AddSpirvBlockDecoration() = default;
 
-void AddSpirvBlockDecoration::Run(CloneContext& ctx, const DataMap&, DataMap&) {
+void AddSpirvBlockDecoration::Run(CloneContext& ctx,
+                                  const DataMap&,
+                                  DataMap&) const {
   auto& sem = ctx.src->Sem();
 
   // Collect the set of structs that are nested in other types.
diff --git a/src/transform/add_spirv_block_decoration.h b/src/transform/add_spirv_block_decoration.h
index 2f23fb9..047c55e 100644
--- a/src/transform/add_spirv_block_decoration.h
+++ b/src/transform/add_spirv_block_decoration.h
@@ -65,7 +65,9 @@
   /// ProgramBuilder
   /// @param inputs optional extra transform-specific input data
   /// @param outputs optional extra transform-specific output data
-  void Run(CloneContext& ctx, const DataMap& inputs, DataMap& outputs) override;
+  void Run(CloneContext& ctx,
+           const DataMap& inputs,
+           DataMap& outputs) const override;
 };
 
 }  // namespace transform
diff --git a/src/transform/array_length_from_uniform.cc b/src/transform/array_length_from_uniform.cc
index 32289fe..b34dad3 100644
--- a/src/transform/array_length_from_uniform.cc
+++ b/src/transform/array_length_from_uniform.cc
@@ -95,7 +95,7 @@
 
 void ArrayLengthFromUniform::Run(CloneContext& ctx,
                                  const DataMap& inputs,
-                                 DataMap& outputs) {
+                                 DataMap& outputs) const {
   if (!Requires<SimplifyPointers>(ctx)) {
     return;
   }
diff --git a/src/transform/array_length_from_uniform.h b/src/transform/array_length_from_uniform.h
index bd7a461..bfeaffe 100644
--- a/src/transform/array_length_from_uniform.h
+++ b/src/transform/array_length_from_uniform.h
@@ -103,7 +103,9 @@
   /// ProgramBuilder
   /// @param inputs optional extra transform-specific input data
   /// @param outputs optional extra transform-specific output data
-  void Run(CloneContext& ctx, const DataMap& inputs, DataMap& outputs) override;
+  void Run(CloneContext& ctx,
+           const DataMap& inputs,
+           DataMap& outputs) const override;
 };
 
 }  // namespace transform
diff --git a/src/transform/binding_remapper.cc b/src/transform/binding_remapper.cc
index f1ead01..feff411 100644
--- a/src/transform/binding_remapper.cc
+++ b/src/transform/binding_remapper.cc
@@ -42,7 +42,9 @@
 BindingRemapper::BindingRemapper() = default;
 BindingRemapper::~BindingRemapper() = default;
 
-void BindingRemapper::Run(CloneContext& ctx, const DataMap& inputs, DataMap&) {
+void BindingRemapper::Run(CloneContext& ctx,
+                          const DataMap& inputs,
+                          DataMap&) const {
   auto* remappings = inputs.Get<Remappings>();
   if (!remappings) {
     ctx.dst->Diagnostics().add_error(
diff --git a/src/transform/binding_remapper.h b/src/transform/binding_remapper.h
index 8e0d8fd..da837bd 100644
--- a/src/transform/binding_remapper.h
+++ b/src/transform/binding_remapper.h
@@ -75,7 +75,9 @@
   /// ProgramBuilder
   /// @param inputs optional extra transform-specific input data
   /// @param outputs optional extra transform-specific output data
-  void Run(CloneContext& ctx, const DataMap& inputs, DataMap& outputs) override;
+  void Run(CloneContext& ctx,
+           const DataMap& inputs,
+           DataMap& outputs) const override;
 };
 
 }  // namespace transform
diff --git a/src/transform/calculate_array_length.cc b/src/transform/calculate_array_length.cc
index 6c6c6ff..9d560ed 100644
--- a/src/transform/calculate_array_length.cc
+++ b/src/transform/calculate_array_length.cc
@@ -71,7 +71,9 @@
 CalculateArrayLength::CalculateArrayLength() = default;
 CalculateArrayLength::~CalculateArrayLength() = default;
 
-void CalculateArrayLength::Run(CloneContext& ctx, const DataMap&, DataMap&) {
+void CalculateArrayLength::Run(CloneContext& ctx,
+                               const DataMap&,
+                               DataMap&) const {
   auto& sem = ctx.src->Sem();
   if (!Requires<SimplifyPointers>(ctx)) {
     return;
diff --git a/src/transform/calculate_array_length.h b/src/transform/calculate_array_length.h
index 55aabe4..6394dd7 100644
--- a/src/transform/calculate_array_length.h
+++ b/src/transform/calculate_array_length.h
@@ -63,7 +63,9 @@
   /// ProgramBuilder
   /// @param inputs optional extra transform-specific input data
   /// @param outputs optional extra transform-specific output data
-  void Run(CloneContext& ctx, const DataMap& inputs, DataMap& outputs) override;
+  void Run(CloneContext& ctx,
+           const DataMap& inputs,
+           DataMap& outputs) const override;
 };
 
 }  // namespace transform
diff --git a/src/transform/canonicalize_entry_point_io.cc b/src/transform/canonicalize_entry_point_io.cc
index c78ac19..d0734a0 100644
--- a/src/transform/canonicalize_entry_point_io.cc
+++ b/src/transform/canonicalize_entry_point_io.cc
@@ -550,7 +550,7 @@
 
 void CanonicalizeEntryPointIO::Run(CloneContext& ctx,
                                    const DataMap& inputs,
-                                   DataMap&) {
+                                   DataMap&) const {
   if (!Requires<Unshadow>(ctx)) {
     return;
   }
diff --git a/src/transform/canonicalize_entry_point_io.h b/src/transform/canonicalize_entry_point_io.h
index 0bf16ba..6271444 100644
--- a/src/transform/canonicalize_entry_point_io.h
+++ b/src/transform/canonicalize_entry_point_io.h
@@ -131,7 +131,9 @@
   /// ProgramBuilder
   /// @param inputs optional extra transform-specific input data
   /// @param outputs optional extra transform-specific output data
-  void Run(CloneContext& ctx, const DataMap& inputs, DataMap& outputs) override;
+  void Run(CloneContext& ctx,
+           const DataMap& inputs,
+           DataMap& outputs) const override;
 
   struct State;
 };
diff --git a/src/transform/combine_samplers.cc b/src/transform/combine_samplers.cc
index 66f6a94..ac48cdb 100644
--- a/src/transform/combine_samplers.cc
+++ b/src/transform/combine_samplers.cc
@@ -304,7 +304,9 @@
 
 CombineSamplers::~CombineSamplers() = default;
 
-void CombineSamplers::Run(CloneContext& ctx, const DataMap& inputs, DataMap&) {
+void CombineSamplers::Run(CloneContext& ctx,
+                          const DataMap& inputs,
+                          DataMap&) const {
   auto* binding_info = inputs.Get<BindingInfo>();
   if (!binding_info) {
     ctx.dst->Diagnostics().add_error(
diff --git a/src/transform/combine_samplers.h b/src/transform/combine_samplers.h
index ce83373..2108ccb 100644
--- a/src/transform/combine_samplers.h
+++ b/src/transform/combine_samplers.h
@@ -95,7 +95,9 @@
   /// ProgramBuilder
   /// @param inputs optional extra transform-specific input data
   /// @param outputs optional extra transform-specific output data
-  void Run(CloneContext& ctx, const DataMap& inputs, DataMap& outputs) override;
+  void Run(CloneContext& ctx,
+           const DataMap& inputs,
+           DataMap& outputs) const override;
 };
 
 }  // namespace transform
diff --git a/src/transform/decompose_memory_access.cc b/src/transform/decompose_memory_access.cc
index fecb76f..81511dc 100644
--- a/src/transform/decompose_memory_access.cc
+++ b/src/transform/decompose_memory_access.cc
@@ -790,7 +790,9 @@
 DecomposeMemoryAccess::DecomposeMemoryAccess() = default;
 DecomposeMemoryAccess::~DecomposeMemoryAccess() = default;
 
-void DecomposeMemoryAccess::Run(CloneContext& ctx, const DataMap&, DataMap&) {
+void DecomposeMemoryAccess::Run(CloneContext& ctx,
+                                const DataMap&,
+                                DataMap&) const {
   auto& sem = ctx.src->Sem();
 
   State state(ctx);
diff --git a/src/transform/decompose_memory_access.h b/src/transform/decompose_memory_access.h
index 9fb1b0f..76fbbc4 100644
--- a/src/transform/decompose_memory_access.h
+++ b/src/transform/decompose_memory_access.h
@@ -112,7 +112,9 @@
   /// ProgramBuilder
   /// @param inputs optional extra transform-specific input data
   /// @param outputs optional extra transform-specific output data
-  void Run(CloneContext& ctx, const DataMap& inputs, DataMap& outputs) override;
+  void Run(CloneContext& ctx,
+           const DataMap& inputs,
+           DataMap& outputs) const override;
 
   struct State;
 };
diff --git a/src/transform/decompose_strided_matrix.cc b/src/transform/decompose_strided_matrix.cc
index 9b55528..11eb5c6 100644
--- a/src/transform/decompose_strided_matrix.cc
+++ b/src/transform/decompose_strided_matrix.cc
@@ -107,7 +107,7 @@
 
 DecomposeStridedMatrix::~DecomposeStridedMatrix() = default;
 
-bool DecomposeStridedMatrix::ShouldRun(const Program* program) {
+bool DecomposeStridedMatrix::ShouldRun(const Program* program) const {
   bool should_run = false;
   GatherCustomStrideMatrixMembers(
       program, [&](const sem::StructMember*, sem::Matrix*, uint32_t) {
@@ -117,7 +117,9 @@
   return should_run;
 }
 
-void DecomposeStridedMatrix::Run(CloneContext& ctx, const DataMap&, DataMap&) {
+void DecomposeStridedMatrix::Run(CloneContext& ctx,
+                                 const DataMap&,
+                                 DataMap&) const {
   if (!Requires<SimplifyPointers>(ctx)) {
     return;
   }
diff --git a/src/transform/decompose_strided_matrix.h b/src/transform/decompose_strided_matrix.h
index 3283049..587b676 100644
--- a/src/transform/decompose_strided_matrix.h
+++ b/src/transform/decompose_strided_matrix.h
@@ -36,7 +36,7 @@
 
   /// @param program the program to inspect
   /// @returns true if this transform should be run for the given program
-  static bool ShouldRun(const Program* program);
+  bool ShouldRun(const Program* program) const override;
 
  protected:
   /// Runs the transform using the CloneContext built for transforming a
@@ -45,7 +45,9 @@
   /// ProgramBuilder
   /// @param inputs optional extra transform-specific input data
   /// @param outputs optional extra transform-specific output data
-  void Run(CloneContext& ctx, const DataMap& inputs, DataMap& outputs) override;
+  void Run(CloneContext& ctx,
+           const DataMap& inputs,
+           DataMap& outputs) const override;
 };
 
 }  // namespace transform
diff --git a/src/transform/decompose_strided_matrix_test.cc b/src/transform/decompose_strided_matrix_test.cc
index 8561ccf..97aa391 100644
--- a/src/transform/decompose_strided_matrix_test.cc
+++ b/src/transform/decompose_strided_matrix_test.cc
@@ -41,11 +41,45 @@
 }
 
 TEST_F(DecomposeStridedMatrixTest, MissingDependencySimplify) {
-  auto* src = R"()";
+  // struct S {
+  //   [[offset(16), stride(32)]]
+  //   [[internal(ignore_stride_decoration)]]
+  //   m : mat2x2<f32>;
+  // };
+  // [[group(0), binding(0)]] var<uniform> s : S;
+  //
+  // [[stage(compute), workgroup_size(1)]]
+  // fn f() {
+  //   let x : mat2x2<f32> = s.m;
+  // }
+  ProgramBuilder b;
+  auto* S = b.Structure(
+      "S",
+      {
+          b.Member(
+              "m", b.ty.mat2x2<f32>(),
+              {
+                  b.create<ast::StructMemberOffsetDecoration>(16),
+                  b.create<ast::StrideDecoration>(32),
+                  b.Disable(ast::DisabledValidation::kIgnoreStrideDecoration),
+              }),
+      });
+  b.Global("s", b.ty.Of(S), ast::StorageClass::kUniform,
+           b.GroupAndBinding(0, 0));
+  b.Func(
+      "f", {}, b.ty.void_(),
+      {
+          b.Decl(b.Const("x", b.ty.mat2x2<f32>(), b.MemberAccessor("s", "m"))),
+      },
+      {
+          b.Stage(ast::PipelineStage::kCompute),
+          b.WorkgroupSize(1),
+      });
+
   auto* expect =
       R"(error: tint::transform::DecomposeStridedMatrix depends on tint::transform::SimplifyPointers but the dependency was not run)";
 
-  auto got = Run<DecomposeStridedMatrix>(src);
+  auto got = Run<DecomposeStridedMatrix>(Program(std::move(b)));
 
   EXPECT_EQ(expect, str(got));
 }
diff --git a/src/transform/external_texture_transform.cc b/src/transform/external_texture_transform.cc
index 4dcf1fe..1d71260 100644
--- a/src/transform/external_texture_transform.cc
+++ b/src/transform/external_texture_transform.cc
@@ -28,7 +28,7 @@
 
 void ExternalTextureTransform::Run(CloneContext& ctx,
                                    const DataMap&,
-                                   DataMap&) {
+                                   DataMap&) const {
   auto& sem = ctx.src->Sem();
 
   // Within this transform, usages of texture_external are replaced with a
diff --git a/src/transform/external_texture_transform.h b/src/transform/external_texture_transform.h
index 6bb8091..4e70bc7 100644
--- a/src/transform/external_texture_transform.h
+++ b/src/transform/external_texture_transform.h
@@ -42,7 +42,9 @@
   /// ProgramBuilder
   /// @param inputs optional extra transform-specific input data
   /// @param outputs optional extra transform-specific output data
-  void Run(CloneContext& ctx, const DataMap& inputs, DataMap& outputs) override;
+  void Run(CloneContext& ctx,
+           const DataMap& inputs,
+           DataMap& outputs) const override;
 };
 
 }  // namespace transform
diff --git a/src/transform/first_index_offset.cc b/src/transform/first_index_offset.cc
index 6fcff16..50a65fa 100644
--- a/src/transform/first_index_offset.cc
+++ b/src/transform/first_index_offset.cc
@@ -59,7 +59,7 @@
 
 void FirstIndexOffset::Run(CloneContext& ctx,
                            const DataMap& inputs,
-                           DataMap& outputs) {
+                           DataMap& outputs) const {
   // Get the uniform buffer binding point
   uint32_t ub_binding = binding_;
   uint32_t ub_group = group_;
diff --git a/src/transform/first_index_offset.h b/src/transform/first_index_offset.h
index a885581..8b7e0e0 100644
--- a/src/transform/first_index_offset.h
+++ b/src/transform/first_index_offset.h
@@ -122,7 +122,9 @@
   /// ProgramBuilder
   /// @param inputs optional extra transform-specific input data
   /// @param outputs optional extra transform-specific output data
-  void Run(CloneContext& ctx, const DataMap& inputs, DataMap& outputs) override;
+  void Run(CloneContext& ctx,
+           const DataMap& inputs,
+           DataMap& outputs) const override;
 
  private:
   uint32_t binding_ = 0;
diff --git a/src/transform/fold_constants.cc b/src/transform/fold_constants.cc
index 215c5bf..8ef513c 100644
--- a/src/transform/fold_constants.cc
+++ b/src/transform/fold_constants.cc
@@ -33,7 +33,7 @@
 
 FoldConstants::~FoldConstants() = default;
 
-void FoldConstants::Run(CloneContext& ctx, const DataMap&, DataMap&) {
+void FoldConstants::Run(CloneContext& ctx, const DataMap&, DataMap&) const {
   ctx.ReplaceAll([&](const ast::Expression* expr) -> const ast::Expression* {
     auto* call = ctx.src->Sem().Get<sem::Call>(expr);
     if (!call) {
diff --git a/src/transform/fold_constants.h b/src/transform/fold_constants.h
index 861a06b..87d8522 100644
--- a/src/transform/fold_constants.h
+++ b/src/transform/fold_constants.h
@@ -36,7 +36,9 @@
   /// ProgramBuilder
   /// @param inputs optional extra transform-specific input data
   /// @param outputs optional extra transform-specific output data
-  void Run(CloneContext& ctx, const DataMap& inputs, DataMap& outputs) override;
+  void Run(CloneContext& ctx,
+           const DataMap& inputs,
+           DataMap& outputs) const override;
 };
 
 }  // namespace transform
diff --git a/src/transform/fold_trivial_single_use_lets.cc b/src/transform/fold_trivial_single_use_lets.cc
index aa83b8f..a213d5c 100644
--- a/src/transform/fold_trivial_single_use_lets.cc
+++ b/src/transform/fold_trivial_single_use_lets.cc
@@ -51,7 +51,7 @@
 
 void FoldTrivialSingleUseLets::Run(CloneContext& ctx,
                                    const DataMap&,
-                                   DataMap&) {
+                                   DataMap&) const {
   for (auto* node : ctx.src->ASTNodes().Objects()) {
     if (auto* block = node->As<ast::BlockStatement>()) {
       auto& stmts = block->statements;
diff --git a/src/transform/fold_trivial_single_use_lets.h b/src/transform/fold_trivial_single_use_lets.h
index 05ff33e..6c8f17a 100644
--- a/src/transform/fold_trivial_single_use_lets.h
+++ b/src/transform/fold_trivial_single_use_lets.h
@@ -50,7 +50,9 @@
   /// ProgramBuilder
   /// @param inputs optional extra transform-specific input data
   /// @param outputs optional extra transform-specific output data
-  void Run(CloneContext& ctx, const DataMap& inputs, DataMap& outputs) override;
+  void Run(CloneContext& ctx,
+           const DataMap& inputs,
+           DataMap& outputs) const override;
 };
 
 }  // namespace transform
diff --git a/src/transform/for_loop_to_loop.cc b/src/transform/for_loop_to_loop.cc
index 1eab804..6277aed 100644
--- a/src/transform/for_loop_to_loop.cc
+++ b/src/transform/for_loop_to_loop.cc
@@ -25,7 +25,7 @@
 
 ForLoopToLoop::~ForLoopToLoop() = default;
 
-void ForLoopToLoop::Run(CloneContext& ctx, const DataMap&, DataMap&) {
+void ForLoopToLoop::Run(CloneContext& ctx, const DataMap&, DataMap&) const {
   ctx.ReplaceAll(
       [&](const ast::ForLoopStatement* for_loop) -> const ast::Statement* {
         ast::StatementList stmts;
diff --git a/src/transform/for_loop_to_loop.h b/src/transform/for_loop_to_loop.h
index 0b738ec..80a64e0 100644
--- a/src/transform/for_loop_to_loop.h
+++ b/src/transform/for_loop_to_loop.h
@@ -37,7 +37,9 @@
   /// ProgramBuilder
   /// @param inputs optional extra transform-specific input data
   /// @param outputs optional extra transform-specific output data
-  void Run(CloneContext& ctx, const DataMap& inputs, DataMap& outputs) override;
+  void Run(CloneContext& ctx,
+           const DataMap& inputs,
+           DataMap& outputs) const override;
 };
 
 }  // namespace transform
diff --git a/src/transform/glsl.cc b/src/transform/glsl.cc
index 8f51bee..af97f0b 100644
--- a/src/transform/glsl.cc
+++ b/src/transform/glsl.cc
@@ -45,7 +45,7 @@
 Glsl::Glsl() = default;
 Glsl::~Glsl() = default;
 
-Output Glsl::Run(const Program* in, const DataMap& inputs) {
+Output Glsl::Run(const Program* in, const DataMap& inputs) const {
   Manager manager;
   DataMap data;
 
diff --git a/src/transform/glsl.h b/src/transform/glsl.h
index de3b225..bc6a2b9 100644
--- a/src/transform/glsl.h
+++ b/src/transform/glsl.h
@@ -61,7 +61,7 @@
   /// @param program the source program to transform
   /// @param data optional extra transform-specific data
   /// @returns the transformation result
-  Output Run(const Program* program, const DataMap& data = {}) override;
+  Output Run(const Program* program, const DataMap& data = {}) const override;
 };
 
 }  // namespace transform
diff --git a/src/transform/localize_struct_array_assignment.cc b/src/transform/localize_struct_array_assignment.cc
index 6d73ec9..af3c99e 100644
--- a/src/transform/localize_struct_array_assignment.cc
+++ b/src/transform/localize_struct_array_assignment.cc
@@ -215,7 +215,7 @@
 
 void LocalizeStructArrayAssignment::Run(CloneContext& ctx,
                                         const DataMap&,
-                                        DataMap&) {
+                                        DataMap&) const {
   if (!Requires<SimplifyPointers>(ctx)) {
     return;
   }
diff --git a/src/transform/localize_struct_array_assignment.h b/src/transform/localize_struct_array_assignment.h
index ce56e14..7fa18a2 100644
--- a/src/transform/localize_struct_array_assignment.h
+++ b/src/transform/localize_struct_array_assignment.h
@@ -41,7 +41,9 @@
   /// ProgramBuilder
   /// @param inputs optional extra transform-specific input data
   /// @param outputs optional extra transform-specific output data
-  void Run(CloneContext& ctx, const DataMap& inputs, DataMap& outputs) override;
+  void Run(CloneContext& ctx,
+           const DataMap& inputs,
+           DataMap& outputs) const override;
 
  private:
   class State;
diff --git a/src/transform/loop_to_for_loop.cc b/src/transform/loop_to_for_loop.cc
index d2da837..9378a71 100644
--- a/src/transform/loop_to_for_loop.cc
+++ b/src/transform/loop_to_for_loop.cc
@@ -56,7 +56,7 @@
 
 LoopToForLoop::~LoopToForLoop() = default;
 
-void LoopToForLoop::Run(CloneContext& ctx, const DataMap&, DataMap&) {
+void LoopToForLoop::Run(CloneContext& ctx, const DataMap&, DataMap&) const {
   ctx.ReplaceAll([&](const ast::LoopStatement* loop) -> const ast::Statement* {
     // For loop condition is taken from the first statement in the loop.
     // This requires an if-statement with either:
diff --git a/src/transform/loop_to_for_loop.h b/src/transform/loop_to_for_loop.h
index 0c855fb..f3f729d 100644
--- a/src/transform/loop_to_for_loop.h
+++ b/src/transform/loop_to_for_loop.h
@@ -37,7 +37,9 @@
   /// ProgramBuilder
   /// @param inputs optional extra transform-specific input data
   /// @param outputs optional extra transform-specific output data
-  void Run(CloneContext& ctx, const DataMap& inputs, DataMap& outputs) override;
+  void Run(CloneContext& ctx,
+           const DataMap& inputs,
+           DataMap& outputs) const override;
 };
 
 }  // namespace transform
diff --git a/src/transform/manager.cc b/src/transform/manager.cc
index 43e6712..8841dd7 100644
--- a/src/transform/manager.cc
+++ b/src/transform/manager.cc
@@ -32,7 +32,7 @@
 Manager::Manager() = default;
 Manager::~Manager() = default;
 
-Output Manager::Run(const Program* program, const DataMap& data) {
+Output Manager::Run(const Program* program, const DataMap& data) const {
 #if TINT_PRINT_PROGRAM_FOR_EACH_TRANSFORM
   auto print_program = [&](const char* msg, const Transform* transform) {
     auto wgsl = Program::printer(program);
@@ -49,26 +49,33 @@
   };
 #endif
 
+  const Program* in = program;
+
   Output out;
-  if (!transforms_.empty()) {
-    for (const auto& transform : transforms_) {
-      TINT_IF_PRINT_PROGRAM(print_program("Input to", transform.get()));
-
-      auto res = transform->Run(program, data);
-      out.program = std::move(res.program);
-      out.data.Add(std::move(res.data));
-      program = &out.program;
-      if (!program->IsValid()) {
-        TINT_IF_PRINT_PROGRAM(
-            print_program("Invalid output of", transform.get()));
-        return out;
-      }
-
-      if (transform == transforms_.back()) {
-        TINT_IF_PRINT_PROGRAM(print_program("Output of", transform.get()));
-      }
+  for (const auto& transform : transforms_) {
+    if (!transform->ShouldRun(in)) {
+      TINT_IF_PRINT_PROGRAM(std::cout << "Skipping "
+                                      << transform->TypeInfo().name);
+      continue;
     }
-  } else {
+    TINT_IF_PRINT_PROGRAM(print_program("Input to", transform.get()));
+
+    auto res = transform->Run(in, data);
+    out.program = std::move(res.program);
+    out.data.Add(std::move(res.data));
+    in = &out.program;
+    if (!in->IsValid()) {
+      TINT_IF_PRINT_PROGRAM(
+          print_program("Invalid output of", transform.get()));
+      return out;
+    }
+
+    if (transform == transforms_.back()) {
+      TINT_IF_PRINT_PROGRAM(print_program("Output of", transform.get()));
+    }
+  }
+
+  if (program == in) {
     out.program = program->Clone();
   }
 
diff --git a/src/transform/manager.h b/src/transform/manager.h
index 8d31bb5..e5ef910 100644
--- a/src/transform/manager.h
+++ b/src/transform/manager.h
@@ -52,7 +52,7 @@
   /// @param program the source program to transform
   /// @param data optional extra transform-specific input data
   /// @returns the transformed program and diagnostics
-  Output Run(const Program* program, const DataMap& data = {}) override;
+  Output Run(const Program* program, const DataMap& data = {}) const override;
 
  private:
   std::vector<std::unique_ptr<Transform>> transforms_;
diff --git a/src/transform/module_scope_var_to_entry_point_param.cc b/src/transform/module_scope_var_to_entry_point_param.cc
index cdd0e49..9005450 100644
--- a/src/transform/module_scope_var_to_entry_point_param.cc
+++ b/src/transform/module_scope_var_to_entry_point_param.cc
@@ -379,7 +379,7 @@
 
 void ModuleScopeVarToEntryPointParam::Run(CloneContext& ctx,
                                           const DataMap&,
-                                          DataMap&) {
+                                          DataMap&) const {
   State state{ctx};
   state.Process();
   ctx.Clone();
diff --git a/src/transform/module_scope_var_to_entry_point_param.h b/src/transform/module_scope_var_to_entry_point_param.h
index 29132c8..0ba88a5 100644
--- a/src/transform/module_scope_var_to_entry_point_param.h
+++ b/src/transform/module_scope_var_to_entry_point_param.h
@@ -77,7 +77,9 @@
   /// ProgramBuilder
   /// @param inputs optional extra transform-specific input data
   /// @param outputs optional extra transform-specific output data
-  void Run(CloneContext& ctx, const DataMap& inputs, DataMap& outputs) override;
+  void Run(CloneContext& ctx,
+           const DataMap& inputs,
+           DataMap& outputs) const override;
 
   struct State;
 };
diff --git a/src/transform/multiplanar_external_texture.cc b/src/transform/multiplanar_external_texture.cc
index 74ef782..f18c0cc 100644
--- a/src/transform/multiplanar_external_texture.cc
+++ b/src/transform/multiplanar_external_texture.cc
@@ -413,10 +413,10 @@
 // parameters. Calls to textureLoad or textureSampleLevel that contain a
 // texture_external parameter will be transformed into a newly generated version
 // of the function, which can perform the desired operation on a single RGBA
-// plane or on seperate Y and UV planes.
+// plane or on separate Y and UV planes.
 void MultiplanarExternalTexture::Run(CloneContext& ctx,
                                      const DataMap& inputs,
-                                     DataMap&) {
+                                     DataMap&) const {
   auto* new_binding_points = inputs.Get<NewBindingPoints>();
 
   if (!new_binding_points) {
diff --git a/src/transform/multiplanar_external_texture.h b/src/transform/multiplanar_external_texture.h
index ad1e61b..0a999da 100644
--- a/src/transform/multiplanar_external_texture.h
+++ b/src/transform/multiplanar_external_texture.h
@@ -85,7 +85,9 @@
   /// ProgramBuilder
   /// @param inputs optional extra transform-specific input data
   /// @param outputs optional extra transform-specific output data
-  void Run(CloneContext& ctx, const DataMap& inputs, DataMap& outputs) override;
+  void Run(CloneContext& ctx,
+           const DataMap& inputs,
+           DataMap& outputs) const override;
 };
 
 }  // namespace transform
diff --git a/src/transform/num_workgroups_from_uniform.cc b/src/transform/num_workgroups_from_uniform.cc
index 1e0f77b..b190935 100644
--- a/src/transform/num_workgroups_from_uniform.cc
+++ b/src/transform/num_workgroups_from_uniform.cc
@@ -54,7 +54,7 @@
 
 void NumWorkgroupsFromUniform::Run(CloneContext& ctx,
                                    const DataMap& inputs,
-                                   DataMap&) {
+                                   DataMap&) const {
   if (!Requires<CanonicalizeEntryPointIO>(ctx)) {
     return;
   }
diff --git a/src/transform/num_workgroups_from_uniform.h b/src/transform/num_workgroups_from_uniform.h
index ab8daa6..794768c 100644
--- a/src/transform/num_workgroups_from_uniform.h
+++ b/src/transform/num_workgroups_from_uniform.h
@@ -70,7 +70,9 @@
   /// ProgramBuilder
   /// @param inputs optional extra transform-specific input data
   /// @param outputs optional extra transform-specific output data
-  void Run(CloneContext& ctx, const DataMap& inputs, DataMap& outputs) override;
+  void Run(CloneContext& ctx,
+           const DataMap& inputs,
+           DataMap& outputs) const override;
 };
 
 }  // namespace transform
diff --git a/src/transform/pad_array_elements.cc b/src/transform/pad_array_elements.cc
index b732af5..f469a20 100644
--- a/src/transform/pad_array_elements.cc
+++ b/src/transform/pad_array_elements.cc
@@ -97,7 +97,7 @@
 
 PadArrayElements::~PadArrayElements() = default;
 
-void PadArrayElements::Run(CloneContext& ctx, const DataMap&, DataMap&) {
+void PadArrayElements::Run(CloneContext& ctx, const DataMap&, DataMap&) const {
   auto& sem = ctx.src->Sem();
 
   std::unordered_map<const sem::Array*, ArrayBuilder> padded_arrays;
diff --git a/src/transform/pad_array_elements.h b/src/transform/pad_array_elements.h
index cbb3e14..78a8c01 100644
--- a/src/transform/pad_array_elements.h
+++ b/src/transform/pad_array_elements.h
@@ -45,7 +45,9 @@
   /// ProgramBuilder
   /// @param inputs optional extra transform-specific input data
   /// @param outputs optional extra transform-specific output data
-  void Run(CloneContext& ctx, const DataMap& inputs, DataMap& outputs) override;
+  void Run(CloneContext& ctx,
+           const DataMap& inputs,
+           DataMap& outputs) const override;
 };
 
 }  // namespace transform
diff --git a/src/transform/promote_side_effects_to_decl.cc b/src/transform/promote_side_effects_to_decl.cc
index f3e5eb1..6274187 100644
--- a/src/transform/promote_side_effects_to_decl.cc
+++ b/src/transform/promote_side_effects_to_decl.cc
@@ -398,7 +398,7 @@
 
 void PromoteSideEffectsToDecl::Run(CloneContext& ctx,
                                    const DataMap& inputs,
-                                   DataMap&) {
+                                   DataMap&) const {
   auto* cfg = inputs.Get<Config>();
   if (cfg == nullptr) {
     ctx.dst->Diagnostics().add_error(
diff --git a/src/transform/promote_side_effects_to_decl.h b/src/transform/promote_side_effects_to_decl.h
index e3d17bd..7bfc31e 100644
--- a/src/transform/promote_side_effects_to_decl.h
+++ b/src/transform/promote_side_effects_to_decl.h
@@ -61,7 +61,9 @@
   /// ProgramBuilder
   /// @param inputs optional extra transform-specific input data
   /// @param outputs optional extra transform-specific output data
-  void Run(CloneContext& ctx, const DataMap& inputs, DataMap& outputs) override;
+  void Run(CloneContext& ctx,
+           const DataMap& inputs,
+           DataMap& outputs) const override;
 
  private:
   class State;
diff --git a/src/transform/remove_phonies.cc b/src/transform/remove_phonies.cc
index 3efa18c..8dfb9b4 100644
--- a/src/transform/remove_phonies.cc
+++ b/src/transform/remove_phonies.cc
@@ -68,7 +68,7 @@
 
 RemovePhonies::~RemovePhonies() = default;
 
-void RemovePhonies::Run(CloneContext& ctx, const DataMap&, DataMap&) {
+void RemovePhonies::Run(CloneContext& ctx, const DataMap&, DataMap&) const {
   auto& sem = ctx.src->Sem();
 
   std::unordered_map<SinkSignature, Symbol, SinkSignature::Hasher> sinks;
diff --git a/src/transform/remove_phonies.h b/src/transform/remove_phonies.h
index c94959b..45b117f 100644
--- a/src/transform/remove_phonies.h
+++ b/src/transform/remove_phonies.h
@@ -41,7 +41,9 @@
   /// ProgramBuilder
   /// @param inputs optional extra transform-specific input data
   /// @param outputs optional extra transform-specific output data
-  void Run(CloneContext& ctx, const DataMap& inputs, DataMap& outputs) override;
+  void Run(CloneContext& ctx,
+           const DataMap& inputs,
+           DataMap& outputs) const override;
 };
 
 }  // namespace transform
diff --git a/src/transform/remove_unreachable_statements.cc b/src/transform/remove_unreachable_statements.cc
index 30f8f42..adb1f41 100644
--- a/src/transform/remove_unreachable_statements.cc
+++ b/src/transform/remove_unreachable_statements.cc
@@ -39,7 +39,7 @@
 
 void RemoveUnreachableStatements::Run(CloneContext& ctx,
                                       const DataMap&,
-                                      DataMap&) {
+                                      DataMap&) const {
   for (auto* node : ctx.src->ASTNodes().Objects()) {
     if (auto* stmt = ctx.src->Sem().Get<sem::Statement>(node)) {
       if (!stmt->IsReachable()) {
diff --git a/src/transform/remove_unreachable_statements.h b/src/transform/remove_unreachable_statements.h
index f7edeee..7f0fc0d 100644
--- a/src/transform/remove_unreachable_statements.h
+++ b/src/transform/remove_unreachable_statements.h
@@ -41,7 +41,9 @@
   /// ProgramBuilder
   /// @param inputs optional extra transform-specific input data
   /// @param outputs optional extra transform-specific output data
-  void Run(CloneContext& ctx, const DataMap& inputs, DataMap& outputs) override;
+  void Run(CloneContext& ctx,
+           const DataMap& inputs,
+           DataMap& outputs) const override;
 };
 
 }  // namespace transform
diff --git a/src/transform/renamer.cc b/src/transform/renamer.cc
index ca5e7dd..c793f86 100644
--- a/src/transform/renamer.cc
+++ b/src/transform/renamer.cc
@@ -1252,7 +1252,7 @@
 Renamer::Renamer() = default;
 Renamer::~Renamer() = default;
 
-Output Renamer::Run(const Program* in, const DataMap& inputs) {
+Output Renamer::Run(const Program* in, const DataMap& inputs) const {
   ProgramBuilder out;
   // Disable auto-cloning of symbols, since we want to rename them.
   CloneContext ctx(&out, in, false);
diff --git a/src/transform/renamer.h b/src/transform/renamer.h
index 2c2ea0a..4bec367 100644
--- a/src/transform/renamer.h
+++ b/src/transform/renamer.h
@@ -85,7 +85,7 @@
   /// @param program the source program to transform
   /// @param data optional extra transform-specific input data
   /// @returns the transformation result
-  Output Run(const Program* program, const DataMap& data = {}) override;
+  Output Run(const Program* program, const DataMap& data = {}) const override;
 };
 
 }  // namespace transform
diff --git a/src/transform/robustness.cc b/src/transform/robustness.cc
index 0d50a5e..ae01845 100644
--- a/src/transform/robustness.cc
+++ b/src/transform/robustness.cc
@@ -293,7 +293,7 @@
 Robustness::Robustness() = default;
 Robustness::~Robustness() = default;
 
-void Robustness::Run(CloneContext& ctx, const DataMap& inputs, DataMap&) {
+void Robustness::Run(CloneContext& ctx, const DataMap& inputs, DataMap&) const {
   Config cfg;
   if (auto* cfg_data = inputs.Get<Config>()) {
     cfg = *cfg_data;
diff --git a/src/transform/robustness.h b/src/transform/robustness.h
index 0447340..f4cb0ee 100644
--- a/src/transform/robustness.h
+++ b/src/transform/robustness.h
@@ -74,7 +74,9 @@
   /// ProgramBuilder
   /// @param inputs optional extra transform-specific input data
   /// @param outputs optional extra transform-specific output data
-  void Run(CloneContext& ctx, const DataMap& inputs, DataMap& outputs) override;
+  void Run(CloneContext& ctx,
+           const DataMap& inputs,
+           DataMap& outputs) const override;
 
  private:
   struct State;
diff --git a/src/transform/simplify_pointers.cc b/src/transform/simplify_pointers.cc
index b789e87..c050a2e 100644
--- a/src/transform/simplify_pointers.cc
+++ b/src/transform/simplify_pointers.cc
@@ -231,7 +231,7 @@
 
 SimplifyPointers::~SimplifyPointers() = default;
 
-void SimplifyPointers::Run(CloneContext& ctx, const DataMap&, DataMap&) {
+void SimplifyPointers::Run(CloneContext& ctx, const DataMap&, DataMap&) const {
   if (!Requires<Unshadow>(ctx)) {
     return;
   }
diff --git a/src/transform/simplify_pointers.h b/src/transform/simplify_pointers.h
index 1f8cf71..33af4ad 100644
--- a/src/transform/simplify_pointers.h
+++ b/src/transform/simplify_pointers.h
@@ -46,7 +46,9 @@
   /// ProgramBuilder
   /// @param inputs optional extra transform-specific input data
   /// @param outputs optional extra transform-specific output data
-  void Run(CloneContext& ctx, const DataMap& inputs, DataMap& outputs) override;
+  void Run(CloneContext& ctx,
+           const DataMap& inputs,
+           DataMap& outputs) const override;
 };
 
 }  // namespace transform
diff --git a/src/transform/single_entry_point.cc b/src/transform/single_entry_point.cc
index fb99663..a1caa7d 100644
--- a/src/transform/single_entry_point.cc
+++ b/src/transform/single_entry_point.cc
@@ -31,7 +31,9 @@
 
 SingleEntryPoint::~SingleEntryPoint() = default;
 
-void SingleEntryPoint::Run(CloneContext& ctx, const DataMap& inputs, DataMap&) {
+void SingleEntryPoint::Run(CloneContext& ctx,
+                           const DataMap& inputs,
+                           DataMap&) const {
   auto* cfg = inputs.Get<Config>();
   if (cfg == nullptr) {
     ctx.dst->Diagnostics().add_error(
diff --git a/src/transform/single_entry_point.h b/src/transform/single_entry_point.h
index 447b5c4..01a70d6 100644
--- a/src/transform/single_entry_point.h
+++ b/src/transform/single_entry_point.h
@@ -61,7 +61,9 @@
   /// ProgramBuilder
   /// @param inputs optional extra transform-specific input data
   /// @param outputs optional extra transform-specific output data
-  void Run(CloneContext& ctx, const DataMap& inputs, DataMap& outputs) override;
+  void Run(CloneContext& ctx,
+           const DataMap& inputs,
+           DataMap& outputs) const override;
 };
 
 }  // namespace transform
diff --git a/src/transform/transform.cc b/src/transform/transform.cc
index 21c4d81..0834d97 100644
--- a/src/transform/transform.cc
+++ b/src/transform/transform.cc
@@ -46,7 +46,8 @@
 Transform::Transform() = default;
 Transform::~Transform() = default;
 
-Output Transform::Run(const Program* program, const DataMap& data /* = {} */) {
+Output Transform::Run(const Program* program,
+                      const DataMap& data /* = {} */) const {
   ProgramBuilder builder;
   CloneContext ctx(&builder, program);
   Output output;
@@ -56,13 +57,18 @@
   return output;
 }
 
-void Transform::Run(CloneContext& ctx, const DataMap&, DataMap&) {
+void Transform::Run(CloneContext& ctx, const DataMap&, DataMap&) const {
   TINT_UNIMPLEMENTED(Transform, ctx.dst->Diagnostics())
       << "Transform::Run() unimplemented for " << TypeInfo().name;
 }
 
-bool Transform::Requires(CloneContext& ctx,
-                         std::initializer_list<const ::tint::TypeInfo*> deps) {
+bool Transform::ShouldRun(const Program*) const {
+  return true;
+}
+
+bool Transform::Requires(
+    CloneContext& ctx,
+    std::initializer_list<const ::tint::TypeInfo*> deps) const {
   for (auto* dep : deps) {
     if (!ctx.src->HasTransformApplied(dep)) {
       ctx.dst->Diagnostics().add_error(
diff --git a/src/transform/transform.h b/src/transform/transform.h
index 59a04e7..5f8a107 100644
--- a/src/transform/transform.h
+++ b/src/transform/transform.h
@@ -157,7 +157,11 @@
   /// @param program the source program to transform
   /// @param data optional extra transform-specific input data
   /// @returns the transformation result
-  virtual Output Run(const Program* program, const DataMap& data = {});
+  virtual Output Run(const Program* program, const DataMap& data = {}) const;
+
+  /// @param program the program to inspect
+  /// @returns true if this transform should be run for the given program
+  virtual bool ShouldRun(const Program* program) const;
 
  protected:
   /// Runs the transform using the CloneContext built for transforming a
@@ -166,14 +170,16 @@
   /// ProgramBuilder
   /// @param inputs optional extra transform-specific input data
   /// @param outputs optional extra transform-specific output data
-  virtual void Run(CloneContext& ctx, const DataMap& inputs, DataMap& outputs);
+  virtual void Run(CloneContext& ctx,
+                   const DataMap& inputs,
+                   DataMap& outputs) const;
 
   /// Requires appends an error diagnostic to `ctx.dst` if the template type
   /// transforms were not already run on `ctx.src`.
   /// @param ctx the CloneContext
   /// @returns true if all dependency transforms have been run
   template <typename... TRANSFORMS>
-  bool Requires(CloneContext& ctx) {
+  bool Requires(CloneContext& ctx) const {
     return Requires(ctx, {&::tint::TypeInfo::Of<TRANSFORMS>()...});
   }
 
@@ -183,7 +189,7 @@
   /// @param deps the list of Transform TypeInfos
   /// @returns true if all dependency transforms have been run
   bool Requires(CloneContext& ctx,
-                std::initializer_list<const ::tint::TypeInfo*> deps);
+                std::initializer_list<const ::tint::TypeInfo*> deps) const;
 
   /// Removes the statement `stmt` from the transformed program.
   /// RemoveStatement handles edge cases, like statements in the initializer and
diff --git a/src/transform/transform_test.cc b/src/transform/transform_test.cc
index e8b8736..053e6b3 100644
--- a/src/transform/transform_test.cc
+++ b/src/transform/transform_test.cc
@@ -24,7 +24,7 @@
 
 // Inherit from Transform so we have access to protected methods
 struct CreateASTTypeForTest : public testing::Test, public Transform {
-  Output Run(const Program*, const DataMap&) override { return {}; }
+  Output Run(const Program*, const DataMap&) const override { return {}; }
 
   const ast::Type* create(
       std::function<sem::Type*(ProgramBuilder&)> create_sem_type) {
diff --git a/src/transform/unshadow.cc b/src/transform/unshadow.cc
index a7bc66d..7d94fd7 100644
--- a/src/transform/unshadow.cc
+++ b/src/transform/unshadow.cc
@@ -91,7 +91,7 @@
 
 Unshadow::~Unshadow() = default;
 
-void Unshadow::Run(CloneContext& ctx, const DataMap&, DataMap&) {
+void Unshadow::Run(CloneContext& ctx, const DataMap&, DataMap&) const {
   State(ctx).Run();
 }
 
diff --git a/src/transform/unshadow.h b/src/transform/unshadow.h
index 7c16bcf..ca7be17 100644
--- a/src/transform/unshadow.h
+++ b/src/transform/unshadow.h
@@ -39,7 +39,9 @@
   /// ProgramBuilder
   /// @param inputs optional extra transform-specific input data
   /// @param outputs optional extra transform-specific output data
-  void Run(CloneContext& ctx, const DataMap& inputs, DataMap& outputs) override;
+  void Run(CloneContext& ctx,
+           const DataMap& inputs,
+           DataMap& outputs) const override;
 };
 
 }  // namespace transform
diff --git a/src/transform/vectorize_scalar_matrix_constructors.cc b/src/transform/vectorize_scalar_matrix_constructors.cc
index dc4ae12..d72efa2 100644
--- a/src/transform/vectorize_scalar_matrix_constructors.cc
+++ b/src/transform/vectorize_scalar_matrix_constructors.cc
@@ -34,7 +34,7 @@
 
 void VectorizeScalarMatrixConstructors::Run(CloneContext& ctx,
                                             const DataMap&,
-                                            DataMap&) {
+                                            DataMap&) const {
   ctx.ReplaceAll(
       [&](const ast::CallExpression* expr) -> const ast::CallExpression* {
         auto* call = ctx.src->Sem().Get(expr);
diff --git a/src/transform/vectorize_scalar_matrix_constructors.h b/src/transform/vectorize_scalar_matrix_constructors.h
index d03f503..d6e1df3 100644
--- a/src/transform/vectorize_scalar_matrix_constructors.h
+++ b/src/transform/vectorize_scalar_matrix_constructors.h
@@ -37,7 +37,9 @@
   /// ProgramBuilder
   /// @param inputs optional extra transform-specific input data
   /// @param outputs optional extra transform-specific output data
-  void Run(CloneContext& ctx, const DataMap& inputs, DataMap& outputs) override;
+  void Run(CloneContext& ctx,
+           const DataMap& inputs,
+           DataMap& outputs) const override;
 };
 
 }  // namespace transform
diff --git a/src/transform/vertex_pulling.cc b/src/transform/vertex_pulling.cc
index ea15e85..6305020 100644
--- a/src/transform/vertex_pulling.cc
+++ b/src/transform/vertex_pulling.cc
@@ -903,7 +903,9 @@
 VertexPulling::VertexPulling() = default;
 VertexPulling::~VertexPulling() = default;
 
-void VertexPulling::Run(CloneContext& ctx, const DataMap& inputs, DataMap&) {
+void VertexPulling::Run(CloneContext& ctx,
+                        const DataMap& inputs,
+                        DataMap&) const {
   auto cfg = cfg_;
   if (auto* cfg_data = inputs.Get<Config>()) {
     cfg = *cfg_data;
diff --git a/src/transform/vertex_pulling.h b/src/transform/vertex_pulling.h
index c6250b7..bf6b230 100644
--- a/src/transform/vertex_pulling.h
+++ b/src/transform/vertex_pulling.h
@@ -172,7 +172,9 @@
   /// ProgramBuilder
   /// @param inputs optional extra transform-specific input data
   /// @param outputs optional extra transform-specific output data
-  void Run(CloneContext& ctx, const DataMap& inputs, DataMap& outputs) override;
+  void Run(CloneContext& ctx,
+           const DataMap& inputs,
+           DataMap& outputs) const override;
 
  private:
   Config cfg_;
diff --git a/src/transform/wrap_arrays_in_structs.cc b/src/transform/wrap_arrays_in_structs.cc
index 62d18ac..64f851e 100644
--- a/src/transform/wrap_arrays_in_structs.cc
+++ b/src/transform/wrap_arrays_in_structs.cc
@@ -38,7 +38,9 @@
 
 WrapArraysInStructs::~WrapArraysInStructs() = default;
 
-void WrapArraysInStructs::Run(CloneContext& ctx, const DataMap&, DataMap&) {
+void WrapArraysInStructs::Run(CloneContext& ctx,
+                              const DataMap&,
+                              DataMap&) const {
   auto& sem = ctx.src->Sem();
 
   std::unordered_map<const sem::Array*, WrappedArrayInfo> wrapped_arrays;
diff --git a/src/transform/wrap_arrays_in_structs.h b/src/transform/wrap_arrays_in_structs.h
index 64dc047..4af74dc 100644
--- a/src/transform/wrap_arrays_in_structs.h
+++ b/src/transform/wrap_arrays_in_structs.h
@@ -51,7 +51,9 @@
   /// ProgramBuilder
   /// @param inputs optional extra transform-specific input data
   /// @param outputs optional extra transform-specific output data
-  void Run(CloneContext& ctx, const DataMap& inputs, DataMap& outputs) override;
+  void Run(CloneContext& ctx,
+           const DataMap& inputs,
+           DataMap& outputs) const override;
 
  private:
   struct WrappedArrayInfo {
diff --git a/src/transform/zero_init_workgroup_memory.cc b/src/transform/zero_init_workgroup_memory.cc
index 8601356..398b893 100644
--- a/src/transform/zero_init_workgroup_memory.cc
+++ b/src/transform/zero_init_workgroup_memory.cc
@@ -433,7 +433,9 @@
 
 ZeroInitWorkgroupMemory::~ZeroInitWorkgroupMemory() = default;
 
-void ZeroInitWorkgroupMemory::Run(CloneContext& ctx, const DataMap&, DataMap&) {
+void ZeroInitWorkgroupMemory::Run(CloneContext& ctx,
+                                  const DataMap&,
+                                  DataMap&) const {
   for (auto* fn : ctx.src->AST().Functions()) {
     if (fn->PipelineStage() == ast::PipelineStage::kCompute) {
       State{ctx}.Run(fn);
diff --git a/src/transform/zero_init_workgroup_memory.h b/src/transform/zero_init_workgroup_memory.h
index 1644b4d..9eb3a3e 100644
--- a/src/transform/zero_init_workgroup_memory.h
+++ b/src/transform/zero_init_workgroup_memory.h
@@ -39,7 +39,9 @@
   /// ProgramBuilder
   /// @param inputs optional extra transform-specific input data
   /// @param outputs optional extra transform-specific output data
-  void Run(CloneContext& ctx, const DataMap& inputs, DataMap& outputs) override;
+  void Run(CloneContext& ctx,
+           const DataMap& inputs,
+           DataMap& outputs) const override;
 
  private:
   struct State;