David Brazdil | 46e2a39 | 2015-03-16 17:31:52 +0000 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2015 The Android Open Source Project |
| 3 | * |
| 4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
| 5 | * you may not use this file except in compliance with the License. |
| 6 | * You may obtain a copy of the License at |
| 7 | * |
| 8 | * http://www.apache.org/licenses/LICENSE-2.0 |
| 9 | * |
| 10 | * Unless required by applicable law or agreed to in writing, software |
| 11 | * distributed under the License is distributed on an "AS IS" BASIS, |
| 12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 13 | * See the License for the specific language governing permissions and |
| 14 | * limitations under the License. |
| 15 | */ |
| 16 | |
| 17 | #include "boolean_simplifier.h" |
| 18 | |
| 19 | namespace art { |
| 20 | |
David Brazdil | 46e2a39 | 2015-03-16 17:31:52 +0000 | [diff] [blame] | 21 | // Returns true if 'block1' and 'block2' are empty, merge into the same single |
| 22 | // successor and the successor can only be reached from them. |
| 23 | static bool BlocksDoMergeTogether(HBasicBlock* block1, HBasicBlock* block2) { |
| 24 | if (!block1->IsSingleGoto() || !block2->IsSingleGoto()) return false; |
| 25 | HBasicBlock* succ1 = block1->GetSuccessors().Get(0); |
| 26 | HBasicBlock* succ2 = block2->GetSuccessors().Get(0); |
| 27 | return succ1 == succ2 && succ1->GetPredecessors().Size() == 2u; |
| 28 | } |
| 29 | |
| 30 | // Returns true if the outcome of the branching matches the boolean value of |
| 31 | // the branching condition. |
| 32 | static bool PreservesCondition(HInstruction* input_true, HInstruction* input_false) { |
David Brazdil | b2bd1c5 | 2015-03-25 11:17:37 +0000 | [diff] [blame] | 33 | return input_true->IsIntConstant() && input_true->AsIntConstant()->IsOne() |
| 34 | && input_false->IsIntConstant() && input_false->AsIntConstant()->IsZero(); |
David Brazdil | 46e2a39 | 2015-03-16 17:31:52 +0000 | [diff] [blame] | 35 | } |
| 36 | |
| 37 | // Returns true if the outcome of the branching is exactly opposite of the |
| 38 | // boolean value of the branching condition. |
| 39 | static bool NegatesCondition(HInstruction* input_true, HInstruction* input_false) { |
David Brazdil | b2bd1c5 | 2015-03-25 11:17:37 +0000 | [diff] [blame] | 40 | return input_true->IsIntConstant() && input_true->AsIntConstant()->IsZero() |
| 41 | && input_false->IsIntConstant() && input_false->AsIntConstant()->IsOne(); |
David Brazdil | 46e2a39 | 2015-03-16 17:31:52 +0000 | [diff] [blame] | 42 | } |
| 43 | |
| 44 | // Returns an instruction with the opposite boolean value from 'cond'. |
| 45 | static HInstruction* GetOppositeCondition(HInstruction* cond) { |
| 46 | HGraph* graph = cond->GetBlock()->GetGraph(); |
| 47 | ArenaAllocator* allocator = graph->GetArena(); |
| 48 | |
| 49 | if (cond->IsCondition()) { |
| 50 | HInstruction* lhs = cond->InputAt(0); |
| 51 | HInstruction* rhs = cond->InputAt(1); |
| 52 | if (cond->IsEqual()) { |
| 53 | return new (allocator) HNotEqual(lhs, rhs); |
| 54 | } else if (cond->IsNotEqual()) { |
| 55 | return new (allocator) HEqual(lhs, rhs); |
| 56 | } else if (cond->IsLessThan()) { |
| 57 | return new (allocator) HGreaterThanOrEqual(lhs, rhs); |
| 58 | } else if (cond->IsLessThanOrEqual()) { |
| 59 | return new (allocator) HGreaterThan(lhs, rhs); |
| 60 | } else if (cond->IsGreaterThan()) { |
| 61 | return new (allocator) HLessThanOrEqual(lhs, rhs); |
David Brazdil | 2846b68 | 2015-03-31 09:59:27 +0100 | [diff] [blame] | 62 | } else { |
| 63 | DCHECK(cond->IsGreaterThanOrEqual()); |
David Brazdil | 46e2a39 | 2015-03-16 17:31:52 +0000 | [diff] [blame] | 64 | return new (allocator) HLessThan(lhs, rhs); |
| 65 | } |
| 66 | } else if (cond->IsIntConstant()) { |
David Brazdil | b2bd1c5 | 2015-03-25 11:17:37 +0000 | [diff] [blame] | 67 | HIntConstant* int_const = cond->AsIntConstant(); |
| 68 | if (int_const->IsZero()) { |
David Brazdil | 8d5b8b2 | 2015-03-24 10:51:52 +0000 | [diff] [blame] | 69 | return graph->GetIntConstant(1); |
David Brazdil | 46e2a39 | 2015-03-16 17:31:52 +0000 | [diff] [blame] | 70 | } else { |
David Brazdil | b2bd1c5 | 2015-03-25 11:17:37 +0000 | [diff] [blame] | 71 | DCHECK(int_const->IsOne()); |
David Brazdil | 8d5b8b2 | 2015-03-24 10:51:52 +0000 | [diff] [blame] | 72 | return graph->GetIntConstant(0); |
David Brazdil | 46e2a39 | 2015-03-16 17:31:52 +0000 | [diff] [blame] | 73 | } |
David Brazdil | 2846b68 | 2015-03-31 09:59:27 +0100 | [diff] [blame] | 74 | } else { |
| 75 | // General case when 'cond' is another instruction of type boolean. |
| 76 | // Negate with 'cond == 0'. |
| 77 | return new (allocator) HEqual(cond, graph->GetIntConstant(0)); |
David Brazdil | 46e2a39 | 2015-03-16 17:31:52 +0000 | [diff] [blame] | 78 | } |
David Brazdil | 46e2a39 | 2015-03-16 17:31:52 +0000 | [diff] [blame] | 79 | } |
| 80 | |
| 81 | void HBooleanSimplifier::Run() { |
| 82 | // Iterate in post order in the unlikely case that removing one occurrence of |
| 83 | // the pattern empties a branch block of another occurrence. Otherwise the |
| 84 | // order does not matter. |
| 85 | for (HPostOrderIterator it(*graph_); !it.Done(); it.Advance()) { |
| 86 | HBasicBlock* block = it.Current(); |
David Brazdil | b2bd1c5 | 2015-03-25 11:17:37 +0000 | [diff] [blame] | 87 | if (!block->EndsWithIf()) continue; |
David Brazdil | 46e2a39 | 2015-03-16 17:31:52 +0000 | [diff] [blame] | 88 | |
| 89 | // Find elements of the pattern. |
| 90 | HIf* if_instruction = block->GetLastInstruction()->AsIf(); |
| 91 | HBasicBlock* true_block = if_instruction->IfTrueSuccessor(); |
| 92 | HBasicBlock* false_block = if_instruction->IfFalseSuccessor(); |
| 93 | if (!BlocksDoMergeTogether(true_block, false_block)) { |
| 94 | continue; |
| 95 | } |
| 96 | HBasicBlock* merge_block = true_block->GetSuccessors().Get(0); |
David Brazdil | b2bd1c5 | 2015-03-25 11:17:37 +0000 | [diff] [blame] | 97 | if (!merge_block->HasSinglePhi()) { |
David Brazdil | 46e2a39 | 2015-03-16 17:31:52 +0000 | [diff] [blame] | 98 | continue; |
| 99 | } |
| 100 | HPhi* phi = merge_block->GetFirstPhi()->AsPhi(); |
| 101 | HInstruction* true_value = phi->InputAt(merge_block->GetPredecessorIndexOf(true_block)); |
| 102 | HInstruction* false_value = phi->InputAt(merge_block->GetPredecessorIndexOf(false_block)); |
| 103 | |
| 104 | // Check if the selection negates/preserves the value of the condition and |
| 105 | // if so, generate a suitable replacement instruction. |
| 106 | HInstruction* if_condition = if_instruction->InputAt(0); |
| 107 | HInstruction* replacement; |
| 108 | if (NegatesCondition(true_value, false_value)) { |
| 109 | replacement = GetOppositeCondition(if_condition); |
David Brazdil | 46e2a39 | 2015-03-16 17:31:52 +0000 | [diff] [blame] | 110 | if (replacement->GetBlock() == nullptr) { |
| 111 | block->InsertInstructionBefore(replacement, if_instruction); |
| 112 | } |
| 113 | } else if (PreservesCondition(true_value, false_value)) { |
| 114 | replacement = if_condition; |
| 115 | } else { |
| 116 | continue; |
| 117 | } |
| 118 | |
| 119 | // Replace the selection outcome with the new instruction. |
| 120 | phi->ReplaceWith(replacement); |
| 121 | merge_block->RemovePhi(phi); |
| 122 | |
| 123 | // Link the start/end blocks and remove empty branches. |
| 124 | graph_->MergeEmptyBranches(block, merge_block); |
| 125 | |
| 126 | // Remove the original condition if it is now unused. |
| 127 | if (!if_condition->HasUses()) { |
| 128 | if_condition->GetBlock()->RemoveInstruction(if_condition); |
| 129 | } |
| 130 | } |
| 131 | } |
| 132 | |
| 133 | } // namespace art |