Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2014 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 "ssa_liveness_analysis.h" |
Nicolas Geoffray | 31d76b4 | 2014-06-09 15:02:22 +0100 | [diff] [blame] | 18 | |
Ian Rogers | e77493c | 2014-08-20 15:08:45 -0700 | [diff] [blame] | 19 | #include "base/bit_vector-inl.h" |
Nicolas Geoffray | 31d76b4 | 2014-06-09 15:02:22 +0100 | [diff] [blame] | 20 | #include "code_generator.h" |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 21 | #include "nodes.h" |
| 22 | |
| 23 | namespace art { |
| 24 | |
| 25 | void SsaLivenessAnalysis::Analyze() { |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 26 | LinearizeGraph(); |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 27 | NumberInstructions(); |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 28 | ComputeLiveness(); |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 29 | } |
| 30 | |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 31 | static bool IsLoop(HLoopInformation* info) { |
| 32 | return info != nullptr; |
| 33 | } |
| 34 | |
| 35 | static bool InSameLoop(HLoopInformation* first_loop, HLoopInformation* second_loop) { |
| 36 | return first_loop == second_loop; |
| 37 | } |
| 38 | |
| 39 | static bool IsInnerLoop(HLoopInformation* outer, HLoopInformation* inner) { |
| 40 | return (inner != outer) |
| 41 | && (inner != nullptr) |
| 42 | && (outer != nullptr) |
| 43 | && inner->IsIn(*outer); |
| 44 | } |
| 45 | |
Nicolas Geoffray | a8eed3a | 2014-11-24 17:47:10 +0000 | [diff] [blame] | 46 | static void AddToListForLinearization(GrowableArray<HBasicBlock*>* worklist, HBasicBlock* block) { |
| 47 | size_t insert_at = worklist->Size(); |
| 48 | HLoopInformation* block_loop = block->GetLoopInformation(); |
| 49 | for (; insert_at > 0; --insert_at) { |
| 50 | HBasicBlock* current = worklist->Get(insert_at - 1); |
| 51 | HLoopInformation* current_loop = current->GetLoopInformation(); |
| 52 | if (InSameLoop(block_loop, current_loop) |
| 53 | || !IsLoop(current_loop) |
| 54 | || IsInnerLoop(current_loop, block_loop)) { |
| 55 | // The block can be processed immediately. |
| 56 | break; |
Nicolas Geoffray | e50fa58 | 2014-11-24 17:44:15 +0000 | [diff] [blame] | 57 | } |
Nicolas Geoffray | e50fa58 | 2014-11-24 17:44:15 +0000 | [diff] [blame] | 58 | } |
Nicolas Geoffray | a8eed3a | 2014-11-24 17:47:10 +0000 | [diff] [blame] | 59 | worklist->InsertAt(insert_at, block); |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 60 | } |
| 61 | |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 62 | void SsaLivenessAnalysis::LinearizeGraph() { |
Nicolas Geoffray | a8eed3a | 2014-11-24 17:47:10 +0000 | [diff] [blame] | 63 | // Create a reverse post ordering with the following properties: |
| 64 | // - Blocks in a loop are consecutive, |
| 65 | // - Back-edge is the last block before loop exits. |
| 66 | |
| 67 | // (1): Record the number of forward predecessors for each block. This is to |
| 68 | // ensure the resulting order is reverse post order. We could use the |
| 69 | // current reverse post order in the graph, but it would require making |
| 70 | // order queries to a GrowableArray, which is not the best data structure |
| 71 | // for it. |
| 72 | GrowableArray<uint32_t> forward_predecessors(graph_.GetArena(), graph_.GetBlocks().Size()); |
| 73 | forward_predecessors.SetSize(graph_.GetBlocks().Size()); |
| 74 | for (size_t i = 0, e = graph_.GetBlocks().Size(); i < e; ++i) { |
| 75 | HBasicBlock* block = graph_.GetBlocks().Get(i); |
| 76 | size_t number_of_forward_predecessors = block->GetPredecessors().Size(); |
| 77 | if (block->IsLoopHeader()) { |
| 78 | // We rely on having simplified the CFG. |
| 79 | DCHECK_EQ(1u, block->GetLoopInformation()->NumberOfBackEdges()); |
| 80 | number_of_forward_predecessors--; |
| 81 | } |
| 82 | forward_predecessors.Put(block->GetBlockId(), number_of_forward_predecessors); |
| 83 | } |
| 84 | |
| 85 | // (2): Following a worklist approach, first start with the entry block, and |
| 86 | // iterate over the successors. When all non-back edge predecessors of a |
| 87 | // successor block are visited, the successor block is added in the worklist |
| 88 | // following an order that satisfies the requirements to build our linear graph. |
| 89 | GrowableArray<HBasicBlock*> worklist(graph_.GetArena(), 1); |
| 90 | worklist.Add(graph_.GetEntryBlock()); |
| 91 | do { |
| 92 | HBasicBlock* current = worklist.Pop(); |
| 93 | linear_order_.Add(current); |
| 94 | for (size_t i = 0, e = current->GetSuccessors().Size(); i < e; ++i) { |
| 95 | HBasicBlock* successor = current->GetSuccessors().Get(i); |
| 96 | int block_id = successor->GetBlockId(); |
| 97 | size_t number_of_remaining_predecessors = forward_predecessors.Get(block_id); |
| 98 | if (number_of_remaining_predecessors == 1) { |
| 99 | AddToListForLinearization(&worklist, successor); |
| 100 | } |
| 101 | forward_predecessors.Put(block_id, number_of_remaining_predecessors - 1); |
| 102 | } |
| 103 | } while (!worklist.IsEmpty()); |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 104 | } |
| 105 | |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 106 | void SsaLivenessAnalysis::NumberInstructions() { |
| 107 | int ssa_index = 0; |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 108 | size_t lifetime_position = 0; |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 109 | // Each instruction gets a lifetime position, and a block gets a lifetime |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 110 | // start and end position. Non-phi instructions have a distinct lifetime position than |
| 111 | // the block they are in. Phi instructions have the lifetime start of their block as |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 112 | // lifetime position. |
| 113 | // |
| 114 | // Because the register allocator will insert moves in the graph, we need |
| 115 | // to differentiate between the start and end of an instruction. Adding 2 to |
| 116 | // the lifetime position for each instruction ensures the start of an |
| 117 | // instruction is different than the end of the previous instruction. |
Nicolas Geoffray | 31d76b4 | 2014-06-09 15:02:22 +0100 | [diff] [blame] | 118 | for (HLinearOrderIterator it(*this); !it.Done(); it.Advance()) { |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 119 | HBasicBlock* block = it.Current(); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 120 | block->SetLifetimeStart(lifetime_position); |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 121 | |
Andreas Gampe | 277ccbd | 2014-11-03 21:36:10 -0800 | [diff] [blame] | 122 | for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { |
| 123 | HInstruction* current = inst_it.Current(); |
Nicolas Geoffray | c0572a4 | 2015-02-06 14:35:25 +0000 | [diff] [blame] | 124 | codegen_->AllocateLocations(current); |
Nicolas Geoffray | 31d76b4 | 2014-06-09 15:02:22 +0100 | [diff] [blame] | 125 | LocationSummary* locations = current->GetLocations(); |
| 126 | if (locations != nullptr && locations->Out().IsValid()) { |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 127 | instructions_from_ssa_index_.Add(current); |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 128 | current->SetSsaIndex(ssa_index++); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 129 | current->SetLiveInterval( |
Mingyao Yang | 296bd60 | 2014-10-06 16:47:28 -0700 | [diff] [blame] | 130 | LiveInterval::MakeInterval(graph_.GetArena(), current->GetType(), current)); |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 131 | } |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 132 | current->SetLifetimePosition(lifetime_position); |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 133 | } |
Nicolas Geoffray | ec7e472 | 2014-06-06 11:24:33 +0100 | [diff] [blame] | 134 | lifetime_position += 2; |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 135 | |
Nicolas Geoffray | 31d76b4 | 2014-06-09 15:02:22 +0100 | [diff] [blame] | 136 | // Add a null marker to notify we are starting a block. |
| 137 | instructions_from_lifetime_position_.Add(nullptr); |
| 138 | |
Andreas Gampe | 277ccbd | 2014-11-03 21:36:10 -0800 | [diff] [blame] | 139 | for (HInstructionIterator inst_it(block->GetInstructions()); !inst_it.Done(); |
| 140 | inst_it.Advance()) { |
| 141 | HInstruction* current = inst_it.Current(); |
Nicolas Geoffray | c0572a4 | 2015-02-06 14:35:25 +0000 | [diff] [blame] | 142 | codegen_->AllocateLocations(current); |
Nicolas Geoffray | 31d76b4 | 2014-06-09 15:02:22 +0100 | [diff] [blame] | 143 | LocationSummary* locations = current->GetLocations(); |
| 144 | if (locations != nullptr && locations->Out().IsValid()) { |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 145 | instructions_from_ssa_index_.Add(current); |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 146 | current->SetSsaIndex(ssa_index++); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 147 | current->SetLiveInterval( |
Mingyao Yang | 296bd60 | 2014-10-06 16:47:28 -0700 | [diff] [blame] | 148 | LiveInterval::MakeInterval(graph_.GetArena(), current->GetType(), current)); |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 149 | } |
Nicolas Geoffray | 31d76b4 | 2014-06-09 15:02:22 +0100 | [diff] [blame] | 150 | instructions_from_lifetime_position_.Add(current); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 151 | current->SetLifetimePosition(lifetime_position); |
| 152 | lifetime_position += 2; |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 153 | } |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 154 | |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 155 | block->SetLifetimeEnd(lifetime_position); |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 156 | } |
| 157 | number_of_ssa_values_ = ssa_index; |
| 158 | } |
| 159 | |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 160 | void SsaLivenessAnalysis::ComputeLiveness() { |
Nicolas Geoffray | 31d76b4 | 2014-06-09 15:02:22 +0100 | [diff] [blame] | 161 | for (HLinearOrderIterator it(*this); !it.Done(); it.Advance()) { |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 162 | HBasicBlock* block = it.Current(); |
| 163 | block_infos_.Put( |
| 164 | block->GetBlockId(), |
| 165 | new (graph_.GetArena()) BlockInfo(graph_.GetArena(), *block, number_of_ssa_values_)); |
| 166 | } |
| 167 | |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 168 | // Compute the live ranges, as well as the initial live_in, live_out, and kill sets. |
| 169 | // This method does not handle backward branches for the sets, therefore live_in |
| 170 | // and live_out sets are not yet correct. |
| 171 | ComputeLiveRanges(); |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 172 | |
| 173 | // Do a fixed point calculation to take into account backward branches, |
| 174 | // that will update live_in of loop headers, and therefore live_out and live_in |
| 175 | // of blocks in the loop. |
| 176 | ComputeLiveInAndLiveOutSets(); |
| 177 | } |
| 178 | |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 179 | void SsaLivenessAnalysis::ComputeLiveRanges() { |
| 180 | // Do a post order visit, adding inputs of instructions live in the block where |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 181 | // that instruction is defined, and killing instructions that are being visited. |
Nicolas Geoffray | 31d76b4 | 2014-06-09 15:02:22 +0100 | [diff] [blame] | 182 | for (HLinearPostOrderIterator it(*this); !it.Done(); it.Advance()) { |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 183 | HBasicBlock* block = it.Current(); |
| 184 | |
| 185 | BitVector* kill = GetKillSet(*block); |
| 186 | BitVector* live_in = GetLiveInSet(*block); |
| 187 | |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 188 | // Set phi inputs of successors of this block corresponding to this block |
| 189 | // as live_in. |
| 190 | for (size_t i = 0, e = block->GetSuccessors().Size(); i < e; ++i) { |
| 191 | HBasicBlock* successor = block->GetSuccessors().Get(i); |
| 192 | live_in->Union(GetLiveInSet(*successor)); |
| 193 | size_t phi_input_index = successor->GetPredecessorIndexOf(block); |
Andreas Gampe | 277ccbd | 2014-11-03 21:36:10 -0800 | [diff] [blame] | 194 | for (HInstructionIterator inst_it(successor->GetPhis()); !inst_it.Done(); inst_it.Advance()) { |
| 195 | HInstruction* phi = inst_it.Current(); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 196 | HInstruction* input = phi->InputAt(phi_input_index); |
Nicolas Geoffray | 31d76b4 | 2014-06-09 15:02:22 +0100 | [diff] [blame] | 197 | input->GetLiveInterval()->AddPhiUse(phi, phi_input_index, block); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 198 | // A phi input whose last user is the phi dies at the end of the predecessor block, |
| 199 | // and not at the phi's lifetime position. |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 200 | live_in->SetBit(input->GetSsaIndex()); |
| 201 | } |
| 202 | } |
| 203 | |
| 204 | // Add a range that covers this block to all instructions live_in because of successors. |
Nicolas Geoffray | 8ddb00c | 2014-09-29 12:00:40 +0100 | [diff] [blame] | 205 | // Instructions defined in this block will have their start of the range adjusted. |
Vladimir Marko | a5b8fde | 2014-05-23 15:16:44 +0100 | [diff] [blame] | 206 | for (uint32_t idx : live_in->Indexes()) { |
| 207 | HInstruction* current = instructions_from_ssa_index_.Get(idx); |
| 208 | current->GetLiveInterval()->AddRange(block->GetLifetimeStart(), block->GetLifetimeEnd()); |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 209 | } |
| 210 | |
Andreas Gampe | 277ccbd | 2014-11-03 21:36:10 -0800 | [diff] [blame] | 211 | for (HBackwardInstructionIterator back_it(block->GetInstructions()); !back_it.Done(); |
| 212 | back_it.Advance()) { |
| 213 | HInstruction* current = back_it.Current(); |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 214 | if (current->HasSsaIndex()) { |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 215 | // Kill the instruction and shorten its interval. |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 216 | kill->SetBit(current->GetSsaIndex()); |
| 217 | live_in->ClearBit(current->GetSsaIndex()); |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 218 | current->GetLiveInterval()->SetFrom(current->GetLifetimePosition()); |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 219 | } |
| 220 | |
| 221 | // All inputs of an instruction must be live. |
| 222 | for (size_t i = 0, e = current->InputCount(); i < e; ++i) { |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 223 | HInstruction* input = current->InputAt(i); |
Nicolas Geoffray | e503832 | 2014-07-04 09:41:32 +0100 | [diff] [blame] | 224 | // Some instructions 'inline' their inputs, that is they do not need |
| 225 | // to be materialized. |
| 226 | if (input->HasSsaIndex()) { |
| 227 | live_in->SetBit(input->GetSsaIndex()); |
| 228 | input->GetLiveInterval()->AddUse(current, i, false); |
| 229 | } |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 230 | } |
| 231 | |
| 232 | if (current->HasEnvironment()) { |
| 233 | // All instructions in the environment must be live. |
David Brazdil | ed59619 | 2015-01-23 10:39:45 +0000 | [diff] [blame] | 234 | HEnvironment* environment = current->GetEnvironment(); |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 235 | for (size_t i = 0, e = environment->Size(); i < e; ++i) { |
David Brazdil | ed59619 | 2015-01-23 10:39:45 +0000 | [diff] [blame] | 236 | HInstruction* instruction = environment->GetInstructionAt(i); |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 237 | if (instruction != nullptr) { |
| 238 | DCHECK(instruction->HasSsaIndex()); |
| 239 | live_in->SetBit(instruction->GetSsaIndex()); |
Nicolas Geoffray | 31d76b4 | 2014-06-09 15:02:22 +0100 | [diff] [blame] | 240 | instruction->GetLiveInterval()->AddUse(current, i, true); |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 241 | } |
| 242 | } |
| 243 | } |
| 244 | } |
| 245 | |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 246 | // Kill phis defined in this block. |
Andreas Gampe | 277ccbd | 2014-11-03 21:36:10 -0800 | [diff] [blame] | 247 | for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { |
| 248 | HInstruction* current = inst_it.Current(); |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 249 | if (current->HasSsaIndex()) { |
| 250 | kill->SetBit(current->GetSsaIndex()); |
| 251 | live_in->ClearBit(current->GetSsaIndex()); |
Nicolas Geoffray | 31d76b4 | 2014-06-09 15:02:22 +0100 | [diff] [blame] | 252 | LiveInterval* interval = current->GetLiveInterval(); |
| 253 | DCHECK((interval->GetFirstRange() == nullptr) |
| 254 | || (interval->GetStart() == current->GetLifetimePosition())); |
| 255 | interval->SetFrom(current->GetLifetimePosition()); |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 256 | } |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 257 | } |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 258 | |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 259 | if (block->IsLoopHeader()) { |
| 260 | HBasicBlock* back_edge = block->GetLoopInformation()->GetBackEdges().Get(0); |
| 261 | // For all live_in instructions at the loop header, we need to create a range |
| 262 | // that covers the full loop. |
Vladimir Marko | a5b8fde | 2014-05-23 15:16:44 +0100 | [diff] [blame] | 263 | for (uint32_t idx : live_in->Indexes()) { |
| 264 | HInstruction* current = instructions_from_ssa_index_.Get(idx); |
| 265 | current->GetLiveInterval()->AddLoopRange(block->GetLifetimeStart(), |
| 266 | back_edge->GetLifetimeEnd()); |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 267 | } |
| 268 | } |
| 269 | } |
| 270 | } |
| 271 | |
| 272 | void SsaLivenessAnalysis::ComputeLiveInAndLiveOutSets() { |
| 273 | bool changed; |
| 274 | do { |
| 275 | changed = false; |
| 276 | |
| 277 | for (HPostOrderIterator it(graph_); !it.Done(); it.Advance()) { |
| 278 | const HBasicBlock& block = *it.Current(); |
| 279 | |
| 280 | // The live_in set depends on the kill set (which does not |
| 281 | // change in this loop), and the live_out set. If the live_out |
| 282 | // set does not change, there is no need to update the live_in set. |
| 283 | if (UpdateLiveOut(block) && UpdateLiveIn(block)) { |
| 284 | changed = true; |
| 285 | } |
| 286 | } |
| 287 | } while (changed); |
| 288 | } |
| 289 | |
| 290 | bool SsaLivenessAnalysis::UpdateLiveOut(const HBasicBlock& block) { |
| 291 | BitVector* live_out = GetLiveOutSet(block); |
| 292 | bool changed = false; |
| 293 | // The live_out set of a block is the union of live_in sets of its successors. |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 294 | for (size_t i = 0, e = block.GetSuccessors().Size(); i < e; ++i) { |
| 295 | HBasicBlock* successor = block.GetSuccessors().Get(i); |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 296 | if (live_out->Union(GetLiveInSet(*successor))) { |
| 297 | changed = true; |
| 298 | } |
| 299 | } |
| 300 | return changed; |
| 301 | } |
| 302 | |
| 303 | |
| 304 | bool SsaLivenessAnalysis::UpdateLiveIn(const HBasicBlock& block) { |
| 305 | BitVector* live_out = GetLiveOutSet(block); |
| 306 | BitVector* kill = GetKillSet(block); |
| 307 | BitVector* live_in = GetLiveInSet(block); |
| 308 | // If live_out is updated (because of backward branches), we need to make |
| 309 | // sure instructions in live_out are also in live_in, unless they are killed |
| 310 | // by this block. |
| 311 | return live_in->UnionIfNotIn(live_out, kill); |
| 312 | } |
| 313 | |
Nicolas Geoffray | da02afe | 2015-02-11 02:29:42 +0000 | [diff] [blame^] | 314 | static int RegisterOrLowRegister(Location location) { |
| 315 | return location.IsPair() ? location.low() : location.reg(); |
| 316 | } |
| 317 | |
Nicolas Geoffray | 01ef345 | 2014-10-01 11:32:17 +0100 | [diff] [blame] | 318 | int LiveInterval::FindFirstRegisterHint(size_t* free_until) const { |
Nicolas Geoffray | da02afe | 2015-02-11 02:29:42 +0000 | [diff] [blame^] | 319 | DCHECK(!IsHighInterval()); |
Nicolas Geoffray | 01ef345 | 2014-10-01 11:32:17 +0100 | [diff] [blame] | 320 | if (GetParent() == this && defined_by_ != nullptr) { |
| 321 | // This is the first interval for the instruction. Try to find |
| 322 | // a register based on its definition. |
| 323 | DCHECK_EQ(defined_by_->GetLiveInterval(), this); |
| 324 | int hint = FindHintAtDefinition(); |
| 325 | if (hint != kNoRegister && free_until[hint] > GetStart()) { |
| 326 | return hint; |
| 327 | } |
| 328 | } |
| 329 | |
| 330 | UsePosition* use = first_use_; |
| 331 | size_t start = GetStart(); |
| 332 | size_t end = GetEnd(); |
| 333 | while (use != nullptr && use->GetPosition() <= end) { |
| 334 | size_t use_position = use->GetPosition(); |
| 335 | if (use_position >= start && !use->GetIsEnvironment()) { |
| 336 | HInstruction* user = use->GetUser(); |
| 337 | size_t input_index = use->GetInputIndex(); |
| 338 | if (user->IsPhi()) { |
| 339 | // If the phi has a register, try to use the same. |
| 340 | Location phi_location = user->GetLiveInterval()->ToLocation(); |
Nicolas Geoffray | da02afe | 2015-02-11 02:29:42 +0000 | [diff] [blame^] | 341 | if (phi_location.IsRegisterKind()) { |
| 342 | DCHECK(SameRegisterKind(phi_location)); |
| 343 | int reg = RegisterOrLowRegister(phi_location); |
| 344 | if (free_until[reg] >= use_position) { |
| 345 | return reg; |
| 346 | } |
Nicolas Geoffray | 01ef345 | 2014-10-01 11:32:17 +0100 | [diff] [blame] | 347 | } |
| 348 | const GrowableArray<HBasicBlock*>& predecessors = user->GetBlock()->GetPredecessors(); |
| 349 | // If the instruction dies at the phi assignment, we can try having the |
| 350 | // same register. |
| 351 | if (end == predecessors.Get(input_index)->GetLifetimeEnd()) { |
| 352 | for (size_t i = 0, e = user->InputCount(); i < e; ++i) { |
| 353 | if (i == input_index) { |
| 354 | continue; |
| 355 | } |
| 356 | HInstruction* input = user->InputAt(i); |
| 357 | Location location = input->GetLiveInterval()->GetLocationAt( |
| 358 | predecessors.Get(i)->GetLifetimeEnd() - 1); |
Nicolas Geoffray | da02afe | 2015-02-11 02:29:42 +0000 | [diff] [blame^] | 359 | if (location.IsRegisterKind()) { |
| 360 | int reg = RegisterOrLowRegister(location); |
| 361 | if (free_until[reg] >= use_position) { |
| 362 | return reg; |
| 363 | } |
Nicolas Geoffray | 01ef345 | 2014-10-01 11:32:17 +0100 | [diff] [blame] | 364 | } |
| 365 | } |
| 366 | } |
| 367 | } else { |
| 368 | // If the instruction is expected in a register, try to use it. |
| 369 | LocationSummary* locations = user->GetLocations(); |
| 370 | Location expected = locations->InAt(use->GetInputIndex()); |
| 371 | // We use the user's lifetime position - 1 (and not `use_position`) because the |
| 372 | // register is blocked at the beginning of the user. |
| 373 | size_t position = user->GetLifetimePosition() - 1; |
Nicolas Geoffray | da02afe | 2015-02-11 02:29:42 +0000 | [diff] [blame^] | 374 | if (expected.IsRegisterKind()) { |
| 375 | DCHECK(SameRegisterKind(expected)); |
| 376 | int reg = RegisterOrLowRegister(expected); |
| 377 | if (free_until[reg] >= position) { |
| 378 | return reg; |
| 379 | } |
Nicolas Geoffray | 01ef345 | 2014-10-01 11:32:17 +0100 | [diff] [blame] | 380 | } |
| 381 | } |
| 382 | } |
| 383 | use = use->GetNext(); |
| 384 | } |
| 385 | |
| 386 | return kNoRegister; |
| 387 | } |
| 388 | |
| 389 | int LiveInterval::FindHintAtDefinition() const { |
| 390 | if (defined_by_->IsPhi()) { |
| 391 | // Try to use the same register as one of the inputs. |
| 392 | const GrowableArray<HBasicBlock*>& predecessors = defined_by_->GetBlock()->GetPredecessors(); |
| 393 | for (size_t i = 0, e = defined_by_->InputCount(); i < e; ++i) { |
| 394 | HInstruction* input = defined_by_->InputAt(i); |
| 395 | size_t end = predecessors.Get(i)->GetLifetimeEnd(); |
| 396 | const LiveInterval& input_interval = input->GetLiveInterval()->GetIntervalAt(end - 1); |
| 397 | if (input_interval.GetEnd() == end) { |
| 398 | // If the input dies at the end of the predecessor, we know its register can |
| 399 | // be reused. |
| 400 | Location input_location = input_interval.ToLocation(); |
Nicolas Geoffray | da02afe | 2015-02-11 02:29:42 +0000 | [diff] [blame^] | 401 | if (input_location.IsRegisterKind()) { |
| 402 | DCHECK(SameRegisterKind(input_location)); |
| 403 | return RegisterOrLowRegister(input_location); |
Nicolas Geoffray | 01ef345 | 2014-10-01 11:32:17 +0100 | [diff] [blame] | 404 | } |
| 405 | } |
| 406 | } |
| 407 | } else { |
| 408 | LocationSummary* locations = GetDefinedBy()->GetLocations(); |
| 409 | Location out = locations->Out(); |
| 410 | if (out.IsUnallocated() && out.GetPolicy() == Location::kSameAsFirstInput) { |
| 411 | // Try to use the same register as the first input. |
| 412 | const LiveInterval& input_interval = |
| 413 | GetDefinedBy()->InputAt(0)->GetLiveInterval()->GetIntervalAt(GetStart() - 1); |
| 414 | if (input_interval.GetEnd() == GetStart()) { |
| 415 | // If the input dies at the start of this instruction, we know its register can |
| 416 | // be reused. |
| 417 | Location location = input_interval.ToLocation(); |
Nicolas Geoffray | da02afe | 2015-02-11 02:29:42 +0000 | [diff] [blame^] | 418 | if (location.IsRegisterKind()) { |
| 419 | DCHECK(SameRegisterKind(location)); |
| 420 | return RegisterOrLowRegister(location); |
Nicolas Geoffray | 01ef345 | 2014-10-01 11:32:17 +0100 | [diff] [blame] | 421 | } |
| 422 | } |
| 423 | } |
| 424 | } |
| 425 | return kNoRegister; |
| 426 | } |
| 427 | |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 428 | bool LiveInterval::SameRegisterKind(Location other) const { |
Nicolas Geoffray | da02afe | 2015-02-11 02:29:42 +0000 | [diff] [blame^] | 429 | if (IsFloatingPoint()) { |
| 430 | if (IsLowInterval() || IsHighInterval()) { |
| 431 | return other.IsFpuRegisterPair(); |
| 432 | } else { |
| 433 | return other.IsFpuRegister(); |
| 434 | } |
| 435 | } else { |
| 436 | if (IsLowInterval() || IsHighInterval()) { |
| 437 | return other.IsRegisterPair(); |
| 438 | } else { |
| 439 | return other.IsRegister(); |
| 440 | } |
| 441 | } |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 442 | } |
| 443 | |
Nicolas Geoffray | 01ef345 | 2014-10-01 11:32:17 +0100 | [diff] [blame] | 444 | bool LiveInterval::NeedsTwoSpillSlots() const { |
| 445 | return type_ == Primitive::kPrimLong || type_ == Primitive::kPrimDouble; |
| 446 | } |
| 447 | |
| 448 | Location LiveInterval::ToLocation() const { |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 449 | DCHECK(!IsHighInterval()); |
Nicolas Geoffray | 01ef345 | 2014-10-01 11:32:17 +0100 | [diff] [blame] | 450 | if (HasRegister()) { |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 451 | if (IsFloatingPoint()) { |
| 452 | if (HasHighInterval()) { |
| 453 | return Location::FpuRegisterPairLocation(GetRegister(), GetHighInterval()->GetRegister()); |
| 454 | } else { |
| 455 | return Location::FpuRegisterLocation(GetRegister()); |
| 456 | } |
| 457 | } else { |
| 458 | if (HasHighInterval()) { |
| 459 | return Location::RegisterPairLocation(GetRegister(), GetHighInterval()->GetRegister()); |
| 460 | } else { |
| 461 | return Location::RegisterLocation(GetRegister()); |
| 462 | } |
| 463 | } |
Nicolas Geoffray | 01ef345 | 2014-10-01 11:32:17 +0100 | [diff] [blame] | 464 | } else { |
| 465 | HInstruction* defined_by = GetParent()->GetDefinedBy(); |
| 466 | if (defined_by->IsConstant()) { |
| 467 | return defined_by->GetLocations()->Out(); |
| 468 | } else if (GetParent()->HasSpillSlot()) { |
| 469 | if (NeedsTwoSpillSlots()) { |
| 470 | return Location::DoubleStackSlot(GetParent()->GetSpillSlot()); |
| 471 | } else { |
| 472 | return Location::StackSlot(GetParent()->GetSpillSlot()); |
| 473 | } |
| 474 | } else { |
| 475 | return Location(); |
| 476 | } |
| 477 | } |
| 478 | } |
| 479 | |
| 480 | Location LiveInterval::GetLocationAt(size_t position) const { |
| 481 | return GetIntervalAt(position).ToLocation(); |
| 482 | } |
| 483 | |
| 484 | const LiveInterval& LiveInterval::GetIntervalAt(size_t position) const { |
| 485 | const LiveInterval* current = this; |
| 486 | while (!current->Covers(position)) { |
| 487 | current = current->GetNextSibling(); |
| 488 | DCHECK(current != nullptr); |
| 489 | } |
| 490 | return *current; |
| 491 | } |
| 492 | |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 493 | } // namespace art |