Leverage frames for linear scan in open/closed interfaces analysis

Change-Id: I0cb76522fae740bc89c6299a0e163f9db8704924
diff --git a/src/main/java/com/android/tools/r8/R8.java b/src/main/java/com/android/tools/r8/R8.java
index a39c6b2..4cc8c25 100644
--- a/src/main/java/com/android/tools/r8/R8.java
+++ b/src/main/java/com/android/tools/r8/R8.java
@@ -442,7 +442,6 @@
       assert appView.appInfo().hasLiveness();
       AppView<AppInfoWithLiveness> appViewWithLiveness = appView.withLiveness();
 
-      // TODO(b/214496607): Avoid fixpoint when frames are present.
       new CfOpenClosedInterfacesAnalysis(appViewWithLiveness).run(executorService);
 
       new StartupInstrumentation(appView).instrumentAllClasses(executorService);
diff --git a/src/main/java/com/android/tools/r8/cf/code/CfFrameVerifier.java b/src/main/java/com/android/tools/r8/cf/code/CfFrameVerifier.java
index db01f47..7866b2d 100644
--- a/src/main/java/com/android/tools/r8/cf/code/CfFrameVerifier.java
+++ b/src/main/java/com/android/tools/r8/cf/code/CfFrameVerifier.java
@@ -117,6 +117,7 @@
       if (instruction.isLabel()) {
         updateActiveCatchHandlers(instruction.asLabel());
       }
+      eventConsumer.acceptInstructionState(instruction, state);
       state = instruction.evaluate(state, appView, config);
       if (instruction.isJumpWithNormalTarget()) {
         CfInstruction fallthroughInstruction =
@@ -373,6 +374,14 @@
     INVALID,
     VALID;
 
+    public boolean isNotPresent() {
+      return this == NOT_PRESENT;
+    }
+
+    public boolean isValid() {
+      return this == VALID;
+    }
+
     public boolean isValidOrNotPresent() {
       return this == VALID || this == NOT_PRESENT;
     }
diff --git a/src/main/java/com/android/tools/r8/cf/code/CfFrameVerifierEventConsumer.java b/src/main/java/com/android/tools/r8/cf/code/CfFrameVerifierEventConsumer.java
index a149a5f..043dea6 100644
--- a/src/main/java/com/android/tools/r8/cf/code/CfFrameVerifierEventConsumer.java
+++ b/src/main/java/com/android/tools/r8/cf/code/CfFrameVerifierEventConsumer.java
@@ -5,8 +5,11 @@
 package com.android.tools.r8.cf.code;
 
 import com.android.tools.r8.graph.CfCodeDiagnostics;
+import com.android.tools.r8.optimize.interfaces.analysis.CfFrameState;
 
 public interface CfFrameVerifierEventConsumer {
 
-  void acceptError(CfCodeDiagnostics diagnostics);
+  default void acceptError(CfCodeDiagnostics diagnostics) {}
+
+  default void acceptInstructionState(CfInstruction instruction, CfFrameState state) {}
 }
diff --git a/src/main/java/com/android/tools/r8/optimize/interfaces/analysis/CfOpenClosedInterfacesAnalysis.java b/src/main/java/com/android/tools/r8/optimize/interfaces/analysis/CfOpenClosedInterfacesAnalysis.java
index 3bb80f6..bc44d01 100644
--- a/src/main/java/com/android/tools/r8/optimize/interfaces/analysis/CfOpenClosedInterfacesAnalysis.java
+++ b/src/main/java/com/android/tools/r8/optimize/interfaces/analysis/CfOpenClosedInterfacesAnalysis.java
@@ -5,11 +5,15 @@
 package com.android.tools.r8.optimize.interfaces.analysis;
 
 import com.android.tools.r8.cf.code.CfAssignability;
+import com.android.tools.r8.cf.code.CfFrameVerifier;
+import com.android.tools.r8.cf.code.CfFrameVerifier.StackMapStatus;
+import com.android.tools.r8.cf.code.CfFrameVerifierEventConsumer;
 import com.android.tools.r8.cf.code.CfInstruction;
 import com.android.tools.r8.cf.code.CfSubtypingAssignability;
 import com.android.tools.r8.cf.code.frame.FrameType;
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.CfCode;
+import com.android.tools.r8.graph.CfCodeDiagnostics;
 import com.android.tools.r8.graph.Code;
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexClassAndMember;
@@ -83,34 +87,109 @@
       assert code.isDefaultInstanceInitializerCode() || code.isDexCode() || code.isThrowNullCode();
       return Collections.emptySet();
     }
-
     CfCode cfCode = code.asCfCode();
-    CfControlFlowGraph cfg = CfControlFlowGraph.create(cfCode, options);
-    TransferFunction transfer = new TransferFunction(method);
+    CfAnalysisConfig config = createConfig(method, cfCode);
+    CfOpenClosedInterfacesAnalysisHelper helper =
+        new CfOpenClosedInterfacesAnalysisHelper(appView, method, unverifiableCodeDiagnostics);
+    if (runLinearScan(method, cfCode, config, helper).isNotPresent()) {
+      runFixpoint(method, cfCode, config, helper);
+    }
+    return helper.getOpenInterfaces();
+  }
+
+  private CfAnalysisConfig createConfig(ProgramMethod method, CfCode code) {
+    return new CfAnalysisConfig() {
+
+      @Override
+      public CfAssignability getAssignability() {
+        return assignability;
+      }
+
+      @Override
+      public DexMethod getCurrentContext() {
+        return method.getReference();
+      }
+
+      @Override
+      public int getMaxLocals() {
+        return code.getMaxLocals();
+      }
+
+      @Override
+      public int getMaxStack() {
+        return code.getMaxStack();
+      }
+
+      @Override
+      public boolean isImmediateSuperClassOfCurrentContext(DexType type) {
+        return type == method.getHolder().getSuperType();
+      }
+
+      @Override
+      public boolean isStrengthenFramesEnabled() {
+        return true;
+      }
+    };
+  }
+
+  private StackMapStatus runLinearScan(
+      ProgramMethod method,
+      CfCode code,
+      CfAnalysisConfig config,
+      CfOpenClosedInterfacesAnalysisHelper helper) {
+    CfFrameVerifierEventConsumer eventConsumer =
+        new CfFrameVerifierEventConsumer() {
+
+          @Override
+          public void acceptError(CfCodeDiagnostics diagnostics) {
+            helper.registerUnverifiableCodeWithFrames(diagnostics);
+          }
+
+          @Override
+          public void acceptInstructionState(CfInstruction instruction, CfFrameState state) {
+            helper.processInstruction(instruction, state);
+          }
+        };
+    CfFrameVerifier verifier =
+        CfFrameVerifier.builder(appView, code, method)
+            .setConfig(config)
+            .setEventConsumer(eventConsumer)
+            .build();
+    StackMapStatus stackMapStatus = verifier.run();
+    assert stackMapStatus.isValid() || helper.getOpenInterfaces().isEmpty();
+    return stackMapStatus;
+  }
+
+  private void runFixpoint(
+      ProgramMethod method,
+      CfCode code,
+      CfAnalysisConfig config,
+      CfOpenClosedInterfacesAnalysisHelper helper) {
+    CfControlFlowGraph cfg = CfControlFlowGraph.create(code, options);
+    TransferFunction transfer = new TransferFunction(config, method);
     CfIntraproceduralDataflowAnalysis<CfFrameState> analysis =
         new CfIntraproceduralDataflowAnalysis<>(appView, CfFrameState.bottom(), cfg, transfer);
     DataflowAnalysisResult result = analysis.run(cfg.getEntryBlock());
     assert result.isSuccessfulAnalysisResult();
-
-    CfOpenClosedInterfacesAnalysisHelper helper =
-        new CfOpenClosedInterfacesAnalysisHelper(appView, method);
     for (CfBlock block : cfg.getBlocks()) {
       if (analysis.isIntermediateBlock(block)) {
         continue;
       }
       CfFrameState state = analysis.computeBlockEntryState(block);
       if (state.isError()) {
-        return registerUnverifiableCode(method, 0, state.asError());
+        helper.registerUnverifiableCode(method, 0, state.asError());
+        return;
       }
       do {
         for (int instructionIndex = block.getFirstInstructionIndex();
             instructionIndex <= block.getLastInstructionIndex();
             instructionIndex++) {
-          CfInstruction instruction = cfCode.getInstruction(instructionIndex);
+          CfInstruction instruction = code.getInstruction(instructionIndex);
           helper.processInstruction(instruction, state);
           state = transfer.apply(instruction, state).asAbstractState();
           if (state.isError()) {
-            return registerUnverifiableCode(method, instructionIndex, state.asError());
+            helper.registerUnverifiableCode(method, instructionIndex, state.asError());
+            return;
           }
         }
         if (analysis.isBlockWithIntermediateSuccessorBlock(block)) {
@@ -120,7 +199,6 @@
         }
       } while (block != null);
     }
-    return helper.getOpenInterfaces();
   }
 
   private void setClosedInterfaces() {
@@ -160,20 +238,6 @@
     }
   }
 
-  private Set<DexClass> registerUnverifiableCode(
-      ProgramMethod method, int instructionIndex, ErroneousCfFrameState state) {
-    if (options.getCfCodeAnalysisOptions().isUnverifiableCodeReportingEnabled()) {
-      unverifiableCodeDiagnostics.put(
-          method,
-          new UnverifiableCfCodeDiagnostic(
-              method.getMethodReference(),
-              instructionIndex,
-              state.getMessage(),
-              method.getOrigin()));
-    }
-    return Collections.emptySet();
-  }
-
   private void reportUnverifiableCodeDiagnostics() {
     Reporter reporter = appView.reporter();
     List<ProgramMethod> methods = new ArrayList<>(unverifiableCodeDiagnostics.size());
@@ -188,43 +252,8 @@
     private final CfAnalysisConfig config;
     private final ProgramMethod context;
 
-    TransferFunction(ProgramMethod context) {
-      CfCode code = context.getDefinition().getCode().asCfCode();
-      int maxLocals = code.getMaxLocals();
-      int maxStack = code.getMaxStack();
-      this.config =
-          new CfAnalysisConfig() {
-
-            @Override
-            public CfAssignability getAssignability() {
-              return assignability;
-            }
-
-            @Override
-            public DexMethod getCurrentContext() {
-              return context.getReference();
-            }
-
-            @Override
-            public int getMaxLocals() {
-              return maxLocals;
-            }
-
-            @Override
-            public int getMaxStack() {
-              return maxStack;
-            }
-
-            @Override
-            public boolean isImmediateSuperClassOfCurrentContext(DexType type) {
-              return type == context.getHolder().getSuperType();
-            }
-
-            @Override
-            public boolean isStrengthenFramesEnabled() {
-              return true;
-            }
-          };
+    TransferFunction(CfAnalysisConfig config, ProgramMethod context) {
+      this.config = config;
       this.context = context;
     }
 
diff --git a/src/main/java/com/android/tools/r8/optimize/interfaces/analysis/CfOpenClosedInterfacesAnalysisHelper.java b/src/main/java/com/android/tools/r8/optimize/interfaces/analysis/CfOpenClosedInterfacesAnalysisHelper.java
index 8f50fc3..515fa4e 100644
--- a/src/main/java/com/android/tools/r8/optimize/interfaces/analysis/CfOpenClosedInterfacesAnalysisHelper.java
+++ b/src/main/java/com/android/tools/r8/optimize/interfaces/analysis/CfOpenClosedInterfacesAnalysisHelper.java
@@ -11,6 +11,7 @@
 import com.android.tools.r8.cf.code.CfStaticFieldWrite;
 import com.android.tools.r8.cf.code.frame.FrameType;
 import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.CfCodeDiagnostics;
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexMethod;
@@ -22,6 +23,8 @@
 import com.android.tools.r8.ir.analysis.type.TypeElement;
 import com.android.tools.r8.shaking.AppInfoWithLiveness;
 import com.android.tools.r8.utils.InternalOptions;
+import com.android.tools.r8.utils.UnverifiableCfCodeDiagnostic;
+import com.android.tools.r8.utils.collections.ProgramMethodMap;
 import com.google.common.collect.Sets;
 import java.util.Set;
 
@@ -33,12 +36,17 @@
   private final InternalOptions options;
 
   private final Set<DexClass> openInterfaces = Sets.newIdentityHashSet();
+  private final ProgramMethodMap<UnverifiableCfCodeDiagnostic> unverifiableCodeDiagnostics;
 
-  CfOpenClosedInterfacesAnalysisHelper(AppView<AppInfoWithLiveness> appView, ProgramMethod method) {
+  CfOpenClosedInterfacesAnalysisHelper(
+      AppView<AppInfoWithLiveness> appView,
+      ProgramMethod method,
+      ProgramMethodMap<UnverifiableCfCodeDiagnostic> unverifiableCodeDiagnostics) {
     this.appView = appView;
     this.dexItemFactory = appView.dexItemFactory();
     this.method = method;
     this.options = appView.options();
+    this.unverifiableCodeDiagnostics = unverifiableCodeDiagnostics;
   }
 
   Set<DexClass> getOpenInterfaces() {
@@ -168,6 +176,33 @@
         });
   }
 
+  void registerUnverifiableCode(
+      ProgramMethod method, int instructionIndex, ErroneousCfFrameState state) {
+    if (options.getCfCodeAnalysisOptions().isUnverifiableCodeReportingEnabled()) {
+      unverifiableCodeDiagnostics.put(
+          method,
+          new UnverifiableCfCodeDiagnostic(
+              method.getMethodReference(),
+              instructionIndex,
+              state.getMessage(),
+              method.getOrigin()));
+    }
+    openInterfaces.clear();
+  }
+
+  void registerUnverifiableCodeWithFrames(CfCodeDiagnostics diagnostics) {
+    if (options.getCfCodeAnalysisOptions().isUnverifiableCodeReportingEnabled()) {
+      unverifiableCodeDiagnostics.put(
+          method,
+          new UnverifiableCfCodeDiagnostic(
+              method.getMethodReference(),
+              -1,
+              diagnostics.getDiagnosticMessage(),
+              method.getOrigin()));
+    }
+    openInterfaces.clear();
+  }
+
   private boolean verifyOpenInterfaceWitnessIsSuppressed(
       TypeElement valueType, DexClass openInterface) {
     assert options.getOpenClosedInterfacesOptions().isSuppressed(appView, valueType, openInterface)
diff --git a/src/main/java/com/android/tools/r8/utils/UnverifiableCfCodeDiagnostic.java b/src/main/java/com/android/tools/r8/utils/UnverifiableCfCodeDiagnostic.java
index e3aac9b..1724acc 100644
--- a/src/main/java/com/android/tools/r8/utils/UnverifiableCfCodeDiagnostic.java
+++ b/src/main/java/com/android/tools/r8/utils/UnverifiableCfCodeDiagnostic.java
@@ -37,12 +37,13 @@
 
   @Override
   public String getDiagnosticMessage() {
-    return "Unverifiable code in `"
-        + MethodReferenceUtils.toSourceString(methodReference)
-        + "` at instruction "
-        + instructionIndex
-        + ": "
-        + message
-        + ".";
+    StringBuilder builder =
+        new StringBuilder("Unverifiable code in `")
+            .append(MethodReferenceUtils.toSourceString(methodReference))
+            .append("`");
+    if (instructionIndex >= 0) {
+      builder.append(" at instruction ").append(instructionIndex);
+    }
+    return builder.append(": ").append(message).append(".").toString();
   }
 }
diff --git a/src/test/java/com/android/tools/r8/cf/stackmap/StackMapVerificationNoFrameForHandlerTest.java b/src/test/java/com/android/tools/r8/cf/stackmap/StackMapVerificationNoFrameForHandlerTest.java
index c3c79fb..49d84b1 100644
--- a/src/test/java/com/android/tools/r8/cf/stackmap/StackMapVerificationNoFrameForHandlerTest.java
+++ b/src/test/java/com/android/tools/r8/cf/stackmap/StackMapVerificationNoFrameForHandlerTest.java
@@ -95,7 +95,11 @@
         .addKeepMainRule(Main.class)
         .setMinApi(parameters.getApiLevel())
         .allowDiagnosticWarningMessages(!includeFrameInHandler)
-        .addOptionsModification(options -> options.testing.readInputStackMaps = true)
+        .addOptionsModification(
+            options -> {
+              options.getCfCodeAnalysisOptions().setEnableUnverifiableCodeReporting(false);
+              options.testing.readInputStackMaps = true;
+            })
         .compileWithExpectedDiagnostics(this::verifyWarningsRegardingStackMap)
         .run(parameters.getRuntime(), Main.class)
         .assertSuccessWithOutputLines(EXPECTED_OUTPUT);
diff --git a/src/test/java/com/android/tools/r8/internal/ClankDepsTest.java b/src/test/java/com/android/tools/r8/internal/ClankDepsTest.java
index ddd9bd4..d7878b9 100644
--- a/src/test/java/com/android/tools/r8/internal/ClankDepsTest.java
+++ b/src/test/java/com/android/tools/r8/internal/ClankDepsTest.java
@@ -49,6 +49,8 @@
         .addDontWarn("dalvik.system.VMStack")
         .addDontWarn("zzz.com.facebook.litho.R$id")
         .addDontWarn("com.google.android.libraries.elements.R$id")
+        .addOptionsModification(
+            options -> options.getOpenClosedInterfacesOptions().suppressAllOpenInterfaces())
         .allowUnusedDontWarnPatterns()
         .allowUnusedProguardConfigurationRules()
         .allowUnnecessaryDontWarnWildcards()
diff --git a/src/test/java/com/android/tools/r8/missingclasses/MissingClassReferencedFromCatchHandlerTest.java b/src/test/java/com/android/tools/r8/missingclasses/MissingClassReferencedFromCatchHandlerTest.java
index 11bc862..85e2d31 100644
--- a/src/test/java/com/android/tools/r8/missingclasses/MissingClassReferencedFromCatchHandlerTest.java
+++ b/src/test/java/com/android/tools/r8/missingclasses/MissingClassReferencedFromCatchHandlerTest.java
@@ -5,6 +5,7 @@
 package com.android.tools.r8.missingclasses;
 
 import com.android.tools.r8.CompilationFailedException;
+import com.android.tools.r8.R8FullTestBuilder;
 import com.android.tools.r8.TestDiagnosticMessages;
 import com.android.tools.r8.TestParameters;
 import com.android.tools.r8.diagnostic.DefinitionContext;
@@ -27,19 +28,25 @@
   @Test(expected = CompilationFailedException.class)
   public void testNoRules() throws Exception {
     compileWithExpectedDiagnostics(
-        Main.class, diagnostics -> inspectDiagnosticsWithNoRules(diagnostics, referencedFrom));
+        Main.class,
+        diagnostics -> inspectDiagnosticsWithNoRules(diagnostics, referencedFrom),
+        this::configure);
   }
 
   @Test
   public void testDontWarnMainClass() throws Exception {
     compileWithExpectedDiagnostics(
-        Main.class, TestDiagnosticMessages::assertNoMessages, addDontWarn(Main.class));
+        Main.class,
+        TestDiagnosticMessages::assertNoMessages,
+        addDontWarn(Main.class).andThen(this::configure));
   }
 
   @Test
   public void testDontWarnMissingClass() throws Exception {
     compileWithExpectedDiagnostics(
-        Main.class, TestDiagnosticMessages::assertNoMessages, addDontWarn(MissingClass.class));
+        Main.class,
+        TestDiagnosticMessages::assertNoMessages,
+        addDontWarn(MissingClass.class).andThen(this::configure));
   }
 
   @Test
@@ -47,7 +54,12 @@
     compileWithExpectedDiagnostics(
         Main.class,
         diagnostics -> inspectDiagnosticsWithIgnoreWarnings(diagnostics, referencedFrom),
-        addIgnoreWarnings());
+        addIgnoreWarnings().andThen(this::configure));
+  }
+
+  public void configure(R8FullTestBuilder testBuilder) {
+    testBuilder.addOptionsModification(
+        options -> options.getCfCodeAnalysisOptions().setEnableUnverifiableCodeReporting(false));
   }
 
   static class Main {