diff --git a/include/swift/AST/GenericSignatureBuilder.h b/include/swift/AST/GenericSignatureBuilder.h
index 7eb4f11..6cf3b17 100644
--- a/include/swift/AST/GenericSignatureBuilder.h
+++ b/include/swift/AST/GenericSignatureBuilder.h
@@ -445,19 +445,16 @@
   /// Note that we have added the nested type nestedPA
   void addedNestedType(PotentialArchetype *nestedPA);
 
-  /// Add a rewrite rule that makes \c otherPA a part of the given equivalence
-  /// class.
+  /// Add a rewrite rule from that makes the two types equivalent.
   ///
   /// \returns true if a new rewrite rule was added, and false otherwise.
-  bool addSameTypeRewriteRule(EquivalenceClass *equivClass,
-                              PotentialArchetype *otherPA);
+  bool addSameTypeRewriteRule(CanType type1, CanType type2);
 
-  /// \brief Add a new conformance requirement specifying that the given
-  /// potential archetypes are equivalent.
-  ConstraintResult addSameTypeRequirementBetweenArchetypes(
-                                               PotentialArchetype *T1,
-                                               PotentialArchetype *T2,
-                                               const RequirementSource *Source);
+  /// \brief Add a same-type requirement between two types that are known to
+  /// refer to type parameters.
+  ConstraintResult addSameTypeRequirementBetweenTypeParameters(
+                                         ResolvedType type1, ResolvedType type2,
+                                         const RequirementSource *source);
   
   /// \brief Add a new conformance requirement specifying that the given
   /// potential archetype is bound to a concrete type.
@@ -811,9 +808,6 @@
   bool areInSameEquivalenceClass(Type type1, Type type2);
 
   /// Simplify the given dependent type down to its canonical representation.
-  ///
-  /// \returns null if the type involved dependent member types that
-  /// don't have associated types.
   Type getCanonicalTypeParameter(Type type);
 
   /// For each requirement in \c sig, create a new signature without it and see
diff --git a/lib/AST/GenericSignatureBuilder.cpp b/lib/AST/GenericSignatureBuilder.cpp
index 4154b8c..158ab66 100644
--- a/lib/AST/GenericSignatureBuilder.cpp
+++ b/lib/AST/GenericSignatureBuilder.cpp
@@ -166,17 +166,17 @@
   ///
   /// \returns the path, or None if it contained unresolved dependent member
   /// types.
-  Optional<RewritePath> static createPath(Type type);
+  RewritePath static createPath(Type type);
 
   /// Decompose a type into a path.
   ///
   /// \param path Will be filled in with the components of the path, in
   /// reverse order.
   ///
-  /// \returns the generic parameter at the start of the path, or \c None if
-  ///
-  Optional<GenericParamKey>
-  static createPath(Type type, SmallVectorImpl<AssociatedTypeDecl *> &path);
+  /// \returns the generic parameter at the start of the path.
+  static GenericParamKey createPath(
+                                Type type,
+                                SmallVectorImpl<AssociatedTypeDecl *> &path);
 
   /// Compute the longer common prefix between this path and \c other.
   RewritePath commonPath(const RewritePath &other) const;
@@ -216,11 +216,11 @@
                   EquivalenceClass &equivClass)
     : builder(builder), equivClass(equivClass) { }
 
-  Optional<RewritePath> getAnchorPath() {
-    if (anchorPath) return anchorPath;
+  const RewritePath &getAnchorPath() {
+    if (anchorPath) return *anchorPath;
 
     anchorPath = RewritePath::createPath(equivClass.getAnchor(builder, { }));
-    return anchorPath;
+    return *anchorPath;
   }
 };
 
@@ -437,9 +437,9 @@
   /// Equivalence classes that are not currently being used.
   std::vector<void *> FreeEquivalenceClasses;
 
-  /// The roots of the rewrite tree.
-  DenseMap<const EquivalenceClass *, std::unique_ptr<RewriteTreeNode>>
-    RewriteTreeRoots;
+  /// The roots of the rewrite tree, keyed on the canonical, dependent
+  /// types.
+  DenseMap<CanType, std::unique_ptr<RewriteTreeNode>> RewriteTreeRoots;
 
   /// The generation number for the term-rewriting system, which is
   /// increased every time a new rule gets added.
@@ -482,15 +482,12 @@
   /// Deallocate the given equivalence class, returning it to the free list.
   void deallocateEquivalenceClass(EquivalenceClass *equivClass);
 
-  /// Retrieve the rewrite tree root for the given equivalence class,
-  /// if present.
-  RewriteTreeNode *getRewriteTreeRootIfPresent(
-                                      const EquivalenceClass *equivClass);
+  /// Retrieve the rewrite tree root for the given anchor type.
+  RewriteTreeNode *getRewriteTreeRootIfPresent(CanType anchor);
 
-  /// Retrieve the rewrite tree root for the given equivalence class,
+  /// Retrieve the rewrite tree root for the given anchor type,
   /// creating it if needed.
-  RewriteTreeNode *getOrCreateRewriteTreeRoot(
-                                        const EquivalenceClass *equivClass);
+  RewriteTreeNode *getOrCreateRewriteTreeRoot(CanType anchor);
 
   /// Minimize the rewrite tree by minimizing the right-hand sides and
   /// removing redundant rules.
@@ -2293,8 +2290,8 @@
   bool updatedAnchor = false;
   for (auto member : members) {
     auto anchorType =
-      builder.getCanonicalTypeParameter(member->getDependentType(genericParams));
-    if (!anchorType) continue;
+      builder.getCanonicalTypeParameter(
+                                    member->getDependentType(genericParams));
 
 #ifndef NDEBUG
     // Check that we get consistent results from all of the anchors.
@@ -2493,7 +2490,11 @@
   out << "\n";
 
   if (builder) {
-    if (auto rewriteRoot = builder->Impl->getRewriteTreeRootIfPresent(this)) {
+    CanType anchorType =
+      const_cast<EquivalenceClass *>(this)->getAnchor(*builder, { })
+        ->getCanonicalType();
+    if (auto rewriteRoot =
+          builder->Impl->getRewriteTreeRootIfPresent(anchorType)) {
       out << "---Rewrite tree---\n";
       rewriteRoot->dump(out);
     }
@@ -3173,30 +3174,23 @@
   }
 }
 
-Optional<RewritePath> RewritePath::createPath(Type type) {
+RewritePath RewritePath::createPath(Type type) {
   SmallVector<AssociatedTypeDecl *, 4> path;
-  if (auto genericParam = createPath(type, path)) {
-    return RewritePath(*genericParam, path, Reverse);
-  }
-
-  return None;
+  auto genericParam = createPath(type, path);
+  return RewritePath(genericParam, path, Reverse);
 }
 
-Optional<GenericParamKey>
-RewritePath::createPath(Type type,
-                        SmallVectorImpl<AssociatedTypeDecl *> &path) {
+GenericParamKey RewritePath::createPath(
+                                Type type,
+                                SmallVectorImpl<AssociatedTypeDecl *> &path) {
   while (auto depMemTy = type->getAs<DependentMemberType>()) {
     auto assocType = depMemTy->getAssocType();
-    if (!assocType) return None;
-
+    assert(assocType && "Unresolved dependent member type");
     path.push_back(assocType);
     type = depMemTy->getBase();
   }
 
-  auto genericParam = type->getAs<GenericTypeParamType>();
-  if (!genericParam) return None;
-
-  return GenericParamKey(genericParam);
+  return type->castTo<GenericTypeParamType>();
 }
 
 RewritePath RewritePath::commonPath(const RewritePath &other) const {
@@ -3244,15 +3238,14 @@
     return CanType(::formDependentType(ctx, *base, getPath()));
 
   assert(anchorPathCache && "Need an anchor path cache");
-  Optional<RewritePath> anchorPath = anchorPathCache->getAnchorPath();
-  if (!anchorPath) return CanType();
+  const RewritePath &anchorPath = anchorPathCache->getAnchorPath();
 
   // Add the relative path to the anchor path.
   SmallVector<AssociatedTypeDecl *, 4> absolutePath;
-  absolutePath.append(anchorPath->getPath().begin(),
-                      anchorPath->getPath().end());
+  absolutePath.append(anchorPath.getPath().begin(),
+                      anchorPath.getPath().end());
   absolutePath.append(getPath().begin(), getPath().end());
-  return CanType(::formDependentType(ctx, *anchorPath->getBase(),
+  return CanType(::formDependentType(ctx, *anchorPath.getBase(),
                                      absolutePath));
 
 }
@@ -3551,8 +3544,8 @@
 
 RewriteTreeNode *
 GenericSignatureBuilder::Implementation::getRewriteTreeRootIfPresent(
-                                          const EquivalenceClass *equivClass) {
-  auto known = RewriteTreeRoots.find(equivClass);
+                                          CanType anchor) {
+  auto known = RewriteTreeRoots.find(anchor);
   if (known != RewriteTreeRoots.end()) return known->second.get();
 
   return nullptr;
@@ -3560,11 +3553,11 @@
 
 RewriteTreeNode *
 GenericSignatureBuilder::Implementation::getOrCreateRewriteTreeRoot(
-                                          const EquivalenceClass *equivClass) {
-  auto known = RewriteTreeRoots.find(equivClass);
+                                          CanType anchor) {
+  auto known = RewriteTreeRoots.find(anchor);
   if (known != RewriteTreeRoots.end()) return known->second.get();
 
-  auto &root = RewriteTreeRoots[equivClass];
+  auto &root = RewriteTreeRoots[anchor];
   root = std::unique_ptr<RewriteTreeNode>(new RewriteTreeNode(nullptr));
   return root.get();
 }
@@ -3593,7 +3586,8 @@
 
   // Minimize the right-hand sides of each rule in the tree.
   for (auto &equivClass : EquivalenceClasses) {
-    auto root = RewriteTreeRoots.find(&equivClass);
+    CanType anchorType = equivClass.getAnchor(builder, { })->getCanonicalType();
+    auto root = RewriteTreeRoots.find(anchorType);
     if (root == RewriteTreeRoots.end()) continue;
 
     AnchorPathCache anchorPathCache(builder, equivClass);
@@ -3618,9 +3612,9 @@
       ++NumRewriteRhsSimplified;
 
       // Determine replacement path, which might be relative to the anchor.
-      auto canonicalRhsPath = *RewritePath::createPath(canonicalRhsType);
+      auto canonicalRhsPath = RewritePath::createPath(canonicalRhsType);
       auto anchorPath = anchorPathCache.getAnchorPath();
-      if (auto prefix = anchorPath->commonPath(canonicalRhsPath)) {
+      if (auto prefix = anchorPath.commonPath(canonicalRhsPath)) {
         unsigned prefixLength = prefix.getPath().size();
         RelativeRewritePath replacementRhsPath =
           canonicalRhsPath.getPath().slice(prefixLength);
@@ -3648,7 +3642,8 @@
 
   // Minimize the right-hand sides of each rule in the tree.
   for (auto &equivClass : EquivalenceClasses) {
-    auto root = RewriteTreeRoots.find(&equivClass);
+    CanType anchorType = equivClass.getAnchor(builder, { })->getCanonicalType();
+    auto root = RewriteTreeRoots.find(anchorType);
     if (root == RewriteTreeRoots.end()) continue;
 
     AnchorPathCache anchorPathCache(builder, equivClass);
@@ -3663,7 +3658,6 @@
 
       // Simplify the left-hand type.
       Type simplifiedLhsType = builder.getCanonicalTypeParameter(lhsType);
-      if (!simplifiedLhsType) return RewriteTreeNode::RuleAction::none();
 
       // Compute the type of the right-hand side.
       Type rhsType = rhs.formDependentType(ctx, &anchorPathCache);
@@ -3680,25 +3674,13 @@
   }
 }
 
-bool GenericSignatureBuilder::addSameTypeRewriteRule(
-                                                EquivalenceClass *equivClass,
-                                                PotentialArchetype *otherPA){
-  // Simplify both sides in the hope of uncovering a common path.
-  Type simplifiedType1 = equivClass->getAnchor(*this, { });
-  if (!simplifiedType1) return false;
-
-  Type simplifiedType2;
-  if (auto otherEquivClass = otherPA->getEquivalenceClassIfPresent())
-    simplifiedType2 = otherEquivClass->getAnchor(*this, { });
-  else
-    simplifiedType2 = getCanonicalTypeParameter(otherPA->getDependentType({ }));
-  if (!simplifiedType2) return false;
-
+bool GenericSignatureBuilder::addSameTypeRewriteRule(CanType type1,
+                                                     CanType type2) {
   // We already effectively have this rewrite rule.
-  if (simplifiedType1->isEqual(simplifiedType2)) return false;
+  if (type1 == type2) return false;
 
-  auto path1 = *RewritePath::createPath(simplifiedType1);
-  auto path2 = *RewritePath::createPath(simplifiedType2);
+  auto path1 = RewritePath::createPath(type1);
+  auto path2 = RewritePath::createPath(type2);
 
   // Look for a common prefix. When we have one, form a rewrite rule using
   // relative paths.
@@ -3712,14 +3694,13 @@
     if (compareDependentPaths(relPath1, relPath2) < 0)
       std::swap(relPath1, relPath2);
 
-    // Find the equivalence class for the prefix.
+    // Find the anchor for the prefix.
     CanType commonType = prefix.formDependentType(getASTContext());
-    auto equivClass =
-      resolveEquivalenceClass(commonType, ArchetypeResolutionKind::WellFormed);
-    assert(equivClass && "Prefix cannot be resolved?");
+    CanType commonAnchor =
+      getCanonicalTypeParameter(commonType)->getCanonicalType();
 
     // Add the rewrite rule.
-    auto root = Impl->getOrCreateRewriteTreeRoot(equivClass);
+    auto root = Impl->getOrCreateRewriteTreeRoot(commonAnchor);
     return root->addRewriteRule(
                           relPath1,
                           RewritePath(None, relPath2, RewritePath::Forward));
@@ -3728,44 +3709,36 @@
   // Otherwise, form a rewrite rule with absolute paths.
 
   // Find the better path and make sure it's in path2.
-  if (compareDependentTypes(simplifiedType1, simplifiedType2) < 0) {
+  if (compareDependentTypes(type1, type2) < 0) {
     std::swap(path1, path2);
-    std::swap(simplifiedType1, simplifiedType2);
+    std::swap(type1, type2);
   }
 
   // Add the rewrite rule.
   Type firstBase =
     GenericTypeParamType::get(path1.getBase()->Depth, path1.getBase()->Index,
                               getASTContext());
-  auto baseEquivClass =
-    resolveEquivalenceClass(firstBase, ArchetypeResolutionKind::WellFormed);
-  assert(baseEquivClass && "Base cannot be resolved?");
-
-  auto root = Impl->getOrCreateRewriteTreeRoot(baseEquivClass);
+  CanType baseAnchor =
+    getCanonicalTypeParameter(firstBase)->getCanonicalType();
+  auto root = Impl->getOrCreateRewriteTreeRoot(baseAnchor);
   return root->addRewriteRule(path1.getPath(), path2);
 }
 
 Type GenericSignatureBuilder::getCanonicalTypeParameter(Type type) {
   auto initialPath = RewritePath::createPath(type);
-  if (!initialPath) return nullptr;
-
   auto genericParamType =
-    GenericTypeParamType::get(initialPath->getBase()->Depth,
-                              initialPath->getBase()->Index,
+    GenericTypeParamType::get(initialPath.getBase()->Depth,
+                              initialPath.getBase()->Index,
                               getASTContext());
-  auto initialEquivClass =
-    resolveEquivalenceClass(genericParamType,
-                            ArchetypeResolutionKind::WellFormed);
-  if (!initialEquivClass) return nullptr;
 
   unsigned startIndex = 0;
-  auto equivClass = initialEquivClass;
   Type currentType = genericParamType;
-  SmallVector<AssociatedTypeDecl *, 4> path(initialPath->getPath().begin(),
-                                            initialPath->getPath().end());
+  SmallVector<AssociatedTypeDecl *, 4> path(initialPath.getPath().begin(),
+                                            initialPath.getPath().end());
   bool simplified = false;
   do {
-    if (auto rootNode = Impl->getRewriteTreeRootIfPresent(equivClass)) {
+    CanType currentAnchor = currentType->getCanonicalType();
+    if (auto rootNode = Impl->getRewriteTreeRootIfPresent(currentAnchor)) {
       // Find the best rewrite rule for the path starting at startIndex.
       auto match =
         rootNode->bestRewritePath(genericParamType,
@@ -3795,17 +3768,12 @@
           genericParamType =
             GenericTypeParamType::get(newBase->Depth, newBase->Index,
                                       getASTContext());
-          initialEquivClass =
-            resolveEquivalenceClass(genericParamType,
-                                    ArchetypeResolutionKind::WellFormed);
-          assert(initialEquivClass && "Must have an equivalence class");
         }
 
         // Move back to the beginning; we may have opened up other rewrites.
         simplified = true;
         startIndex = 0;
         currentType = genericParamType;
-        equivClass = initialEquivClass;
         continue;
       }
     }
@@ -3813,12 +3781,7 @@
     // If we've hit the end of the path, we're done.
     if (startIndex >= path.size()) break;
 
-    // FIXME: It would be nice if there were a better way to get the equivalence
-    // class of a named nested type.
     currentType = DependentMemberType::get(currentType, path[startIndex++]);
-    equivClass =
-      resolveEquivalenceClass(currentType, ArchetypeResolutionKind::WellFormed);
-    if (!equivClass) break;
   } while (true);
 
   return formDependentType(genericParamType, path);
@@ -4865,14 +4828,18 @@
 }
 
 ConstraintResult
-GenericSignatureBuilder::addSameTypeRequirementBetweenArchetypes(
-       PotentialArchetype *OrigT1,
-       PotentialArchetype *OrigT2,
-       const RequirementSource *Source) 
+GenericSignatureBuilder::addSameTypeRequirementBetweenTypeParameters(
+                                         ResolvedType type1, ResolvedType type2,
+                                         const RequirementSource *source)
 {
+  // Both sides are type parameters; equate them.
+  // FIXME: Realizes potential archetypes far too early.
+  auto OrigT1 = type1.realizePotentialArchetype(*this);
+  auto OrigT2 = type2.realizePotentialArchetype(*this);
+
   // Record the same-type constraint, and bail out if it was already known.
   if (!OrigT1->getOrCreateEquivalenceClass(*this)
-        ->recordSameTypeConstraint(OrigT1, OrigT2, Source))
+        ->recordSameTypeConstraint(OrigT1, OrigT2, source))
     return ConstraintResult::Resolved;
 
   // Operate on the representatives
@@ -4889,10 +4856,15 @@
     std::swap(OrigT1, OrigT2);
   }
 
-  // Add a rewrite rule to map T2 down to the anchor.
   auto equivClass = T1->getOrCreateEquivalenceClass(*this);
-  if (addSameTypeRewriteRule(equivClass, T2))
-    ++Impl->RewriteGeneration;
+  auto equivClass2 = T2->getEquivalenceClassIfPresent();
+
+  // Determine the anchor types of the two equivalence classes.
+  CanType anchor1 = equivClass->getAnchor(*this, { })->getCanonicalType();
+  CanType anchor2 =
+    (equivClass2 ? equivClass2->getAnchor(*this, { })
+                 : getCanonicalTypeParameter(T2->getDependentType({ })))
+      ->getCanonicalType();
 
   // Merge the equivalence classes.
   equivClass->modified(*this);
@@ -4902,7 +4874,6 @@
     equivClass->addMember(equiv);
 
   // Grab the old equivalence class, if present. We'll deallocate it at the end.
-  auto equivClass2 = T2->getEquivalenceClassIfPresent();
   SWIFT_DEFER {
     if (equivClass2)
       Impl->deallocateEquivalenceClass(equivClass2);
@@ -4918,31 +4889,35 @@
                                    equivClass->sameTypeConstraints.end(),
                                    equivClass2->sameTypeConstraints.begin(),
                                    equivClass2->sameTypeConstraints.end());
+  }
 
-    // Combine the rewrite rules.
-    if (auto rewriteRoot2 = Impl->getOrCreateRewriteTreeRoot(equivClass2)) {
-      if (auto rewriteRoot1 = Impl->getOrCreateRewriteTreeRoot(equivClass)) {
-        // Merge the second rewrite tree into the first.
-        if (rewriteRoot2->mergeInto(rewriteRoot1))
-          ++Impl->RewriteGeneration;
-        Impl->RewriteTreeRoots.erase(equivClass2);
-      } else {
-        // Take the second rewrite tree and make it the first.
-        auto root2Entry = Impl->RewriteTreeRoots.find(equivClass2);
-        auto root2Ptr = std::move(root2Entry->second);
-        Impl->RewriteTreeRoots.erase(root2Entry);
-        (void)Impl->RewriteTreeRoots.insert({equivClass, std::move(root2Ptr)});
-      }
+  // Combine the rewrite rules.
+  if (auto rewriteRoot2 = Impl->getOrCreateRewriteTreeRoot(anchor2)) {
+    if (auto rewriteRoot1 = Impl->getOrCreateRewriteTreeRoot(anchor1)) {
+      // Merge the second rewrite tree into the first.
+      if (rewriteRoot2->mergeInto(rewriteRoot1))
+        ++Impl->RewriteGeneration;
+      Impl->RewriteTreeRoots.erase(anchor2);
+    } else {
+      // Take the second rewrite tree and make it the first.
+      auto root2Entry = Impl->RewriteTreeRoots.find(anchor2);
+      auto root2Ptr = std::move(root2Entry->second);
+      Impl->RewriteTreeRoots.erase(root2Entry);
+      (void)Impl->RewriteTreeRoots.insert({anchor1, std::move(root2Ptr)});
     }
   }
 
+  // Add a rewrite rule to map the anchor of T2 down to the anchor of T1.
+  if (addSameTypeRewriteRule(anchor2, anchor1))
+    ++Impl->RewriteGeneration;
+
   // Same-type-to-concrete requirements.
   bool t1IsConcrete = !equivClass->concreteType.isNull();
   bool t2IsConcrete = equivClass2 && !equivClass2->concreteType.isNull();
   if (t2IsConcrete) {
     if (t1IsConcrete) {
       (void)addSameTypeRequirement(equivClass->concreteType,
-                                   equivClass2->concreteType, Source,
+                                   equivClass2->concreteType, source,
                                    UnresolvedHandlingKind::GenerateConstraints,
                                    SameTypeConflictCheckedLater());
     } else {
@@ -5187,15 +5162,9 @@
                         source.getSource(*this, type1.getDependentType(*this)));
   }
 
-  // Both sides are type parameters; equate them.
-  // FIXME: Realizes potential archetypes far too early.
-  auto pa1 = type1.realizePotentialArchetype(*this);
-  auto pa2 = type2.realizePotentialArchetype(*this);
-
-  return addSameTypeRequirementBetweenArchetypes(
-                     pa1, pa2,
-                     source.getSource(*this,
-                                      type2.getDependentType(*this)));
+  return addSameTypeRequirementBetweenTypeParameters(
+                     type1, type2,
+                     source.getSource(*this, type2.getDependentType(*this)));
 }
 
 ConstraintResult GenericSignatureBuilder::addInheritedRequirements(