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
TryRemovingNegatedCondition(HBasicBlock * block)21 void HBooleanSimplifier::TryRemovingNegatedCondition(HBasicBlock* block) {
22 DCHECK(block->EndsWithIf());
23
24 // Check if the condition is a Boolean negation.
25 HIf* if_instruction = block->GetLastInstruction()->AsIf();
26 HInstruction* boolean_not = if_instruction->InputAt(0);
27 if (!boolean_not->IsBooleanNot()) {
28 return;
29 }
30
31 // Make BooleanNot's input the condition of the If and swap branches.
32 if_instruction->ReplaceInput(boolean_not->InputAt(0), 0);
33 block->SwapSuccessors();
34
35 // Remove the BooleanNot if it is now unused.
36 if (!boolean_not->HasUses()) {
37 boolean_not->GetBlock()->RemoveInstruction(boolean_not);
38 }
39 }
40
41 // Returns true if 'block1' and 'block2' are empty, merge into the same single
42 // successor and the successor can only be reached from them.
BlocksDoMergeTogether(HBasicBlock * block1,HBasicBlock * block2)43 static bool BlocksDoMergeTogether(HBasicBlock* block1, HBasicBlock* block2) {
44 if (!block1->IsSingleGoto() || !block2->IsSingleGoto()) return false;
45 HBasicBlock* succ1 = block1->GetSuccessors().Get(0);
46 HBasicBlock* succ2 = block2->GetSuccessors().Get(0);
47 return succ1 == succ2 && succ1->GetPredecessors().Size() == 2u;
48 }
49
50 // Returns true if the outcome of the branching matches the boolean value of
51 // the branching condition.
PreservesCondition(HInstruction * input_true,HInstruction * input_false)52 static bool PreservesCondition(HInstruction* input_true, HInstruction* input_false) {
53 return input_true->IsIntConstant() && input_true->AsIntConstant()->IsOne()
54 && input_false->IsIntConstant() && input_false->AsIntConstant()->IsZero();
55 }
56
57 // Returns true if the outcome of the branching is exactly opposite of the
58 // boolean value of the branching condition.
NegatesCondition(HInstruction * input_true,HInstruction * input_false)59 static bool NegatesCondition(HInstruction* input_true, HInstruction* input_false) {
60 return input_true->IsIntConstant() && input_true->AsIntConstant()->IsZero()
61 && input_false->IsIntConstant() && input_false->AsIntConstant()->IsOne();
62 }
63
64 // Returns an instruction with the opposite boolean value from 'cond'.
GetOppositeCondition(HInstruction * cond)65 static HInstruction* GetOppositeCondition(HInstruction* cond) {
66 HGraph* graph = cond->GetBlock()->GetGraph();
67 ArenaAllocator* allocator = graph->GetArena();
68
69 if (cond->IsCondition()) {
70 HInstruction* lhs = cond->InputAt(0);
71 HInstruction* rhs = cond->InputAt(1);
72 if (cond->IsEqual()) {
73 return new (allocator) HNotEqual(lhs, rhs);
74 } else if (cond->IsNotEqual()) {
75 return new (allocator) HEqual(lhs, rhs);
76 } else if (cond->IsLessThan()) {
77 return new (allocator) HGreaterThanOrEqual(lhs, rhs);
78 } else if (cond->IsLessThanOrEqual()) {
79 return new (allocator) HGreaterThan(lhs, rhs);
80 } else if (cond->IsGreaterThan()) {
81 return new (allocator) HLessThanOrEqual(lhs, rhs);
82 } else {
83 DCHECK(cond->IsGreaterThanOrEqual());
84 return new (allocator) HLessThan(lhs, rhs);
85 }
86 } else if (cond->IsIntConstant()) {
87 HIntConstant* int_const = cond->AsIntConstant();
88 if (int_const->IsZero()) {
89 return graph->GetIntConstant(1);
90 } else {
91 DCHECK(int_const->IsOne());
92 return graph->GetIntConstant(0);
93 }
94 } else {
95 // General case when 'cond' is another instruction of type boolean,
96 // as verified by SSAChecker.
97 return new (allocator) HBooleanNot(cond);
98 }
99 }
100
TryRemovingBooleanSelection(HBasicBlock * block)101 void HBooleanSimplifier::TryRemovingBooleanSelection(HBasicBlock* block) {
102 DCHECK(block->EndsWithIf());
103
104 // Find elements of the pattern.
105 HIf* if_instruction = block->GetLastInstruction()->AsIf();
106 HBasicBlock* true_block = if_instruction->IfTrueSuccessor();
107 HBasicBlock* false_block = if_instruction->IfFalseSuccessor();
108 if (!BlocksDoMergeTogether(true_block, false_block)) {
109 return;
110 }
111 HBasicBlock* merge_block = true_block->GetSuccessors().Get(0);
112 if (!merge_block->HasSinglePhi()) {
113 return;
114 }
115 HPhi* phi = merge_block->GetFirstPhi()->AsPhi();
116 HInstruction* true_value = phi->InputAt(merge_block->GetPredecessorIndexOf(true_block));
117 HInstruction* false_value = phi->InputAt(merge_block->GetPredecessorIndexOf(false_block));
118
119 // Check if the selection negates/preserves the value of the condition and
120 // if so, generate a suitable replacement instruction.
121 HInstruction* if_condition = if_instruction->InputAt(0);
122 HInstruction* replacement;
123 if (NegatesCondition(true_value, false_value)) {
124 replacement = GetOppositeCondition(if_condition);
125 if (replacement->GetBlock() == nullptr) {
126 block->InsertInstructionBefore(replacement, if_instruction);
127 }
128 } else if (PreservesCondition(true_value, false_value)) {
129 replacement = if_condition;
130 } else {
131 return;
132 }
133
134 // Replace the selection outcome with the new instruction.
135 phi->ReplaceWith(replacement);
136 merge_block->RemovePhi(phi);
137
138 // Delete the true branch and merge the resulting chain of blocks
139 // 'block->false_block->merge_block' into one.
140 true_block->DisconnectAndDelete();
141 block->MergeWith(false_block);
142 block->MergeWith(merge_block);
143
144 // No need to update any dominance information, as we are simplifying
145 // a simple diamond shape, where the join block is merged with the
146 // entry block. Any following blocks would have had the join block
147 // as a dominator, and `MergeWith` handles changing that to the
148 // entry block.
149 }
150
Run()151 void HBooleanSimplifier::Run() {
152 // Iterate in post order in the unlikely case that removing one occurrence of
153 // the selection pattern empties a branch block of another occurrence.
154 // Otherwise the order does not matter.
155 for (HPostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
156 HBasicBlock* block = it.Current();
157 if (!block->EndsWithIf()) continue;
158
159 // If condition is negated, remove the negation and swap the branches.
160 TryRemovingNegatedCondition(block);
161
162 // If this is a boolean-selection diamond pattern, replace its result with
163 // the condition value (or its negation) and simplify the graph.
164 TryRemovingBooleanSelection(block);
165 }
166 }
167
168 } // namespace art
169