1 /*
2 * Copyright (C) 2016 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 "select_generator.h"
18
19 #include "reference_type_propagation.h"
20
21 namespace art {
22
23 static constexpr size_t kMaxInstructionsInBranch = 1u;
24
HSelectGenerator(HGraph * graph,VariableSizedHandleScope * handles,OptimizingCompilerStats * stats,const char * name)25 HSelectGenerator::HSelectGenerator(HGraph* graph,
26 VariableSizedHandleScope* handles,
27 OptimizingCompilerStats* stats,
28 const char* name)
29 : HOptimization(graph, name, stats),
30 handle_scope_(handles) {
31 }
32
33 // Returns true if `block` has only one predecessor, ends with a Goto
34 // or a Return and contains at most `kMaxInstructionsInBranch` other
35 // movable instruction with no side-effects.
IsSimpleBlock(HBasicBlock * block)36 static bool IsSimpleBlock(HBasicBlock* block) {
37 if (block->GetPredecessors().size() != 1u) {
38 return false;
39 }
40 DCHECK(block->GetPhis().IsEmpty());
41
42 size_t num_instructions = 0u;
43 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
44 HInstruction* instruction = it.Current();
45 if (instruction->IsControlFlow()) {
46 if (num_instructions > kMaxInstructionsInBranch) {
47 return false;
48 }
49 return instruction->IsGoto() || instruction->IsReturn();
50 } else if (instruction->CanBeMoved() && !instruction->HasSideEffects()) {
51 num_instructions++;
52 } else {
53 return false;
54 }
55 }
56
57 LOG(FATAL) << "Unreachable";
58 UNREACHABLE();
59 }
60
61 // Returns true if 'block1' and 'block2' are empty and merge into the
62 // same single successor.
BlocksMergeTogether(HBasicBlock * block1,HBasicBlock * block2)63 static bool BlocksMergeTogether(HBasicBlock* block1, HBasicBlock* block2) {
64 return block1->GetSingleSuccessor() == block2->GetSingleSuccessor();
65 }
66
67 // Returns nullptr if `block` has either no phis or there is more than one phi
68 // with different inputs at `index1` and `index2`. Otherwise returns that phi.
GetSingleChangedPhi(HBasicBlock * block,size_t index1,size_t index2)69 static HPhi* GetSingleChangedPhi(HBasicBlock* block, size_t index1, size_t index2) {
70 DCHECK_NE(index1, index2);
71
72 HPhi* select_phi = nullptr;
73 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
74 HPhi* phi = it.Current()->AsPhi();
75 if (phi->InputAt(index1) != phi->InputAt(index2)) {
76 if (select_phi == nullptr) {
77 // First phi with different inputs for the two indices found.
78 select_phi = phi;
79 } else {
80 // More than one phis has different inputs for the two indices.
81 return nullptr;
82 }
83 }
84 }
85 return select_phi;
86 }
87
Run()88 void HSelectGenerator::Run() {
89 // Iterate in post order in the unlikely case that removing one occurrence of
90 // the selection pattern empties a branch block of another occurrence.
91 // Otherwise the order does not matter.
92 for (HBasicBlock* block : graph_->GetPostOrder()) {
93 if (!block->EndsWithIf()) continue;
94
95 // Find elements of the diamond pattern.
96 HIf* if_instruction = block->GetLastInstruction()->AsIf();
97 HBasicBlock* true_block = if_instruction->IfTrueSuccessor();
98 HBasicBlock* false_block = if_instruction->IfFalseSuccessor();
99 DCHECK_NE(true_block, false_block);
100 if (!IsSimpleBlock(true_block) ||
101 !IsSimpleBlock(false_block) ||
102 !BlocksMergeTogether(true_block, false_block)) {
103 continue;
104 }
105 HBasicBlock* merge_block = true_block->GetSingleSuccessor();
106
107 // If the branches are not empty, move instructions in front of the If.
108 // TODO(dbrazdil): This puts an instruction between If and its condition.
109 // Implement moving of conditions to first users if possible.
110 if (!true_block->IsSingleGoto() && !true_block->IsSingleReturn()) {
111 true_block->GetFirstInstruction()->MoveBefore(if_instruction);
112 }
113 if (!false_block->IsSingleGoto() && !false_block->IsSingleReturn()) {
114 false_block->GetFirstInstruction()->MoveBefore(if_instruction);
115 }
116 DCHECK(true_block->IsSingleGoto() || true_block->IsSingleReturn());
117 DCHECK(false_block->IsSingleGoto() || false_block->IsSingleReturn());
118
119 // Find the resulting true/false values.
120 size_t predecessor_index_true = merge_block->GetPredecessorIndexOf(true_block);
121 size_t predecessor_index_false = merge_block->GetPredecessorIndexOf(false_block);
122 DCHECK_NE(predecessor_index_true, predecessor_index_false);
123
124 bool both_successors_return = true_block->IsSingleReturn() && false_block->IsSingleReturn();
125 HPhi* phi = GetSingleChangedPhi(merge_block, predecessor_index_true, predecessor_index_false);
126
127 HInstruction* true_value = nullptr;
128 HInstruction* false_value = nullptr;
129 if (both_successors_return) {
130 true_value = true_block->GetFirstInstruction()->InputAt(0);
131 false_value = false_block->GetFirstInstruction()->InputAt(0);
132 } else if (phi != nullptr) {
133 true_value = phi->InputAt(predecessor_index_true);
134 false_value = phi->InputAt(predecessor_index_false);
135 } else {
136 continue;
137 }
138 DCHECK(both_successors_return || phi != nullptr);
139
140 // Create the Select instruction and insert it in front of the If.
141 HSelect* select = new (graph_->GetAllocator()) HSelect(if_instruction->InputAt(0),
142 true_value,
143 false_value,
144 if_instruction->GetDexPc());
145 if (both_successors_return) {
146 if (true_value->GetType() == DataType::Type::kReference) {
147 DCHECK(false_value->GetType() == DataType::Type::kReference);
148 ReferenceTypePropagation::FixUpInstructionType(select, handle_scope_);
149 }
150 } else if (phi->GetType() == DataType::Type::kReference) {
151 select->SetReferenceTypeInfo(phi->GetReferenceTypeInfo());
152 }
153 block->InsertInstructionBefore(select, if_instruction);
154
155 // Remove the true branch which removes the corresponding Phi
156 // input if needed. If left only with the false branch, the Phi is
157 // automatically removed.
158 if (both_successors_return) {
159 false_block->GetFirstInstruction()->ReplaceInput(select, 0);
160 } else {
161 phi->ReplaceInput(select, predecessor_index_false);
162 }
163
164 bool only_two_predecessors = (merge_block->GetPredecessors().size() == 2u);
165 true_block->DisconnectAndDelete();
166
167 // Merge remaining blocks which are now connected with Goto.
168 DCHECK_EQ(block->GetSingleSuccessor(), false_block);
169 block->MergeWith(false_block);
170 if (!both_successors_return && only_two_predecessors) {
171 DCHECK_EQ(only_two_predecessors, phi->GetBlock() == nullptr);
172 DCHECK_EQ(block->GetSingleSuccessor(), merge_block);
173 block->MergeWith(merge_block);
174 }
175
176 MaybeRecordStat(stats_, MethodCompilationStat::kSelectGenerated);
177
178 // No need to update dominance information, as we are simplifying
179 // a simple diamond shape, where the join block is merged with the
180 // entry block. Any following blocks would have had the join block
181 // as a dominator, and `MergeWith` handles changing that to the
182 // entry block.
183 }
184 }
185
186 } // namespace art
187