ART: Simplify Ifs with BooleanNot condition
If statements with negated condition can be simplified by removing the
negation and swapping the true and false branches.
Change-Id: I197afbc79fb7344d73b7b85d3611e7ca2519717f
diff --git a/compiler/optimizing/boolean_simplifier.cc b/compiler/optimizing/boolean_simplifier.cc
index 9a92151..8100a29 100644
--- a/compiler/optimizing/boolean_simplifier.cc
+++ b/compiler/optimizing/boolean_simplifier.cc
@@ -18,6 +18,26 @@
namespace art {
+void HBooleanSimplifier::TryRemovingNegatedCondition(HBasicBlock* block) {
+ DCHECK(block->EndsWithIf());
+
+ // Check if the condition is a Boolean negation.
+ HIf* if_instruction = block->GetLastInstruction()->AsIf();
+ HInstruction* boolean_not = if_instruction->InputAt(0);
+ if (!boolean_not->IsBooleanNot()) {
+ return;
+ }
+
+ // Make BooleanNot's input the condition of the If and swap branches.
+ if_instruction->ReplaceInput(boolean_not->InputAt(0), 0);
+ block->SwapSuccessors();
+
+ // Remove the BooleanNot if it is now unused.
+ if (!boolean_not->HasUses()) {
+ boolean_not->GetBlock()->RemoveInstruction(boolean_not);
+ }
+}
+
// Returns true if 'block1' and 'block2' are empty, merge into the same single
// successor and the successor can only be reached from them.
static bool BlocksDoMergeTogether(HBasicBlock* block1, HBasicBlock* block2) {
@@ -78,58 +98,69 @@
}
}
+void HBooleanSimplifier::TryRemovingBooleanSelection(HBasicBlock* block) {
+ DCHECK(block->EndsWithIf());
+
+ // Find elements of the pattern.
+ HIf* if_instruction = block->GetLastInstruction()->AsIf();
+ HBasicBlock* true_block = if_instruction->IfTrueSuccessor();
+ HBasicBlock* false_block = if_instruction->IfFalseSuccessor();
+ if (!BlocksDoMergeTogether(true_block, false_block)) {
+ return;
+ }
+ HBasicBlock* merge_block = true_block->GetSuccessors().Get(0);
+ if (!merge_block->HasSinglePhi()) {
+ return;
+ }
+ HPhi* phi = merge_block->GetFirstPhi()->AsPhi();
+ HInstruction* true_value = phi->InputAt(merge_block->GetPredecessorIndexOf(true_block));
+ HInstruction* false_value = phi->InputAt(merge_block->GetPredecessorIndexOf(false_block));
+
+ // Check if the selection negates/preserves the value of the condition and
+ // if so, generate a suitable replacement instruction.
+ HInstruction* if_condition = if_instruction->InputAt(0);
+ HInstruction* replacement;
+ if (NegatesCondition(true_value, false_value)) {
+ replacement = GetOppositeCondition(if_condition);
+ if (replacement->GetBlock() == nullptr) {
+ block->InsertInstructionBefore(replacement, if_instruction);
+ }
+ } else if (PreservesCondition(true_value, false_value)) {
+ replacement = if_condition;
+ } else {
+ return;
+ }
+
+ // Replace the selection outcome with the new instruction.
+ phi->ReplaceWith(replacement);
+ merge_block->RemovePhi(phi);
+
+ // Delete the true branch and merge the resulting chain of blocks
+ // 'block->false_block->merge_block' into one.
+ true_block->DisconnectAndDelete();
+ block->MergeWith(false_block);
+ block->MergeWith(merge_block);
+
+ // Remove the original condition if it is now unused.
+ if (!if_condition->HasUses()) {
+ if_condition->GetBlock()->RemoveInstructionOrPhi(if_condition);
+ }
+}
+
void HBooleanSimplifier::Run() {
// Iterate in post order in the unlikely case that removing one occurrence of
- // the pattern empties a branch block of another occurrence. Otherwise the
- // order does not matter.
+ // the selection pattern empties a branch block of another occurrence.
+ // Otherwise the order does not matter.
for (HPostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
HBasicBlock* block = it.Current();
if (!block->EndsWithIf()) continue;
- // Find elements of the pattern.
- HIf* if_instruction = block->GetLastInstruction()->AsIf();
- HBasicBlock* true_block = if_instruction->IfTrueSuccessor();
- HBasicBlock* false_block = if_instruction->IfFalseSuccessor();
- if (!BlocksDoMergeTogether(true_block, false_block)) {
- continue;
- }
- HBasicBlock* merge_block = true_block->GetSuccessors().Get(0);
- if (!merge_block->HasSinglePhi()) {
- continue;
- }
- HPhi* phi = merge_block->GetFirstPhi()->AsPhi();
- HInstruction* true_value = phi->InputAt(merge_block->GetPredecessorIndexOf(true_block));
- HInstruction* false_value = phi->InputAt(merge_block->GetPredecessorIndexOf(false_block));
+ // If condition is negated, remove the negation and swap the branches.
+ TryRemovingNegatedCondition(block);
- // Check if the selection negates/preserves the value of the condition and
- // if so, generate a suitable replacement instruction.
- HInstruction* if_condition = if_instruction->InputAt(0);
- HInstruction* replacement;
- if (NegatesCondition(true_value, false_value)) {
- replacement = GetOppositeCondition(if_condition);
- if (replacement->GetBlock() == nullptr) {
- block->InsertInstructionBefore(replacement, if_instruction);
- }
- } else if (PreservesCondition(true_value, false_value)) {
- replacement = if_condition;
- } else {
- continue;
- }
-
- // Replace the selection outcome with the new instruction.
- phi->ReplaceWith(replacement);
- merge_block->RemovePhi(phi);
-
- // Delete the true branch and merge the resulting chain of blocks
- // 'block->false_block->merge_block' into one.
- true_block->DisconnectAndDelete();
- block->MergeWith(false_block);
- block->MergeWith(merge_block);
-
- // Remove the original condition if it is now unused.
- if (!if_condition->HasUses()) {
- if_condition->GetBlock()->RemoveInstructionOrPhi(if_condition);
- }
+ // If this is a boolean-selection diamond pattern, replace its result with
+ // the condition value (or its negation) and simplify the graph.
+ TryRemovingBooleanSelection(block);
}
}
diff --git a/compiler/optimizing/boolean_simplifier.h b/compiler/optimizing/boolean_simplifier.h
index a88733e..733ebaa 100644
--- a/compiler/optimizing/boolean_simplifier.h
+++ b/compiler/optimizing/boolean_simplifier.h
@@ -14,11 +14,15 @@
* limitations under the License.
*/
-// This optimization recognizes a common pattern where a boolean value is
-// either cast to an integer or negated by selecting from zero/one integer
-// constants with an If statement. Because boolean values are internally
-// represented as zero/one, we can safely replace the pattern with a suitable
-// condition instruction.
+// This optimization recognizes two common patterns:
+// (a) Boolean selection: Casting a boolean to an integer or negating it is
+// carried out with an If statement selecting from zero/one integer
+// constants. Because Boolean values are represented as zero/one, the
+// pattern can be replaced with the condition instruction itself or its
+// negation, depending on the layout.
+// (b) Negated condition: Instruction simplifier may replace an If's condition
+// with a boolean value. If this value is the result of a Boolean negation,
+// the true/false branches can be swapped and negation removed.
// Example: Negating a boolean value
// B1:
@@ -66,6 +70,9 @@
static constexpr const char* kBooleanSimplifierPassName = "boolean_simplifier";
private:
+ void TryRemovingNegatedCondition(HBasicBlock* block);
+ void TryRemovingBooleanSelection(HBasicBlock* block);
+
DISALLOW_COPY_AND_ASSIGN(HBooleanSimplifier);
};
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 753c95b..863b0b9 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -526,6 +526,13 @@
predecessors_.Put(1, temp);
}
+ void SwapSuccessors() {
+ DCHECK_EQ(successors_.Size(), 2u);
+ HBasicBlock* temp = successors_.Get(0);
+ successors_.Put(0, successors_.Get(1));
+ successors_.Put(1, temp);
+ }
+
size_t GetPredecessorIndexOf(HBasicBlock* predecessor) {
for (size_t i = 0, e = predecessors_.Size(); i < e; ++i) {
if (predecessors_.Get(i) == predecessor) {