Simple iterative liveness analysis over SSA.

runtime/vm/flow_graph_allocator.cc

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "vm/flow_graph_allocator.h"
 
+#include "vm/bit_vector.h"
 #include "vm/intermediate_language.h"
+#include "vm/flow_graph_compiler.h"
 
 namespace dart {
 
+DEFINE_FLAG(bool, print_ssa_liveness, false,
+            "Print liveness for ssa variables.");
+
+FlowGraphAllocator::FlowGraphAllocator(
+  const GrowableArray<BlockEntryInstr*>& postorder,
+  intptr_t max_ssa_temp_index)
+  : live_out_(postorder.length()),
+    kill_(postorder.length()),
+    gen_(postorder.length()),
+    live_in_(postorder.length()),
+    postorder_(postorder),
+    vreg_count_(max_ssa_temp_index) {
+}
+
+
 void FlowGraphAllocator::ResolveConstraints() {
   // TODO(fschneider): Resolve register constraints.
 }
 
+
+static intptr_t ToVirtualRegister(Instruction* instr) {
+  const Definition* def = instr->AsDefinition();
+  if (def == 0) return -1;

[Florian Schneider, 2012/06/25 14:38:29]

Better def == NULL?

[Vyacheslav Egorov (Google), 2012/06/25 16:58:26]

Done.

+  return def->ssa_temp_index();
+}

[srdjan, 2012/06/25 17:30:05]

return (def == NULL) ? -1 : def->ssa_temp_index();

+
+
+void FlowGraphAllocator::ComputeKillAndGenSets() {
+  const intptr_t block_count = postorder_.length();
+  for (intptr_t i = 0; i < block_count; i++) {
+    BlockEntryInstr* block = postorder_[i];
+
+    BitVector* kill = kill_[i];
+    BitVector* gen = gen_[i];

[srdjan, 2012/06/25 17:30:05]

ASSERT kill and gen are not NULL.

+
+    if (block->IsJoinEntry()) {
+      JoinEntryInstr* join = block->AsJoinEntry();
+      for (intptr_t j = 0; j < join->phis()->length(); j++) {

[Florian Schneider, 2012/06/25 14:38:29]

Missing NULL check: join->phis() can be NULL for join blocks that do not contain
any phis.

[Vyacheslav Egorov (Google), 2012/06/25 16:58:26]

Done.

+        PhiInstr* phi = (*join->phis())[j];
+        if (phi == NULL) continue;
+
+        const intptr_t def = ToVirtualRegister(phi);
+        if (def >= 0) kill->Add(def);
+
+        for (intptr_t k = 0; k < phi->InputCount(); k++) {
+          Value* val = phi->InputAt(k);
+          if (!val->IsUse()) continue;
+          const intptr_t use = ToVirtualRegister(val->AsUse()->definition());
+          if (use >= 0) {
+            BlockEntryInstr* pred = block->PredecessorAt(k);
+            live_out_[pred->postorder_number()]->Add(use);
+          }
+        }
+      }
+    }
+
+    Instruction* current = block->StraightLineSuccessor();
+    // TODO(vegorov): iterate backwards.
+    while ((current != NULL) && !current->IsBlockEntry()) {
+      for (intptr_t j = 0; j < current->InputCount(); j++) {
+        Value* input = current->InputAt(j);
+        if (!input->IsUse()) continue;
+        const intptr_t use = ToVirtualRegister(input->AsUse()->definition());
+        if (use >= 0 && !kill->Contains(use)) gen->Add(use);
+      }
+
+      const intptr_t def = ToVirtualRegister(current);
+      if (def >= 0) kill->Add(def);
+
+      current = current->StraightLineSuccessor();
+    }
+
+    live_in_[i]->AddAll(gen);
+    UpdateLiveIn(block);
+  }
+}
+
+
+bool FlowGraphAllocator::UpdateLiveOut(BlockEntryInstr* instr) {
+  BitVector* live_out = live_out_[instr->postorder_number()];
+  bool changed = false;
+  Instruction* last = instr->last_instruction();

[srdjan, 2012/06/25 17:30:05]

ASSERT (last != NULL, live_out != NULL) ?

[Vyacheslav Egorov (Google), 2012/06/25 17:42:23]

live_out_ != NULL is a fundamental property of initialization code. I don't see
a reason to assert it.

I am also not sure what is the benefit of asserting not-nullness for a values
that are immediately derefed --- we will get SIGSEGV anyways. 

[srdjan, 2012/06/25 17:51:44]

Agree with the fundamental property. SIGSEGV is much uglier to debug then an
ASSERT, IMHO.

+  for (intptr_t i = 0; i < last->SuccessorCount(); i++) {

[srdjan, 2012/06/25 17:30:05]

SuccessotCount can be 0 or 1, is a loop necessary?

[Vyacheslav Egorov (Google), 2012/06/25 17:42:23]

it can be 0, 1 (implicit goto), 2 (branch), 1 + #catch entries (graph entry).

if we introduce switch-tables we might get even more different values, so I
prefer to have a loop.

[srdjan, 2012/06/25 17:51:44]

Mea culpa.

+    BlockEntryInstr* succ = last->SuccessorAt(i);

[srdjan, 2012/06/25 17:30:05]

ASSERT(succ != NULL) ?

+    if (live_out->AddAll(live_in_[succ->postorder_number()])) {
+      changed = true;
+    }
+  }
+  return changed;
+}
+
+
+bool FlowGraphAllocator::UpdateLiveIn(BlockEntryInstr* instr) {
+  BitVector* live_out = live_out_[instr->postorder_number()];
+  BitVector* kill = kill_[instr->postorder_number()];
+  BitVector* live_in = live_in_[instr->postorder_number()];
+  return live_in->KillAndAdd(kill, live_out);
+}
+
+
+void FlowGraphAllocator::ComputeLiveInAndLiveOutSets() {
+  const intptr_t block_count = postorder_.length();
+  bool changed;

[srdjan, 2012/06/25 17:30:05]

bool changed = false;

+  do {
+    changed = false;

[srdjan, 2012/06/25 17:30:05]

Remove this line.

[Vyacheslav Egorov (Google), 2012/06/25 17:42:23]

I need to reset changed to false after each iteration. 

[srdjan, 2012/06/25 17:51:44]

I negated the condition while reading. Mea Culpa

+
+    for (intptr_t i = 0; i < block_count; i++) {
+      BlockEntryInstr* block = postorder_[i];

[srdjan, 2012/06/25 17:30:05]

Maybe add comments that you do not need to update live-ins if there was no
change in live outs.

+      if (UpdateLiveOut(block) && UpdateLiveIn(block)) {
+        changed = true;
+      }
+    }
+  } while (changed);
+}
+
+
+void FlowGraphAllocator::AnalyzeLiveness() {
+  const intptr_t block_count = postorder_.length();
+  for (intptr_t i = 0; i < block_count; i++) {
+    live_out_.Add(new BitVector(vreg_count_));
+    kill_.Add(new BitVector(vreg_count_));
+    gen_.Add(new BitVector(vreg_count_));
+    live_in_.Add(new BitVector(vreg_count_));
+  }
+
+  ComputeKillAndGenSets();
+  ComputeLiveInAndLiveOutSets();
+
+  if (FLAG_print_ssa_liveness) {
+    DumpLiveness();
+  }
+}
+
+
+static void PrintBitVector(const char* tag, BitVector* v) {
+  printf("%s:", tag);

[Florian Schneider, 2012/06/25 14:38:29]

Use OS::Print instead.

[Vyacheslav Egorov (Google), 2012/06/25 16:58:26]

Done.

+  for (BitVector::Iterator it(v); !it.Done(); it.Advance()) {
+    printf(" %d", it.Current());

[Florian Schneider, 2012/06/25 14:38:29]

OS::Print

[Vyacheslav Egorov (Google), 2012/06/25 16:58:26]

Done.

+  }
+  printf("\n");

[Florian Schneider, 2012/06/25 14:38:29]

OS::Print

[Vyacheslav Egorov (Google), 2012/06/25 16:58:26]

Done.

+}
+
+
+void FlowGraphAllocator::DumpLiveness() {
+  const intptr_t block_count = postorder_.length();
+  for (intptr_t i = 0; i < block_count; i++) {
+    BlockEntryInstr* block = postorder_[i];
+    printf("block @%d -> ", block->block_id());

[srdjan, 2012/06/25 17:30:05]

OS::Print here as well.

+
+    Instruction* last = block->last_instruction();
+    for (intptr_t j = 0; j < last->SuccessorCount(); j++) {
+      BlockEntryInstr* succ = last->SuccessorAt(j);
+      printf(" @%d", succ->block_id());
+    }
+    printf("\n");
+
+    PrintBitVector("  live out", live_out_[i]);
+    PrintBitVector("  kill", kill_[i]);
+    PrintBitVector("  gen", gen_[i]);
+    PrintBitVector("  live in", live_in_[i]);

[Florian Schneider, 2012/06/25 14:38:29]

Maybe print in a different order? e.g. live_in, gen, kill, live_out

[Vyacheslav Egorov (Google), 2012/06/25 16:58:26]

We print blocks in post order so printing live out first seems to match it.

+  }
+}
+
+
 }  // namespace dart