1 /* 2 * Copyright (C) 2017 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 "code_sinking.h" 18 19 #include "common_dominator.h" 20 #include "nodes.h" 21 22 namespace art { 23 24 void CodeSinking::Run() { 25 HBasicBlock* exit = graph_->GetExitBlock(); 26 if (exit == nullptr) { 27 // Infinite loop, just bail. 28 return; 29 } 30 // TODO(ngeoffray): we do not profile branches yet, so use throw instructions 31 // as an indicator of an uncommon branch. 32 for (HBasicBlock* exit_predecessor : exit->GetPredecessors()) { 33 if (exit_predecessor->GetLastInstruction()->IsThrow()) { 34 SinkCodeToUncommonBranch(exit_predecessor); 35 } 36 } 37 } 38 39 static bool IsInterestingInstruction(HInstruction* instruction) { 40 // Instructions from the entry graph (for example constants) are never interesting to move. 41 if (instruction->GetBlock() == instruction->GetBlock()->GetGraph()->GetEntryBlock()) { 42 return false; 43 } 44 // We want to move moveable instructions that cannot throw, as well as 45 // heap stores and allocations. 46 47 // Volatile stores cannot be moved. 48 if (instruction->IsInstanceFieldSet()) { 49 if (instruction->AsInstanceFieldSet()->IsVolatile()) { 50 return false; 51 } 52 } 53 54 // Check allocations first, as they can throw, but it is safe to move them. 55 if (instruction->IsNewInstance() || instruction->IsNewArray()) { 56 return true; 57 } 58 59 // Check it is safe to move ConstructorFence. 60 // (Safe to move ConstructorFence for only protecting the new-instance but not for finals.) 61 if (instruction->IsConstructorFence()) { 62 HConstructorFence* ctor_fence = instruction->AsConstructorFence(); 63 64 // A fence with "0" inputs is dead and should've been removed in a prior pass. 65 DCHECK_NE(0u, ctor_fence->InputCount()); 66 67 return ctor_fence->GetAssociatedAllocation() != nullptr; 68 } 69 70 // All other instructions that can throw cannot be moved. 71 if (instruction->CanThrow()) { 72 return false; 73 } 74 75 // We can only store on local allocations. Other heap references can 76 // be escaping. Note that allocations can escape too, but we only move 77 // allocations if their users can move to, or are in the list of 78 // post dominated blocks. 79 if (instruction->IsInstanceFieldSet()) { 80 if (!instruction->InputAt(0)->IsNewInstance()) { 81 return false; 82 } 83 } 84 85 if (instruction->IsArraySet()) { 86 if (!instruction->InputAt(0)->IsNewArray()) { 87 return false; 88 } 89 } 90 91 // Heap accesses cannot go pass instructions that have memory side effects, which 92 // we are not tracking here. Note that the load/store elimination optimization 93 // runs before this optimization, and should have removed interesting ones. 94 // In theory, we could handle loads of local allocations, but this is currently 95 // hard to test, as LSE removes them. 96 if (instruction->IsStaticFieldGet() || 97 instruction->IsInstanceFieldGet() || 98 instruction->IsArrayGet()) { 99 return false; 100 } 101 102 if (instruction->IsInstanceFieldSet() || 103 instruction->IsArraySet() || 104 instruction->CanBeMoved()) { 105 return true; 106 } 107 return false; 108 } 109 110 static void AddInstruction(HInstruction* instruction, 111 const ArenaBitVector& processed_instructions, 112 const ArenaBitVector& discard_blocks, 113 ArenaVector<HInstruction*>* worklist) { 114 // Add to the work list if the instruction is not in the list of blocks 115 // to discard, hasn't been already processed and is of interest. 116 if (!discard_blocks.IsBitSet(instruction->GetBlock()->GetBlockId()) && 117 !processed_instructions.IsBitSet(instruction->GetId()) && 118 IsInterestingInstruction(instruction)) { 119 worklist->push_back(instruction); 120 } 121 } 122 123 static void AddInputs(HInstruction* instruction, 124 const ArenaBitVector& processed_instructions, 125 const ArenaBitVector& discard_blocks, 126 ArenaVector<HInstruction*>* worklist) { 127 for (HInstruction* input : instruction->GetInputs()) { 128 AddInstruction(input, processed_instructions, discard_blocks, worklist); 129 } 130 } 131 132 static void AddInputs(HBasicBlock* block, 133 const ArenaBitVector& processed_instructions, 134 const ArenaBitVector& discard_blocks, 135 ArenaVector<HInstruction*>* worklist) { 136 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 137 AddInputs(it.Current(), processed_instructions, discard_blocks, worklist); 138 } 139 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { 140 AddInputs(it.Current(), processed_instructions, discard_blocks, worklist); 141 } 142 } 143 144 static bool ShouldFilterUse(HInstruction* instruction, 145 HInstruction* user, 146 const ArenaBitVector& post_dominated) { 147 if (instruction->IsNewInstance()) { 148 return (user->IsInstanceFieldSet() || user->IsConstructorFence()) && 149 (user->InputAt(0) == instruction) && 150 !post_dominated.IsBitSet(user->GetBlock()->GetBlockId()); 151 } else if (instruction->IsNewArray()) { 152 return (user->IsArraySet() || user->IsConstructorFence()) && 153 (user->InputAt(0) == instruction) && 154 !post_dominated.IsBitSet(user->GetBlock()->GetBlockId()); 155 } 156 return false; 157 } 158 159 160 // Find the ideal position for moving `instruction`. If `filter` is true, 161 // we filter out store instructions to that instruction, which are processed 162 // first in the step (3) of the sinking algorithm. 163 // This method is tailored to the sinking algorithm, unlike 164 // the generic HInstruction::MoveBeforeFirstUserAndOutOfLoops. 165 static HInstruction* FindIdealPosition(HInstruction* instruction, 166 const ArenaBitVector& post_dominated, 167 bool filter = false) { 168 DCHECK(!instruction->IsPhi()); // Makes no sense for Phi. 169 170 // Find the target block. 171 CommonDominator finder(/* start_block */ nullptr); 172 for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) { 173 HInstruction* user = use.GetUser(); 174 if (!(filter && ShouldFilterUse(instruction, user, post_dominated))) { 175 HBasicBlock* block = user->GetBlock(); 176 if (user->IsPhi()) { 177 // Special case phis by taking the incoming block for regular ones, 178 // or the dominator for catch phis. 179 block = user->AsPhi()->IsCatchPhi() 180 ? block->GetDominator() 181 : block->GetPredecessors()[use.GetIndex()]; 182 } 183 finder.Update(block); 184 } 185 } 186 for (const HUseListNode<HEnvironment*>& use : instruction->GetEnvUses()) { 187 DCHECK(!use.GetUser()->GetHolder()->IsPhi()); 188 DCHECK(!filter || !ShouldFilterUse(instruction, use.GetUser()->GetHolder(), post_dominated)); 189 finder.Update(use.GetUser()->GetHolder()->GetBlock()); 190 } 191 HBasicBlock* target_block = finder.Get(); 192 if (target_block == nullptr) { 193 // No user we can go next to? Likely a LSE or DCE limitation. 194 return nullptr; 195 } 196 197 // Move to the first dominator not in a loop, if we can. 198 while (target_block->IsInLoop()) { 199 if (!post_dominated.IsBitSet(target_block->GetDominator()->GetBlockId())) { 200 break; 201 } 202 target_block = target_block->GetDominator(); 203 DCHECK(target_block != nullptr); 204 } 205 206 // Find insertion position. No need to filter anymore, as we have found a 207 // target block. 208 HInstruction* insert_pos = nullptr; 209 for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) { 210 if (use.GetUser()->GetBlock() == target_block && 211 (insert_pos == nullptr || use.GetUser()->StrictlyDominates(insert_pos))) { 212 insert_pos = use.GetUser(); 213 } 214 } 215 for (const HUseListNode<HEnvironment*>& use : instruction->GetEnvUses()) { 216 HInstruction* user = use.GetUser()->GetHolder(); 217 if (user->GetBlock() == target_block && 218 (insert_pos == nullptr || user->StrictlyDominates(insert_pos))) { 219 insert_pos = user; 220 } 221 } 222 if (insert_pos == nullptr) { 223 // No user in `target_block`, insert before the control flow instruction. 224 insert_pos = target_block->GetLastInstruction(); 225 DCHECK(insert_pos->IsControlFlow()); 226 // Avoid splitting HCondition from HIf to prevent unnecessary materialization. 227 if (insert_pos->IsIf()) { 228 HInstruction* if_input = insert_pos->AsIf()->InputAt(0); 229 if (if_input == insert_pos->GetPrevious()) { 230 insert_pos = if_input; 231 } 232 } 233 } 234 DCHECK(!insert_pos->IsPhi()); 235 return insert_pos; 236 } 237 238 239 void CodeSinking::SinkCodeToUncommonBranch(HBasicBlock* end_block) { 240 // Local allocator to discard data structures created below at the end of 241 // this optimization. 242 ArenaAllocator allocator(graph_->GetArena()->GetArenaPool()); 243 244 size_t number_of_instructions = graph_->GetCurrentInstructionId(); 245 ArenaVector<HInstruction*> worklist(allocator.Adapter(kArenaAllocMisc)); 246 ArenaBitVector processed_instructions(&allocator, number_of_instructions, /* expandable */ false); 247 ArenaBitVector post_dominated(&allocator, graph_->GetBlocks().size(), /* expandable */ false); 248 ArenaBitVector instructions_that_can_move( 249 &allocator, number_of_instructions, /* expandable */ false); 250 ArenaVector<HInstruction*> move_in_order(allocator.Adapter(kArenaAllocMisc)); 251 252 // Step (1): Visit post order to get a subset of blocks post dominated by `end_block`. 253 // TODO(ngeoffray): Getting the full set of post-dominated shoud be done by 254 // computint the post dominator tree, but that could be too time consuming. Also, 255 // we should start the analysis from blocks dominated by an uncommon branch, but we 256 // don't profile branches yet. 257 bool found_block = false; 258 for (HBasicBlock* block : graph_->GetPostOrder()) { 259 if (block == end_block) { 260 found_block = true; 261 post_dominated.SetBit(block->GetBlockId()); 262 } else if (found_block) { 263 bool is_post_dominated = true; 264 if (block->GetSuccessors().empty()) { 265 // We currently bail for loops. 266 is_post_dominated = false; 267 } else { 268 for (HBasicBlock* successor : block->GetSuccessors()) { 269 if (!post_dominated.IsBitSet(successor->GetBlockId())) { 270 is_post_dominated = false; 271 break; 272 } 273 } 274 } 275 if (is_post_dominated) { 276 post_dominated.SetBit(block->GetBlockId()); 277 } 278 } 279 } 280 281 // Now that we have found a subset of post-dominated blocks, add to the worklist all inputs 282 // of instructions in these blocks that are not themselves in these blocks. 283 // Also find the common dominator of the found post dominated blocks, to help filtering 284 // out un-movable uses in step (2). 285 CommonDominator finder(end_block); 286 for (size_t i = 0, e = graph_->GetBlocks().size(); i < e; ++i) { 287 if (post_dominated.IsBitSet(i)) { 288 finder.Update(graph_->GetBlocks()[i]); 289 AddInputs(graph_->GetBlocks()[i], processed_instructions, post_dominated, &worklist); 290 } 291 } 292 HBasicBlock* common_dominator = finder.Get(); 293 294 // Step (2): iterate over the worklist to find sinking candidates. 295 while (!worklist.empty()) { 296 HInstruction* instruction = worklist.back(); 297 if (processed_instructions.IsBitSet(instruction->GetId())) { 298 // The instruction has already been processed, continue. This happens 299 // when the instruction is the input/user of multiple instructions. 300 worklist.pop_back(); 301 continue; 302 } 303 bool all_users_in_post_dominated_blocks = true; 304 bool can_move = true; 305 // Check users of the instruction. 306 for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) { 307 HInstruction* user = use.GetUser(); 308 if (!post_dominated.IsBitSet(user->GetBlock()->GetBlockId()) && 309 !instructions_that_can_move.IsBitSet(user->GetId())) { 310 all_users_in_post_dominated_blocks = false; 311 // If we've already processed this user, or the user cannot be moved, or 312 // is not dominating the post dominated blocks, bail. 313 // TODO(ngeoffray): The domination check is an approximation. We should 314 // instead check if the dominated blocks post dominate the user's block, 315 // but we do not have post dominance information here. 316 if (processed_instructions.IsBitSet(user->GetId()) || 317 !IsInterestingInstruction(user) || 318 !user->GetBlock()->Dominates(common_dominator)) { 319 can_move = false; 320 break; 321 } 322 } 323 } 324 325 // Check environment users of the instruction. Some of these users require 326 // the instruction not to move. 327 if (all_users_in_post_dominated_blocks) { 328 for (const HUseListNode<HEnvironment*>& use : instruction->GetEnvUses()) { 329 HEnvironment* environment = use.GetUser(); 330 HInstruction* user = environment->GetHolder(); 331 if (!post_dominated.IsBitSet(user->GetBlock()->GetBlockId())) { 332 if (graph_->IsDebuggable() || 333 user->IsDeoptimize() || 334 user->CanThrowIntoCatchBlock() || 335 (user->IsSuspendCheck() && graph_->IsCompilingOsr())) { 336 can_move = false; 337 break; 338 } 339 } 340 } 341 } 342 if (!can_move) { 343 // Instruction cannot be moved, mark it as processed and remove it from the work 344 // list. 345 processed_instructions.SetBit(instruction->GetId()); 346 worklist.pop_back(); 347 } else if (all_users_in_post_dominated_blocks) { 348 // Instruction is a candidate for being sunk. Mark it as such, remove it from the 349 // work list, and add its inputs to the work list. 350 instructions_that_can_move.SetBit(instruction->GetId()); 351 move_in_order.push_back(instruction); 352 processed_instructions.SetBit(instruction->GetId()); 353 worklist.pop_back(); 354 AddInputs(instruction, processed_instructions, post_dominated, &worklist); 355 // Drop the environment use not in the list of post-dominated block. This is 356 // to help step (3) of this optimization, when we start moving instructions 357 // closer to their use. 358 for (const HUseListNode<HEnvironment*>& use : instruction->GetEnvUses()) { 359 HEnvironment* environment = use.GetUser(); 360 HInstruction* user = environment->GetHolder(); 361 if (!post_dominated.IsBitSet(user->GetBlock()->GetBlockId())) { 362 environment->RemoveAsUserOfInput(use.GetIndex()); 363 environment->SetRawEnvAt(use.GetIndex(), nullptr); 364 } 365 } 366 } else { 367 // The information we have on the users was not enough to decide whether the 368 // instruction could be moved. 369 // Add the users to the work list, and keep the instruction in the work list 370 // to process it again once all users have been processed. 371 for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) { 372 AddInstruction(use.GetUser(), processed_instructions, post_dominated, &worklist); 373 } 374 } 375 } 376 377 // Make sure we process instructions in dominated order. This is required for heap 378 // stores. 379 std::sort(move_in_order.begin(), move_in_order.end(), [](HInstruction* a, HInstruction* b) { 380 return b->StrictlyDominates(a); 381 }); 382 383 // Step (3): Try to move sinking candidates. 384 for (HInstruction* instruction : move_in_order) { 385 HInstruction* position = nullptr; 386 if (instruction->IsArraySet() 387 || instruction->IsInstanceFieldSet() 388 || instruction->IsConstructorFence()) { 389 if (!instructions_that_can_move.IsBitSet(instruction->InputAt(0)->GetId())) { 390 // A store can trivially move, but it can safely do so only if the heap 391 // location it stores to can also move. 392 // TODO(ngeoffray): Handle allocation/store cycles by pruning these instructions 393 // from the set and all their inputs. 394 continue; 395 } 396 // Find the position of the instruction we're storing into, filtering out this 397 // store and all other stores to that instruction. 398 position = FindIdealPosition(instruction->InputAt(0), post_dominated, /* filter */ true); 399 400 // The position needs to be dominated by the store, in order for the store to move there. 401 if (position == nullptr || !instruction->GetBlock()->Dominates(position->GetBlock())) { 402 continue; 403 } 404 } else { 405 // Find the ideal position within the post dominated blocks. 406 position = FindIdealPosition(instruction, post_dominated); 407 if (position == nullptr) { 408 continue; 409 } 410 } 411 // Bail if we could not find a position in the post dominated blocks (for example, 412 // if there are multiple users whose common dominator is not in the list of 413 // post dominated blocks). 414 if (!post_dominated.IsBitSet(position->GetBlock()->GetBlockId())) { 415 continue; 416 } 417 MaybeRecordStat(MethodCompilationStat::kInstructionSunk); 418 instruction->MoveBefore(position, /* ensure_safety */ false); 419 } 420 } 421 422 } // namespace art 423