Build live-in, live-out and kill sets for each block.
This information will be used when computing live ranges of
instructions.
Change-Id: I345ee833c1ccb4a8e725c7976453f6d58d350d74
diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk
index 429c523..d4e2cbb 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -78,6 +78,7 @@
compiler/oat_test.cc \
compiler/optimizing/codegen_test.cc \
compiler/optimizing/dominator_test.cc \
+ compiler/optimizing/liveness_test.cc \
compiler/optimizing/pretty_printer_test.cc \
compiler/optimizing/ssa_test.cc \
compiler/output_stream_test.cc \
diff --git a/compiler/Android.mk b/compiler/Android.mk
index e3201e7..a993251 100644
--- a/compiler/Android.mk
+++ b/compiler/Android.mk
@@ -79,6 +79,7 @@
optimizing/nodes.cc \
optimizing/optimizing_compiler.cc \
optimizing/ssa_builder.cc \
+ optimizing/ssa_liveness_analysis.cc \
trampolines/trampoline_compiler.cc \
utils/arena_allocator.cc \
utils/arena_bit_vector.cc \
diff --git a/compiler/optimizing/code_generator.cc b/compiler/optimizing/code_generator.cc
index 8b85d71..bbebd3a 100644
--- a/compiler/optimizing/code_generator.cc
+++ b/compiler/optimizing/code_generator.cc
@@ -30,12 +30,12 @@
namespace art {
void CodeGenerator::Compile(CodeAllocator* allocator) {
- const GrowableArray<HBasicBlock*>* blocks = GetGraph()->GetBlocks();
- DCHECK(blocks->Get(0) == GetGraph()->GetEntryBlock());
- DCHECK(GoesToNextBlock(GetGraph()->GetEntryBlock(), blocks->Get(1)));
+ const GrowableArray<HBasicBlock*>& blocks = GetGraph()->GetBlocks();
+ DCHECK(blocks.Get(0) == GetGraph()->GetEntryBlock());
+ DCHECK(GoesToNextBlock(GetGraph()->GetEntryBlock(), blocks.Get(1)));
GenerateFrameEntry();
- for (size_t i = 0; i < blocks->Size(); i++) {
- CompileBlock(blocks->Get(i));
+ for (size_t i = 0, e = blocks.Size(); i < e; ++i) {
+ CompileBlock(blocks.Get(i));
}
size_t code_size = GetAssembler()->CodeSize();
uint8_t* buffer = allocator->Allocate(code_size);
diff --git a/compiler/optimizing/code_generator.h b/compiler/optimizing/code_generator.h
index 74cbccc..aafd801 100644
--- a/compiler/optimizing/code_generator.h
+++ b/compiler/optimizing/code_generator.h
@@ -354,7 +354,7 @@
pc_infos_(graph->GetArena(), 32),
blocked_registers_(static_cast<bool*>(
graph->GetArena()->Alloc(number_of_registers * sizeof(bool), kArenaAllocData))) {
- block_labels_.SetSize(graph->GetBlocks()->Size());
+ block_labels_.SetSize(graph->GetBlocks().Size());
}
~CodeGenerator() { }
diff --git a/compiler/optimizing/dominator_test.cc b/compiler/optimizing/dominator_test.cc
index 1c30b79..0417050 100644
--- a/compiler/optimizing/dominator_test.cc
+++ b/compiler/optimizing/dominator_test.cc
@@ -32,13 +32,13 @@
HGraph* graph = builder.BuildGraph(*item);
ASSERT_NE(graph, nullptr);
graph->BuildDominatorTree();
- ASSERT_EQ(graph->GetBlocks()->Size(), blocks_length);
- for (size_t i = 0; i < blocks_length; i++) {
+ ASSERT_EQ(graph->GetBlocks().Size(), blocks_length);
+ for (size_t i = 0, e = blocks_length; i < e; ++i) {
if (blocks[i] == -1) {
- ASSERT_EQ(nullptr, graph->GetBlocks()->Get(i)->GetDominator());
+ ASSERT_EQ(nullptr, graph->GetBlocks().Get(i)->GetDominator());
} else {
- ASSERT_NE(nullptr, graph->GetBlocks()->Get(i)->GetDominator());
- ASSERT_EQ(blocks[i], graph->GetBlocks()->Get(i)->GetDominator()->GetBlockId());
+ ASSERT_NE(nullptr, graph->GetBlocks().Get(i)->GetDominator());
+ ASSERT_EQ(blocks[i], graph->GetBlocks().Get(i)->GetDominator()->GetBlockId());
}
}
}
diff --git a/compiler/optimizing/liveness_test.cc b/compiler/optimizing/liveness_test.cc
new file mode 100644
index 0000000..aa4d35e
--- /dev/null
+++ b/compiler/optimizing/liveness_test.cc
@@ -0,0 +1,515 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "builder.h"
+#include "dex_file.h"
+#include "dex_instruction.h"
+#include "nodes.h"
+#include "optimizing_unit_test.h"
+#include "ssa_liveness_analysis.h"
+#include "utils/arena_allocator.h"
+
+#include "gtest/gtest.h"
+
+namespace art {
+
+static void TestCode(const uint16_t* data, const char* expected) {
+ ArenaPool pool;
+ ArenaAllocator allocator(&pool);
+ HGraphBuilder builder(&allocator);
+ const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data);
+ HGraph* graph = builder.BuildGraph(*item);
+ ASSERT_NE(graph, nullptr);
+ graph->BuildDominatorTree();
+ graph->TransformToSSA();
+ SsaLivenessAnalysis liveness(*graph);
+ liveness.Analyze();
+
+ std::ostringstream buffer;
+ for (HInsertionOrderIterator it(*graph); !it.Done(); it.Advance()) {
+ HBasicBlock* block = it.Current();
+ buffer << "Block " << block->GetBlockId() << std::endl;
+ BitVector* live_in = liveness.GetLiveInSet(*block);
+ live_in->Dump(buffer, " live in: ");
+ BitVector* live_out = liveness.GetLiveOutSet(*block);
+ live_out->Dump(buffer, " live out: ");
+ BitVector* kill = liveness.GetKillSet(*block);
+ kill->Dump(buffer, " kill: ");
+ }
+ ASSERT_STREQ(expected, buffer.str().c_str());
+}
+
+TEST(LivenessTest, CFG1) {
+ const char* expected =
+ "Block 0\n"
+ " live in: ()\n"
+ " live out: ()\n"
+ " kill: ()\n"
+ "Block 1\n"
+ " live in: ()\n"
+ " live out: ()\n"
+ " kill: ()\n"
+ "Block 2\n"
+ " live in: ()\n"
+ " live out: ()\n"
+ " kill: ()\n";
+
+ // Constant is not used.
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::RETURN_VOID);
+
+ TestCode(data, expected);
+}
+
+TEST(LivenessTest, CFG2) {
+ const char* expected =
+ "Block 0\n"
+ " live in: (0)\n"
+ " live out: (1)\n"
+ " kill: (1)\n"
+ "Block 1\n"
+ " live in: (1)\n"
+ " live out: (0)\n"
+ " kill: (0)\n"
+ "Block 2\n"
+ " live in: (0)\n"
+ " live out: (0)\n"
+ " kill: (0)\n";
+
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::RETURN);
+
+ TestCode(data, expected);
+}
+
+TEST(LivenessTest, CFG3) {
+ const char* expected =
+ "Block 0\n" // entry block
+ " live in: (000)\n"
+ " live out: (110)\n"
+ " kill: (110)\n"
+ "Block 1\n" // block with add
+ " live in: (110)\n"
+ " live out: (001)\n"
+ " kill: (001)\n"
+ "Block 2\n" // block with return
+ " live in: (001)\n"
+ " live out: (000)\n"
+ " kill: (000)\n"
+ "Block 3\n" // exit block
+ " live in: (000)\n"
+ " live out: (000)\n"
+ " kill: (000)\n";
+
+ const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
+ Instruction::CONST_4 | 3 << 12 | 0,
+ Instruction::CONST_4 | 4 << 12 | 1 << 8,
+ Instruction::ADD_INT_2ADDR | 1 << 12,
+ Instruction::GOTO | 0x100,
+ Instruction::RETURN);
+
+ TestCode(data, expected);
+}
+
+TEST(LivenessTest, CFG4) {
+ // var a;
+ // if (0 == 0) {
+ // a = 5;
+ // } else {
+ // a = 4;
+ // }
+ // return a;
+ //
+ // Bitsets are made of:
+ // (constant0, constant4, constant5, phi, equal test)
+ const char* expected =
+ "Block 0\n" // entry block
+ " live in: (00000)\n"
+ " live out: (11100)\n"
+ " kill: (11100)\n"
+ "Block 1\n" // block with if
+ " live in: (11100)\n"
+ " live out: (01100)\n"
+ " kill: (00010)\n"
+ "Block 2\n" // else block
+ " live in: (01000)\n"
+ " live out: (00000)\n"
+ " kill: (00000)\n"
+ "Block 3\n" // then block
+ " live in: (00100)\n"
+ " live out: (00000)\n"
+ " kill: (00000)\n"
+ "Block 4\n" // return block
+ " live in: (00000)\n"
+ " live out: (00000)\n"
+ " kill: (00001)\n"
+ "Block 5\n" // exit block
+ " live in: (00000)\n"
+ " live out: (00000)\n"
+ " kill: (00000)\n";
+
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::IF_EQ, 4,
+ Instruction::CONST_4 | 4 << 12 | 0,
+ Instruction::GOTO | 0x200,
+ Instruction::CONST_4 | 5 << 12 | 0,
+ Instruction::RETURN | 0 << 8);
+
+ TestCode(data, expected);
+}
+
+TEST(LivenessTest, CFG5) {
+ // var a = 0;
+ // if (0 == 0) {
+ // } else {
+ // a = 4;
+ // }
+ // return a;
+ const char* expected =
+ "Block 0\n" // entry block
+ " live in: (0000)\n"
+ " live out: (1100)\n"
+ " kill: (1100)\n"
+ "Block 1\n" // block with if
+ " live in: (1100)\n"
+ " live out: (0100)\n"
+ " kill: (0010)\n"
+ "Block 2\n" // else block
+ " live in: (0100)\n"
+ " live out: (0000)\n"
+ " kill: (0000)\n"
+ "Block 3\n" // return block
+ " live in: (0000)\n"
+ " live out: (0000)\n"
+ " kill: (0001)\n"
+ "Block 4\n" // exit block
+ " live in: (0000)\n"
+ " live out: (0000)\n"
+ " kill: (0000)\n";
+
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::IF_EQ, 3,
+ Instruction::CONST_4 | 4 << 12 | 0,
+ Instruction::RETURN | 0 << 8);
+
+ TestCode(data, expected);
+}
+
+TEST(LivenessTest, Loop1) {
+ // Simple loop with one preheader and one back edge.
+ // var a = 0;
+ // while (a == a) {
+ // a = 4;
+ // }
+ // return;
+ const char* expected =
+ "Block 0\n" // entry block
+ " live in: (0000)\n"
+ " live out: (1100)\n"
+ " kill: (1100)\n"
+ "Block 1\n" // pre header
+ " live in: (1100)\n"
+ " live out: (0100)\n"
+ " kill: (0000)\n"
+ "Block 2\n" // loop header
+ " live in: (0100)\n"
+ " live out: (0100)\n"
+ " kill: (0011)\n"
+ "Block 3\n" // back edge
+ " live in: (0100)\n"
+ " live out: (0100)\n"
+ " kill: (0000)\n"
+ "Block 4\n" // return block
+ " live in: (0000)\n"
+ " live out: (0000)\n"
+ " kill: (0000)\n"
+ "Block 5\n" // exit block
+ " live in: (0000)\n"
+ " live out: (0000)\n"
+ " kill: (0000)\n";
+
+
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::IF_EQ, 4,
+ Instruction::CONST_4 | 4 << 12 | 0,
+ Instruction::GOTO | 0xFD00,
+ Instruction::RETURN_VOID);
+
+ TestCode(data, expected);
+}
+
+TEST(LivenessTest, Loop3) {
+ // Test that the returned value stays live in a preceding loop.
+ // var a = 0;
+ // while (a == a) {
+ // a = 4;
+ // }
+ // return 5;
+ const char* expected =
+ "Block 0\n"
+ " live in: (00000)\n"
+ " live out: (11100)\n"
+ " kill: (11100)\n"
+ "Block 1\n"
+ " live in: (11100)\n"
+ " live out: (01100)\n"
+ " kill: (00000)\n"
+ "Block 2\n" // loop header
+ " live in: (01100)\n"
+ " live out: (01100)\n"
+ " kill: (00011)\n"
+ "Block 3\n" // back edge
+ " live in: (01100)\n"
+ " live out: (01100)\n"
+ " kill: (00000)\n"
+ "Block 4\n" // return block
+ " live in: (00100)\n"
+ " live out: (00000)\n"
+ " kill: (00000)\n"
+ "Block 5\n" // exit block
+ " live in: (00000)\n"
+ " live out: (00000)\n"
+ " kill: (00000)\n";
+
+ const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::IF_EQ, 4,
+ Instruction::CONST_4 | 4 << 12 | 0,
+ Instruction::GOTO | 0xFD00,
+ Instruction::CONST_4 | 5 << 12 | 1 << 8,
+ Instruction::RETURN | 1 << 8);
+
+ TestCode(data, expected);
+}
+
+
+TEST(LivenessTest, Loop4) {
+ // Make sure we support a preheader of a loop not being the first predecessor
+ // in the predecessor list of the header.
+ // var a = 0;
+ // while (a == a) {
+ // a = 4;
+ // }
+ // return a;
+ // Bitsets are made of:
+ // (constant0, constant4, phi, equal test)
+ const char* expected =
+ "Block 0\n"
+ " live in: (0000)\n"
+ " live out: (1100)\n"
+ " kill: (1100)\n"
+ "Block 1\n"
+ " live in: (1100)\n"
+ " live out: (1100)\n"
+ " kill: (0000)\n"
+ "Block 2\n" // loop header
+ " live in: (0100)\n"
+ " live out: (0110)\n"
+ " kill: (0011)\n"
+ "Block 3\n" // back edge
+ " live in: (0100)\n"
+ " live out: (0100)\n"
+ " kill: (0000)\n"
+ "Block 4\n" // pre loop header
+ " live in: (1100)\n"
+ " live out: (0100)\n"
+ " kill: (0000)\n"
+ "Block 5\n" // return block
+ " live in: (0010)\n"
+ " live out: (0000)\n"
+ " kill: (0000)\n"
+ "Block 6\n" // exit block
+ " live in: (0000)\n"
+ " live out: (0000)\n"
+ " kill: (0000)\n";
+
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::GOTO | 0x500,
+ Instruction::IF_EQ, 5,
+ Instruction::CONST_4 | 4 << 12 | 0,
+ Instruction::GOTO | 0xFD00,
+ Instruction::GOTO | 0xFC00,
+ Instruction::RETURN | 0 << 8);
+
+ TestCode(data, expected);
+}
+
+TEST(LivenessTest, Loop5) {
+ // Make sure we create a preheader of a loop when a header originally has two
+ // incoming blocks and one back edge.
+ // Bitsets are made of:
+ // (constant0, constant4, constant5, equal in block 1, phi in block 8, phi in block 4,
+ // equal in block 4)
+ const char* expected =
+ "Block 0\n"
+ " live in: (0000000)\n"
+ " live out: (1110000)\n"
+ " kill: (1110000)\n"
+ "Block 1\n"
+ " live in: (1110000)\n"
+ " live out: (0110000)\n"
+ " kill: (0001000)\n"
+ "Block 2\n"
+ " live in: (0100000)\n"
+ " live out: (0000000)\n"
+ " kill: (0000000)\n"
+ "Block 3\n"
+ " live in: (0010000)\n"
+ " live out: (0000000)\n"
+ " kill: (0000000)\n"
+ "Block 4\n" // loop header
+ " live in: (0000000)\n"
+ " live out: (0000010)\n"
+ " kill: (0000011)\n"
+ "Block 5\n" // back edge
+ " live in: (0000010)\n"
+ " live out: (0000000)\n"
+ " kill: (0000000)\n"
+ "Block 6\n" // return block
+ " live in: (0000010)\n"
+ " live out: (0000000)\n"
+ " kill: (0000000)\n"
+ "Block 7\n" // exit block
+ " live in: (0000000)\n"
+ " live out: (0000000)\n"
+ " kill: (0000000)\n"
+ "Block 8\n" // synthesized pre header
+ " live in: (0000000)\n"
+ " live out: (0000000)\n"
+ " kill: (0000100)\n";
+
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::IF_EQ, 4,
+ Instruction::CONST_4 | 4 << 12 | 0,
+ Instruction::GOTO | 0x200,
+ Instruction::CONST_4 | 5 << 12 | 0,
+ Instruction::IF_EQ, 3,
+ Instruction::GOTO | 0xFE00,
+ Instruction::RETURN | 0 << 8);
+
+ TestCode(data, expected);
+}
+
+TEST(LivenessTest, Loop6) {
+ // Bitsets are made of:
+ // (constant0, constant4, constant5, phi in block 2, equal in block 2, equal in block 3)
+ const char* expected =
+ "Block 0\n"
+ " live in: (000000)\n"
+ " live out: (111000)\n"
+ " kill: (111000)\n"
+ "Block 1\n"
+ " live in: (111000)\n"
+ " live out: (011000)\n"
+ " kill: (000000)\n"
+ "Block 2\n" // loop header
+ " live in: (011000)\n"
+ " live out: (011100)\n"
+ " kill: (000110)\n"
+ "Block 3\n"
+ " live in: (011000)\n"
+ " live out: (011000)\n"
+ " kill: (000001)\n"
+ "Block 4\n" // back edge
+ " live in: (011000)\n"
+ " live out: (011000)\n"
+ " kill: (000000)\n"
+ "Block 5\n" // back edge
+ " live in: (011000)\n"
+ " live out: (011000)\n"
+ " kill: (000000)\n"
+ "Block 6\n" // return block
+ " live in: (000100)\n"
+ " live out: (000000)\n"
+ " kill: (000000)\n"
+ "Block 7\n" // exit block
+ " live in: (000000)\n"
+ " live out: (000000)\n"
+ " kill: (000000)\n";
+
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::IF_EQ, 8,
+ Instruction::CONST_4 | 4 << 12 | 0,
+ Instruction::IF_EQ, 4,
+ Instruction::CONST_4 | 5 << 12 | 0,
+ Instruction::GOTO | 0xFA00,
+ Instruction::GOTO | 0xF900,
+ Instruction::RETURN | 0 << 8);
+
+ TestCode(data, expected);
+}
+
+
+TEST(LivenessTest, Loop7) {
+ // Bitsets are made of:
+ // (constant0, constant4, constant5, phi in block 2, equal in block 2, equal in block 3,
+ // phi in block 6)
+ const char* expected =
+ "Block 0\n"
+ " live in: (0000000)\n"
+ " live out: (1110000)\n"
+ " kill: (1110000)\n"
+ "Block 1\n"
+ " live in: (1110000)\n"
+ " live out: (0110000)\n"
+ " kill: (0000000)\n"
+ "Block 2\n" // loop header
+ " live in: (0110000)\n"
+ " live out: (0110000)\n"
+ " kill: (0001100)\n"
+ "Block 3\n"
+ " live in: (0110000)\n"
+ " live out: (0110000)\n"
+ " kill: (0000010)\n"
+ "Block 4\n" // loop exit
+ " live in: (0010000)\n"
+ " live out: (0000000)\n"
+ " kill: (0000000)\n"
+ "Block 5\n" // back edge
+ " live in: (0110000)\n"
+ " live out: (0110000)\n"
+ " kill: (0000000)\n"
+ "Block 6\n" // return block
+ " live in: (0000000)\n"
+ " live out: (0000000)\n"
+ " kill: (0000001)\n"
+ "Block 7\n" // exit block
+ " live in: (0000000)\n"
+ " live out: (0000000)\n"
+ " kill: (0000000)\n";
+
+ const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::IF_EQ, 8,
+ Instruction::CONST_4 | 4 << 12 | 0,
+ Instruction::IF_EQ, 4,
+ Instruction::CONST_4 | 5 << 12 | 0,
+ Instruction::GOTO | 0x0200,
+ Instruction::GOTO | 0xF900,
+ Instruction::RETURN | 0 << 8);
+
+ TestCode(data, expected);
+}
+
+} // namespace art
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 3d6aeb7..d153bf7 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -25,7 +25,7 @@
blocks_.Add(block);
}
-void HGraph::FindBackEdges(ArenaBitVector* visited) const {
+void HGraph::FindBackEdges(ArenaBitVector* visited) {
ArenaBitVector visiting(arena_, blocks_.Size(), false);
VisitBlockForBackEdges(entry_block_, visited, &visiting);
}
@@ -49,7 +49,7 @@
void HGraph::VisitBlockForBackEdges(HBasicBlock* block,
ArenaBitVector* visited,
- ArenaBitVector* visiting) const {
+ ArenaBitVector* visiting) {
int id = block->GetBlockId();
if (visited->IsBitSet(id)) return;
@@ -63,6 +63,7 @@
VisitBlockForBackEdges(successor, visited, visiting);
}
}
+ post_order_.Add(block);
visiting->ClearBit(id);
}
@@ -82,7 +83,6 @@
// have been processed.
GrowableArray<size_t> visits(arena_, blocks_.Size());
visits.SetSize(blocks_.Size());
- dominator_order_.Add(entry_block_);
for (size_t i = 0; i < entry_block_->GetSuccessors()->Size(); i++) {
VisitBlockForDominatorTree(entry_block_->GetSuccessors()->Get(i), entry_block_, &visits);
}
@@ -120,7 +120,6 @@
// dominator of the block. We can then start visiting its successors.
if (visits->Get(block->GetBlockId()) ==
block->GetPredecessors()->Size() - block->NumberOfBackEdges()) {
- dominator_order_.Add(block);
for (size_t i = 0; i < block->GetSuccessors()->Size(); i++) {
VisitBlockForDominatorTree(block->GetSuccessors()->Get(i), block, visits);
}
@@ -128,15 +127,15 @@
}
void HGraph::TransformToSSA() {
- DCHECK(!dominator_order_.IsEmpty());
+ DCHECK(!post_order_.IsEmpty());
SimplifyCFG();
SsaBuilder ssa_builder(this);
ssa_builder.BuildSsa();
}
void HGraph::SimplifyCFG() {
- for (size_t i = 0; i < dominator_order_.Size(); i++) {
- HBasicBlock* current = dominator_order_.Get(i);
+ for (size_t i = post_order_.Size(); i > 0; --i) {
+ HBasicBlock* current = post_order_.Get(i - 1);
if (current->IsLoopHeader()) {
// Make sure the loop has only one pre header. This simplifies SSA building by having
// to just look at the pre header to know which locals are initialized at entry of the
@@ -149,10 +148,9 @@
pre_header->AddInstruction(new (arena_) HGoto());
pre_header->SetDominator(current->GetDominator());
current->SetDominator(pre_header);
- dominator_order_.InsertAt(i, pre_header);
- i++;
+ post_order_.InsertAt(i, pre_header);
- ArenaBitVector back_edges(arena_, GetBlocks()->Size(), false);
+ ArenaBitVector back_edges(arena_, GetBlocks().Size(), false);
for (size_t pred = 0; pred < info->GetBackEdges()->Size(); pred++) {
back_edges.SetBit(info->GetBackEdges()->Get(pred)->GetBlockId());
}
@@ -298,9 +296,9 @@
#undef DEFINE_ACCEPT
void HGraphVisitor::VisitInsertionOrder() {
- const GrowableArray<HBasicBlock*>* blocks = graph_->GetBlocks();
- for (size_t i = 0 ; i < blocks->Size(); i++) {
- VisitBasicBlock(blocks->Get(i));
+ const GrowableArray<HBasicBlock*>& blocks = graph_->GetBlocks();
+ for (size_t i = 0 ; i < blocks.Size(); i++) {
+ VisitBasicBlock(blocks.Get(i));
}
}
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 581c1d5..bd3d703 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -49,6 +49,7 @@
friend class HBasicBlock;
friend class HInstructionIterator;
+ friend class HBackwardInstructionIterator;
DISALLOW_COPY_AND_ASSIGN(HInstructionList);
};
@@ -59,14 +60,14 @@
explicit HGraph(ArenaAllocator* arena)
: arena_(arena),
blocks_(arena, kDefaultNumberOfBlocks),
- dominator_order_(arena, kDefaultNumberOfBlocks),
+ post_order_(arena, kDefaultNumberOfBlocks),
maximum_number_of_out_vregs_(0),
number_of_vregs_(0),
number_of_in_vregs_(0),
current_instruction_id_(0) { }
ArenaAllocator* GetArena() const { return arena_; }
- const GrowableArray<HBasicBlock*>* GetBlocks() const { return &blocks_; }
+ const GrowableArray<HBasicBlock*>& GetBlocks() const { return blocks_; }
HBasicBlock* GetEntryBlock() const { return entry_block_; }
HBasicBlock* GetExitBlock() const { return exit_block_; }
@@ -108,8 +109,8 @@
return number_of_in_vregs_;
}
- GrowableArray<HBasicBlock*>* GetDominatorOrder() {
- return &dominator_order_;
+ const GrowableArray<HBasicBlock*>& GetPostOrder() const {
+ return post_order_;
}
private:
@@ -117,10 +118,10 @@
void VisitBlockForDominatorTree(HBasicBlock* block,
HBasicBlock* predecessor,
GrowableArray<size_t>* visits);
- void FindBackEdges(ArenaBitVector* visited) const;
+ void FindBackEdges(ArenaBitVector* visited);
void VisitBlockForBackEdges(HBasicBlock* block,
ArenaBitVector* visited,
- ArenaBitVector* visiting) const;
+ ArenaBitVector* visiting);
void RemoveDeadBlocks(const ArenaBitVector& visited) const;
ArenaAllocator* const arena_;
@@ -128,8 +129,8 @@
// List of blocks in insertion order.
GrowableArray<HBasicBlock*> blocks_;
- // List of blocks to perform a pre-order dominator tree traversal.
- GrowableArray<HBasicBlock*> dominator_order_;
+ // List of blocks to perform a post order tree traversal.
+ GrowableArray<HBasicBlock*> post_order_;
HBasicBlock* entry_block_;
HBasicBlock* exit_block_;
@@ -322,6 +323,7 @@
next_(nullptr),
block_(nullptr),
id_(-1),
+ ssa_index_(-1),
uses_(nullptr),
env_uses_(nullptr),
environment_(nullptr),
@@ -360,11 +362,17 @@
HUseListNode<HInstruction>* GetUses() const { return uses_; }
HUseListNode<HEnvironment>* GetEnvUses() const { return env_uses_; }
- bool HasUses() const { return uses_ != nullptr; }
+ bool HasUses() const { return uses_ != nullptr || env_uses_ != nullptr; }
int GetId() const { return id_; }
void SetId(int id) { id_ = id; }
+ int GetSsaIndex() const { return ssa_index_; }
+ void SetSsaIndex(int ssa_index) { ssa_index_ = ssa_index; }
+ bool HasSsaIndex() const { return ssa_index_ != -1; }
+
+ bool HasEnvironment() const { return environment_ != nullptr; }
+ HEnvironment* GetEnvironment() const { return environment_; }
void SetEnvironment(HEnvironment* environment) { environment_ = environment; }
LocationSummary* GetLocations() const { return locations_; }
@@ -388,6 +396,9 @@
// has not beed added to the graph.
int id_;
+ // When doing liveness analysis, instructions that have uses get an SSA index.
+ int ssa_index_;
+
// List of instructions that have this instruction as input.
HUseListNode<HInstruction>* uses_;
@@ -496,6 +507,25 @@
HInstruction* next_;
};
+class HBackwardInstructionIterator : public ValueObject {
+ public:
+ explicit HBackwardInstructionIterator(const HInstructionList& instructions)
+ : instruction_(instructions.last_instruction_) {
+ next_ = Done() ? nullptr : instruction_->GetPrevious();
+ }
+
+ bool Done() const { return instruction_ == nullptr; }
+ HInstruction* Current() const { return instruction_; }
+ void Advance() {
+ instruction_ = next_;
+ next_ = Done() ? nullptr : instruction_->GetPrevious();
+ }
+
+ private:
+ HInstruction* instruction_;
+ HInstruction* next_;
+};
+
// An embedded container with N elements of type T. Used (with partial
// specialization for N=0) because embedded arrays cannot have size 0.
template<typename T, intptr_t N>
@@ -966,6 +996,52 @@
DISALLOW_COPY_AND_ASSIGN(HGraphVisitor);
};
+class HInsertionOrderIterator : public ValueObject {
+ public:
+ explicit HInsertionOrderIterator(const HGraph& graph) : graph_(graph), index_(0) {}
+
+ bool Done() const { return index_ == graph_.GetBlocks().Size(); }
+ HBasicBlock* Current() const { return graph_.GetBlocks().Get(index_); }
+ void Advance() { ++index_; }
+
+ private:
+ const HGraph& graph_;
+ size_t index_;
+
+ DISALLOW_COPY_AND_ASSIGN(HInsertionOrderIterator);
+};
+
+class HPostOrderIterator : public ValueObject {
+ public:
+ explicit HPostOrderIterator(const HGraph& graph) : graph_(graph), index_(0) {}
+
+ bool Done() const { return index_ == graph_.GetPostOrder().Size(); }
+ HBasicBlock* Current() const { return graph_.GetPostOrder().Get(index_); }
+ void Advance() { ++index_; }
+
+ private:
+ const HGraph& graph_;
+ size_t index_;
+
+ DISALLOW_COPY_AND_ASSIGN(HPostOrderIterator);
+};
+
+class HReversePostOrderIterator : public ValueObject {
+ public:
+ explicit HReversePostOrderIterator(const HGraph& graph)
+ : graph_(graph), index_(graph_.GetPostOrder().Size()) {}
+
+ bool Done() const { return index_ == 0; }
+ HBasicBlock* Current() const { return graph_.GetPostOrder().Get(index_ - 1); }
+ void Advance() { --index_; }
+
+ private:
+ const HGraph& graph_;
+ size_t index_;
+
+ DISALLOW_COPY_AND_ASSIGN(HReversePostOrderIterator);
+};
+
} // namespace art
#endif // ART_COMPILER_OPTIMIZING_NODES_H_
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index 9438890..4c75cd4 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -22,6 +22,7 @@
#include "driver/compiler_driver.h"
#include "driver/dex_compilation_unit.h"
#include "nodes.h"
+#include "ssa_liveness_analysis.h"
#include "utils/arena_allocator.h"
namespace art {
@@ -103,6 +104,7 @@
// Run these phases to get some test coverage.
graph->BuildDominatorTree();
graph->TransformToSSA();
+ SsaLivenessAnalysis(*graph).Analyze();
return new CompiledMethod(driver,
instruction_set,
diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc
index bfb4f38..ee1e1e4 100644
--- a/compiler/optimizing/ssa_builder.cc
+++ b/compiler/optimizing/ssa_builder.cc
@@ -20,11 +20,11 @@
namespace art {
void SsaBuilder::BuildSsa() {
- // 1) Visit in dominator order. We need to have all predecessors of a block visited
+ // 1) Visit in reverse post order. We need to have all predecessors of a block visited
// (with the exception of loops) in order to create the right environment for that
// block. For loops, we create phis whose inputs will be set in 2).
- for (size_t i = 0; i < GetGraph()->GetDominatorOrder()->Size(); i++) {
- VisitBasicBlock(GetGraph()->GetDominatorOrder()->Get(i));
+ for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) {
+ VisitBasicBlock(it.Current());
}
// 2) Set inputs of loop phis.
@@ -59,7 +59,7 @@
if (block->IsLoopHeader()) {
// If the block is a loop header, we know we only have visited the pre header
- // because we are visiting in dominator order. We create phis for all initialized
+ // because we are visiting in reverse post order. We create phis for all initialized
// locals from the pre header. Their inputs will be populated at the end of
// the analysis.
for (size_t local = 0; local < current_locals_->Size(); local++) {
@@ -76,7 +76,7 @@
// blocks need to be updated.
loop_headers_.Add(block);
} else if (block->GetPredecessors()->Size() > 0) {
- // All predecessors have already been visited because we are visiting in dominator order.
+ // All predecessors have already been visited because we are visiting in reverse post order.
// We merge the values of all locals, creating phis if those values differ.
for (size_t local = 0; local < current_locals_->Size(); local++) {
bool is_different = false;
diff --git a/compiler/optimizing/ssa_builder.h b/compiler/optimizing/ssa_builder.h
index b6c6c0b..9d8c072 100644
--- a/compiler/optimizing/ssa_builder.h
+++ b/compiler/optimizing/ssa_builder.h
@@ -29,8 +29,8 @@
: HGraphVisitor(graph),
current_locals_(nullptr),
loop_headers_(graph->GetArena(), kDefaultNumberOfLoops),
- locals_for_(graph->GetArena(), graph->GetBlocks()->Size()) {
- locals_for_.SetSize(graph->GetBlocks()->Size());
+ locals_for_(graph->GetArena(), graph->GetBlocks().Size()) {
+ locals_for_.SetSize(graph->GetBlocks().Size());
}
void BuildSsa();
diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc
new file mode 100644
index 0000000..838597d
--- /dev/null
+++ b/compiler/optimizing/ssa_liveness_analysis.cc
@@ -0,0 +1,170 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "ssa_liveness_analysis.h"
+#include "nodes.h"
+
+namespace art {
+
+void SsaLivenessAnalysis::Analyze() {
+ NumberInstructions();
+ ComputeSets();
+}
+
+void SsaLivenessAnalysis::NumberInstructions() {
+ int ssa_index = 0;
+ for (HReversePostOrderIterator it(graph_); !it.Done(); it.Advance()) {
+ HBasicBlock* block = it.Current();
+
+ for (HInstructionIterator it(*block->GetPhis()); !it.Done(); it.Advance()) {
+ HInstruction* current = it.Current();
+ if (current->HasUses()) {
+ current->SetSsaIndex(ssa_index++);
+ }
+ }
+
+ for (HInstructionIterator it(*block->GetInstructions()); !it.Done(); it.Advance()) {
+ HInstruction* current = it.Current();
+ if (current->HasUses()) {
+ current->SetSsaIndex(ssa_index++);
+ }
+ }
+ }
+ number_of_ssa_values_ = ssa_index;
+}
+
+void SsaLivenessAnalysis::ComputeSets() {
+ for (HReversePostOrderIterator it(graph_); !it.Done(); it.Advance()) {
+ HBasicBlock* block = it.Current();
+ block_infos_.Put(
+ block->GetBlockId(),
+ new (graph_.GetArena()) BlockInfo(graph_.GetArena(), *block, number_of_ssa_values_));
+ }
+
+ // Compute the initial live_in, live_out, and kill sets. This method does not handle
+ // backward branches, therefore live_in and live_out sets are not yet correct.
+ ComputeInitialSets();
+
+ // Do a fixed point calculation to take into account backward branches,
+ // that will update live_in of loop headers, and therefore live_out and live_in
+ // of blocks in the loop.
+ ComputeLiveInAndLiveOutSets();
+}
+
+void SsaLivenessAnalysis::ComputeInitialSets() {
+ // Do a post orderr visit, adding inputs of instructions live in the block where
+ // that instruction is defined, and killing instructions that are being visited.
+ for (HPostOrderIterator it(graph_); !it.Done(); it.Advance()) {
+ HBasicBlock* block = it.Current();
+
+ BitVector* kill = GetKillSet(*block);
+ BitVector* live_in = GetLiveInSet(*block);
+
+ for (HBackwardInstructionIterator it(*block->GetInstructions()); !it.Done(); it.Advance()) {
+ HInstruction* current = it.Current();
+ if (current->HasSsaIndex()) {
+ kill->SetBit(current->GetSsaIndex());
+ live_in->ClearBit(current->GetSsaIndex());
+ }
+
+ // All inputs of an instruction must be live.
+ for (size_t i = 0, e = current->InputCount(); i < e; ++i) {
+ DCHECK(current->InputAt(i)->HasSsaIndex());
+ live_in->SetBit(current->InputAt(i)->GetSsaIndex());
+ }
+
+ if (current->HasEnvironment()) {
+ // All instructions in the environment must be live.
+ GrowableArray<HInstruction*>* environment = current->GetEnvironment()->GetVRegs();
+ for (size_t i = 0, e = environment->Size(); i < e; ++i) {
+ HInstruction* instruction = environment->Get(i);
+ if (instruction != nullptr) {
+ DCHECK(instruction->HasSsaIndex());
+ live_in->SetBit(instruction->GetSsaIndex());
+ }
+ }
+ }
+ }
+
+ for (HInstructionIterator it(*block->GetPhis()); !it.Done(); it.Advance()) {
+ HInstruction* current = it.Current();
+ if (current->HasSsaIndex()) {
+ kill->SetBit(current->GetSsaIndex());
+ live_in->ClearBit(current->GetSsaIndex());
+ }
+
+ // Mark a phi input live_in for its corresponding predecessor.
+ for (size_t i = 0, e = current->InputCount(); i < e; ++i) {
+ HInstruction* input = current->InputAt(i);
+
+ HBasicBlock* predecessor = block->GetPredecessors()->Get(i);
+ size_t ssa_index = input->GetSsaIndex();
+ BitVector* predecessor_kill = GetKillSet(*predecessor);
+ BitVector* predecessor_live_in = GetLiveInSet(*predecessor);
+
+ // Phi inputs from a back edge have already been visited. If the back edge
+ // block defines that input, we should not add it to its live_in.
+ if (!predecessor_kill->IsBitSet(ssa_index)) {
+ predecessor_live_in->SetBit(ssa_index);
+ }
+ }
+ }
+ }
+}
+
+void SsaLivenessAnalysis::ComputeLiveInAndLiveOutSets() {
+ bool changed;
+ do {
+ changed = false;
+
+ for (HPostOrderIterator it(graph_); !it.Done(); it.Advance()) {
+ const HBasicBlock& block = *it.Current();
+
+ // The live_in set depends on the kill set (which does not
+ // change in this loop), and the live_out set. If the live_out
+ // set does not change, there is no need to update the live_in set.
+ if (UpdateLiveOut(block) && UpdateLiveIn(block)) {
+ changed = true;
+ }
+ }
+ } while (changed);
+}
+
+bool SsaLivenessAnalysis::UpdateLiveOut(const HBasicBlock& block) {
+ BitVector* live_out = GetLiveOutSet(block);
+ bool changed = false;
+ // The live_out set of a block is the union of live_in sets of its successors.
+ for (size_t i = 0, e = block.GetSuccessors()->Size(); i < e; ++i) {
+ HBasicBlock* successor = block.GetSuccessors()->Get(i);
+ if (live_out->Union(GetLiveInSet(*successor))) {
+ changed = true;
+ }
+ }
+ return changed;
+}
+
+
+bool SsaLivenessAnalysis::UpdateLiveIn(const HBasicBlock& block) {
+ BitVector* live_out = GetLiveOutSet(block);
+ BitVector* kill = GetKillSet(block);
+ BitVector* live_in = GetLiveInSet(block);
+ // If live_out is updated (because of backward branches), we need to make
+ // sure instructions in live_out are also in live_in, unless they are killed
+ // by this block.
+ return live_in->UnionIfNotIn(live_out, kill);
+}
+
+} // namespace art
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
new file mode 100644
index 0000000..6a901d1
--- /dev/null
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -0,0 +1,101 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_COMPILER_OPTIMIZING_SSA_LIVENESS_ANALYSIS_H_
+#define ART_COMPILER_OPTIMIZING_SSA_LIVENESS_ANALYSIS_H_
+
+#include "nodes.h"
+
+namespace art {
+
+class BlockInfo : public ArenaObject {
+ public:
+ BlockInfo(ArenaAllocator* allocator, const HBasicBlock& block, size_t number_of_ssa_values)
+ : block_(block),
+ live_in_(allocator, number_of_ssa_values, false),
+ live_out_(allocator, number_of_ssa_values, false),
+ kill_(allocator, number_of_ssa_values, false) {
+ live_in_.ClearAllBits();
+ live_out_.ClearAllBits();
+ kill_.ClearAllBits();
+ }
+
+ private:
+ const HBasicBlock& block_;
+ ArenaBitVector live_in_;
+ ArenaBitVector live_out_;
+ ArenaBitVector kill_;
+
+ friend class SsaLivenessAnalysis;
+
+ DISALLOW_COPY_AND_ASSIGN(BlockInfo);
+};
+
+class SsaLivenessAnalysis : public ValueObject {
+ public:
+ explicit SsaLivenessAnalysis(const HGraph& graph)
+ : graph_(graph),
+ block_infos_(graph.GetArena(), graph.GetBlocks().Size()),
+ number_of_ssa_values_(0) {
+ block_infos_.SetSize(graph.GetBlocks().Size());
+ }
+
+ void Analyze();
+
+ BitVector* GetLiveInSet(const HBasicBlock& block) const {
+ return &block_infos_.Get(block.GetBlockId())->live_in_;
+ }
+
+ BitVector* GetLiveOutSet(const HBasicBlock& block) const {
+ return &block_infos_.Get(block.GetBlockId())->live_out_;
+ }
+
+ BitVector* GetKillSet(const HBasicBlock& block) const {
+ return &block_infos_.Get(block.GetBlockId())->kill_;
+ }
+
+ private:
+ // Give an SSA number to each instruction that defines a value used by another instruction.
+ void NumberInstructions();
+
+ // Compute live_in, live_out and kill sets.
+ void ComputeSets();
+
+ // Compute the initial live_in, live_out and kill sets, without analyzing
+ // backward branches.
+ void ComputeInitialSets();
+
+ // After computing the initial sets, this method does a fixed point
+ // calculation over the live_in and live_out set to take into account
+ // backwards branches.
+ void ComputeLiveInAndLiveOutSets();
+
+ // Update the live_in set of the block and returns whether it has changed.
+ bool UpdateLiveIn(const HBasicBlock& block);
+
+ // Update the live_out set of the block and returns whether it has changed.
+ bool UpdateLiveOut(const HBasicBlock& block);
+
+ const HGraph& graph_;
+ GrowableArray<BlockInfo*> block_infos_;
+ size_t number_of_ssa_values_;
+
+ DISALLOW_COPY_AND_ASSIGN(SsaLivenessAnalysis);
+};
+
+} // namespace art
+
+#endif // ART_COMPILER_OPTIMIZING_SSA_LIVENESS_ANALYSIS_H_
diff --git a/compiler/optimizing/ssa_test.cc b/compiler/optimizing/ssa_test.cc
index 7c3633b..e4aafb7 100644
--- a/compiler/optimizing/ssa_test.cc
+++ b/compiler/optimizing/ssa_test.cc
@@ -64,8 +64,8 @@
static void ReNumberInstructions(HGraph* graph) {
int id = 0;
- for (size_t i = 0; i < graph->GetBlocks()->Size(); i++) {
- HBasicBlock* block = graph->GetBlocks()->Get(i);
+ for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++i) {
+ HBasicBlock* block = graph->GetBlocks().Get(i);
for (HInstructionIterator it(*block->GetPhis()); !it.Done(); it.Advance()) {
it.Current()->SetId(id++);
}
@@ -147,7 +147,7 @@
TEST(SsaTest, CFG3) {
// Test that we create a phi for the join block of an if control flow instruction
- // when there both branches update a local.
+ // when both branches update a local.
const char* expected =
"BasicBlock 0, succ: 1\n"
" 0: IntConstant 0 [4, 4]\n"
diff --git a/runtime/base/bit_vector.cc b/runtime/base/bit_vector.cc
index 3df5101..47e85a3 100644
--- a/runtime/base/bit_vector.cc
+++ b/runtime/base/bit_vector.cc
@@ -43,7 +43,8 @@
: allocator_(allocator),
expandable_(expandable),
storage_size_(storage_size),
- storage_(storage) {
+ storage_(storage),
+ number_of_bits_(start_bits) {
DCHECK_EQ(sizeof(*storage_), 4U); // Assuming 32-bit units.
if (storage_ == nullptr) {
storage_size_ = BitsToWords(start_bits);
@@ -93,6 +94,7 @@
// TOTO: collect stats on space wasted because of resize.
storage_ = new_storage;
storage_size_ = new_size;
+ number_of_bits_ = num;
}
storage_[num >> 5] |= check_masks[num & 0x1f];
@@ -156,13 +158,14 @@
/*
* Union with another bit vector.
*/
-void BitVector::Union(const BitVector* src) {
+bool BitVector::Union(const BitVector* src) {
// Get the highest bit to determine how much we need to expand.
int highest_bit = src->GetHighestBitSet();
+ bool changed = false;
// If src has no bit set, we are done: there is no need for a union with src.
if (highest_bit == -1) {
- return;
+ return changed;
}
// Update src_size to how many cells we actually care about: where the bit is + 1.
@@ -170,6 +173,8 @@
// Is the storage size smaller than src's?
if (storage_size_ < src_size) {
+ changed = true;
+
// Set it to reallocate.
SetBit(highest_bit);
@@ -178,8 +183,62 @@
}
for (uint32_t idx = 0; idx < src_size; idx++) {
- storage_[idx] |= src->GetRawStorageWord(idx);
+ uint32_t existing = storage_[idx];
+ uint32_t update = existing | src->GetRawStorageWord(idx);
+ if (existing != update) {
+ changed = true;
+ storage_[idx] = update;
+ }
}
+ return changed;
+}
+
+bool BitVector::UnionIfNotIn(const BitVector* union_with, const BitVector* not_in) {
+ // Get the highest bit to determine how much we need to expand.
+ int highest_bit = union_with->GetHighestBitSet();
+ bool changed = false;
+
+ // If src has no bit set, we are done: there is no need for a union with src.
+ if (highest_bit == -1) {
+ return changed;
+ }
+
+ // Update union_with_size to how many cells we actually care about: where the bit is + 1.
+ uint32_t union_with_size = BitsToWords(highest_bit + 1);
+
+ // Is the storage size smaller than src's?
+ if (storage_size_ < union_with_size) {
+ changed = true;
+
+ // Set it to reallocate.
+ SetBit(highest_bit);
+
+ // Paranoid: storage size should be big enough to hold this bit now.
+ DCHECK_LT(static_cast<uint32_t> (highest_bit), storage_size_ * sizeof(*(storage_)) * 8);
+ }
+
+ uint32_t not_in_size = not_in->GetStorageSize();
+
+ uint32_t idx = 0;
+ for (; idx < std::min(not_in_size, union_with_size); idx++) {
+ uint32_t existing = storage_[idx];
+ uint32_t update = existing |
+ (union_with->GetRawStorageWord(idx) & ~not_in->GetRawStorageWord(idx));
+ if (existing != update) {
+ changed = true;
+ storage_[idx] = update;
+ }
+ }
+
+ for (; idx < union_with_size; idx++) {
+ uint32_t existing = storage_[idx];
+ uint32_t update = existing | union_with->GetRawStorageWord(idx);
+ if (existing != update) {
+ changed = true;
+ storage_[idx] = update;
+ }
+ }
+ return changed;
}
void BitVector::Subtract(const BitVector *src) {
@@ -342,7 +401,7 @@
void BitVector::Dump(std::ostream& os, const char *prefix) {
std::ostringstream buffer;
DumpHelper(buffer, prefix);
- os << buffer << std::endl;
+ os << buffer.str() << std::endl;
}
void BitVector::DumpDot(FILE* file, const char* prefix, bool last_entry) {
@@ -367,13 +426,11 @@
buffer << prefix;
}
- int max = GetHighestBitSet();
-
- for (int i = 0; i <= max; i++) {
- if (IsBitSet(i)) {
- buffer << i << " ";
- }
+ buffer << '(';
+ for (size_t i = 0; i < number_of_bits_; i++) {
+ buffer << IsBitSet(i);
}
+ buffer << ')';
}
} // namespace art
diff --git a/runtime/base/bit_vector.h b/runtime/base/bit_vector.h
index db29c49..6ee6b00 100644
--- a/runtime/base/bit_vector.h
+++ b/runtime/base/bit_vector.h
@@ -103,7 +103,11 @@
void Copy(const BitVector* src);
void Intersect(const BitVector* src2);
- void Union(const BitVector* src);
+ bool Union(const BitVector* src);
+
+ // Set bits of union_with that are not in not_in.
+ bool UnionIfNotIn(const BitVector* union_with, const BitVector* not_in);
+
void Subtract(const BitVector* src);
// Are we equal to another bit vector? Note: expandability attributes must also match.
bool Equal(const BitVector* src) {
@@ -155,6 +159,7 @@
const bool expandable_; // expand bitmap if we run out?
uint32_t storage_size_; // current size, in 32-bit words.
uint32_t* storage_;
+ uint32_t number_of_bits_;
};