Optimizing: double-negated bitwise operations simplifications
Generic instruction simplifications applying to bitwise operations when
both inputs are Not's. And and Or are handled by De Morgan's laws,
removing one instruction:
~a & ~b -> ~(a | b)
~a | ~b -> ~(a & b)
Xor is handled by this trivial relation, removing two instructions:
~a ^ ~b = a ^ b
The simplifications only happen when neither Not is used by other
instructions.
Change-Id: I5d5187af2f625c475c3e49466af6bc3e87595f8f
diff --git a/compiler/optimizing/instruction_simplifier.cc b/compiler/optimizing/instruction_simplifier.cc
index 49fc8c7..3f66c66 100644
--- a/compiler/optimizing/instruction_simplifier.cc
+++ b/compiler/optimizing/instruction_simplifier.cc
@@ -46,6 +46,10 @@
bool TryReplaceWithRotateRegisterSubPattern(HBinaryOperation* op, HUShr* ushr, HShl* shl);
bool TryMoveNegOnInputsAfterBinop(HBinaryOperation* binop);
+ // `op` should be either HOr or HAnd.
+ // De Morgan's laws:
+ // ~a & ~b = ~(a | b) and ~a | ~b = ~(a & b)
+ bool TryApplyDeMorgan(HBinaryOperation* op);
void VisitShift(HBinaryOperation* shift);
void VisitSuspendCheck(HSuspendCheck* check) OVERRIDE;
@@ -162,6 +166,64 @@
return true;
}
+bool InstructionSimplifierVisitor::TryApplyDeMorgan(HBinaryOperation* op) {
+ DCHECK(op->IsAnd() || op->IsOr());
+ Primitive::Type type = op->GetType();
+ HInstruction* left = op->GetLeft();
+ HInstruction* right = op->GetRight();
+
+ // We can apply De Morgan's laws if both inputs are Not's and are only used
+ // by `op`.
+ if (left->IsNot() &&
+ right->IsNot() &&
+ left->HasOnlyOneNonEnvironmentUse() &&
+ right->HasOnlyOneNonEnvironmentUse()) {
+ // Replace code looking like
+ // NOT nota, a
+ // NOT notb, b
+ // AND dst, nota, notb (respectively OR)
+ // with
+ // OR or, a, b (respectively AND)
+ // NOT dest, or
+ HInstruction* src_left = left->AsNot()->GetInput();
+ HInstruction* src_right = right->AsNot()->GetInput();
+ uint32_t dex_pc = op->GetDexPc();
+
+ HBinaryOperation* hbin;
+ if (op->IsAnd()) {
+ hbin = new (GetGraph()->GetArena()) HOr(type, src_left, src_right, dex_pc);
+ } else {
+ hbin = new (GetGraph()->GetArena()) HAnd(type, src_left, src_right, dex_pc);
+ }
+ // Step 1: replace left Not by new binary operation (this is arbitrary,
+ // the right one could have been used instead).
+ // SL SR SL SR
+ // | | | / |
+ // Not Not NewBin Not
+ // \ / -> \ /
+ // OldBin OldBin
+ // | |
+ left->GetBlock()->ReplaceAndRemoveInstructionWith(left, hbin);
+
+ HNot* hnot = new (GetGraph()->GetArena()) HNot(type, hbin, dex_pc);
+ // Step 2: replace old binary operation by a new Not, and remove
+ // the now disconnected right Not.
+ // SL SR SL SR
+ // | / | | / |
+ // NewBin Not NewBin Not [removed]
+ // \ / -> \ x
+ // OldBin Not
+ // | |
+ op->GetBlock()->ReplaceAndRemoveInstructionWith(op, hnot);
+ right->GetBlock()->RemoveInstruction(right);
+
+ RecordSimplification();
+ return true;
+ }
+
+ return false;
+}
+
void InstructionSimplifierVisitor::VisitShift(HBinaryOperation* instruction) {
DCHECK(instruction->IsShl() || instruction->IsShr() || instruction->IsUShr());
HConstant* input_cst = instruction->GetConstantRight();
@@ -739,7 +801,10 @@
// src
instruction->ReplaceWith(instruction->GetLeft());
instruction->GetBlock()->RemoveInstruction(instruction);
+ return;
}
+
+ TryApplyDeMorgan(instruction);
}
void InstructionSimplifierVisitor::VisitGreaterThan(HGreaterThan* condition) {
@@ -1053,6 +1118,8 @@
return;
}
+ if (TryApplyDeMorgan(instruction)) return;
+
TryReplaceWithRotate(instruction);
}
@@ -1175,6 +1242,26 @@
return;
}
+ HInstruction* left = instruction->GetLeft();
+ HInstruction* right = instruction->GetRight();
+ if (left->IsNot() &&
+ right->IsNot() &&
+ left->HasOnlyOneNonEnvironmentUse() &&
+ right->HasOnlyOneNonEnvironmentUse()) {
+ // Replace code looking like
+ // NOT nota, a
+ // NOT notb, b
+ // XOR dst, nota, notb
+ // with
+ // XOR dst, a, b
+ instruction->ReplaceInput(left->AsNot()->GetInput(), 0);
+ instruction->ReplaceInput(right->AsNot()->GetInput(), 1);
+ left->GetBlock()->RemoveInstruction(left);
+ right->GetBlock()->RemoveInstruction(right);
+ RecordSimplification();
+ return;
+ }
+
TryReplaceWithRotate(instruction);
}