Opt compiler: Basic simplification for arithmetic operations.
The optimisations in this patch do not look further than the
inputs of each operation.
Change-Id: Iddd0ab6b360b9e7bb042db22086d51a31be85530
diff --git a/compiler/optimizing/constant_folding.cc b/compiler/optimizing/constant_folding.cc
index fca9933..ec0cc3e 100644
--- a/compiler/optimizing/constant_folding.cc
+++ b/compiler/optimizing/constant_folding.cc
@@ -18,7 +18,28 @@
namespace art {
+// This visitor tries to simplify operations that yield 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 VisitAnd(HAnd* 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;
+};
+
void HConstantFolding::Run() {
+ InstructionWithAbsorbingInputSimplifier simplifier(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
@@ -38,6 +59,8 @@
inst->AsBinaryOperation()->TryStaticEvaluation();
if (constant != nullptr) {
inst->GetBlock()->ReplaceAndRemoveInstructionWith(inst, constant);
+ } else {
+ inst->Accept(&simplifier);
}
} else if (inst->IsUnaryOperation()) {
// Constant folding: replace `op(a)' with a constant at compile
@@ -47,9 +70,166 @@
if (constant != nullptr) {
inst->GetBlock()->ReplaceAndRemoveInstructionWith(inst, constant);
}
+ } else if (inst->IsDivZeroCheck()) {
+ // We can safely remove the check if the input is a non-null constant.
+ HDivZeroCheck* check = inst->AsDivZeroCheck();
+ HInstruction* check_input = check->InputAt(0);
+ if (check_input->IsConstant() && !check_input->AsConstant()->IsZero()) {
+ check->ReplaceWith(check_input);
+ check->GetBlock()->RemoveInstruction(check);
+ }
}
}
}
}
+void InstructionWithAbsorbingInputSimplifier::VisitShift(HBinaryOperation* instruction) {
+ DCHECK(instruction->IsShl() || instruction->IsShr() || instruction->IsUShr());
+ HInstruction* left = instruction->GetLeft();
+ if (left->IsConstant() && left->AsConstant()->IsZero()) {
+ // Replace code looking like
+ // SHL dst, 0, shift_amount
+ // with
+ // CONSTANT 0
+ instruction->ReplaceWith(left);
+ instruction->GetBlock()->RemoveInstruction(instruction);
+ }
+}
+
+void InstructionWithAbsorbingInputSimplifier::VisitAnd(HAnd* instruction) {
+ HConstant* input_cst = instruction->GetConstantRight();
+ if ((input_cst != nullptr) && input_cst->IsZero()) {
+ // Replace code looking like
+ // AND dst, src, 0
+ // with
+ // CONSTANT 0
+ instruction->ReplaceWith(input_cst);
+ instruction->GetBlock()->RemoveInstruction(instruction);
+ }
+}
+
+void InstructionWithAbsorbingInputSimplifier::VisitMul(HMul* instruction) {
+ HConstant* input_cst = instruction->GetConstantRight();
+ Primitive::Type type = instruction->GetType();
+ if (Primitive::IsIntOrLongType(type) &&
+ (input_cst != nullptr) && input_cst->IsZero()) {
+ // 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) {
+ Primitive::Type type = instruction->GetType();
+
+ if (!Primitive::IsIntegralType(type)) {
+ return;
+ }
+
+ HBasicBlock* block = instruction->GetBlock();
+
+ if (instruction->GetLeft()->IsConstant() &&
+ instruction->GetLeft()->AsConstant()->IsZero()) {
+ // 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
+ ArenaAllocator* allocator = GetGraph()->GetArena();
+ block->ReplaceAndRemoveInstructionWith(instruction,
+ HConstant::NewConstant(allocator, type, 0));
+ }
+}
+
+void InstructionWithAbsorbingInputSimplifier::VisitShl(HShl* instruction) {
+ VisitShift(instruction);
+}
+
+void InstructionWithAbsorbingInputSimplifier::VisitShr(HShr* instruction) {
+ VisitShift(instruction);
+}
+
+void InstructionWithAbsorbingInputSimplifier::VisitSub(HSub* instruction) {
+ Primitive::Type type = instruction->GetType();
+
+ if (!Primitive::IsIntegralType(type)) {
+ return;
+ }
+
+ HBasicBlock* block = instruction->GetBlock();
+ ArenaAllocator* allocator = GetGraph()->GetArena();
+
+ // 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 optimisation
+ // opportunity.
+ if (instruction->GetLeft() == instruction->GetRight()) {
+ // Replace code looking like
+ // SUB dst, src, src
+ // with
+ // CONSTANT 0
+ // Note that we cannot optimise `x - x` to `0` for floating-point. It does
+ // not work when `x` is an infinity.
+ block->ReplaceAndRemoveInstructionWith(instruction,
+ HConstant::NewConstant(allocator, type, 0));
+ }
+}
+
+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
+ Primitive::Type type = instruction->GetType();
+ HBasicBlock* block = instruction->GetBlock();
+ ArenaAllocator* allocator = GetGraph()->GetArena();
+
+ block->ReplaceAndRemoveInstructionWith(instruction,
+ HConstant::NewConstant(allocator, type, 0));
+ }
+}
+
} // namespace art