ssa_liveness_analysis.cc revision a5b8fde2d2bc3167078694fad417fddfe442a6fd 
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
20namespace art {
21
22void SsaLivenessAnalysis::Analyze() {
23  LinearizeGraph();
24  NumberInstructions();
25  ComputeLiveness();
26}
27
28static 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
33static bool IsLoop(HLoopInformation* info) {
34  return info != nullptr;
35}
36
37static bool InSameLoop(HLoopInformation* first_loop, HLoopInformation* second_loop) {
38  return first_loop == second_loop;
39}
40
41static bool IsInnerLoop(HLoopInformation* outer, HLoopInformation* inner) {
42  return (inner != outer)
43      && (inner != nullptr)
44      && (outer != nullptr)
45      && inner->IsIn(*outer);
46}
47
48static 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
83class 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
99class 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
115void 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
122void SsaLivenessAnalysis::NumberInstructions() {
123  int ssa_index = 0;
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
129  for (HLinearOrderIterator it(linear_post_order_); !it.Done(); it.Advance()) {
130    HBasicBlock* block = it.Current();
131    block->SetLifetimeStart(++lifetime_position);
132
133    for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
134      HInstruction* current = it.Current();
135      if (current->HasUses()) {
136        instructions_from_ssa_index_.Add(current);
137        current->SetSsaIndex(ssa_index++);
138        current->SetLiveInterval(new (graph_.GetArena()) LiveInterval(graph_.GetArena()));
139      }
140      current->SetLifetimePosition(lifetime_position);
141    }
142
143    for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
144      HInstruction* current = it.Current();
145      if (current->HasUses()) {
146        instructions_from_ssa_index_.Add(current);
147        current->SetSsaIndex(ssa_index++);
148        current->SetLiveInterval(new (graph_.GetArena()) LiveInterval(graph_.GetArena()));
149      }
150      current->SetLifetimePosition(++lifetime_position);
151    }
152
153    block->SetLifetimeEnd(++lifetime_position);
154  }
155  number_of_ssa_values_ = ssa_index;
156}
157
158void SsaLivenessAnalysis::ComputeLiveness() {
159  for (HLinearOrderIterator it(linear_post_order_); !it.Done(); it.Advance()) {
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
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();
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
177void SsaLivenessAnalysis::ComputeLiveRanges() {
178  // Do a post order visit, adding inputs of instructions live in the block where
179  // that instruction is defined, and killing instructions that are being visited.
180  for (HLinearPostOrderIterator it(linear_post_order_); !it.Done(); it.Advance()) {
181    HBasicBlock* block = it.Current();
182
183    BitVector* kill = GetKillSet(*block);
184    BitVector* live_in = GetLiveInSet(*block);
185
186    // Set phi inputs of successors of this block corresponding to this block
187    // as live_in.
188    for (size_t i = 0, e = block->GetSuccessors().Size(); i < e; ++i) {
189      HBasicBlock* successor = block->GetSuccessors().Get(i);
190      live_in->Union(GetLiveInSet(*successor));
191      size_t phi_input_index = successor->GetPredecessorIndexOf(block);
192      for (HInstructionIterator it(successor->GetPhis()); !it.Done(); it.Advance()) {
193        HInstruction* input = it.Current()->InputAt(phi_input_index);
194        live_in->SetBit(input->GetSsaIndex());
195      }
196    }
197
198    // Add a range that covers this block to all instructions live_in because of successors.
199    for (uint32_t idx : live_in->Indexes()) {
200      HInstruction* current = instructions_from_ssa_index_.Get(idx);
201      current->GetLiveInterval()->AddRange(block->GetLifetimeStart(), block->GetLifetimeEnd());
202    }
203
204    for (HBackwardInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
205      HInstruction* current = it.Current();
206      if (current->HasSsaIndex()) {
207        // Kill the instruction and shorten its interval.
208        kill->SetBit(current->GetSsaIndex());
209        live_in->ClearBit(current->GetSsaIndex());
210        current->GetLiveInterval()->SetFrom(current->GetLifetimePosition());
211      }
212
213      // All inputs of an instruction must be live.
214      for (size_t i = 0, e = current->InputCount(); i < e; ++i) {
215        HInstruction* input = current->InputAt(i);
216        DCHECK(input->HasSsaIndex());
217        live_in->SetBit(input->GetSsaIndex());
218        input->GetLiveInterval()->AddUse(current);
219      }
220
221      if (current->HasEnvironment()) {
222        // All instructions in the environment must be live.
223        GrowableArray<HInstruction*>* environment = current->GetEnvironment()->GetVRegs();
224        for (size_t i = 0, e = environment->Size(); i < e; ++i) {
225          HInstruction* instruction = environment->Get(i);
226          if (instruction != nullptr) {
227            DCHECK(instruction->HasSsaIndex());
228            live_in->SetBit(instruction->GetSsaIndex());
229            instruction->GetLiveInterval()->AddUse(current);
230          }
231        }
232      }
233    }
234
235    // Kill phis defined in this block.
236    for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
237      HInstruction* current = it.Current();
238      if (current->HasSsaIndex()) {
239        kill->SetBit(current->GetSsaIndex());
240        live_in->ClearBit(current->GetSsaIndex());
241      }
242    }
243
244    if (block->IsLoopHeader()) {
245      HBasicBlock* back_edge = block->GetLoopInformation()->GetBackEdges().Get(0);
246      // For all live_in instructions at the loop header, we need to create a range
247      // that covers the full loop.
248      for (uint32_t idx : live_in->Indexes()) {
249        HInstruction* current = instructions_from_ssa_index_.Get(idx);
250        current->GetLiveInterval()->AddLoopRange(block->GetLifetimeStart(),
251                                                 back_edge->GetLifetimeEnd());
252      }
253    }
254  }
255}
256
257void SsaLivenessAnalysis::ComputeLiveInAndLiveOutSets() {
258  bool changed;
259  do {
260    changed = false;
261
262    for (HPostOrderIterator it(graph_); !it.Done(); it.Advance()) {
263      const HBasicBlock& block = *it.Current();
264
265      // The live_in set depends on the kill set (which does not
266      // change in this loop), and the live_out set.  If the live_out
267      // set does not change, there is no need to update the live_in set.
268      if (UpdateLiveOut(block) && UpdateLiveIn(block)) {
269        changed = true;
270      }
271    }
272  } while (changed);
273}
274
275bool SsaLivenessAnalysis::UpdateLiveOut(const HBasicBlock& block) {
276  BitVector* live_out = GetLiveOutSet(block);
277  bool changed = false;
278  // The live_out set of a block is the union of live_in sets of its successors.
279  for (size_t i = 0, e = block.GetSuccessors().Size(); i < e; ++i) {
280    HBasicBlock* successor = block.GetSuccessors().Get(i);
281    if (live_out->Union(GetLiveInSet(*successor))) {
282      changed = true;
283    }
284  }
285  return changed;
286}
287
288
289bool SsaLivenessAnalysis::UpdateLiveIn(const HBasicBlock& block) {
290  BitVector* live_out = GetLiveOutSet(block);
291  BitVector* kill = GetKillSet(block);
292  BitVector* live_in = GetLiveInSet(block);
293  // If live_out is updated (because of backward branches), we need to make
294  // sure instructions in live_out are also in live_in, unless they are killed
295  // by this block.
296  return live_in->UnionIfNotIn(live_out, kill);
297}
298
299}  // namespace art
300