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" |
| 18 | #include "nodes.h" |
| 19 | |
| 20 | namespace art { |
| 21 | |
| 22 | void SsaLivenessAnalysis::Analyze() { |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 23 | LinearizeGraph(); |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 24 | NumberInstructions(); |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 25 | ComputeLiveness(); |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 26 | } |
| 27 | |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 28 | static bool IsLoopExit(HLoopInformation* current, HLoopInformation* to) { |
| 29 | // `to` is either not part of a loop, or `current` is an inner loop of `to`. |
| 30 | return to == nullptr || (current != to && current->IsIn(*to)); |
| 31 | } |
| 32 | |
| 33 | static bool IsLoop(HLoopInformation* info) { |
| 34 | return info != nullptr; |
| 35 | } |
| 36 | |
| 37 | static bool InSameLoop(HLoopInformation* first_loop, HLoopInformation* second_loop) { |
| 38 | return first_loop == second_loop; |
| 39 | } |
| 40 | |
| 41 | static bool IsInnerLoop(HLoopInformation* outer, HLoopInformation* inner) { |
| 42 | return (inner != outer) |
| 43 | && (inner != nullptr) |
| 44 | && (outer != nullptr) |
| 45 | && inner->IsIn(*outer); |
| 46 | } |
| 47 | |
| 48 | static void VisitBlockForLinearization(HBasicBlock* block, |
| 49 | GrowableArray<HBasicBlock*>* order, |
| 50 | ArenaBitVector* visited) { |
| 51 | if (visited->IsBitSet(block->GetBlockId())) { |
| 52 | return; |
| 53 | } |
| 54 | visited->SetBit(block->GetBlockId()); |
| 55 | size_t number_of_successors = block->GetSuccessors().Size(); |
| 56 | if (number_of_successors == 0) { |
| 57 | // Nothing to do. |
| 58 | } else if (number_of_successors == 1) { |
| 59 | VisitBlockForLinearization(block->GetSuccessors().Get(0), order, visited); |
| 60 | } else { |
| 61 | DCHECK_EQ(number_of_successors, 2u); |
| 62 | HBasicBlock* first_successor = block->GetSuccessors().Get(0); |
| 63 | HBasicBlock* second_successor = block->GetSuccessors().Get(1); |
| 64 | HLoopInformation* my_loop = block->GetLoopInformation(); |
| 65 | HLoopInformation* first_loop = first_successor->GetLoopInformation(); |
| 66 | HLoopInformation* second_loop = second_successor->GetLoopInformation(); |
| 67 | |
| 68 | if (!IsLoop(my_loop)) { |
| 69 | // Nothing to do. Current order is fine. |
| 70 | } else if (IsLoopExit(my_loop, second_loop) && InSameLoop(my_loop, first_loop)) { |
| 71 | // Visit the loop exit first in post order. |
| 72 | std::swap(first_successor, second_successor); |
| 73 | } else if (IsInnerLoop(my_loop, first_loop) && !IsInnerLoop(my_loop, second_loop)) { |
| 74 | // Visit the inner loop last in post order. |
| 75 | std::swap(first_successor, second_successor); |
| 76 | } |
| 77 | VisitBlockForLinearization(first_successor, order, visited); |
| 78 | VisitBlockForLinearization(second_successor, order, visited); |
| 79 | } |
| 80 | order->Add(block); |
| 81 | } |
| 82 | |
| 83 | class HLinearOrderIterator : public ValueObject { |
| 84 | public: |
| 85 | explicit HLinearOrderIterator(const GrowableArray<HBasicBlock*>& post_order) |
| 86 | : post_order_(post_order), index_(post_order.Size()) {} |
| 87 | |
| 88 | bool Done() const { return index_ == 0; } |
| 89 | HBasicBlock* Current() const { return post_order_.Get(index_ -1); } |
| 90 | void Advance() { --index_; DCHECK_GE(index_, 0U); } |
| 91 | |
| 92 | private: |
| 93 | const GrowableArray<HBasicBlock*>& post_order_; |
| 94 | size_t index_; |
| 95 | |
| 96 | DISALLOW_COPY_AND_ASSIGN(HLinearOrderIterator); |
| 97 | }; |
| 98 | |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 99 | class HLinearPostOrderIterator : public ValueObject { |
| 100 | public: |
| 101 | explicit HLinearPostOrderIterator(const GrowableArray<HBasicBlock*>& post_order) |
| 102 | : post_order_(post_order), index_(0) {} |
| 103 | |
| 104 | bool Done() const { return index_ == post_order_.Size(); } |
| 105 | HBasicBlock* Current() const { return post_order_.Get(index_); } |
| 106 | void Advance() { ++index_; } |
| 107 | |
| 108 | private: |
| 109 | const GrowableArray<HBasicBlock*>& post_order_; |
| 110 | size_t index_; |
| 111 | |
| 112 | DISALLOW_COPY_AND_ASSIGN(HLinearPostOrderIterator); |
| 113 | }; |
| 114 | |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 115 | void SsaLivenessAnalysis::LinearizeGraph() { |
| 116 | // For simplicity of the implementation, we create post linear order. The order for |
| 117 | // computing live ranges is the reverse of that order. |
| 118 | ArenaBitVector visited(graph_.GetArena(), graph_.GetBlocks().Size(), false); |
| 119 | VisitBlockForLinearization(graph_.GetEntryBlock(), &linear_post_order_, &visited); |
| 120 | } |
| 121 | |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 122 | void SsaLivenessAnalysis::NumberInstructions() { |
| 123 | int ssa_index = 0; |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 124 | size_t lifetime_position = 0; |
| 125 | // Each instruction gets an individual lifetime position, and a block gets a lifetime |
| 126 | // start and end position. Non-phi instructions have a distinct lifetime position than |
| 127 | // the block they are in. Phi instructions have the lifetime start of their block as |
| 128 | // lifetime position |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 129 | for (HLinearOrderIterator it(linear_post_order_); !it.Done(); it.Advance()) { |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 130 | HBasicBlock* block = it.Current(); |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 131 | block->SetLifetimeStart(++lifetime_position); |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 132 | |
Nicolas Geoffray | f635e63 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 133 | for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 134 | HInstruction* current = it.Current(); |
| 135 | if (current->HasUses()) { |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 136 | instructions_from_ssa_index_.Add(current); |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 137 | current->SetSsaIndex(ssa_index++); |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 138 | current->SetLiveInterval(new (graph_.GetArena()) LiveInterval(graph_.GetArena())); |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 139 | } |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 140 | current->SetLifetimePosition(lifetime_position); |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 141 | } |
| 142 | |
Nicolas Geoffray | f635e63 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 143 | for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 144 | HInstruction* current = it.Current(); |
| 145 | if (current->HasUses()) { |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 146 | instructions_from_ssa_index_.Add(current); |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 147 | current->SetSsaIndex(ssa_index++); |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 148 | current->SetLiveInterval(new (graph_.GetArena()) LiveInterval(graph_.GetArena())); |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 149 | } |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 150 | current->SetLifetimePosition(++lifetime_position); |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 151 | } |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 152 | |
| 153 | block->SetLifetimeEnd(++lifetime_position); |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 154 | } |
| 155 | number_of_ssa_values_ = ssa_index; |
| 156 | } |
| 157 | |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 158 | void SsaLivenessAnalysis::ComputeLiveness() { |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 159 | for (HLinearOrderIterator it(linear_post_order_); !it.Done(); it.Advance()) { |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 160 | HBasicBlock* block = it.Current(); |
| 161 | block_infos_.Put( |
| 162 | block->GetBlockId(), |
| 163 | new (graph_.GetArena()) BlockInfo(graph_.GetArena(), *block, number_of_ssa_values_)); |
| 164 | } |
| 165 | |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 166 | // Compute the live ranges, as well as the initial live_in, live_out, and kill sets. |
| 167 | // This method does not handle backward branches for the sets, therefore live_in |
| 168 | // and live_out sets are not yet correct. |
| 169 | ComputeLiveRanges(); |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 170 | |
| 171 | // Do a fixed point calculation to take into account backward branches, |
| 172 | // that will update live_in of loop headers, and therefore live_out and live_in |
| 173 | // of blocks in the loop. |
| 174 | ComputeLiveInAndLiveOutSets(); |
| 175 | } |
| 176 | |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 177 | class InstructionBitVectorIterator : public ValueObject { |
| 178 | public: |
| 179 | InstructionBitVectorIterator(const BitVector& vector, |
| 180 | const GrowableArray<HInstruction*>& instructions) |
| 181 | : instructions_(instructions), |
| 182 | iterator_(BitVector::Iterator(&vector)), |
| 183 | current_bit_index_(iterator_.Next()) {} |
| 184 | |
| 185 | bool Done() const { return current_bit_index_ == -1; } |
| 186 | HInstruction* Current() const { return instructions_.Get(current_bit_index_); } |
| 187 | void Advance() { |
| 188 | current_bit_index_ = iterator_.Next(); |
| 189 | } |
| 190 | |
| 191 | private: |
| 192 | const GrowableArray<HInstruction*> instructions_; |
| 193 | BitVector::Iterator iterator_; |
| 194 | int32_t current_bit_index_; |
| 195 | |
| 196 | DISALLOW_COPY_AND_ASSIGN(InstructionBitVectorIterator); |
| 197 | }; |
| 198 | |
| 199 | void SsaLivenessAnalysis::ComputeLiveRanges() { |
| 200 | // 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] | 201 | // that instruction is defined, and killing instructions that are being visited. |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 202 | for (HLinearPostOrderIterator it(linear_post_order_); !it.Done(); it.Advance()) { |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 203 | HBasicBlock* block = it.Current(); |
| 204 | |
| 205 | BitVector* kill = GetKillSet(*block); |
| 206 | BitVector* live_in = GetLiveInSet(*block); |
| 207 | |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 208 | // Set phi inputs of successors of this block corresponding to this block |
| 209 | // as live_in. |
| 210 | for (size_t i = 0, e = block->GetSuccessors().Size(); i < e; ++i) { |
| 211 | HBasicBlock* successor = block->GetSuccessors().Get(i); |
| 212 | live_in->Union(GetLiveInSet(*successor)); |
| 213 | size_t phi_input_index = successor->GetPredecessorIndexOf(block); |
| 214 | for (HInstructionIterator it(successor->GetPhis()); !it.Done(); it.Advance()) { |
| 215 | HInstruction* input = it.Current()->InputAt(phi_input_index); |
| 216 | live_in->SetBit(input->GetSsaIndex()); |
| 217 | } |
| 218 | } |
| 219 | |
| 220 | // Add a range that covers this block to all instructions live_in because of successors. |
| 221 | for (InstructionBitVectorIterator it(*live_in, instructions_from_ssa_index_); |
| 222 | !it.Done(); |
| 223 | it.Advance()) { |
| 224 | it.Current()->GetLiveInterval()->AddRange(block->GetLifetimeStart(), block->GetLifetimeEnd()); |
| 225 | } |
| 226 | |
Nicolas Geoffray | f635e63 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 227 | for (HBackwardInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 228 | HInstruction* current = it.Current(); |
| 229 | if (current->HasSsaIndex()) { |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 230 | // Kill the instruction and shorten its interval. |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 231 | kill->SetBit(current->GetSsaIndex()); |
| 232 | live_in->ClearBit(current->GetSsaIndex()); |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 233 | current->GetLiveInterval()->SetFrom(current->GetLifetimePosition()); |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 234 | } |
| 235 | |
| 236 | // All inputs of an instruction must be live. |
| 237 | for (size_t i = 0, e = current->InputCount(); i < e; ++i) { |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 238 | HInstruction* input = current->InputAt(i); |
| 239 | DCHECK(input->HasSsaIndex()); |
| 240 | live_in->SetBit(input->GetSsaIndex()); |
| 241 | input->GetLiveInterval()->AddUse(current); |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 242 | } |
| 243 | |
| 244 | if (current->HasEnvironment()) { |
| 245 | // All instructions in the environment must be live. |
| 246 | GrowableArray<HInstruction*>* environment = current->GetEnvironment()->GetVRegs(); |
| 247 | for (size_t i = 0, e = environment->Size(); i < e; ++i) { |
| 248 | HInstruction* instruction = environment->Get(i); |
| 249 | if (instruction != nullptr) { |
| 250 | DCHECK(instruction->HasSsaIndex()); |
| 251 | live_in->SetBit(instruction->GetSsaIndex()); |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 252 | instruction->GetLiveInterval()->AddUse(current); |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 253 | } |
| 254 | } |
| 255 | } |
| 256 | } |
| 257 | |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 258 | // Kill phis defined in this block. |
Nicolas Geoffray | f635e63 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 259 | for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 260 | HInstruction* current = it.Current(); |
| 261 | if (current->HasSsaIndex()) { |
| 262 | kill->SetBit(current->GetSsaIndex()); |
| 263 | live_in->ClearBit(current->GetSsaIndex()); |
| 264 | } |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 265 | } |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 266 | |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 267 | if (block->IsLoopHeader()) { |
| 268 | HBasicBlock* back_edge = block->GetLoopInformation()->GetBackEdges().Get(0); |
| 269 | // For all live_in instructions at the loop header, we need to create a range |
| 270 | // that covers the full loop. |
| 271 | for (InstructionBitVectorIterator it(*live_in, instructions_from_ssa_index_); |
| 272 | !it.Done(); |
| 273 | it.Advance()) { |
| 274 | it.Current()->GetLiveInterval()->AddLoopRange(block->GetLifetimeStart(), |
| 275 | back_edge->GetLifetimeEnd()); |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 276 | } |
| 277 | } |
| 278 | } |
| 279 | } |
| 280 | |
| 281 | void SsaLivenessAnalysis::ComputeLiveInAndLiveOutSets() { |
| 282 | bool changed; |
| 283 | do { |
| 284 | changed = false; |
| 285 | |
| 286 | for (HPostOrderIterator it(graph_); !it.Done(); it.Advance()) { |
| 287 | const HBasicBlock& block = *it.Current(); |
| 288 | |
| 289 | // The live_in set depends on the kill set (which does not |
| 290 | // change in this loop), and the live_out set. If the live_out |
| 291 | // set does not change, there is no need to update the live_in set. |
| 292 | if (UpdateLiveOut(block) && UpdateLiveIn(block)) { |
| 293 | changed = true; |
| 294 | } |
| 295 | } |
| 296 | } while (changed); |
| 297 | } |
| 298 | |
| 299 | bool SsaLivenessAnalysis::UpdateLiveOut(const HBasicBlock& block) { |
| 300 | BitVector* live_out = GetLiveOutSet(block); |
| 301 | bool changed = false; |
| 302 | // 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] | 303 | for (size_t i = 0, e = block.GetSuccessors().Size(); i < e; ++i) { |
| 304 | HBasicBlock* successor = block.GetSuccessors().Get(i); |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 305 | if (live_out->Union(GetLiveInSet(*successor))) { |
| 306 | changed = true; |
| 307 | } |
| 308 | } |
| 309 | return changed; |
| 310 | } |
| 311 | |
| 312 | |
| 313 | bool SsaLivenessAnalysis::UpdateLiveIn(const HBasicBlock& block) { |
| 314 | BitVector* live_out = GetLiveOutSet(block); |
| 315 | BitVector* kill = GetKillSet(block); |
| 316 | BitVector* live_in = GetLiveInSet(block); |
| 317 | // If live_out is updated (because of backward branches), we need to make |
| 318 | // sure instructions in live_out are also in live_in, unless they are killed |
| 319 | // by this block. |
| 320 | return live_in->UnionIfNotIn(live_out, kill); |
| 321 | } |
| 322 | |
| 323 | } // namespace art |