1827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray/* 2827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray * Copyright (C) 2014 The Android Open Source Project 3827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray * 4827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray * Licensed under the Apache License, Version 2.0 (the "License"); 5827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray * you may not use this file except in compliance with the License. 6827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray * You may obtain a copy of the License at 7827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray * 8827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray * http://www.apache.org/licenses/LICENSE-2.0 9827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray * 10827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray * Unless required by applicable law or agreed to in writing, software 11827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray * distributed under the License is distributed on an "AS IS" BASIS, 12827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray * See the License for the specific language governing permissions and 14827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray * limitations under the License. 15827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray */ 16827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray 17827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray#include "side_effects_analysis.h" 18827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray 19827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffraynamespace art { 20827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray 21827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffrayvoid SideEffectsAnalysis::Run() { 22276d9daaedfbff716339f94d55e6eff98b7434c6Nicolas Geoffray // Inlining might have created more blocks, so we need to increase the size 23276d9daaedfbff716339f94d55e6eff98b7434c6Nicolas Geoffray // if needed. 24276d9daaedfbff716339f94d55e6eff98b7434c6Nicolas Geoffray block_effects_.SetSize(graph_->GetBlocks().Size()); 25276d9daaedfbff716339f94d55e6eff98b7434c6Nicolas Geoffray loop_effects_.SetSize(graph_->GetBlocks().Size()); 26276d9daaedfbff716339f94d55e6eff98b7434c6Nicolas Geoffray 27827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray if (kIsDebugBuild) { 28827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 29827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray HBasicBlock* block = it.Current(); 30827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray SideEffects effects = GetBlockEffects(block); 31827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray DCHECK(!effects.HasSideEffects() && !effects.HasDependencies()); 32827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray if (block->IsLoopHeader()) { 33827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray effects = GetLoopEffects(block); 34827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray DCHECK(!effects.HasSideEffects() && !effects.HasDependencies()); 35827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray } 36827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray } 37827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray } 38827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray 39827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray // Do a post order visit to ensure we visit a loop header after its loop body. 40827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray for (HPostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 41827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray HBasicBlock* block = it.Current(); 42827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray 43827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray SideEffects effects = SideEffects::None(); 44827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray // Update `effects` with the side effects of all instructions in this block. 45827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray for (HInstructionIterator inst_it(block->GetInstructions()); !inst_it.Done(); 46827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray inst_it.Advance()) { 47827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray HInstruction* instruction = inst_it.Current(); 48827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray effects = effects.Union(instruction->GetSideEffects()); 49827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray if (effects.HasAllSideEffects()) { 50827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray break; 51827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray } 52827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray } 53827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray 54827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray block_effects_.Put(block->GetBlockId(), effects); 55827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray 56827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray if (block->IsLoopHeader()) { 57827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray // The side effects of the loop header are part of the loop. 58827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray UpdateLoopEffects(block->GetLoopInformation(), effects); 59827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray HBasicBlock* pre_header = block->GetLoopInformation()->GetPreHeader(); 60827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray if (pre_header->IsInLoop()) { 61827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray // Update the side effects of the outer loop with the side effects of the inner loop. 62827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray // Note that this works because we know all the blocks of the inner loop are visited 63827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray // before the loop header of the outer loop. 64827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray UpdateLoopEffects(pre_header->GetLoopInformation(), GetLoopEffects(block)); 65827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray } 66827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray } else if (block->IsInLoop()) { 67827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray // Update the side effects of the loop with the side effects of this block. 68827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray UpdateLoopEffects(block->GetLoopInformation(), effects); 69827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray } 70827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray } 71827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray has_run_ = true; 72827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray} 73827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray 74827eedbfa882496407375f22b08243a38a5bd53bNicolas GeoffraySideEffects SideEffectsAnalysis::GetLoopEffects(HBasicBlock* block) const { 75827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray DCHECK(block->IsLoopHeader()); 76827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray return loop_effects_.Get(block->GetBlockId()); 77827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray} 78827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray 79827eedbfa882496407375f22b08243a38a5bd53bNicolas GeoffraySideEffects SideEffectsAnalysis::GetBlockEffects(HBasicBlock* block) const { 80827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray return block_effects_.Get(block->GetBlockId()); 81827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray} 82827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray 83827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffrayvoid SideEffectsAnalysis::UpdateLoopEffects(HLoopInformation* info, SideEffects effects) { 84827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray int id = info->GetHeader()->GetBlockId(); 85827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray loop_effects_.Put(id, loop_effects_.Get(id).Union(effects)); 86827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray} 87827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray 88827eedbfa882496407375f22b08243a38a5bd53bNicolas Geoffray} // namespace art 89