src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/IntraproceduralDataflowAnalysis.java

// Copyright (c) 2020, 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.analysis.framework.intraprocedural;

import com.android.tools.r8.ir.analysis.framework.intraprocedural.DataflowAnalysisResult.FailedDataflowAnalysisResult;
import com.android.tools.r8.ir.analysis.framework.intraprocedural.DataflowAnalysisResult.SuccessfulDataflowAnalysisResult;
import com.android.tools.r8.ir.code.BasicBlock;
import com.android.tools.r8.ir.code.Instruction;
import com.android.tools.r8.utils.WorkList;
import java.util.IdentityHashMap;
import java.util.Map;

/**
 * This defines a simple fixpoint solver for running an intraprocedural dataflow analysis.
 *
 * <p>The solver computes an {@link AbstractState} for each {@link BasicBlock} using the {@link
 * AbstractTransferFunction} which defines the abstract semantics for each instruction.
 *
 * <p>Once the fixpoint is reached the analysis returns a {@link SuccessfulDataflowAnalysisResult}.
 * If the supplied {@link AbstractTransferFunction} returns a {@link FailedTransferFunctionResult}
 * for a given instruction and abstract state, then the analysis return a {@link
 * FailedDataflowAnalysisResult}.
 */
public class IntraproceduralDataflowAnalysis<StateType extends AbstractState<StateType>> {

  private final StateType bottom;

  // The transfer function that defines the abstract semantics for each instruction.
  private final AbstractTransferFunction<StateType> transfer;

  // The state of the analysis.
  private final Map<BasicBlock, StateType> blockExitStates = new IdentityHashMap<>();

  public IntraproceduralDataflowAnalysis(
      StateType bottom, AbstractTransferFunction<StateType> transfer) {
    this.bottom = bottom;
    this.transfer = transfer;
  }

  public DataflowAnalysisResult run(BasicBlock root) {
    return run(WorkList.newIdentityWorkList(root));
  }

  private DataflowAnalysisResult run(WorkList<BasicBlock> worklist) {
    while (worklist.hasNext()) {
      BasicBlock block = worklist.next();
      BasicBlock end = null;
      // Compute the abstract state upon entry to the basic block, by joining all the predecessor
      // exit states.
      StateType state = computeBlockEntryState(block);
      do {
        for (Instruction instruction : block.getInstructions()) {
          TransferFunctionResult<StateType> transferResult = transfer.apply(instruction, state);
          if (transferResult.isFailedTransferResult()) {
            return new FailedDataflowAnalysisResult();
          }
          assert transferResult.isAbstractState();
          state = transferResult.asAbstractState();
        }
        if (block.hasUniqueSuccessorWithUniquePredecessor()) {
          block = block.getUniqueSuccessor();
        } else {
          end = block;
          block = null;
        }
      } while (block != null);
      // Update the block exit state, and re-enqueue all successor blocks if the abstract state
      // changed.
      if (setBlockExitState(end, state)) {
        worklist.addAllIgnoringSeenSet(end.getSuccessors());
      }
    }
    return new SuccessfulDataflowAnalysisResult<>(blockExitStates);
  }

  private StateType computeBlockEntryState(BasicBlock block) {
    StateType result = bottom;
    for (BasicBlock predecessor : block.getPredecessors()) {
      StateType edgeState =
          transfer.computeBlockEntryState(
              block, predecessor, blockExitStates.getOrDefault(predecessor, bottom));
      result = result.join(edgeState);
    }
    return result;
  }

  private boolean setBlockExitState(BasicBlock block, StateType state) {
    assert !block.hasUniqueSuccessorWithUniquePredecessor();
    StateType previous = blockExitStates.put(block, state);
    assert previous == null || state.isGreaterThanOrEquals(previous);
    return !state.equals(previous);
  }
}