Opt compiler: Instruction simplification for HAdd, HNeg, HNot, HSub.
Under assumptions for the 'cost' of each IR (eg. neither HAdd nor HSub
are faster than the other), transformations are only applied if they
(locally) cannot degrade the quality of the graph. The code could be
extended to look at uses of the IRs and detect more opportunities for
optimisations. The optimisations in this patch do not look at other
uses for their inputs.
Change-Id: Ib60dab007af30f43421ef5bb55db2ec32fb8fc0c
diff --git a/compiler/optimizing/instruction_simplifier.cc b/compiler/optimizing/instruction_simplifier.cc
index 56ec8a7..afbc490 100644
--- a/compiler/optimizing/instruction_simplifier.cc
+++ b/compiler/optimizing/instruction_simplifier.cc
@@ -24,9 +24,21 @@
class InstructionSimplifierVisitor : public HGraphVisitor {
public:
InstructionSimplifierVisitor(HGraph* graph, OptimizingCompilerStats* stats)
- : HGraphVisitor(graph), stats_(stats) {}
+ : HGraphVisitor(graph),
+ stats_(stats) {}
+
+ void Run();
private:
+ void RecordSimplification() {
+ simplification_occurred_ = true;
+ simplifications_at_current_position_++;
+ if (stats_) {
+ stats_->RecordStat(kInstructionSimplifications);
+ }
+ }
+
+ bool TryMoveNegOnInputsAfterBinop(HBinaryOperation* binop);
void VisitShift(HBinaryOperation* shift);
void VisitSuspendCheck(HSuspendCheck* check) OVERRIDE;
@@ -40,6 +52,8 @@
void VisitAnd(HAnd* instruction) OVERRIDE;
void VisitDiv(HDiv* instruction) OVERRIDE;
void VisitMul(HMul* instruction) OVERRIDE;
+ void VisitNeg(HNeg* instruction) OVERRIDE;
+ void VisitNot(HNot* instruction) OVERRIDE;
void VisitOr(HOr* instruction) OVERRIDE;
void VisitShl(HShl* instruction) OVERRIDE;
void VisitShr(HShr* instruction) OVERRIDE;
@@ -48,11 +62,38 @@
void VisitXor(HXor* instruction) OVERRIDE;
OptimizingCompilerStats* stats_;
+ bool simplification_occurred_ = false;
+ int simplifications_at_current_position_ = 0;
+ // We ensure we do not loop infinitely. The value is a finger in the air guess
+ // that should allow enough simplification.
+ static constexpr int kMaxSamePositionSimplifications = 10;
};
void InstructionSimplifier::Run() {
InstructionSimplifierVisitor visitor(graph_, stats_);
- visitor.VisitInsertionOrder();
+ visitor.Run();
+}
+
+void InstructionSimplifierVisitor::Run() {
+ for (HReversePostOrderIterator it(*GetGraph()); !it.Done();) {
+ // The simplification of an instruction to another instruction may yield
+ // possibilities for other simplifications. So although we perform a reverse
+ // post order visit, we sometimes need to revisit an instruction index.
+ simplification_occurred_ = false;
+ VisitBasicBlock(it.Current());
+ if (simplification_occurred_ &&
+ (simplifications_at_current_position_ < kMaxSamePositionSimplifications)) {
+ // New simplifications may be applicable to the instruction at the
+ // current index, so don't advance the iterator.
+ continue;
+ }
+ if (simplifications_at_current_position_ >= kMaxSamePositionSimplifications) {
+ LOG(WARNING) << "Too many simplifications (" << simplifications_at_current_position_
+ << ") occurred at the current position.";
+ }
+ simplifications_at_current_position_ = 0;
+ it.Advance();
+ }
}
namespace {
@@ -63,6 +104,35 @@
} // namespace
+// Returns true if the code was simplified to use only one negation operation
+// after the binary operation instead of one on each of the inputs.
+bool InstructionSimplifierVisitor::TryMoveNegOnInputsAfterBinop(HBinaryOperation* binop) {
+ DCHECK(binop->IsAdd() || binop->IsSub());
+ DCHECK(binop->GetLeft()->IsNeg() && binop->GetRight()->IsNeg());
+ HNeg* left_neg = binop->GetLeft()->AsNeg();
+ HNeg* right_neg = binop->GetRight()->AsNeg();
+ if (!left_neg->HasOnlyOneNonEnvironmentUse() ||
+ !right_neg->HasOnlyOneNonEnvironmentUse()) {
+ return false;
+ }
+ // Replace code looking like
+ // NEG tmp1, a
+ // NEG tmp2, b
+ // ADD dst, tmp1, tmp2
+ // with
+ // ADD tmp, a, b
+ // NEG dst, tmp
+ binop->ReplaceInput(left_neg->GetInput(), 0);
+ binop->ReplaceInput(right_neg->GetInput(), 1);
+ left_neg->GetBlock()->RemoveInstruction(left_neg);
+ right_neg->GetBlock()->RemoveInstruction(right_neg);
+ HNeg* neg = new (GetGraph()->GetArena()) HNeg(binop->GetType(), binop);
+ binop->GetBlock()->InsertInstructionBefore(neg, binop->GetNext());
+ binop->ReplaceWithExceptInReplacementAtIndex(neg, 0);
+ RecordSimplification();
+ return true;
+}
+
void InstructionSimplifierVisitor::VisitShift(HBinaryOperation* instruction) {
DCHECK(instruction->IsShl() || instruction->IsShr() || instruction->IsUShr());
HConstant* input_cst = instruction->GetConstantRight();
@@ -182,6 +252,36 @@
// src
instruction->ReplaceWith(input_other);
instruction->GetBlock()->RemoveInstruction(instruction);
+ return;
+ }
+
+ HInstruction* left = instruction->GetLeft();
+ HInstruction* right = instruction->GetRight();
+ bool left_is_neg = left->IsNeg();
+ bool right_is_neg = right->IsNeg();
+
+ if (left_is_neg && right_is_neg) {
+ if (TryMoveNegOnInputsAfterBinop(instruction)) {
+ return;
+ }
+ }
+
+ HNeg* neg = left_is_neg ? left->AsNeg() : right->AsNeg();
+ if ((left_is_neg ^ right_is_neg) && neg->HasOnlyOneNonEnvironmentUse()) {
+ // Replace code looking like
+ // NEG tmp, b
+ // ADD dst, a, tmp
+ // with
+ // SUB dst, a, b
+ // We do not perform the optimization if the input negation has environment
+ // uses or multiple non-environment uses as it could lead to worse code. In
+ // particular, we do not want the live range of `b` to be extended if we are
+ // not sure the initial 'NEG' instruction can be removed.
+ HInstruction* other = left_is_neg ? right : left;
+ HSub* sub = new(GetGraph()->GetArena()) HSub(instruction->GetType(), other, neg->GetInput());
+ instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, sub);
+ RecordSimplification();
+ neg->GetBlock()->RemoveInstruction(neg);
}
}
@@ -201,7 +301,7 @@
// 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.
+ // are still correct and only miss an optimization opportunity.
if (instruction->GetLeft() == instruction->GetRight()) {
// Replace code looking like
// AND dst, src, src
@@ -235,6 +335,7 @@
// NEG dst, src
instruction->GetBlock()->ReplaceAndRemoveInstructionWith(
instruction, (new (GetGraph()->GetArena()) HNeg(type, input_other)));
+ RecordSimplification();
}
}
@@ -267,6 +368,7 @@
// NEG dst, src
HNeg* neg = new (allocator) HNeg(type, input_other);
block->ReplaceAndRemoveInstructionWith(instruction, neg);
+ RecordSimplification();
return;
}
@@ -280,6 +382,7 @@
// The 'int' and 'long' cases are handled below.
block->ReplaceAndRemoveInstructionWith(instruction,
new (allocator) HAdd(type, input_other, input_other));
+ RecordSimplification();
return;
}
@@ -295,10 +398,75 @@
HIntConstant* shift = GetGraph()->GetIntConstant(WhichPowerOf2(factor));
HShl* shl = new(allocator) HShl(type, input_other, shift);
block->ReplaceAndRemoveInstructionWith(instruction, shl);
+ RecordSimplification();
}
}
}
+void InstructionSimplifierVisitor::VisitNeg(HNeg* instruction) {
+ HInstruction* input = instruction->GetInput();
+ if (input->IsNeg()) {
+ // Replace code looking like
+ // NEG tmp, src
+ // NEG dst, tmp
+ // with
+ // src
+ HNeg* previous_neg = input->AsNeg();
+ instruction->ReplaceWith(previous_neg->GetInput());
+ instruction->GetBlock()->RemoveInstruction(instruction);
+ // We perform the optimization even if the input negation has environment
+ // uses since it allows removing the current instruction. But we only delete
+ // the input negation only if it is does not have any uses left.
+ if (!previous_neg->HasUses()) {
+ previous_neg->GetBlock()->RemoveInstruction(previous_neg);
+ }
+ RecordSimplification();
+ return;
+ }
+
+ if (input->IsSub() && input->HasOnlyOneNonEnvironmentUse()) {
+ // Replace code looking like
+ // SUB tmp, a, b
+ // NEG dst, tmp
+ // with
+ // SUB dst, b, a
+ // We do not perform the optimization if the input subtraction has
+ // environment uses or multiple non-environment uses as it could lead to
+ // worse code. In particular, we do not want the live ranges of `a` and `b`
+ // to be extended if we are not sure the initial 'SUB' instruction can be
+ // removed.
+ HSub* sub = input->AsSub();
+ HSub* new_sub =
+ new (GetGraph()->GetArena()) HSub(instruction->GetType(), sub->GetRight(), sub->GetLeft());
+ instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, new_sub);
+ if (!sub->HasUses()) {
+ sub->GetBlock()->RemoveInstruction(sub);
+ }
+ RecordSimplification();
+ }
+}
+
+void InstructionSimplifierVisitor::VisitNot(HNot* instruction) {
+ HInstruction* input = instruction->GetInput();
+ if (input->IsNot()) {
+ // Replace code looking like
+ // NOT tmp, src
+ // NOT dst, tmp
+ // with
+ // src
+ // We perform the optimization even if the input negation has environment
+ // uses since it allows removing the current instruction. But we only delete
+ // the input negation only if it is does not have any uses left.
+ HNot* previous_not = input->AsNot();
+ instruction->ReplaceWith(previous_not->GetInput());
+ instruction->GetBlock()->RemoveInstruction(instruction);
+ if (!previous_not->HasUses()) {
+ previous_not->GetBlock()->RemoveInstruction(previous_not);
+ }
+ RecordSimplification();
+ }
+}
+
void InstructionSimplifierVisitor::VisitOr(HOr* instruction) {
HConstant* input_cst = instruction->GetConstantRight();
HInstruction* input_other = instruction->GetLeastConstantLeft();
@@ -315,7 +483,7 @@
// 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.
+ // are still correct and only miss an optimization opportunity.
if (instruction->GetLeft() == instruction->GetRight()) {
// Replace code looking like
// OR dst, src, src
@@ -356,20 +524,61 @@
HBasicBlock* block = instruction->GetBlock();
ArenaAllocator* allocator = GetGraph()->GetArena();
- if (instruction->GetLeft()->IsConstant()) {
- int64_t left = Int64FromConstant(instruction->GetLeft()->AsConstant());
- if (left == 0) {
+ HInstruction* left = instruction->GetLeft();
+ HInstruction* right = instruction->GetRight();
+ if (left->IsConstant()) {
+ if (Int64FromConstant(left->AsConstant()) == 0) {
// Replace code looking like
// SUB dst, 0, src
// with
// NEG dst, src
- // Note that we cannot optimise `0.0 - x` to `-x` for floating-point. When
+ // Note that we cannot optimize `0.0 - x` to `-x` for floating-point. When
// `x` is `0.0`, the former expression yields `0.0`, while the later
// yields `-0.0`.
- HNeg* neg = new (allocator) HNeg(type, instruction->GetRight());
+ HNeg* neg = new (allocator) HNeg(type, right);
block->ReplaceAndRemoveInstructionWith(instruction, neg);
+ RecordSimplification();
+ return;
}
}
+
+ if (left->IsNeg() && right->IsNeg()) {
+ if (TryMoveNegOnInputsAfterBinop(instruction)) {
+ return;
+ }
+ }
+
+ if (right->IsNeg() && right->HasOnlyOneNonEnvironmentUse()) {
+ // Replace code looking like
+ // NEG tmp, b
+ // SUB dst, a, tmp
+ // with
+ // ADD dst, a, b
+ HAdd* add = new(GetGraph()->GetArena()) HAdd(type, left, right->AsNeg()->GetInput());
+ instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, add);
+ RecordSimplification();
+ right->GetBlock()->RemoveInstruction(right);
+ return;
+ }
+
+ if (left->IsNeg() && left->HasOnlyOneNonEnvironmentUse()) {
+ // Replace code looking like
+ // NEG tmp, a
+ // SUB dst, tmp, b
+ // with
+ // ADD tmp, a, b
+ // NEG dst, tmp
+ // The second version is not intrinsically better, but enables more
+ // transformations.
+ HAdd* add = new(GetGraph()->GetArena()) HAdd(type, left->AsNeg()->GetInput(), right);
+ instruction->GetBlock()->InsertInstructionBefore(add, instruction);
+ HNeg* neg = new (GetGraph()->GetArena()) HNeg(instruction->GetType(), add);
+ instruction->GetBlock()->InsertInstructionBefore(neg, instruction);
+ instruction->ReplaceWith(neg);
+ instruction->GetBlock()->RemoveInstruction(instruction);
+ RecordSimplification();
+ left->GetBlock()->RemoveInstruction(left);
+ }
}
void InstructionSimplifierVisitor::VisitUShr(HUShr* instruction) {
@@ -397,6 +606,7 @@
// NOT dst, src
HNot* bitwise_not = new (GetGraph()->GetArena()) HNot(instruction->GetType(), input_other);
instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, bitwise_not);
+ RecordSimplification();
return;
}
}
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index f764eb4..5f50494 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -1177,6 +1177,9 @@
bool HasUses() const { return !uses_.IsEmpty() || !env_uses_.IsEmpty(); }
bool HasEnvironmentUses() const { return !env_uses_.IsEmpty(); }
bool HasNonEnvironmentUses() const { return !uses_.IsEmpty(); }
+ bool HasOnlyOneNonEnvironmentUse() const {
+ return !HasEnvironmentUses() && GetUses().HasOnlyOneUse();
+ }
// Does this instruction strictly dominate `other_instruction`?
// Returns false if this instruction and `other_instruction` are the same.
@@ -1214,6 +1217,13 @@
void ReplaceWith(HInstruction* instruction);
void ReplaceInput(HInstruction* replacement, size_t index);
+ // This is almost the same as doing `ReplaceWith()`. But in this helper, the
+ // uses of this instruction by `other` are *not* updated.
+ void ReplaceWithExceptInReplacementAtIndex(HInstruction* other, size_t use_index) {
+ ReplaceWith(other);
+ other->ReplaceInput(this, use_index);
+ }
+
// Move `this` instruction before `cursor`.
void MoveBefore(HInstruction* cursor);
diff --git a/compiler/optimizing/optimizing_compiler_stats.h b/compiler/optimizing/optimizing_compiler_stats.h
index b97a667..4d5b8d0 100644
--- a/compiler/optimizing/optimizing_compiler_stats.h
+++ b/compiler/optimizing/optimizing_compiler_stats.h
@@ -47,6 +47,7 @@
kNotCompiledUnhandledInstruction,
kRemovedCheckedCast,
kRemovedNullCheck,
+ kInstructionSimplifications,
kLastStat
};
@@ -110,6 +111,7 @@
case kNotCompiledUnhandledInstruction : return "kNotCompiledUnhandledInstruction";
case kRemovedCheckedCast: return "kRemovedCheckedCast";
case kRemovedNullCheck: return "kRemovedNullCheck";
+ case kInstructionSimplifications: return "kInstructionSimplifications";
default: LOG(FATAL) << "invalid stat";
}
return "";
diff --git a/test/458-checker-instruction-simplification/src/Main.java b/test/458-checker-instruction-simplification/src/Main.java
index 1f0017e..3cbcebb 100644
--- a/test/458-checker-instruction-simplification/src/Main.java
+++ b/test/458-checker-instruction-simplification/src/Main.java
@@ -309,6 +309,457 @@
return arg ^ -1;
}
+ /**
+ * Test that addition or subtraction operation with both inputs negated are
+ * optimized to use a single negation after the operation.
+ * The transformation tested is implemented in
+ * `InstructionSimplifierVisitor::TryMoveNegOnInputsAfterBinop`.
+ */
+
+ // CHECK-START: int Main.AddNegs1(int, int) instruction_simplifier (before)
+ // CHECK-DAG: [[Arg1:i\d+]] ParameterValue
+ // CHECK-DAG: [[Arg2:i\d+]] ParameterValue
+ // CHECK-DAG: [[Neg1:i\d+]] Neg [ [[Arg1]] ]
+ // CHECK-DAG: [[Neg2:i\d+]] Neg [ [[Arg2]] ]
+ // CHECK-DAG: [[Add:i\d+]] Add [ [[Neg1]] [[Neg2]] ]
+ // CHECK-DAG: Return [ [[Add]] ]
+
+ // CHECK-START: int Main.AddNegs1(int, int) instruction_simplifier (after)
+ // CHECK-DAG: [[Arg1:i\d+]] ParameterValue
+ // CHECK-DAG: [[Arg2:i\d+]] ParameterValue
+ // CHECK-NOT: Neg
+ // CHECK-DAG: [[Add:i\d+]] Add [ [[Arg1]] [[Arg2]] ]
+ // CHECK-DAG: [[Neg:i\d+]] Neg [ [[Add]] ]
+ // CHECK-DAG: Return [ [[Neg]] ]
+
+ public static int AddNegs1(int arg1, int arg2) {
+ return -arg1 + -arg2;
+ }
+
+ /**
+ * This is similar to the test-case AddNegs1, but the negations have
+ * multiple uses.
+ * The transformation tested is implemented in
+ * `InstructionSimplifierVisitor::TryMoveNegOnInputsAfterBinop`.
+ * The current code won't perform the previous optimization. The
+ * transformations do not look at other uses of their inputs. As they don't
+ * know what will happen with other uses, they do not take the risk of
+ * increasing the register pressure by creating or extending live ranges.
+ */
+
+ // CHECK-START: int Main.AddNegs2(int, int) instruction_simplifier (before)
+ // CHECK-DAG: [[Arg1:i\d+]] ParameterValue
+ // CHECK-DAG: [[Arg2:i\d+]] ParameterValue
+ // CHECK-DAG: [[Neg1:i\d+]] Neg [ [[Arg1]] ]
+ // CHECK-DAG: [[Neg2:i\d+]] Neg [ [[Arg2]] ]
+ // CHECK-DAG: [[Add1:i\d+]] Add [ [[Neg1]] [[Neg2]] ]
+ // CHECK-DAG: [[Add2:i\d+]] Add [ [[Neg1]] [[Neg2]] ]
+ // CHECK-DAG: [[Or:i\d+]] Or [ [[Add1]] [[Add2]] ]
+ // CHECK-DAG: Return [ [[Or]] ]
+
+ // CHECK-START: int Main.AddNegs2(int, int) instruction_simplifier (after)
+ // CHECK-DAG: [[Arg1:i\d+]] ParameterValue
+ // CHECK-DAG: [[Arg2:i\d+]] ParameterValue
+ // CHECK-DAG: [[Neg1:i\d+]] Neg [ [[Arg1]] ]
+ // CHECK-DAG: [[Neg2:i\d+]] Neg [ [[Arg2]] ]
+ // CHECK-DAG: [[Add1:i\d+]] Add [ [[Neg1]] [[Neg2]] ]
+ // CHECK-DAG: [[Add2:i\d+]] Add [ [[Neg1]] [[Neg2]] ]
+ // CHECK-NOT: Neg
+ // CHECK-DAG: [[Or:i\d+]] Or [ [[Add1]] [[Add2]] ]
+ // CHECK-DAG: Return [ [[Or]] ]
+
+ public static int AddNegs2(int arg1, int arg2) {
+ int temp1 = -arg1;
+ int temp2 = -arg2;
+ return (temp1 + temp2) | (temp1 + temp2);
+ }
+
+ /**
+ * This follows test-cases AddNegs1 and AddNegs2.
+ * The transformation tested is implemented in
+ * `InstructionSimplifierVisitor::TryMoveNegOnInputsAfterBinop`.
+ * The optimization should not happen if it moves an additional instruction in
+ * the loop.
+ */
+
+ // CHECK-START: long Main.AddNegs3(long, long) instruction_simplifier (before)
+ // -------------- Arguments and initial negation operations.
+ // CHECK-DAG: [[Arg1:j\d+]] ParameterValue
+ // CHECK-DAG: [[Arg2:j\d+]] ParameterValue
+ // CHECK-DAG: [[Neg1:j\d+]] Neg [ [[Arg1]] ]
+ // CHECK-DAG: [[Neg2:j\d+]] Neg [ [[Arg2]] ]
+ // CHECK: Goto
+ // -------------- Loop
+ // CHECK: SuspendCheck
+ // CHECK: [[Add:j\d+]] Add [ [[Neg1]] [[Neg2]] ]
+ // CHECK: Goto
+
+ // CHECK-START: long Main.AddNegs3(long, long) instruction_simplifier (after)
+ // -------------- Arguments and initial negation operations.
+ // CHECK-DAG: [[Arg1:j\d+]] ParameterValue
+ // CHECK-DAG: [[Arg2:j\d+]] ParameterValue
+ // CHECK-DAG: [[Neg1:j\d+]] Neg [ [[Arg1]] ]
+ // CHECK-DAG: [[Neg2:j\d+]] Neg [ [[Arg2]] ]
+ // CHECK: Goto
+ // -------------- Loop
+ // CHECK: SuspendCheck
+ // CHECK: [[Add:j\d+]] Add [ [[Neg1]] [[Neg2]] ]
+ // CHECK-NOT: Neg
+ // CHECK: Goto
+
+ public static long AddNegs3(long arg1, long arg2) {
+ long res = 0;
+ long n_arg1 = -arg1;
+ long n_arg2 = -arg2;
+ for (long i = 0; i < 1; i++) {
+ res += n_arg1 + n_arg2 + i;
+ }
+ return res;
+ }
+
+ /**
+ * Test the simplification of an addition with a negated argument into a
+ * subtraction.
+ * The transformation tested is implemented in `InstructionSimplifierVisitor::VisitAdd`.
+ */
+
+ // CHECK-START: long Main.AddNeg1(long, long) instruction_simplifier (before)
+ // CHECK-DAG: [[Arg1:j\d+]] ParameterValue
+ // CHECK-DAG: [[Arg2:j\d+]] ParameterValue
+ // CHECK-DAG: [[Neg:j\d+]] Neg [ [[Arg1]] ]
+ // CHECK-DAG: [[Add:j\d+]] Add [ [[Neg]] [[Arg2]] ]
+ // CHECK-DAG: Return [ [[Add]] ]
+
+ // CHECK-START: long Main.AddNeg1(long, long) instruction_simplifier (after)
+ // CHECK-DAG: [[Arg1:j\d+]] ParameterValue
+ // CHECK-DAG: [[Arg2:j\d+]] ParameterValue
+ // CHECK-DAG: [[Sub:j\d+]] Sub [ [[Arg2]] [[Arg1]] ]
+ // CHECK-DAG: Return [ [[Sub]] ]
+
+ // CHECK-START: long Main.AddNeg1(long, long) instruction_simplifier (after)
+ // CHECK-NOT: Neg
+ // CHECK-NOT: Add
+
+ public static long AddNeg1(long arg1, long arg2) {
+ return -arg1 + arg2;
+ }
+
+ /**
+ * This is similar to the test-case AddNeg1, but the negation has two uses.
+ * The transformation tested is implemented in `InstructionSimplifierVisitor::VisitAdd`.
+ * The current code won't perform the previous optimization. The
+ * transformations do not look at other uses of their inputs. As they don't
+ * know what will happen with other uses, they do not take the risk of
+ * increasing the register pressure by creating or extending live ranges.
+ */
+
+ // CHECK-START: long Main.AddNeg2(long, long) instruction_simplifier (before)
+ // CHECK-DAG: [[Arg1:j\d+]] ParameterValue
+ // CHECK-DAG: [[Arg2:j\d+]] ParameterValue
+ // CHECK-DAG: [[Neg:j\d+]] Neg [ [[Arg2]] ]
+ // CHECK-DAG: [[Add1:j\d+]] Add [ [[Arg1]] [[Neg]] ]
+ // CHECK-DAG: [[Add2:j\d+]] Add [ [[Arg1]] [[Neg]] ]
+ // CHECK-DAG: [[Res:j\d+]] Or [ [[Add1]] [[Add2]] ]
+ // CHECK-DAG: Return [ [[Res]] ]
+
+ // CHECK-START: long Main.AddNeg2(long, long) instruction_simplifier (after)
+ // CHECK-DAG: [[Arg1:j\d+]] ParameterValue
+ // CHECK-DAG: [[Arg2:j\d+]] ParameterValue
+ // CHECK-DAG: [[Neg:j\d+]] Neg [ [[Arg2]] ]
+ // CHECK-DAG: [[Add1:j\d+]] Add [ [[Arg1]] [[Neg]] ]
+ // CHECK-DAG: [[Add2:j\d+]] Add [ [[Arg1]] [[Neg]] ]
+ // CHECK-DAG: [[Res:j\d+]] Or [ [[Add1]] [[Add2]] ]
+ // CHECK-DAG: Return [ [[Res]] ]
+
+ // CHECK-START: long Main.AddNeg2(long, long) instruction_simplifier (after)
+ // CHECK-NOT: Sub
+
+ public static long AddNeg2(long arg1, long arg2) {
+ long temp = -arg2;
+ return (arg1 + temp) | (arg1 + temp);
+ }
+
+ /**
+ * Test simplification of the `-(-var)` pattern.
+ * The transformation tested is implemented in `InstructionSimplifierVisitor::VisitNeg`.
+ */
+
+ // CHECK-START: long Main.NegNeg1(long) instruction_simplifier (before)
+ // CHECK-DAG: [[Arg:j\d+]] ParameterValue
+ // CHECK-DAG: [[Neg1:j\d+]] Neg [ [[Arg]] ]
+ // CHECK-DAG: [[Neg2:j\d+]] Neg [ [[Neg1]] ]
+ // CHECK-DAG: Return [ [[Neg2]] ]
+
+ // CHECK-START: long Main.NegNeg1(long) instruction_simplifier (after)
+ // CHECK-DAG: [[Arg:j\d+]] ParameterValue
+ // CHECK-DAG: Return [ [[Arg]] ]
+
+ // CHECK-START: long Main.NegNeg1(long) instruction_simplifier (after)
+ // CHECK-NOT: Neg
+
+ public static long NegNeg1(long arg) {
+ return -(-arg);
+ }
+
+ /**
+ * Test 'multi-step' simplification, where a first transformation yields a
+ * new simplification possibility for the current instruction.
+ * The transformations tested are implemented in `InstructionSimplifierVisitor::VisitNeg`
+ * and in `InstructionSimplifierVisitor::VisitAdd`.
+ */
+
+ // CHECK-START: int Main.NegNeg2(int) instruction_simplifier (before)
+ // CHECK-DAG: [[Arg:i\d+]] ParameterValue
+ // CHECK-DAG: [[Neg1:i\d+]] Neg [ [[Arg]] ]
+ // CHECK-DAG: [[Neg2:i\d+]] Neg [ [[Neg1]] ]
+ // CHECK-DAG: [[Add:i\d+]] Add [ [[Neg1]] [[Neg2]] ]
+ // CHECK-DAG: Return [ [[Add]] ]
+
+ // CHECK-START: int Main.NegNeg2(int) instruction_simplifier (after)
+ // CHECK-DAG: [[Arg:i\d+]] ParameterValue
+ // CHECK-DAG: [[Sub:i\d+]] Sub [ [[Arg]] [[Arg]] ]
+ // CHECK-DAG: Return [ [[Sub]] ]
+
+ // CHECK-START: int Main.NegNeg2(int) instruction_simplifier (after)
+ // CHECK-NOT: Neg
+ // CHECK-NOT: Add
+
+ public static int NegNeg2(int arg) {
+ int temp = -arg;
+ return temp + -temp;
+ }
+
+ /**
+ * Test another 'multi-step' simplification, where a first transformation
+ * yields a new simplification possibility for the current instruction.
+ * The transformations tested are implemented in `InstructionSimplifierVisitor::VisitNeg`
+ * and in `InstructionSimplifierVisitor::VisitSub`.
+ */
+
+ // CHECK-START: long Main.NegNeg3(long) instruction_simplifier (before)
+ // CHECK-DAG: [[Arg:j\d+]] ParameterValue
+ // CHECK-DAG: [[Const0:j\d+]] LongConstant 0
+ // CHECK-DAG: [[Neg:j\d+]] Neg [ [[Arg]] ]
+ // CHECK-DAG: [[Sub:j\d+]] Sub [ [[Const0]] [[Neg]] ]
+ // CHECK-DAG: Return [ [[Sub]] ]
+
+ // CHECK-START: long Main.NegNeg3(long) instruction_simplifier (after)
+ // CHECK-DAG: [[Arg:j\d+]] ParameterValue
+ // CHECK-DAG: Return [ [[Arg]] ]
+
+ // CHECK-START: long Main.NegNeg3(long) instruction_simplifier (after)
+ // CHECK-NOT: Neg
+ // CHECK-NOT: Sub
+
+ public static long NegNeg3(long arg) {
+ return 0 - -arg;
+ }
+
+ /**
+ * Test that a negated subtraction is simplified to a subtraction with its
+ * arguments reversed.
+ * The transformation tested is implemented in `InstructionSimplifierVisitor::VisitNeg`.
+ */
+
+ // CHECK-START: int Main.NegSub1(int, int) instruction_simplifier (before)
+ // CHECK-DAG: [[Arg1:i\d+]] ParameterValue
+ // CHECK-DAG: [[Arg2:i\d+]] ParameterValue
+ // CHECK-DAG: [[Sub:i\d+]] Sub [ [[Arg1]] [[Arg2]] ]
+ // CHECK-DAG: [[Neg:i\d+]] Neg [ [[Sub]] ]
+ // CHECK-DAG: Return [ [[Neg]] ]
+
+ // CHECK-START: int Main.NegSub1(int, int) instruction_simplifier (after)
+ // CHECK-DAG: [[Arg1:i\d+]] ParameterValue
+ // CHECK-DAG: [[Arg2:i\d+]] ParameterValue
+ // CHECK-DAG: [[Sub:i\d+]] Sub [ [[Arg2]] [[Arg1]] ]
+ // CHECK-DAG: Return [ [[Sub]] ]
+
+ // CHECK-START: int Main.NegSub1(int, int) instruction_simplifier (after)
+ // CHECK-NOT: Neg
+
+ public static int NegSub1(int arg1, int arg2) {
+ return -(arg1 - arg2);
+ }
+
+ /**
+ * This is similar to the test-case NegSub1, but the subtraction has
+ * multiple uses.
+ * The transformation tested is implemented in `InstructionSimplifierVisitor::VisitNeg`.
+ * The current code won't perform the previous optimization. The
+ * transformations do not look at other uses of their inputs. As they don't
+ * know what will happen with other uses, they do not take the risk of
+ * increasing the register pressure by creating or extending live ranges.
+ */
+
+ // CHECK-START: int Main.NegSub2(int, int) instruction_simplifier (before)
+ // CHECK-DAG: [[Arg1:i\d+]] ParameterValue
+ // CHECK-DAG: [[Arg2:i\d+]] ParameterValue
+ // CHECK-DAG: [[Sub:i\d+]] Sub [ [[Arg1]] [[Arg2]] ]
+ // CHECK-DAG: [[Neg1:i\d+]] Neg [ [[Sub]] ]
+ // CHECK-DAG: [[Neg2:i\d+]] Neg [ [[Sub]] ]
+ // CHECK-DAG: [[Or:i\d+]] Or [ [[Neg1]] [[Neg2]] ]
+ // CHECK-DAG: Return [ [[Or]] ]
+
+ // CHECK-START: int Main.NegSub2(int, int) instruction_simplifier (after)
+ // CHECK-DAG: [[Arg1:i\d+]] ParameterValue
+ // CHECK-DAG: [[Arg2:i\d+]] ParameterValue
+ // CHECK-DAG: [[Sub:i\d+]] Sub [ [[Arg1]] [[Arg2]] ]
+ // CHECK-DAG: [[Neg1:i\d+]] Neg [ [[Sub]] ]
+ // CHECK-DAG: [[Neg2:i\d+]] Neg [ [[Sub]] ]
+ // CHECK-DAG: [[Or:i\d+]] Or [ [[Neg1]] [[Neg2]] ]
+ // CHECK-DAG: Return [ [[Or]] ]
+
+ public static int NegSub2(int arg1, int arg2) {
+ int temp = arg1 - arg2;
+ return -temp | -temp;
+ }
+
+ /**
+ * Test simplification of the `~~var` pattern.
+ * The transformation tested is implemented in `InstructionSimplifierVisitor::VisitNot`.
+ */
+
+ // CHECK-START: long Main.NotNot1(long) instruction_simplifier (before)
+ // CHECK-DAG: [[Arg:j\d+]] ParameterValue
+ // CHECK-DAG: [[ConstF1:j\d+]] LongConstant -1
+ // CHECK-DAG: [[Xor1:j\d+]] Xor [ [[Arg]] [[ConstF1]] ]
+ // CHECK-DAG: [[Xor2:j\d+]] Xor [ [[Xor1]] [[ConstF1]] ]
+ // CHECK-DAG: Return [ [[Xor2]] ]
+
+ // CHECK-START: long Main.NotNot1(long) instruction_simplifier (after)
+ // CHECK-DAG: [[Arg:j\d+]] ParameterValue
+ // CHECK-DAG: Return [ [[Arg]] ]
+
+ // CHECK-START: long Main.NotNot1(long) instruction_simplifier (after)
+ // CHECK-NOT: Xor
+
+ public static long NotNot1(long arg) {
+ return ~~arg;
+ }
+
+ // CHECK-START: int Main.NotNot2(int) instruction_simplifier (before)
+ // CHECK-DAG: [[Arg:i\d+]] ParameterValue
+ // CHECK-DAG: [[ConstF1:i\d+]] IntConstant -1
+ // CHECK-DAG: [[Xor1:i\d+]] Xor [ [[Arg]] [[ConstF1]] ]
+ // CHECK-DAG: [[Xor2:i\d+]] Xor [ [[Xor1]] [[ConstF1]] ]
+ // CHECK-DAG: [[Add:i\d+]] Add [ [[Xor1]] [[Xor2]] ]
+ // CHECK-DAG: Return [ [[Add]] ]
+
+ // CHECK-START: int Main.NotNot2(int) instruction_simplifier (after)
+ // CHECK-DAG: [[Arg:i\d+]] ParameterValue
+ // CHECK-DAG: [[Not:i\d+]] Not [ [[Arg]] ]
+ // CHECK-DAG: [[Add:i\d+]] Add [ [[Not]] [[Arg]] ]
+ // CHECK-DAG: Return [ [[Add]] ]
+
+ // CHECK-START: int Main.NotNot2(int) instruction_simplifier (after)
+ // CHECK-NOT: Xor
+
+ public static int NotNot2(int arg) {
+ int temp = ~arg;
+ return temp + ~temp;
+ }
+
+ /**
+ * Test the simplification of a subtraction with a negated argument.
+ * The transformation tested is implemented in `InstructionSimplifierVisitor::VisitSub`.
+ */
+
+ // CHECK-START: int Main.SubNeg1(int, int) instruction_simplifier (before)
+ // CHECK-DAG: [[Arg1:i\d+]] ParameterValue
+ // CHECK-DAG: [[Arg2:i\d+]] ParameterValue
+ // CHECK-DAG: [[Neg:i\d+]] Neg [ [[Arg1]] ]
+ // CHECK-DAG: [[Sub:i\d+]] Sub [ [[Neg]] [[Arg2]] ]
+ // CHECK-DAG: Return [ [[Sub]] ]
+
+ // CHECK-START: int Main.SubNeg1(int, int) instruction_simplifier (after)
+ // CHECK-DAG: [[Arg1:i\d+]] ParameterValue
+ // CHECK-DAG: [[Arg2:i\d+]] ParameterValue
+ // CHECK-DAG: [[Add:i\d+]] Add [ [[Arg1]] [[Arg2]] ]
+ // CHECK-DAG: [[Neg:i\d+]] Neg [ [[Add]] ]
+ // CHECK-DAG: Return [ [[Neg]] ]
+
+ // CHECK-START: int Main.SubNeg1(int, int) instruction_simplifier (after)
+ // CHECK-NOT: Sub
+
+ public static int SubNeg1(int arg1, int arg2) {
+ return -arg1 - arg2;
+ }
+
+ /**
+ * This is similar to the test-case SubNeg1, but the negation has
+ * multiple uses.
+ * The transformation tested is implemented in `InstructionSimplifierVisitor::VisitSub`.
+ * The current code won't perform the previous optimization. The
+ * transformations do not look at other uses of their inputs. As they don't
+ * know what will happen with other uses, they do not take the risk of
+ * increasing the register pressure by creating or extending live ranges.
+ */
+
+ // CHECK-START: int Main.SubNeg2(int, int) instruction_simplifier (before)
+ // CHECK-DAG: [[Arg1:i\d+]] ParameterValue
+ // CHECK-DAG: [[Arg2:i\d+]] ParameterValue
+ // CHECK-DAG: [[Neg:i\d+]] Neg [ [[Arg1]] ]
+ // CHECK-DAG: [[Sub1:i\d+]] Sub [ [[Neg]] [[Arg2]] ]
+ // CHECK-DAG: [[Sub2:i\d+]] Sub [ [[Neg]] [[Arg2]] ]
+ // CHECK-DAG: [[Or:i\d+]] Or [ [[Sub1]] [[Sub2]] ]
+ // CHECK-DAG: Return [ [[Or]] ]
+
+ // CHECK-START: int Main.SubNeg2(int, int) instruction_simplifier (after)
+ // CHECK-DAG: [[Arg1:i\d+]] ParameterValue
+ // CHECK-DAG: [[Arg2:i\d+]] ParameterValue
+ // CHECK-DAG: [[Neg:i\d+]] Neg [ [[Arg1]] ]
+ // CHECK-DAG: [[Sub1:i\d+]] Sub [ [[Neg]] [[Arg2]] ]
+ // CHECK-DAG: [[Sub2:i\d+]] Sub [ [[Neg]] [[Arg2]] ]
+ // CHECK-DAG: [[Or:i\d+]] Or [ [[Sub1]] [[Sub2]] ]
+ // CHECK-DAG: Return [ [[Or]] ]
+
+ // CHECK-START: int Main.SubNeg2(int, int) instruction_simplifier (after)
+ // CHECK-NOT: Add
+
+ public static int SubNeg2(int arg1, int arg2) {
+ int temp = -arg1;
+ return (temp - arg2) | (temp - arg2);
+ }
+
+ /**
+ * This follows test-cases SubNeg1 and SubNeg2.
+ * The transformation tested is implemented in `InstructionSimplifierVisitor::VisitSub`.
+ * The optimization should not happen if it moves an additional instruction in
+ * the loop.
+ */
+
+ // CHECK-START: long Main.SubNeg3(long, long) instruction_simplifier (before)
+ // -------------- Arguments and initial negation operation.
+ // CHECK-DAG: [[Arg1:j\d+]] ParameterValue
+ // CHECK-DAG: [[Arg2:j\d+]] ParameterValue
+ // CHECK-DAG: [[Neg:j\d+]] Neg [ [[Arg1]] ]
+ // CHECK: Goto
+ // -------------- Loop
+ // CHECK: SuspendCheck
+ // CHECK: [[Sub:j\d+]] Sub [ [[Neg]] [[Arg2]] ]
+ // CHECK: Goto
+
+ // CHECK-START: long Main.SubNeg3(long, long) instruction_simplifier (after)
+ // -------------- Arguments and initial negation operation.
+ // CHECK-DAG: [[Arg1:j\d+]] ParameterValue
+ // CHECK-DAG: [[Arg2:j\d+]] ParameterValue
+ // CHECK-DAG: [[Neg:j\d+]] Neg [ [[Arg1]] ]
+ // CHECK-DAG: Goto
+ // -------------- Loop
+ // CHECK: SuspendCheck
+ // CHECK: [[Sub:j\d+]] Sub [ [[Neg]] [[Arg2]] ]
+ // CHECK-NOT: Neg
+ // CHECK: Goto
+
+ public static long SubNeg3(long arg1, long arg2) {
+ long res = 0;
+ long temp = -arg1;
+ for (long i = 0; i < 1; i++) {
+ res += temp - arg2 - i;
+ }
+ return res;
+ }
+
public static void main(String[] args) {
int arg = 123456;
@@ -328,5 +779,20 @@
assertLongEquals(UShr0(arg), arg);
assertIntEquals(Xor0(arg), arg);
assertIntEquals(XorAllOnes(arg), ~arg);
+ assertIntEquals(AddNegs1(arg, arg + 1), -(arg + arg + 1));
+ assertIntEquals(AddNegs2(arg, arg + 1), -(arg + arg + 1));
+ assertLongEquals(AddNegs3(arg, arg + 1), -(2 * arg + 1));
+ assertLongEquals(AddNeg1(arg, arg + 1), 1);
+ assertLongEquals(AddNeg2(arg, arg + 1), -1);
+ assertLongEquals(NegNeg1(arg), arg);
+ assertIntEquals(NegNeg2(arg), 0);
+ assertLongEquals(NegNeg3(arg), arg);
+ assertIntEquals(NegSub1(arg, arg + 1), 1);
+ assertIntEquals(NegSub2(arg, arg + 1), 1);
+ assertLongEquals(NotNot1(arg), arg);
+ assertIntEquals(NotNot2(arg), -1);
+ assertIntEquals(SubNeg1(arg, arg + 1), -(arg + arg + 1));
+ assertIntEquals(SubNeg2(arg, arg + 1), -(arg + arg + 1));
+ assertLongEquals(SubNeg3(arg, arg + 1), -(2 * arg + 1));
}
}