diff --git a/src/main/java/com/android/tools/r8/graph/GenericSignature.java b/src/main/java/com/android/tools/r8/graph/GenericSignature.java
index 91ba7b7..97d49a5 100644
--- a/src/main/java/com/android/tools/r8/graph/GenericSignature.java
+++ b/src/main/java/com/android/tools/r8/graph/GenericSignature.java
@@ -96,6 +96,8 @@
  */
 public class GenericSignature {
 
+  private static final List<FormalTypeParameter> EMPTY_TYPE_PARAMS = ImmutableList.of();
+
   interface DexDefinitionSignature<T extends DexDefinition> {
     default boolean isClassSignature() {
       return false;
@@ -122,19 +124,51 @@
     }
   }
 
+  public static class FormalTypeParameter {
+
+    final String name;
+    final FieldTypeSignature classBound;
+    final List<FieldTypeSignature> interfaceBounds;
+
+    FormalTypeParameter(
+        String name, FieldTypeSignature classBound, List<FieldTypeSignature> interfaceBounds) {
+      this.name = name;
+      this.classBound = classBound;
+      this.interfaceBounds = interfaceBounds;
+    }
+
+    public String getName() {
+      return name;
+    }
+
+    public FieldTypeSignature getClassBound() {
+      return classBound;
+    }
+
+    public List<FieldTypeSignature> getInterfaceBounds() {
+      return interfaceBounds;
+    }
+  }
+
   public static class ClassSignature implements DexDefinitionSignature<DexClass> {
     static final ClassSignature UNKNOWN_CLASS_SIGNATURE =
-        new ClassSignature(ClassTypeSignature.UNKNOWN_CLASS_TYPE_SIGNATURE, ImmutableList.of());
+        new ClassSignature(
+            ImmutableList.of(),
+            ClassTypeSignature.UNKNOWN_CLASS_TYPE_SIGNATURE,
+            ImmutableList.of());
 
-    // TODO(b/129925954): encoding formal type parameters
+    final List<FormalTypeParameter> formalTypeParameters;
     final ClassTypeSignature superClassSignature;
     final List<ClassTypeSignature> superInterfaceSignatures;
 
     ClassSignature(
+        List<FormalTypeParameter> formalTypeParameters,
         ClassTypeSignature superClassSignature,
         List<ClassTypeSignature> superInterfaceSignatures) {
+      assert formalTypeParameters != null;
       assert superClassSignature != null;
       assert superInterfaceSignatures != null;
+      this.formalTypeParameters = formalTypeParameters;
       this.superClassSignature = superClassSignature;
       this.superInterfaceSignatures = superInterfaceSignatures;
     }
@@ -221,6 +255,10 @@
     public TypeVariableSignature asTypeVariableSignature() {
       return null;
     }
+
+    public boolean isUnknown() {
+      return this == ClassTypeSignature.UNKNOWN_CLASS_TYPE_SIGNATURE;
+    }
   }
 
   public static class ClassTypeSignature extends FieldTypeSignature {
@@ -331,7 +369,7 @@
   public static class TypeVariableSignature extends FieldTypeSignature {
     final String typeVariable;
 
-    TypeVariableSignature(String typeVariable) {
+    private TypeVariableSignature(String typeVariable) {
       assert typeVariable != null;
       this.typeVariable = typeVariable;
     }
@@ -350,6 +388,10 @@
     public ArrayTypeSignature toArrayTypeSignature(AppView<?> appView) {
       return new ArrayTypeSignature(this);
     }
+
+    public String getTypeVariable() {
+      return typeVariable;
+    }
   }
 
   // TODO(b/129925954): Canonicalization?
@@ -400,20 +442,24 @@
 
   public static class MethodTypeSignature implements DexDefinitionSignature<DexEncodedMethod> {
     static final MethodTypeSignature UNKNOWN_METHOD_TYPE_SIGNATURE =
-        new MethodTypeSignature(ImmutableList.of(), ReturnType.VOID, ImmutableList.of());
+        new MethodTypeSignature(
+            ImmutableList.of(), ImmutableList.of(), ReturnType.VOID, ImmutableList.of());
 
-    // TODO(b/129925954): encoding formal type parameters
+    final List<FormalTypeParameter> formalTypeParameters;
     final List<TypeSignature> typeSignatures;
     final ReturnType returnType;
     final List<TypeSignature> throwsSignatures;
 
     MethodTypeSignature(
+        final List<FormalTypeParameter> formalTypeParameters,
         List<TypeSignature> typeSignatures,
         ReturnType returnType,
         List<TypeSignature> throwsSignatures) {
+      assert formalTypeParameters != null;
       assert typeSignatures != null;
       assert returnType != null;
       assert throwsSignatures != null;
+      this.formalTypeParameters = formalTypeParameters;
       this.typeSignatures = typeSignatures;
       this.returnType = returnType;
       this.throwsSignatures = throwsSignatures;
@@ -443,6 +489,10 @@
     public MethodTypeSignature asMethodTypeSignature() {
       return this;
     }
+
+    public List<FormalTypeParameter> getFormalTypeParameters() {
+      return formalTypeParameters;
+    }
   }
 
   enum Kind {
@@ -688,7 +738,7 @@
     private ClassSignature parseClassSignature() {
       // ClassSignature ::= FormalTypeParameters? SuperclassSignature SuperinterfaceSignature*.
 
-      parseOptFormalTypeParameters();
+      List<FormalTypeParameter> formalTypeParameters = parseOptFormalTypeParameters();
 
       // SuperclassSignature ::= ClassTypeSignature.
       ClassTypeSignature superClassSignature =
@@ -700,42 +750,53 @@
         builder.add(parseClassTypeSignature(ParserPosition.CLASS_SUPER_OR_INTERFACE_ANNOTATION));
       }
 
-      return new ClassSignature(superClassSignature, builder.build());
+      return new ClassSignature(formalTypeParameters, superClassSignature, builder.build());
     }
 
-    private void parseOptFormalTypeParameters() {
+    private List<FormalTypeParameter> parseOptFormalTypeParameters() {
       // FormalTypeParameters ::= "<" FormalTypeParameter+ ">".
-
-      if (symbol == '<') {
-        scanSymbol();
-
-        updateFormalTypeParameter();
-
-        while ((symbol != '>') && (symbol > 0)) {
-          updateFormalTypeParameter();
-        }
-
-        expect('>');
+      if (symbol != '<') {
+        return EMPTY_TYPE_PARAMS;
       }
+      scanSymbol();
+
+      ImmutableList.Builder<FormalTypeParameter> builder = ImmutableList.builder();
+      while ((symbol != '>') && (symbol > 0)) {
+        builder.add(updateFormalTypeParameter());
+      }
+      expect('>');
+      return builder.build();
     }
 
-    private void updateFormalTypeParameter() {
+    private FormalTypeParameter updateFormalTypeParameter() {
       // FormalTypeParameter ::= Identifier ClassBound InterfaceBound*.
       scanIdentifier();
       assert identifier != null;
 
+      String typeParameterIdentifier = identifier;
+
       // ClassBound ::= ":" FieldTypeSignature?.
       expect(':');
 
+      FieldTypeSignature classBound = ClassTypeSignature.UNKNOWN_CLASS_TYPE_SIGNATURE;
       if (symbol == 'L' || symbol == '[' || symbol == 'T') {
-        parseFieldTypeSignature(ParserPosition.MEMBER_ANNOTATION);
+        classBound = parseFieldTypeSignature(ParserPosition.MEMBER_ANNOTATION);
       }
 
+      // Only build the interfacebound builder, which is uncommon, if we actually see an interface.
+      ImmutableList.Builder<FieldTypeSignature> builder = null;
       while (symbol == ':') {
         // InterfaceBound ::= ":" FieldTypeSignature.
+        if (builder == null) {
+          builder = ImmutableList.builder();
+        }
         scanSymbol();
-        parseFieldTypeSignature(ParserPosition.MEMBER_ANNOTATION);
+        builder.add(parseFieldTypeSignature(ParserPosition.MEMBER_ANNOTATION));
       }
+      if (builder == null) {
+        return new FormalTypeParameter(typeParameterIdentifier, classBound, null);
+      }
+      return new FormalTypeParameter(typeParameterIdentifier, classBound, builder.build());
     }
 
     private FieldTypeSignature parseFieldTypeSignature(ParserPosition parserPosition) {
@@ -862,7 +923,7 @@
     private MethodTypeSignature parseMethodTypeSignature() {
       // MethodTypeSignature ::=
       //     FormalTypeParameters? "(" TypeSignature* ")" ReturnType ThrowsSignature*.
-      parseOptFormalTypeParameters();
+      List<FormalTypeParameter> formalTypeParameters = parseOptFormalTypeParameters();
 
       expect('(');
 
@@ -890,7 +951,10 @@
       }
 
       return new MethodTypeSignature(
-          parameterSignatureBuilder.build(), returnType, throwsSignatureBuilder.build());
+          formalTypeParameters,
+          parameterSignatureBuilder.build(),
+          returnType,
+          throwsSignatureBuilder.build());
     }
 
     private ReturnType updateReturnType() {
diff --git a/src/test/java/com/android/tools/r8/graph/GenericSignatureTest.java b/src/test/java/com/android/tools/r8/graph/GenericSignatureTest.java
index 33321eb..582a282 100644
--- a/src/test/java/com/android/tools/r8/graph/GenericSignatureTest.java
+++ b/src/test/java/com/android/tools/r8/graph/GenericSignatureTest.java
@@ -8,16 +8,21 @@
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertFalse;
 import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertNull;
 import static org.junit.Assert.assertTrue;
 
 import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
 import com.android.tools.r8.graph.GenericSignature.ClassSignature;
 import com.android.tools.r8.graph.GenericSignature.ClassTypeSignature;
 import com.android.tools.r8.graph.GenericSignature.FieldTypeSignature;
+import com.android.tools.r8.graph.GenericSignature.FormalTypeParameter;
 import com.android.tools.r8.graph.GenericSignature.MethodTypeSignature;
 import com.android.tools.r8.graph.GenericSignature.Parser;
 import com.android.tools.r8.graph.GenericSignature.ReturnType;
 import com.android.tools.r8.graph.GenericSignature.TypeSignature;
+import com.android.tools.r8.graph.GenericSignatureTestClassA.I;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.utils.AndroidApp;
 import com.android.tools.r8.utils.DescriptorUtils;
@@ -29,9 +34,20 @@
 import java.util.function.Function;
 import java.util.function.Supplier;
 import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
 
+@RunWith(Parameterized.class)
 public class GenericSignatureTest extends TestBase {
 
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withNoneRuntime().build();
+  }
+
+  public GenericSignatureTest(TestParameters parameters) {}
+
   @Test
   public void test() throws Exception {
     AndroidApp app =
@@ -62,6 +78,8 @@
     assertThat(cy, isPresent());
     ClassSubject cyy = inspector.clazz(GenericSignatureTestClassCYY.class);
     assertThat(cyy, isPresent());
+    ClassSubject i = inspector.clazz(I.class);
+    assertThat(cyy, isPresent());
 
     DexEncodedMethod method;
 
@@ -80,13 +98,22 @@
     // Testing ClassSignature
     //
 
-    // class CYY<T extends A<T>.Y> extends CY<T>
+    // class <T:GenericSignatureTestClassA<T>.Y>CYY<T extends A<T>.Y> extends CY<T>
     DexClass clazz = cyy.getDexClass();
     assertNotNull(clazz);
     classSignature = Parser.toClassSignature(clazz, appView);
     assertNotNull(classSignature);
 
-    // TODO(b/129925954): test formal type parameter of CYY
+    assertEquals(1, classSignature.formalTypeParameters.size());
+    FormalTypeParameter formalTypeParameter = classSignature.formalTypeParameters.get(0);
+    assertEquals("T", formalTypeParameter.name);
+    assertNull(formalTypeParameter.interfaceBounds);
+    assertTrue(formalTypeParameter.classBound.isClassTypeSignature());
+    ClassTypeSignature classBoundSignature = formalTypeParameter.classBound.asClassTypeSignature();
+    assertEquals(y.getDexClass().type, classBoundSignature.innerTypeSignature.type);
+    assertEquals(1, classBoundSignature.typeArguments.size());
+    assertEquals(
+        "T", classBoundSignature.typeArguments.get(0).asTypeVariableSignature().typeVariable);
 
     assertTrue(classSignature.superInterfaceSignatures.isEmpty());
     classTypeSignature = classSignature.superClassSignature;
@@ -126,6 +153,18 @@
     methodTypeSignature = Parser.toMethodTypeSignature(method, appView);
     assertNotNull(methodTypeSignature);
 
+    assertEquals(1, methodTypeSignature.formalTypeParameters.size());
+    FormalTypeParameter methodFormalParameter = methodTypeSignature.formalTypeParameters.get(0);
+    assertTrue(methodFormalParameter.classBound.isClassTypeSignature());
+    assertEquals(
+        y.getDexClass().getType(),
+        methodFormalParameter.classBound.asClassTypeSignature().innerTypeSignature.type);
+    assertNotNull(methodFormalParameter.interfaceBounds);
+    assertEquals(1, methodFormalParameter.interfaceBounds.size());
+    FieldTypeSignature interfaceBound = methodFormalParameter.interfaceBounds.get(0);
+    assertTrue(interfaceBound.isClassTypeSignature());
+    assertEquals(i.getDexClass().getType(), interfaceBound.asClassTypeSignature().type);
+
     // return type: A$Y$YY
     returnType = methodTypeSignature.returnType();
     assertFalse(returnType.isVoidDescriptor());
@@ -257,6 +296,9 @@
 //
 
 class GenericSignatureTestClassA<T> {
+
+  interface I {}
+
   class Y {
 
     class YY {}
@@ -264,7 +306,7 @@
     class ZZ<TT> extends YY {
       public YY yy;
 
-      YY newYY(GenericSignatureTestClassB... bs) {
+      <R extends Y & I> YY newYY(GenericSignatureTestClassB... bs) {
         return new YY();
       }