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