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