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