src/test/java/com/android/tools/r8/ir/conversion/NodeExtractionTest.java

// Copyright (c) 2019, the R8 project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
package com.android.tools.r8.ir.conversion;

import static org.hamcrest.CoreMatchers.hasItem;
import static org.hamcrest.MatcherAssert.assertThat;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;

import com.android.tools.r8.graph.DexEncodedMethod;
import com.android.tools.r8.ir.conversion.CallGraph.Node;
import com.android.tools.r8.ir.conversion.CallGraphBuilderBase.CycleEliminator;
import com.android.tools.r8.utils.InternalOptions;
import com.google.common.collect.Sets;
import java.util.Set;
import java.util.TreeSet;
import org.junit.Test;

public class NodeExtractionTest extends CallGraphTestBase {

  private InternalOptions options = new InternalOptions();

  // Note that building a test graph is intentionally repeated to avoid race conditions and/or
  // non-deterministic test results due to cycle elimination.

  @Test
  public void testExtractLeaves_withoutCycle() {
    Node n1, n2, n3, n4, n5, n6;
    Set<Node> nodes;

    n1 = createNode("n1");
    n2 = createNode("n2");
    n3 = createNode("n3");
    n4 = createNode("n4");
    n5 = createNode("n5");
    n6 = createNode("n6");

    n2.addCallerConcurrently(n1);
    n3.addCallerConcurrently(n2);
    n4.addCallerConcurrently(n2);
    n4.addCallerConcurrently(n5);
    n6.addCallerConcurrently(n5);

    nodes = new TreeSet<>();
    nodes.add(n1);
    nodes.add(n2);
    nodes.add(n3);
    nodes.add(n4);
    nodes.add(n5);
    nodes.add(n6);

    Set<Node> wave = Sets.newIdentityHashSet();

    PrimaryMethodProcessor.extractLeaves(nodes, wave::add);
    assertEquals(3, wave.size());
    assertThat(wave, hasItem(n3));
    assertThat(wave, hasItem(n4));
    assertThat(wave, hasItem(n6));
    wave.clear();

    PrimaryMethodProcessor.extractLeaves(nodes, wave::add);
    assertEquals(2, wave.size());
    assertThat(wave, hasItem(n2));
    assertThat(wave, hasItem(n5));
    wave.clear();

    PrimaryMethodProcessor.extractLeaves(nodes, wave::add);
    assertEquals(1, wave.size());
    assertThat(wave, hasItem(n1));
    assertTrue(nodes.isEmpty());
  }

  @Test
  public void testExtractLeaves_withCycle() {
    Node n1, n2, n3, n4, n5, n6;
    Set<Node> nodes;

    n1 = createNode("n1");
    n2 = createNode("n2");
    n3 = createNode("n3");
    n4 = createNode("n4");
    n5 = createNode("n5");
    n6 = createNode("n6");

    n2.addCallerConcurrently(n1);
    n3.addCallerConcurrently(n2);
    n4.addCallerConcurrently(n2);
    n4.addCallerConcurrently(n5);
    n6.addCallerConcurrently(n5);

    nodes = new TreeSet<>();
    nodes.add(n1);
    nodes.add(n2);
    nodes.add(n3);
    nodes.add(n4);
    nodes.add(n5);
    nodes.add(n6);

    n1.addCallerConcurrently(n3);
    n3.method.getMutableOptimizationInfo().markForceInline();
    CycleEliminator cycleEliminator = new CycleEliminator(nodes, options);
    assertEquals(1, cycleEliminator.breakCycles().numberOfRemovedEdges());

    Set<Node> wave = Sets.newIdentityHashSet();

    PrimaryMethodProcessor.extractLeaves(nodes, wave::add);
    assertEquals(3, wave.size());
    assertThat(wave, hasItem(n3));
    assertThat(wave, hasItem(n4));
    assertThat(wave, hasItem(n6));
    wave.clear();

    PrimaryMethodProcessor.extractLeaves(nodes, wave::add);
    assertEquals(2, wave.size());
    assertThat(wave, hasItem(n2));
    assertThat(wave, hasItem(n5));
    wave.clear();

    PrimaryMethodProcessor.extractLeaves(nodes, wave::add);
    assertEquals(1, wave.size());
    assertThat(wave, hasItem(n1));
    assertTrue(nodes.isEmpty());
  }

  @Test
  public void testExtractRoots_withoutCycle() {
    Node n1, n2, n3, n4, n5, n6;
    Set<Node> nodes;

    n1 = createNode("n1");
    n2 = createNode("n2");
    n3 = createNode("n3");
    n4 = createNode("n4");
    n5 = createNode("n5");
    n6 = createNode("n6");

    n2.addCallerConcurrently(n1);
    n3.addCallerConcurrently(n2);
    n4.addCallerConcurrently(n2);
    n4.addCallerConcurrently(n5);
    n6.addCallerConcurrently(n5);

    nodes = new TreeSet<>();
    nodes.add(n1);
    nodes.add(n2);
    nodes.add(n3);
    nodes.add(n4);
    nodes.add(n5);
    nodes.add(n6);

    CallGraph callGraph = new CallGraph(nodes, null);
    Set<DexEncodedMethod> wave = Sets.newIdentityHashSet();

    wave.addAll(callGraph.extractRoots());
    assertEquals(2, wave.size());
    assertThat(wave, hasItem(n1.method));
    assertThat(wave, hasItem(n5.method));
    wave.clear();

    wave.addAll(callGraph.extractRoots());
    assertEquals(2, wave.size());
    assertThat(wave, hasItem(n2.method));
    assertThat(wave, hasItem(n6.method));
    wave.clear();

    wave.addAll(callGraph.extractRoots());
    assertEquals(2, wave.size());
    assertThat(wave, hasItem(n3.method));
    assertThat(wave, hasItem(n4.method));
    assertTrue(nodes.isEmpty());
  }

  @Test
  public void testExtractRoots_withCycle() {
    Node n1, n2, n3, n4, n5, n6;
    Set<Node> nodes;

    n1 = createNode("n1");
    n2 = createNode("n2");
    n3 = createNode("n3");
    n4 = createNode("n4");
    n5 = createNode("n5");
    n6 = createNode("n6");

    n2.addCallerConcurrently(n1);
    n3.addCallerConcurrently(n2);
    n4.addCallerConcurrently(n2);
    n4.addCallerConcurrently(n5);
    n6.addCallerConcurrently(n5);

    nodes = new TreeSet<>();
    nodes.add(n1);
    nodes.add(n2);
    nodes.add(n3);
    nodes.add(n4);
    nodes.add(n5);
    nodes.add(n6);

    n1.addCallerConcurrently(n3);
    n3.method.getMutableOptimizationInfo().markForceInline();
    CycleEliminator cycleEliminator = new CycleEliminator(nodes, options);
    assertEquals(1, cycleEliminator.breakCycles().numberOfRemovedEdges());

    CallGraph callGraph = new CallGraph(nodes, null);
    Set<DexEncodedMethod> wave = Sets.newIdentityHashSet();

    wave.addAll(callGraph.extractRoots());
    assertEquals(2, wave.size());
    assertThat(wave, hasItem(n1.method));
    assertThat(wave, hasItem(n5.method));
    wave.clear();

    wave.addAll(callGraph.extractRoots());
    assertEquals(2, wave.size());
    assertThat(wave, hasItem(n2.method));
    assertThat(wave, hasItem(n6.method));
    wave.clear();

    wave.addAll(callGraph.extractRoots());
    assertEquals(2, wave.size());
    assertThat(wave, hasItem(n3.method));
    assertThat(wave, hasItem(n4.method));
    assertTrue(nodes.isEmpty());
  }
}