/*
|
* Copyright (C) 2014 The Android Open Source Project
|
*
|
* Licensed under the Apache License, Version 2.0 (the "License");
|
* you may not use this file except in compliance with the License.
|
* You may obtain a copy of the License at
|
*
|
* http://www.apache.org/licenses/LICENSE-2.0
|
*
|
* Unless required by applicable law or agreed to in writing, software
|
* distributed under the License is distributed on an "AS IS" BASIS,
|
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
|
* See the License for the specific language governing permissions and
|
* limitations under the License.
|
*/
|
|
#include "constant_folding.h"
|
|
namespace art {
|
|
// This visitor tries to simplify instructions that can be evaluated
|
// as constants.
|
class HConstantFoldingVisitor : public HGraphDelegateVisitor {
|
public:
|
explicit HConstantFoldingVisitor(HGraph* graph)
|
: HGraphDelegateVisitor(graph) {}
|
|
private:
|
void VisitBasicBlock(HBasicBlock* block) override;
|
|
void VisitUnaryOperation(HUnaryOperation* inst) override;
|
void VisitBinaryOperation(HBinaryOperation* inst) override;
|
|
void VisitTypeConversion(HTypeConversion* inst) override;
|
void VisitDivZeroCheck(HDivZeroCheck* inst) override;
|
|
DISALLOW_COPY_AND_ASSIGN(HConstantFoldingVisitor);
|
};
|
|
// This visitor tries to simplify operations with an absorbing input,
|
// yielding a constant. For example `input * 0` is replaced by a
|
// null constant.
|
class InstructionWithAbsorbingInputSimplifier : public HGraphVisitor {
|
public:
|
explicit InstructionWithAbsorbingInputSimplifier(HGraph* graph) : HGraphVisitor(graph) {}
|
|
private:
|
void VisitShift(HBinaryOperation* shift);
|
|
void VisitEqual(HEqual* instruction) override;
|
void VisitNotEqual(HNotEqual* instruction) override;
|
|
void VisitAbove(HAbove* instruction) override;
|
void VisitAboveOrEqual(HAboveOrEqual* instruction) override;
|
void VisitBelow(HBelow* instruction) override;
|
void VisitBelowOrEqual(HBelowOrEqual* instruction) override;
|
|
void VisitAnd(HAnd* instruction) override;
|
void VisitCompare(HCompare* instruction) override;
|
void VisitMul(HMul* instruction) override;
|
void VisitOr(HOr* instruction) override;
|
void VisitRem(HRem* instruction) override;
|
void VisitShl(HShl* instruction) override;
|
void VisitShr(HShr* instruction) override;
|
void VisitSub(HSub* instruction) override;
|
void VisitUShr(HUShr* instruction) override;
|
void VisitXor(HXor* instruction) override;
|
};
|
|
|
bool HConstantFolding::Run() {
|
HConstantFoldingVisitor visitor(graph_);
|
// Process basic blocks in reverse post-order in the dominator tree,
|
// so that an instruction turned into a constant, used as input of
|
// another instruction, may possibly be used to turn that second
|
// instruction into a constant as well.
|
visitor.VisitReversePostOrder();
|
return true;
|
}
|
|
|
void HConstantFoldingVisitor::VisitBasicBlock(HBasicBlock* block) {
|
// Traverse this block's instructions (phis don't need to be
|
// processed) in (forward) order and replace the ones that can be
|
// statically evaluated by a compile-time counterpart.
|
for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
|
it.Current()->Accept(this);
|
}
|
}
|
|
void HConstantFoldingVisitor::VisitUnaryOperation(HUnaryOperation* inst) {
|
// Constant folding: replace `op(a)' with a constant at compile
|
// time if `a' is a constant.
|
HConstant* constant = inst->TryStaticEvaluation();
|
if (constant != nullptr) {
|
inst->ReplaceWith(constant);
|
inst->GetBlock()->RemoveInstruction(inst);
|
}
|
}
|
|
void HConstantFoldingVisitor::VisitBinaryOperation(HBinaryOperation* inst) {
|
// Constant folding: replace `op(a, b)' with a constant at
|
// compile time if `a' and `b' are both constants.
|
HConstant* constant = inst->TryStaticEvaluation();
|
if (constant != nullptr) {
|
inst->ReplaceWith(constant);
|
inst->GetBlock()->RemoveInstruction(inst);
|
} else {
|
InstructionWithAbsorbingInputSimplifier simplifier(GetGraph());
|
inst->Accept(&simplifier);
|
}
|
}
|
|
void HConstantFoldingVisitor::VisitTypeConversion(HTypeConversion* inst) {
|
// Constant folding: replace `TypeConversion(a)' with a constant at
|
// compile time if `a' is a constant.
|
HConstant* constant = inst->TryStaticEvaluation();
|
if (constant != nullptr) {
|
inst->ReplaceWith(constant);
|
inst->GetBlock()->RemoveInstruction(inst);
|
}
|
}
|
|
void HConstantFoldingVisitor::VisitDivZeroCheck(HDivZeroCheck* inst) {
|
// We can safely remove the check if the input is a non-null constant.
|
HInstruction* check_input = inst->InputAt(0);
|
if (check_input->IsConstant() && !check_input->AsConstant()->IsArithmeticZero()) {
|
inst->ReplaceWith(check_input);
|
inst->GetBlock()->RemoveInstruction(inst);
|
}
|
}
|
|
|
void InstructionWithAbsorbingInputSimplifier::VisitShift(HBinaryOperation* instruction) {
|
DCHECK(instruction->IsShl() || instruction->IsShr() || instruction->IsUShr());
|
HInstruction* left = instruction->GetLeft();
|
if (left->IsConstant() && left->AsConstant()->IsArithmeticZero()) {
|
// Replace code looking like
|
// SHL dst, 0, shift_amount
|
// with
|
// CONSTANT 0
|
instruction->ReplaceWith(left);
|
instruction->GetBlock()->RemoveInstruction(instruction);
|
}
|
}
|
|
void InstructionWithAbsorbingInputSimplifier::VisitEqual(HEqual* instruction) {
|
if ((instruction->GetLeft()->IsNullConstant() && !instruction->GetRight()->CanBeNull()) ||
|
(instruction->GetRight()->IsNullConstant() && !instruction->GetLeft()->CanBeNull())) {
|
// Replace code looking like
|
// EQUAL lhs, null
|
// where lhs cannot be null with
|
// CONSTANT false
|
instruction->ReplaceWith(GetGraph()->GetConstant(DataType::Type::kBool, 0));
|
instruction->GetBlock()->RemoveInstruction(instruction);
|
}
|
}
|
|
void InstructionWithAbsorbingInputSimplifier::VisitNotEqual(HNotEqual* instruction) {
|
if ((instruction->GetLeft()->IsNullConstant() && !instruction->GetRight()->CanBeNull()) ||
|
(instruction->GetRight()->IsNullConstant() && !instruction->GetLeft()->CanBeNull())) {
|
// Replace code looking like
|
// NOT_EQUAL lhs, null
|
// where lhs cannot be null with
|
// CONSTANT true
|
instruction->ReplaceWith(GetGraph()->GetConstant(DataType::Type::kBool, 1));
|
instruction->GetBlock()->RemoveInstruction(instruction);
|
}
|
}
|
|
void InstructionWithAbsorbingInputSimplifier::VisitAbove(HAbove* instruction) {
|
if (instruction->GetLeft()->IsConstant() &&
|
instruction->GetLeft()->AsConstant()->IsArithmeticZero()) {
|
// Replace code looking like
|
// ABOVE dst, 0, src // unsigned 0 > src is always false
|
// with
|
// CONSTANT false
|
instruction->ReplaceWith(GetGraph()->GetConstant(DataType::Type::kBool, 0));
|
instruction->GetBlock()->RemoveInstruction(instruction);
|
}
|
}
|
|
void InstructionWithAbsorbingInputSimplifier::VisitAboveOrEqual(HAboveOrEqual* instruction) {
|
if (instruction->GetRight()->IsConstant() &&
|
instruction->GetRight()->AsConstant()->IsArithmeticZero()) {
|
// Replace code looking like
|
// ABOVE_OR_EQUAL dst, src, 0 // unsigned src >= 0 is always true
|
// with
|
// CONSTANT true
|
instruction->ReplaceWith(GetGraph()->GetConstant(DataType::Type::kBool, 1));
|
instruction->GetBlock()->RemoveInstruction(instruction);
|
}
|
}
|
|
void InstructionWithAbsorbingInputSimplifier::VisitBelow(HBelow* instruction) {
|
if (instruction->GetRight()->IsConstant() &&
|
instruction->GetRight()->AsConstant()->IsArithmeticZero()) {
|
// Replace code looking like
|
// BELOW dst, src, 0 // unsigned src < 0 is always false
|
// with
|
// CONSTANT false
|
instruction->ReplaceWith(GetGraph()->GetConstant(DataType::Type::kBool, 0));
|
instruction->GetBlock()->RemoveInstruction(instruction);
|
}
|
}
|
|
void InstructionWithAbsorbingInputSimplifier::VisitBelowOrEqual(HBelowOrEqual* instruction) {
|
if (instruction->GetLeft()->IsConstant() &&
|
instruction->GetLeft()->AsConstant()->IsArithmeticZero()) {
|
// Replace code looking like
|
// BELOW_OR_EQUAL dst, 0, src // unsigned 0 <= src is always true
|
// with
|
// CONSTANT true
|
instruction->ReplaceWith(GetGraph()->GetConstant(DataType::Type::kBool, 1));
|
instruction->GetBlock()->RemoveInstruction(instruction);
|
}
|
}
|
|
void InstructionWithAbsorbingInputSimplifier::VisitAnd(HAnd* instruction) {
|
HConstant* input_cst = instruction->GetConstantRight();
|
if ((input_cst != nullptr) && input_cst->IsZeroBitPattern()) {
|
// Replace code looking like
|
// AND dst, src, 0
|
// with
|
// CONSTANT 0
|
instruction->ReplaceWith(input_cst);
|
instruction->GetBlock()->RemoveInstruction(instruction);
|
}
|
}
|
|
void InstructionWithAbsorbingInputSimplifier::VisitCompare(HCompare* instruction) {
|
HConstant* input_cst = instruction->GetConstantRight();
|
if (input_cst != nullptr) {
|
HInstruction* input_value = instruction->GetLeastConstantLeft();
|
if (DataType::IsFloatingPointType(input_value->GetType()) &&
|
((input_cst->IsFloatConstant() && input_cst->AsFloatConstant()->IsNaN()) ||
|
(input_cst->IsDoubleConstant() && input_cst->AsDoubleConstant()->IsNaN()))) {
|
// Replace code looking like
|
// CMP{G,L}-{FLOAT,DOUBLE} dst, src, NaN
|
// with
|
// CONSTANT +1 (gt bias)
|
// or
|
// CONSTANT -1 (lt bias)
|
instruction->ReplaceWith(GetGraph()->GetConstant(DataType::Type::kInt32,
|
(instruction->IsGtBias() ? 1 : -1)));
|
instruction->GetBlock()->RemoveInstruction(instruction);
|
}
|
}
|
}
|
|
void InstructionWithAbsorbingInputSimplifier::VisitMul(HMul* instruction) {
|
HConstant* input_cst = instruction->GetConstantRight();
|
DataType::Type type = instruction->GetType();
|
if (DataType::IsIntOrLongType(type) &&
|
(input_cst != nullptr) && input_cst->IsArithmeticZero()) {
|
// Replace code looking like
|
// MUL dst, src, 0
|
// with
|
// CONSTANT 0
|
// Integral multiplication by zero always yields zero, but floating-point
|
// multiplication by zero does not always do. For example `Infinity * 0.0`
|
// should yield a NaN.
|
instruction->ReplaceWith(input_cst);
|
instruction->GetBlock()->RemoveInstruction(instruction);
|
}
|
}
|
|
void InstructionWithAbsorbingInputSimplifier::VisitOr(HOr* instruction) {
|
HConstant* input_cst = instruction->GetConstantRight();
|
|
if (input_cst == nullptr) {
|
return;
|
}
|
|
if (Int64FromConstant(input_cst) == -1) {
|
// Replace code looking like
|
// OR dst, src, 0xFFF...FF
|
// with
|
// CONSTANT 0xFFF...FF
|
instruction->ReplaceWith(input_cst);
|
instruction->GetBlock()->RemoveInstruction(instruction);
|
}
|
}
|
|
void InstructionWithAbsorbingInputSimplifier::VisitRem(HRem* instruction) {
|
DataType::Type type = instruction->GetType();
|
|
if (!DataType::IsIntegralType(type)) {
|
return;
|
}
|
|
HBasicBlock* block = instruction->GetBlock();
|
|
if (instruction->GetLeft()->IsConstant() &&
|
instruction->GetLeft()->AsConstant()->IsArithmeticZero()) {
|
// Replace code looking like
|
// REM dst, 0, src
|
// with
|
// CONSTANT 0
|
instruction->ReplaceWith(instruction->GetLeft());
|
block->RemoveInstruction(instruction);
|
}
|
|
HConstant* cst_right = instruction->GetRight()->AsConstant();
|
if (((cst_right != nullptr) &&
|
(cst_right->IsOne() || cst_right->IsMinusOne())) ||
|
(instruction->GetLeft() == instruction->GetRight())) {
|
// Replace code looking like
|
// REM dst, src, 1
|
// or
|
// REM dst, src, -1
|
// or
|
// REM dst, src, src
|
// with
|
// CONSTANT 0
|
instruction->ReplaceWith(GetGraph()->GetConstant(type, 0));
|
block->RemoveInstruction(instruction);
|
}
|
}
|
|
void InstructionWithAbsorbingInputSimplifier::VisitShl(HShl* instruction) {
|
VisitShift(instruction);
|
}
|
|
void InstructionWithAbsorbingInputSimplifier::VisitShr(HShr* instruction) {
|
VisitShift(instruction);
|
}
|
|
void InstructionWithAbsorbingInputSimplifier::VisitSub(HSub* instruction) {
|
DataType::Type type = instruction->GetType();
|
|
if (!DataType::IsIntegralType(type)) {
|
return;
|
}
|
|
HBasicBlock* block = instruction->GetBlock();
|
|
// We assume that GVN has run before, so we only perform a pointer
|
// comparison. If for some reason the values are equal but the pointers are
|
// different, we are still correct and only miss an optimization
|
// opportunity.
|
if (instruction->GetLeft() == instruction->GetRight()) {
|
// Replace code looking like
|
// SUB dst, src, src
|
// with
|
// CONSTANT 0
|
// Note that we cannot optimize `x - x` to `0` for floating-point. It does
|
// not work when `x` is an infinity.
|
instruction->ReplaceWith(GetGraph()->GetConstant(type, 0));
|
block->RemoveInstruction(instruction);
|
}
|
}
|
|
void InstructionWithAbsorbingInputSimplifier::VisitUShr(HUShr* instruction) {
|
VisitShift(instruction);
|
}
|
|
void InstructionWithAbsorbingInputSimplifier::VisitXor(HXor* instruction) {
|
if (instruction->GetLeft() == instruction->GetRight()) {
|
// Replace code looking like
|
// XOR dst, src, src
|
// with
|
// CONSTANT 0
|
DataType::Type type = instruction->GetType();
|
HBasicBlock* block = instruction->GetBlock();
|
instruction->ReplaceWith(GetGraph()->GetConstant(type, 0));
|
block->RemoveInstruction(instruction);
|
}
|
}
|
|
} // namespace art
|
