diff --git a/src/test/java/com/google/devtools/build/lib/actions/ArtifactTest.java b/src/test/java/com/google/devtools/build/lib/actions/ArtifactTest.java
index 0e6f142..013d4bc 100644
--- a/src/test/java/com/google/devtools/build/lib/actions/ArtifactTest.java
+++ b/src/test/java/com/google/devtools/build/lib/actions/ArtifactTest.java
@@ -263,6 +263,8 @@
     anotherArtifact.setGeneratingActionKey(ActionsTestUtil.NULL_ACTION_LOOKUP_DATA);
     new SerializationTester(artifact, anotherArtifact)
         .addDependency(FileSystem.class, scratch.getFileSystem())
+        .addDependency(
+            Root.RootCodecDependencies.class, new Root.RootCodecDependencies(anotherRoot.getRoot()))
         .runTests();
   }
 
@@ -282,9 +284,13 @@
                 .addReferenceConstant(scratch.getFileSystem())
                 .setAllowDefaultCodec(true)
                 .build(),
-            ImmutableMap.of(
-                FileSystem.class, scratch.getFileSystem(),
-                ArtifactResolverSupplier.class, artifactResolverSupplierForTest));
+            ImmutableMap.<Class<?>, Object>builder()
+                .put(FileSystem.class, scratch.getFileSystem())
+                .put(ArtifactResolverSupplier.class, artifactResolverSupplierForTest)
+                .put(
+                    Root.RootCodecDependencies.class,
+                    new Root.RootCodecDependencies(artifactRoot.getRoot()))
+                .build());
 
     PathFragment pathFragment = PathFragment.create("src/foo.cc");
     ArtifactOwner owner = new LabelArtifactOwner(Label.parseAbsoluteUnchecked("//foo:bar"));
diff --git a/src/test/java/com/google/devtools/build/lib/actions/ExecutableSymlinkActionTest.java b/src/test/java/com/google/devtools/build/lib/actions/ExecutableSymlinkActionTest.java
index 1715e15b..704a060 100644
--- a/src/test/java/com/google/devtools/build/lib/actions/ExecutableSymlinkActionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/actions/ExecutableSymlinkActionTest.java
@@ -31,6 +31,7 @@
 import com.google.devtools.build.lib.vfs.FileSystem;
 import com.google.devtools.build.lib.vfs.FileSystemUtils;
 import com.google.devtools.build.lib.vfs.Path;
+import com.google.devtools.build.lib.vfs.Root;
 import org.junit.Before;
 import org.junit.Test;
 import org.junit.runner.RunWith;
@@ -137,6 +138,9 @@
     SymlinkAction action = SymlinkAction.toExecutable(NULL_ACTION_OWNER, input, output, "progress");
     new SerializationTester(action)
         .addDependency(FileSystem.class, scratch.getFileSystem())
+        .addDependency(
+            Root.RootCodecDependencies.class,
+            new Root.RootCodecDependencies(Root.absoluteRoot(scratch.getFileSystem())))
         .setVerificationFunction(
             (in, out) -> {
               SymlinkAction inAction = (SymlinkAction) in;
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/actions/SymlinkActionTest.java b/src/test/java/com/google/devtools/build/lib/analysis/actions/SymlinkActionTest.java
index c8389b1..4c5b88a 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/actions/SymlinkActionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/actions/SymlinkActionTest.java
@@ -34,6 +34,7 @@
 import com.google.devtools.build.lib.vfs.FileSystem;
 import com.google.devtools.build.lib.vfs.FileSystemUtils;
 import com.google.devtools.build.lib.vfs.Path;
+import com.google.devtools.build.lib.vfs.Root;
 import org.junit.Before;
 import org.junit.Test;
 import org.junit.runner.RunWith;
@@ -110,6 +111,7 @@
   public void testCodec() throws Exception {
     new SerializationTester(action)
         .addDependency(FileSystem.class, scratch.getFileSystem())
+        .addDependency(Root.RootCodecDependencies.class, new Root.RootCodecDependencies(root))
         .addDependencies(SerializationDepsUtils.SERIALIZATION_DEPS_FOR_TEST)
         .setVerificationFunction(
             (in, out) -> {
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTest.java
index b96d5c1..597f7a9 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTest.java
@@ -289,6 +289,9 @@
             true);
     new SerializationTester(actionExecutionValue)
         .addDependency(FileSystem.class, root.getFileSystem())
+        .addDependency(
+            Root.RootCodecDependencies.class,
+            new Root.RootCodecDependencies(Root.absoluteRoot(root.getFileSystem())))
         .runTests();
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/CollectPackagesUnderDirectoryCodecTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/CollectPackagesUnderDirectoryCodecTest.java
index 0472323..94a49a1 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/CollectPackagesUnderDirectoryCodecTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/CollectPackagesUnderDirectoryCodecTest.java
@@ -20,7 +20,6 @@
 import com.google.devtools.build.lib.skyframe.serialization.testutils.FsUtils;
 import com.google.devtools.build.lib.skyframe.serialization.testutils.SerializationTester;
 import com.google.devtools.build.lib.skyframe.serialization.testutils.TestUtils;
-import com.google.devtools.build.lib.vfs.FileSystem;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.Root;
 import com.google.devtools.build.lib.vfs.RootedPath;
@@ -34,7 +33,8 @@
 
   @Test
   public void testCodec() throws Exception {
-    new SerializationTester(
+    SerializationTester serializationTester =
+        new SerializationTester(
             NoErrorCollectPackagesUnderDirectoryValue.EMPTY,
             CollectPackagesUnderDirectoryValue.ofNoError(
                 true,
@@ -50,9 +50,9 @@
                 "my error message",
                 ImmutableMap.of(
                     rootedPath("/a", "b"), false,
-                    rootedPath("/c", "d"), true)))
-        .addDependency(FileSystem.class, FsUtils.TEST_FILESYSTEM)
-        .runTests();
+                    rootedPath("/c", "d"), true)));
+    FsUtils.addDependencies(serializationTester);
+    serializationTester.runTests();
   }
 
   @Test
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/FileValueTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/FileValueTest.java
index fad42f0..56e4acc 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/FileValueTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/FileValueTest.java
@@ -19,7 +19,6 @@
 import com.google.devtools.build.lib.actions.FileValue;
 import com.google.devtools.build.lib.skyframe.serialization.testutils.FsUtils;
 import com.google.devtools.build.lib.skyframe.serialization.testutils.SerializationTester;
-import com.google.devtools.build.lib.vfs.FileSystem;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import org.junit.Test;
 import org.junit.runner.RunWith;
@@ -30,28 +29,29 @@
 public class FileValueTest {
   @Test
   public void testCodec() throws Exception {
-    new SerializationTester(
+    SerializationTester serializationTester =
+        new SerializationTester(
             // Assume we have adequate coverage for FileStateValue serialization.
             new FileValue.RegularFileValue(
-                FsUtils.TEST_ROOT, FileStateValue.NONEXISTENT_FILE_STATE_NODE),
+                FsUtils.TEST_ROOTED_PATH, FileStateValue.NONEXISTENT_FILE_STATE_NODE),
             new FileValue.DifferentRealPathFileValueWithStoredChain(
-                FsUtils.TEST_ROOT,
+                FsUtils.TEST_ROOTED_PATH,
                 FileStateValue.DIRECTORY_FILE_STATE_NODE,
-                ImmutableList.of(FsUtils.TEST_ROOT)),
+                ImmutableList.of(FsUtils.TEST_ROOTED_PATH)),
             new FileValue.DifferentRealPathFileValueWithoutStoredChain(
-                FsUtils.TEST_ROOT, FileStateValue.DIRECTORY_FILE_STATE_NODE),
+                FsUtils.TEST_ROOTED_PATH, FileStateValue.DIRECTORY_FILE_STATE_NODE),
             new FileValue.SymlinkFileValueWithStoredChain(
-                FsUtils.TEST_ROOT,
+                FsUtils.TEST_ROOTED_PATH,
                 new FileStateValue.RegularFileStateValue(
                     /*size=*/ 100, /*digest=*/ new byte[] {1, 2, 3, 4, 5}, /*contentsProxy=*/ null),
-                ImmutableList.of(FsUtils.TEST_ROOT),
+                ImmutableList.of(FsUtils.TEST_ROOTED_PATH),
                 PathFragment.create("somewhere/else")),
             new FileValue.SymlinkFileValueWithoutStoredChain(
-                FsUtils.TEST_ROOT,
+                FsUtils.TEST_ROOTED_PATH,
                 new FileStateValue.RegularFileStateValue(
                     /*size=*/ 100, /*digest=*/ new byte[] {1, 2, 3, 4, 5}, /*contentsProxy=*/ null),
-                PathFragment.create("somewhere/else")))
-        .addDependency(FileSystem.class, FsUtils.TEST_FILESYSTEM)
-        .runTests();
+                PathFragment.create("somewhere/else")));
+    FsUtils.addDependencies(serializationTester);
+    serializationTester.runTests();
   }
 }
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/GlobDescriptorTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/GlobDescriptorTest.java
index 3d2e4bd..7eac47f 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/GlobDescriptorTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/GlobDescriptorTest.java
@@ -19,7 +19,6 @@
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
 import com.google.devtools.build.lib.skyframe.serialization.testutils.FsUtils;
 import com.google.devtools.build.lib.skyframe.serialization.testutils.SerializationTester;
-import com.google.devtools.build.lib.vfs.FileSystem;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.Root;
 import org.junit.Test;
@@ -32,22 +31,23 @@
 
   @Test
   public void testSerialization() throws Exception {
-    new SerializationTester(
-            GlobDescriptor.create(
-                PackageIdentifier.create("@foo", PathFragment.create("//bar")),
-                Root.fromPath(FsUtils.TEST_FILESYSTEM.getPath("/packageRoot")),
-                PathFragment.create("subdir"),
-                "pattern",
-                /*excludeDirs=*/ false),
-            GlobDescriptor.create(
-                PackageIdentifier.create("@bar", PathFragment.create("//foo")),
-                Root.fromPath(FsUtils.TEST_FILESYSTEM.getPath("/anotherPackageRoot")),
-                PathFragment.create("anotherSubdir"),
-                "pattern",
-                /*excludeDirs=*/ true))
-        .addDependency(FileSystem.class, FsUtils.TEST_FILESYSTEM)
-        .setVerificationFunction(GlobDescriptorTest::verifyEquivalent)
-        .runTests();
+    SerializationTester serializationTester =
+        new SerializationTester(
+                GlobDescriptor.create(
+                    PackageIdentifier.create("@foo", PathFragment.create("//bar")),
+                    Root.fromPath(FsUtils.TEST_FILESYSTEM.getPath("/packageRoot")),
+                    PathFragment.create("subdir"),
+                    "pattern",
+                    /*excludeDirs=*/ false),
+                GlobDescriptor.create(
+                    PackageIdentifier.create("@bar", PathFragment.create("//foo")),
+                    Root.fromPath(FsUtils.TEST_FILESYSTEM.getPath("/anotherPackageRoot")),
+                    PathFragment.create("anotherSubdir"),
+                    "pattern",
+                    /*excludeDirs=*/ true))
+            .setVerificationFunction(GlobDescriptorTest::verifyEquivalent);
+    FsUtils.addDependencies(serializationTester);
+    serializationTester.runTests();
   }
 
   private static void verifyEquivalent(GlobDescriptor orig, GlobDescriptor deserialized) {
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfTargetsUnderDirectoryKeyCodecTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfTargetsUnderDirectoryKeyCodecTest.java
index 2c80f1d..523776d 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfTargetsUnderDirectoryKeyCodecTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfTargetsUnderDirectoryKeyCodecTest.java
@@ -19,7 +19,6 @@
 import com.google.devtools.build.lib.skyframe.PrepareDepsOfTargetsUnderDirectoryValue.PrepareDepsOfTargetsUnderDirectoryKey;
 import com.google.devtools.build.lib.skyframe.serialization.testutils.FsUtils;
 import com.google.devtools.build.lib.skyframe.serialization.testutils.SerializationTester;
-import com.google.devtools.build.lib.vfs.FileSystem;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.JUnit4;
@@ -30,14 +29,16 @@
 
   @Test
   public void testCodec() throws Exception {
-    new SerializationTester(
+    SerializationTester serializationTester =
+        new SerializationTester(
             PrepareDepsOfTargetsUnderDirectoryKey.create(
                 new RecursivePkgKey(
                     RepositoryName.MAIN,
-                    FsUtils.TEST_ROOT,
+                    FsUtils.TEST_ROOTED_PATH,
                     ImmutableSet.of(FsUtils.rootPathRelative("here"))),
-                FilteringPolicies.and(FilteringPolicies.NO_FILTER, FilteringPolicies.FILTER_TESTS)))
-        .addDependency(FileSystem.class, FsUtils.TEST_FILESYSTEM)
-        .runTests();
+                FilteringPolicies.and(
+                    FilteringPolicies.NO_FILTER, FilteringPolicies.FILTER_TESTS)));
+    FsUtils.addDependencies(serializationTester);
+    serializationTester.runTests();
   }
 }
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupKeyCodecTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupKeyCodecTest.java
index 0e84bb9..1be78b9 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupKeyCodecTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupKeyCodecTest.java
@@ -18,7 +18,6 @@
 import com.google.devtools.build.lib.skyframe.SkylarkImportLookupValue.SkylarkImportLookupKey;
 import com.google.devtools.build.lib.skyframe.serialization.testutils.FsUtils;
 import com.google.devtools.build.lib.skyframe.serialization.testutils.SerializationTester;
-import com.google.devtools.build.lib.vfs.FileSystem;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.JUnit4;
@@ -29,7 +28,8 @@
 
   @Test
   public void testCodec() throws Exception {
-    new SerializationTester(
+    SerializationTester serializationTester =
+        new SerializationTester(
             SkylarkImportLookupKey.create(
                 Label.parseAbsolute("//foo/bar:baz", ImmutableMap.of()), false, -1, null),
             SkylarkImportLookupKey.create(
@@ -40,8 +40,8 @@
                 Label.parseAbsolute("//foo/bar:baz", ImmutableMap.of()),
                 true,
                 4,
-                FsUtils.TEST_ROOT))
-        .addDependency(FileSystem.class, FsUtils.TEST_FILESYSTEM)
-        .runTests();
+                FsUtils.TEST_ROOTED_PATH));
+    FsUtils.addDependencies(serializationTester);
+    serializationTester.runTests();
   }
 }
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactBuildTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactBuildTest.java
index afe1d43..1c73180 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactBuildTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactBuildTest.java
@@ -65,6 +65,7 @@
 import com.google.devtools.build.lib.vfs.FileSystemUtils;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
+import com.google.devtools.build.lib.vfs.Root;
 import com.google.devtools.build.lib.vfs.Symlinks;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyKey;
@@ -131,6 +132,9 @@
     parent.setGeneratingActionKey(ActionLookupData.create(ACTION_LOOKUP_KEY, 0));
     new SerializationTester(parent, ActionInputHelper.treeFileArtifact(parent, "child"))
         .addDependency(FileSystem.class, scratch.getFileSystem())
+        .addDependency(
+            Root.RootCodecDependencies.class,
+            new Root.RootCodecDependencies(Root.absoluteRoot(scratch.getFileSystem())))
         .runTests();
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/vfs/RootTest.java b/src/test/java/com/google/devtools/build/lib/vfs/RootTest.java
index 888ecfb..ace28cc 100644
--- a/src/test/java/com/google/devtools/build/lib/vfs/RootTest.java
+++ b/src/test/java/com/google/devtools/build/lib/vfs/RootTest.java
@@ -16,9 +16,13 @@
 import static com.google.common.truth.Truth.assertThat;
 import static com.google.devtools.build.lib.testutil.MoreAsserts.assertThrows;
 
+import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Lists;
 import com.google.common.testing.EqualsTester;
 import com.google.devtools.build.lib.clock.BlazeClock;
+import com.google.devtools.build.lib.skyframe.serialization.AutoRegistry;
+import com.google.devtools.build.lib.skyframe.serialization.ObjectCodecRegistry;
+import com.google.devtools.build.lib.skyframe.serialization.ObjectCodecs;
 import com.google.devtools.build.lib.skyframe.serialization.testutils.SerializationTester;
 import com.google.devtools.build.lib.vfs.inmemoryfs.InMemoryFileSystem;
 import java.util.Comparator;
@@ -104,9 +108,56 @@
   }
 
   @Test
-  public void testSerialization() throws Exception {
-    new SerializationTester(Root.absoluteRoot(fs), Root.fromPath(fs.getPath("/foo")))
+  public void testSerialization_Simple() throws Exception {
+    Root fooPathRoot = Root.fromPath(fs.getPath("/foo"));
+    Root barPathRoot = Root.fromPath(fs.getPath("/bar"));
+    new SerializationTester(Root.absoluteRoot(fs), fooPathRoot, barPathRoot)
         .addDependency(FileSystem.class, fs)
+        .addDependency(
+            Root.RootCodecDependencies.class,
+            new Root.RootCodecDependencies(/*likelyPopularRoot=*/ fooPathRoot))
         .runTests();
   }
+
+  @Test
+  public void testSerialization_LikelyPopularRootIsCanonicalized() throws Exception {
+    Root fooPathRoot = Root.fromPath(fs.getPath("/foo"));
+    Root otherFooPathRoot = Root.fromPath(fs.getPath("/foo"));
+    Root barPathRoot = Root.fromPath(fs.getPath("/bar"));
+    Root fsAabsoluteRoot = Root.absoluteRoot(fs);
+
+    assertThat(fooPathRoot).isNotSameInstanceAs(otherFooPathRoot);
+    assertThat(fooPathRoot).isEqualTo(otherFooPathRoot);
+
+    ObjectCodecRegistry registry = AutoRegistry.get();
+    ImmutableMap<Class<?>, Object> dependencies =
+        ImmutableMap.<Class<?>, Object>builder()
+            .put(FileSystem.class, fs)
+            .put(
+                Root.RootCodecDependencies.class,
+                new Root.RootCodecDependencies(/*likelyPopularRoot=*/ fooPathRoot))
+            .build();
+    ObjectCodecRegistry.Builder registryBuilder = registry.getBuilder();
+    for (Object val : dependencies.values()) {
+      registryBuilder.addReferenceConstant(val);
+    }
+    ObjectCodecs objectCodecs = new ObjectCodecs(registryBuilder.build(), dependencies);
+
+    Root fooPathRootDeserialized =
+        (Root) objectCodecs.deserialize(objectCodecs.serialize(fooPathRoot));
+    Root otherFooPathRootDeserialized =
+        (Root) objectCodecs.deserialize(objectCodecs.serialize(otherFooPathRoot));
+    assertThat(fooPathRootDeserialized).isSameInstanceAs(fooPathRoot);
+    assertThat(otherFooPathRootDeserialized).isSameInstanceAs(fooPathRoot);
+
+    Root barPathRootDeserialized =
+        (Root) objectCodecs.deserialize(objectCodecs.serialize(barPathRoot));
+    assertThat(barPathRootDeserialized).isNotSameInstanceAs(barPathRoot);
+    assertThat(barPathRootDeserialized).isEqualTo(barPathRoot);
+
+    Root fsAabsoluteRootDeserialized =
+        (Root) objectCodecs.deserialize(objectCodecs.serialize(fsAabsoluteRoot));
+    assertThat(fsAabsoluteRootDeserialized).isNotSameInstanceAs(fsAabsoluteRoot);
+    assertThat(fsAabsoluteRootDeserialized).isEqualTo(fsAabsoluteRoot);
+  }
 }