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