blob: b7909dfffbca9fc1aa23c79ff6812dd710acde63 [file] [log] [blame]
// Copyright (c) 2016, 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.optimize;
import com.android.tools.r8.ir.code.BasicBlock;
import com.android.tools.r8.ir.code.CatchHandlers;
import com.android.tools.r8.ir.code.IRCode;
import com.android.tools.r8.ir.code.Instruction;
import com.android.tools.r8.ir.code.Value;
import com.android.tools.r8.ir.regalloc.RegisterAllocator;
import com.google.common.base.Equivalence;
import java.util.Arrays;
import java.util.List;
class BasicBlockInstructionsEquivalence extends Equivalence<BasicBlock> {
private static final int UNKNOW_HASH = -1;
private static final int MAX_HASH_INSTRUCTIONS = 5;
private final RegisterAllocator allocator;
private final int[] hashes;
BasicBlockInstructionsEquivalence(IRCode code, RegisterAllocator allocator) {
this.allocator = allocator;
hashes = new int[code.getCurrentBlockNumber() + 1];
Arrays.fill(hashes, UNKNOW_HASH);
}
private boolean hasIdenticalInstructions(BasicBlock first, BasicBlock second) {
List<Instruction> instructions0 = first.getInstructions();
List<Instruction> instructions1 = second.getInstructions();
if (instructions0.size() != instructions1.size()) {
return false;
}
for (int i = 0; i < instructions0.size(); i++) {
Instruction i0 = instructions0.get(i);
Instruction i1 = instructions1.get(i);
if (!i0.identicalAfterRegisterAllocation(i1, allocator)) {
return false;
}
}
if (!allocator.hasEqualTypesAtEntry(first, second)) {
return false;
}
CatchHandlers<BasicBlock> handlers0 = first.getCatchHandlers();
CatchHandlers<BasicBlock> handlers1 = second.getCatchHandlers();
if (!handlers0.equals(handlers1)) {
return false;
}
// Normal successors are equal based on equality of the instruction stream. Verify that here.
assert verifyAllSuccessors(first.getSuccessors(), second.getSuccessors());
return true;
}
private boolean verifyAllSuccessors(List<BasicBlock> successors0, List<BasicBlock> successors1) {
if (successors0.size() != successors1.size()) {
return false;
}
for (int i = 0; i < successors0.size(); i++) {
if (successors0.get(i) != successors1.get(i)) {
return false;
}
}
return true;
}
@Override
protected boolean doEquivalent(BasicBlock a, BasicBlock b) {
return hasIdenticalInstructions(a, b);
}
void clearComputedHash(BasicBlock basicBlock) {
hashes[basicBlock.getNumber()] = UNKNOW_HASH;
}
@Override
protected int doHash(BasicBlock basicBlock) {
int hash = hashes[basicBlock.getNumber()];
if (hash != UNKNOW_HASH) {
assert hash == computeHash(basicBlock);
return hash;
}
hash = computeHash(basicBlock);
hashes[basicBlock.getNumber()] = hash;
return hash;
}
private int computeHash(BasicBlock basicBlock) {
List<Instruction> instructions = basicBlock.getInstructions();
int hash = instructions.size();
for (int i = 0; i < instructions.size() && i < MAX_HASH_INSTRUCTIONS; i++) {
Instruction instruction = instructions.get(i);
int hashPart = 0;
if (instruction.outValue() != null && instruction.outValue().needsRegister()) {
hashPart += allocator.getRegisterForValue(instruction.outValue(), instruction.getNumber());
}
for (Value inValue : instruction.inValues()) {
hashPart = hashPart << 4;
if (inValue.needsRegister()) {
hashPart += allocator.getRegisterForValue(inValue, instruction.getNumber());
}
}
hash = hash * 3 + hashPart;
}
return hash;
}
}