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 "base/scoped_arena_containers.h"
20 #include "reference_type_propagation.h"
21
22 namespace art {
23
24 static constexpr size_t kMaxInstructionsInBranch = 1u;
25
HSelectGenerator(HGraph * graph,VariableSizedHandleScope * handles,OptimizingCompilerStats * stats,const char * name)26 HSelectGenerator::HSelectGenerator(HGraph* graph,
27 VariableSizedHandleScope* handles,
28 OptimizingCompilerStats* stats,
29 const char* name)
30 : HOptimization(graph, name, stats),
31 handle_scope_(handles) {
32 }
33
34 // Returns true if `block` has only one predecessor, ends with a Goto
35 // or a Return and contains at most `kMaxInstructionsInBranch` other
36 // movable instruction with no side-effects.
IsSimpleBlock(HBasicBlock * block)37 static bool IsSimpleBlock(HBasicBlock* block) {
38 if (block->GetPredecessors().size() != 1u) {
39 return false;
40 }
41 DCHECK(block->GetPhis().IsEmpty());
42
43 size_t num_instructions = 0u;
44 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
45 HInstruction* instruction = it.Current();
46 if (instruction->IsControlFlow()) {
47 return instruction->IsGoto() || instruction->IsReturn();
48 } else if (instruction->CanBeMoved() &&
49 !instruction->HasSideEffects() &&
50 !instruction->CanThrow()) {
51 if (instruction->IsSelect() &&
52 instruction->AsSelect()->GetCondition()->GetBlock() == block) {
53 // Count one HCondition and HSelect in the same block as a single instruction.
54 // This enables finding nested selects.
55 continue;
56 } else if (++num_instructions > kMaxInstructionsInBranch) {
57 return false; // bail as soon as we exceed number of allowed instructions
58 }
59 } else {
60 return false;
61 }
62 }
63
64 LOG(FATAL) << "Unreachable";
65 UNREACHABLE();
66 }
67
68 // Returns true if 'block1' and 'block2' are empty and merge into the
69 // same single successor.
BlocksMergeTogether(HBasicBlock * block1,HBasicBlock * block2)70 static bool BlocksMergeTogether(HBasicBlock* block1, HBasicBlock* block2) {
71 return block1->GetSingleSuccessor() == block2->GetSingleSuccessor();
72 }
73
74 // Returns nullptr if `block` has either no phis or there is more than one phi
75 // with different inputs at `index1` and `index2`. Otherwise returns that phi.
GetSingleChangedPhi(HBasicBlock * block,size_t index1,size_t index2)76 static HPhi* GetSingleChangedPhi(HBasicBlock* block, size_t index1, size_t index2) {
77 DCHECK_NE(index1, index2);
78
79 HPhi* select_phi = nullptr;
80 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
81 HPhi* phi = it.Current()->AsPhi();
82 if (phi->InputAt(index1) != phi->InputAt(index2)) {
83 if (select_phi == nullptr) {
84 // First phi with different inputs for the two indices found.
85 select_phi = phi;
86 } else {
87 // More than one phis has different inputs for the two indices.
88 return nullptr;
89 }
90 }
91 }
92 return select_phi;
93 }
94
Run()95 bool HSelectGenerator::Run() {
96 bool didSelect = false;
97 // Select cache with local allocator.
98 ScopedArenaAllocator allocator(graph_->GetArenaStack());
99 ScopedArenaSafeMap<HInstruction*, HSelect*> cache(
100 std::less<HInstruction*>(), allocator.Adapter(kArenaAllocSelectGenerator));
101
102 // Iterate in post order in the unlikely case that removing one occurrence of
103 // the selection pattern empties a branch block of another occurrence.
104 for (HBasicBlock* block : graph_->GetPostOrder()) {
105 if (!block->EndsWithIf()) continue;
106
107 // Find elements of the diamond pattern.
108 HIf* if_instruction = block->GetLastInstruction()->AsIf();
109 HBasicBlock* true_block = if_instruction->IfTrueSuccessor();
110 HBasicBlock* false_block = if_instruction->IfFalseSuccessor();
111 DCHECK_NE(true_block, false_block);
112
113 if (!IsSimpleBlock(true_block) ||
114 !IsSimpleBlock(false_block) ||
115 !BlocksMergeTogether(true_block, false_block)) {
116 continue;
117 }
118 HBasicBlock* merge_block = true_block->GetSingleSuccessor();
119
120 // If the branches are not empty, move instructions in front of the If.
121 // TODO(dbrazdil): This puts an instruction between If and its condition.
122 // Implement moving of conditions to first users if possible.
123 while (!true_block->IsSingleGoto() && !true_block->IsSingleReturn()) {
124 HInstruction* instr = true_block->GetFirstInstruction();
125 DCHECK(!instr->CanThrow());
126 instr->MoveBefore(if_instruction);
127 }
128 while (!false_block->IsSingleGoto() && !false_block->IsSingleReturn()) {
129 HInstruction* instr = false_block->GetFirstInstruction();
130 DCHECK(!instr->CanThrow());
131 instr->MoveBefore(if_instruction);
132 }
133 DCHECK(true_block->IsSingleGoto() || true_block->IsSingleReturn());
134 DCHECK(false_block->IsSingleGoto() || false_block->IsSingleReturn());
135
136 // Find the resulting true/false values.
137 size_t predecessor_index_true = merge_block->GetPredecessorIndexOf(true_block);
138 size_t predecessor_index_false = merge_block->GetPredecessorIndexOf(false_block);
139 DCHECK_NE(predecessor_index_true, predecessor_index_false);
140
141 bool both_successors_return = true_block->IsSingleReturn() && false_block->IsSingleReturn();
142 HPhi* phi = GetSingleChangedPhi(merge_block, predecessor_index_true, predecessor_index_false);
143
144 HInstruction* true_value = nullptr;
145 HInstruction* false_value = nullptr;
146 if (both_successors_return) {
147 true_value = true_block->GetFirstInstruction()->InputAt(0);
148 false_value = false_block->GetFirstInstruction()->InputAt(0);
149 } else if (phi != nullptr) {
150 true_value = phi->InputAt(predecessor_index_true);
151 false_value = phi->InputAt(predecessor_index_false);
152 } else {
153 continue;
154 }
155 DCHECK(both_successors_return || phi != nullptr);
156
157 // Create the Select instruction and insert it in front of the If.
158 HInstruction* condition = if_instruction->InputAt(0);
159 HSelect* select = new (graph_->GetAllocator()) HSelect(condition,
160 true_value,
161 false_value,
162 if_instruction->GetDexPc());
163 if (both_successors_return) {
164 if (true_value->GetType() == DataType::Type::kReference) {
165 DCHECK(false_value->GetType() == DataType::Type::kReference);
166 ReferenceTypePropagation::FixUpInstructionType(select, handle_scope_);
167 }
168 } else if (phi->GetType() == DataType::Type::kReference) {
169 select->SetReferenceTypeInfo(phi->GetReferenceTypeInfo());
170 }
171 block->InsertInstructionBefore(select, if_instruction);
172
173 // Remove the true branch which removes the corresponding Phi
174 // input if needed. If left only with the false branch, the Phi is
175 // automatically removed.
176 if (both_successors_return) {
177 false_block->GetFirstInstruction()->ReplaceInput(select, 0);
178 } else {
179 phi->ReplaceInput(select, predecessor_index_false);
180 }
181
182 bool only_two_predecessors = (merge_block->GetPredecessors().size() == 2u);
183 true_block->DisconnectAndDelete();
184
185 // Merge remaining blocks which are now connected with Goto.
186 DCHECK_EQ(block->GetSingleSuccessor(), false_block);
187 block->MergeWith(false_block);
188 if (!both_successors_return && only_two_predecessors) {
189 DCHECK_EQ(only_two_predecessors, phi->GetBlock() == nullptr);
190 DCHECK_EQ(block->GetSingleSuccessor(), merge_block);
191 block->MergeWith(merge_block);
192 }
193
194 MaybeRecordStat(stats_, MethodCompilationStat::kSelectGenerated);
195
196 // Very simple way of finding common subexpressions in the generated HSelect statements
197 // (since this runs after GVN). Lookup by condition, and reuse latest one if possible
198 // (due to post order, latest select is most likely replacement). If needed, we could
199 // improve this by e.g. using the operands in the map as well.
200 auto it = cache.find(condition);
201 if (it == cache.end()) {
202 cache.Put(condition, select);
203 } else {
204 // Found cached value. See if latest can replace cached in the HIR.
205 HSelect* cached = it->second;
206 DCHECK_EQ(cached->GetCondition(), select->GetCondition());
207 if (cached->GetTrueValue() == select->GetTrueValue() &&
208 cached->GetFalseValue() == select->GetFalseValue() &&
209 select->StrictlyDominates(cached)) {
210 cached->ReplaceWith(select);
211 cached->GetBlock()->RemoveInstruction(cached);
212 }
213 it->second = select; // always cache latest
214 }
215
216 // No need to update dominance information, as we are simplifying
217 // a simple diamond shape, where the join block is merged with the
218 // entry block. Any following blocks would have had the join block
219 // as a dominator, and `MergeWith` handles changing that to the
220 // entry block.
221 didSelect = true;
222 }
223 return didSelect;
224 }
225
226 } // namespace art
227