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 "cha_guard_optimization.h" 18 19 namespace art { 20 21 // Note we can only do CHA guard elimination/motion in a single pass, since 22 // if a guard is not removed, another guard might be removed due to 23 // the existence of the first guard. The first guard should not be further 24 // removed in another pass. For example, due to further optimizations, 25 // a receiver of a guard might turn out to be a parameter value, or defined at 26 // a different site, which makes the guard removable as a result. However 27 // it's not safe to remove the guard in another pass since another guard might 28 // have been removed due to the existence of this guard. 29 // 30 // As a consequence, we decided not to rely on other passes to remove them 31 // (such as GVN or instruction simplifier). 32 33 class CHAGuardVisitor : HGraphVisitor { 34 public: 35 explicit CHAGuardVisitor(HGraph* graph) 36 : HGraphVisitor(graph), 37 block_has_cha_guard_(GetGraph()->GetBlocks().size(), 38 0, 39 graph->GetAllocator()->Adapter(kArenaAllocCHA)), 40 instruction_iterator_(nullptr) { 41 number_of_guards_to_visit_ = GetGraph()->GetNumberOfCHAGuards(); 42 DCHECK_NE(number_of_guards_to_visit_, 0u); 43 // Will recount number of guards during guard optimization. 44 GetGraph()->SetNumberOfCHAGuards(0); 45 } 46 47 void VisitShouldDeoptimizeFlag(HShouldDeoptimizeFlag* flag) OVERRIDE; 48 49 void VisitBasicBlock(HBasicBlock* block) OVERRIDE; 50 51 private: 52 void RemoveGuard(HShouldDeoptimizeFlag* flag); 53 // Return true if `flag` is removed. 54 bool OptimizeForParameter(HShouldDeoptimizeFlag* flag, HInstruction* receiver); 55 // Return true if `flag` is removed. 56 bool OptimizeWithDominatingGuard(HShouldDeoptimizeFlag* flag, HInstruction* receiver); 57 // Return true if `flag` is hoisted. 58 bool HoistGuard(HShouldDeoptimizeFlag* flag, HInstruction* receiver); 59 60 // Record if each block has any CHA guard. It's updated during the 61 // reverse post order visit. Use int instead of bool since ArenaVector 62 // does not support bool. 63 ArenaVector<int> block_has_cha_guard_; 64 65 // The iterator that's being used for this visitor. Need it to manually 66 // advance the iterator due to removing/moving more than one instruction. 67 HInstructionIterator* instruction_iterator_; 68 69 // Used to short-circuit the pass when there is no more guards left to visit. 70 uint32_t number_of_guards_to_visit_; 71 72 DISALLOW_COPY_AND_ASSIGN(CHAGuardVisitor); 73 }; 74 75 void CHAGuardVisitor::VisitBasicBlock(HBasicBlock* block) { 76 if (number_of_guards_to_visit_ == 0) { 77 return; 78 } 79 // Skip phis, just iterate through instructions. 80 HInstructionIterator it(block->GetInstructions()); 81 instruction_iterator_ = ⁢ 82 for (; !it.Done(); it.Advance()) { 83 DCHECK(it.Current()->IsInBlock()); 84 it.Current()->Accept(this); 85 } 86 } 87 88 void CHAGuardVisitor::RemoveGuard(HShouldDeoptimizeFlag* flag) { 89 HBasicBlock* block = flag->GetBlock(); 90 HInstruction* compare = flag->GetNext(); 91 DCHECK(compare->IsNotEqual()); 92 HInstruction* deopt = compare->GetNext(); 93 DCHECK(deopt->IsDeoptimize()); 94 95 // Advance instruction iterator first before we remove the guard. 96 // We need to do it twice since we remove three instructions and the 97 // visitor is responsible for advancing it once. 98 instruction_iterator_->Advance(); 99 instruction_iterator_->Advance(); 100 block->RemoveInstruction(deopt); 101 block->RemoveInstruction(compare); 102 block->RemoveInstruction(flag); 103 } 104 105 bool CHAGuardVisitor::OptimizeForParameter(HShouldDeoptimizeFlag* flag, 106 HInstruction* receiver) { 107 // If some compiled code is invalidated by CHA due to class loading, the 108 // compiled code will not be entered anymore. So the very fact that the 109 // compiled code is invoked guarantees that a parameter receiver conforms 110 // to all the CHA devirtualization assumptions made by the compiled code, 111 // since all parameter receivers pre-exist any (potential) invalidation of 112 // the compiled code. 113 // 114 // TODO: allow more cases such as a phi whose inputs are all parameters. 115 if (receiver->IsParameterValue()) { 116 RemoveGuard(flag); 117 return true; 118 } 119 return false; 120 } 121 122 bool CHAGuardVisitor::OptimizeWithDominatingGuard(HShouldDeoptimizeFlag* flag, 123 HInstruction* receiver) { 124 // If there is another guard that dominates the current guard, and 125 // that guard is dominated by receiver's definition, then the current 126 // guard can be eliminated, since receiver must pre-exist that other 127 // guard, and passing that guard guarantees that receiver conforms to 128 // all the CHA devirtualization assumptions. 129 HBasicBlock* dominator = flag->GetBlock(); 130 HBasicBlock* receiver_def_block = receiver->GetBlock(); 131 132 // Complexity of the following algorithm: 133 // We potentially need to traverse the full dominator chain to receiver_def_block, 134 // plus a (partial) linear search within one block for each guard. 135 // So the worst case for each guard is bounded by the size of the 136 // biggest block plus the depth of the dominating tree. 137 138 while (dominator != receiver_def_block) { 139 if (block_has_cha_guard_[dominator->GetBlockId()] == 1) { 140 RemoveGuard(flag); 141 return true; 142 } 143 dominator = dominator->GetDominator(); 144 } 145 146 // At this point dominator is the block where receiver is defined. 147 // We do a linear search within dominator to see if there is a guard after 148 // receiver's definition. 149 HInstruction* instruction; 150 if (dominator == flag->GetBlock()) { 151 // Flag and receiver are defined in the same block. Search backward from 152 // the current guard. 153 instruction = flag->GetPrevious(); 154 } else { 155 // Search backward from the last instruction of that dominator. 156 instruction = dominator->GetLastInstruction(); 157 } 158 while (instruction != receiver) { 159 if (instruction == nullptr) { 160 // receiver must be defined in this block, we didn't find it 161 // in the instruction list, so it must be a Phi. 162 DCHECK(receiver->IsPhi()); 163 break; 164 } 165 if (instruction->IsShouldDeoptimizeFlag()) { 166 RemoveGuard(flag); 167 return true; 168 } 169 instruction = instruction->GetPrevious(); 170 } 171 return false; 172 } 173 174 bool CHAGuardVisitor::HoistGuard(HShouldDeoptimizeFlag* flag, 175 HInstruction* receiver) { 176 // If receiver is loop invariant, we can hoist the guard out of the 177 // loop since passing a guard before entering the loop guarantees that 178 // receiver conforms to all the CHA devirtualization assumptions. 179 // We only hoist guards out of the inner loop since that offers most of the 180 // benefit and it might help remove other guards in the inner loop. 181 HBasicBlock* block = flag->GetBlock(); 182 HLoopInformation* loop_info = block->GetLoopInformation(); 183 if (loop_info != nullptr && 184 !loop_info->IsIrreducible() && 185 loop_info->IsDefinedOutOfTheLoop(receiver)) { 186 HInstruction* compare = flag->GetNext(); 187 DCHECK(compare->IsNotEqual()); 188 HInstruction* deopt = compare->GetNext(); 189 DCHECK(deopt->IsDeoptimize()); 190 191 // Advance instruction iterator first before we move the guard. 192 // We need to do it twice since we move three instructions and the 193 // visitor is responsible for advancing it once. 194 instruction_iterator_->Advance(); 195 instruction_iterator_->Advance(); 196 197 HBasicBlock* pre_header = loop_info->GetPreHeader(); 198 flag->MoveBefore(pre_header->GetLastInstruction()); 199 compare->MoveBefore(pre_header->GetLastInstruction()); 200 201 block->RemoveInstruction(deopt); 202 HInstruction* suspend = loop_info->GetSuspendCheck(); 203 // Need a new deoptimize instruction that copies the environment 204 // of the suspend instruction for the loop. 205 HDeoptimize* deoptimize = new (GetGraph()->GetAllocator()) HDeoptimize( 206 GetGraph()->GetAllocator(), compare, DeoptimizationKind::kCHA, suspend->GetDexPc()); 207 pre_header->InsertInstructionBefore(deoptimize, pre_header->GetLastInstruction()); 208 deoptimize->CopyEnvironmentFromWithLoopPhiAdjustment( 209 suspend->GetEnvironment(), loop_info->GetHeader()); 210 block_has_cha_guard_[pre_header->GetBlockId()] = 1; 211 GetGraph()->IncrementNumberOfCHAGuards(); 212 return true; 213 } 214 return false; 215 } 216 217 void CHAGuardVisitor::VisitShouldDeoptimizeFlag(HShouldDeoptimizeFlag* flag) { 218 number_of_guards_to_visit_--; 219 HInstruction* receiver = flag->InputAt(0); 220 // Don't need the receiver anymore. 221 flag->RemoveInputAt(0); 222 if (receiver->IsNullCheck()) { 223 receiver = receiver->InputAt(0); 224 } 225 226 if (OptimizeForParameter(flag, receiver)) { 227 DCHECK(!flag->IsInBlock()); 228 return; 229 } 230 if (OptimizeWithDominatingGuard(flag, receiver)) { 231 DCHECK(!flag->IsInBlock()); 232 return; 233 } 234 if (HoistGuard(flag, receiver)) { 235 DCHECK(flag->IsInBlock()); 236 return; 237 } 238 239 // Need to keep the CHA guard in place. 240 block_has_cha_guard_[flag->GetBlock()->GetBlockId()] = 1; 241 GetGraph()->IncrementNumberOfCHAGuards(); 242 } 243 244 void CHAGuardOptimization::Run() { 245 if (graph_->GetNumberOfCHAGuards() == 0) { 246 return; 247 } 248 CHAGuardVisitor visitor(graph_); 249 for (HBasicBlock* block : graph_->GetReversePostOrder()) { 250 visitor.VisitBasicBlock(block); 251 } 252 } 253 254 } // namespace art 255
