Add alignment to basic blocks.
A further CL will plumb this into the block builder.
BUG=
Review URL: https://codereview.appspot.com/6822076
git-svn-id: http://sawbuck.googlecode.com/svn/trunk/syzygy@1218 15e8cca8-e42c-11de-a347-f34a4f72eb7d
diff --git a/block_graph/basic_block.cc b/block_graph/basic_block.cc
index 1b2c7d6..d9319c0 100644
--- a/block_graph/basic_block.cc
+++ b/block_graph/basic_block.cc
@@ -624,6 +624,7 @@
BasicBlock::BasicBlock(const base::StringPiece& name,
BasicBlock::BasicBlockType type)
: name_(name.begin(), name.end()),
+ alignment_(1),
type_(type),
offset_(kNoOffset) {
}
diff --git a/block_graph/basic_block.h b/block_graph/basic_block.h
index 417239b..8ca6e40 100644
--- a/block_graph/basic_block.h
+++ b/block_graph/basic_block.h
@@ -22,6 +22,7 @@
#include "base/string_piece.h"
#include "syzygy/block_graph/block_graph.h"
+#include "syzygy/common/align.h"
#include "syzygy/core/assembler.h"
#include "syzygy/core/disassembler_util.h"
@@ -545,6 +546,13 @@
BasicBlockType type() const { return type_; }
const std::string& name() const { return name_; }
+ size_t alignment() const { return alignment_; }
+ void set_alignment(size_t alignment) {
+ DCHECK_LE(1u, alignment_);
+ DCHECK(common::IsPowerOfTwo(alignment));
+ alignment_ = alignment;
+ }
+
Offset offset() const { return offset_; }
void set_offset(Offset offset) { offset_ = offset; }
@@ -570,6 +578,9 @@
// The name of this basic block.
std::string name_;
+ // The alignment of this basic block.
+ size_t alignment_;
+
// The offset of this basic block in the oritinal block. Set to the offset
// of the first byte the basic block originated from during decomposition.
// Useful as a stable, unique identifier for basic blocks in a decomposition.
diff --git a/block_graph/basic_block_assembly_func.asm b/block_graph/basic_block_assembly_func.asm
index ff097b4..6baa614 100644
--- a/block_graph/basic_block_assembly_func.asm
+++ b/block_graph/basic_block_assembly_func.asm
@@ -1,4 +1,4 @@
-; Copyright 2012 Google Inc.
+; Copyright 2012 Google Inc. All Rights Reserved.
;
; Licensed under the Apache License, Version 2.0 (the "License");
; you may not use this file except in compliance with the License.
@@ -82,6 +82,10 @@
interrupt_label LABEL PROC
int 3
+ ; We add some padding so that jump_table ends up being 4-byte aligned.
+ int 3
+ int 3
+
jump_table \
dd case_0
dd case_1
diff --git a/block_graph/basic_block_decomposer.cc b/block_graph/basic_block_decomposer.cc
index 2dc5e5f..e64ac52 100644
--- a/block_graph/basic_block_decomposer.cc
+++ b/block_graph/basic_block_decomposer.cc
@@ -56,6 +56,8 @@
typedef BBAddressSpace::RangeMapConstIter RangeMapConstIter;
typedef BBAddressSpace::RangeMapIter RangeMapIter;
+const size_t kPointerSize = BlockGraph::Reference::kMaximumSize;
+
// We use a (somewhat) arbitrary value as the disassembly address for a block
// so we can tell the difference between a reference to the beginning of the
// block (offset=0) and a null address.
@@ -172,11 +174,21 @@
desc.attributes = block_->attributes();
desc.section = block_->section();
+ // Add the basic blocks to the block descriptor.
Offset offset = 0;
RangeMapConstIter it = original_address_space_.begin();
for (; it != original_address_space_.end(); ++it) {
DCHECK_EQ(it->first.start(), offset);
desc.basic_block_order.push_back(it->second);
+
+ // Any data basic blocks (jump and case tables) with 0 mod 4 alignment
+ // are marked so that the alignment is preserved by the block builder.
+ if (desc.alignment >= kPointerSize &&
+ it->second->type() == BasicBlock::BASIC_DATA_BLOCK &&
+ (offset % kPointerSize) == 0) {
+ it->second->set_alignment(kPointerSize);
+ }
+
offset += it->first.size();
}
diff --git a/block_graph/basic_block_decomposer_unittest.cc b/block_graph/basic_block_decomposer_unittest.cc
index 5bb81cf..afb363e 100644
--- a/block_graph/basic_block_decomposer_unittest.cc
+++ b/block_graph/basic_block_decomposer_unittest.cc
@@ -143,6 +143,7 @@
std::advance(inst_iter, 1);
ASSERT_EQ(1u, inst_iter->references().size());
ASSERT_EQ(bbs_[8], inst_iter->references().begin()->second.basic_block());
+ ASSERT_EQ(1u, bbs_[0]->alignment());
// Basic-block 1 - unreachable-label.
// TODO(rogerm): This is classified as padding for now, it will become code
@@ -154,6 +155,7 @@
// ASSERT_EQ(1u, bbs_[1]->successors().size());;
// ASSERT_EQ(bbs_[2],
// bbs_[1]->successors().front().reference().basic_block());
+ ASSERT_EQ(1u, bbs_[1]->alignment());
// Basic-block 2 - case_0.
ASSERT_TRUE(BasicBlockSubGraph::IsReachable(rm, bbs_[2]));
@@ -163,6 +165,7 @@
ASSERT_EQ(2u, bb2->instructions().size());
ASSERT_EQ(1u, bb2->successors().size());;
ASSERT_EQ(bbs_[3], bb2->successors().front().reference().basic_block());
+ ASSERT_EQ(1u, bbs_[2]->alignment());
// Basic-block 3 - sub eax to jnz.
ASSERT_TRUE(BasicBlockSubGraph::IsReachable(rm, bbs_[3]));
@@ -173,6 +176,7 @@
ASSERT_EQ(2u, bb3->successors().size());;
ASSERT_EQ(bb3, bb3->successors().front().reference().basic_block());
ASSERT_EQ(bbs_[4], bb3->successors().back().reference().basic_block());
+ ASSERT_EQ(1u, bbs_[3]->alignment());
// Basic-block 4 - ret.
ASSERT_TRUE(BasicBlockSubGraph::IsReachable(rm, bbs_[4]));
@@ -181,6 +185,7 @@
ASSERT_TRUE(bb4 != NULL);
ASSERT_EQ(1u, bb4->instructions().size());
ASSERT_EQ(0u, bb4->successors().size());;
+ ASSERT_EQ(1u, bbs_[4]->alignment());
// Basic-block 5 - case_1.
ASSERT_TRUE(BasicBlockSubGraph::IsReachable(rm, bbs_[5]));
@@ -193,6 +198,7 @@
bb5->instructions().front().references().begin()->second.block());
ASSERT_EQ(1u, bb5->successors().size());
ASSERT_EQ(bbs_[6], bb5->successors().front().reference().basic_block());
+ ASSERT_EQ(1u, bbs_[5]->alignment());
// Basic-block 6 - case_default.
ASSERT_TRUE(BasicBlockSubGraph::IsReachable(rm, bbs_[6]));
@@ -204,14 +210,16 @@
func2_,
bb6->instructions().back().references().begin()->second.block());
ASSERT_EQ(0u, bb6->successors().size());
+ ASSERT_EQ(1u, bbs_[6]->alignment());
// Basic-block 7 - interrupt_label.
ASSERT_FALSE(BasicBlockSubGraph::IsReachable(rm, bbs_[7]));
ASSERT_EQ(BasicBlock::BASIC_CODE_BLOCK, bbs_[7]->type());
BasicCodeBlock* bb7 = BasicCodeBlock::Cast(bbs_[7]);
ASSERT_TRUE(bb7 != NULL);
- ASSERT_EQ(1u, bb7->instructions().size());
+ ASSERT_EQ(3u, bb7->instructions().size());
ASSERT_EQ(0u, bb7->successors().size());
+ ASSERT_EQ(1u, bbs_[7]->alignment());
// Basic-block 8 - jump_table.
ASSERT_TRUE(BasicBlockSubGraph::IsReachable(rm, bbs_[8]));
@@ -220,6 +228,7 @@
ASSERT_TRUE(bb8 != NULL);
ASSERT_EQ(3 * Reference::kMaximumSize, bb8->size());
ASSERT_EQ(3u, bb8->references().size());
+ ASSERT_EQ(4u, bbs_[8]->alignment());
// Basic-block 9 - case_table.
ASSERT_TRUE(BasicBlockSubGraph::IsReachable(rm, bbs_[9]));
@@ -228,6 +237,7 @@
ASSERT_TRUE(bb9 != NULL);
ASSERT_EQ(256, bb9->size());
ASSERT_EQ(0u, bb9->references().size());
+ ASSERT_EQ(4u, bbs_[9]->alignment());
// Validate all source ranges.
core::RelativeAddress next_addr(start_addr_);
diff --git a/block_graph/basic_block_test_util.cc b/block_graph/basic_block_test_util.cc
index c5e012d..12d3eab 100644
--- a/block_graph/basic_block_test_util.cc
+++ b/block_graph/basic_block_test_util.cc
@@ -106,6 +106,10 @@
source_ranges().Push(Block::DataRange(0, kAssemblyFuncSize),
Block::SourceRange(start_addr_, kAssemblyFuncSize));
+ // This block contains aligned case and jump tables, so the decomposer would
+ // give it pointer alignment.
+ assembly_func_->set_alignment(4);
+
// Add the data labels.
ASSERT_TRUE(assembly_func_->SetLabel(
kCaseTableOffset, "case_table", kCaseTableAttributes));
diff --git a/reorder/basic_block_optimizer_unittest.cc b/reorder/basic_block_optimizer_unittest.cc
index 96c94fb..b305c86 100644
--- a/reorder/basic_block_optimizer_unittest.cc
+++ b/reorder/basic_block_optimizer_unittest.cc
@@ -244,8 +244,8 @@
TEST_F(BasicBlockOrdererTest, AddWarmDataReferences) {
// Get basic block pointers to the switch, jump table, and case table.
const BasicCodeBlock* code_bb = BasicCodeBlock::Cast(FindBasicBlockAt(0));
- const BasicDataBlock* jump_table = BasicDataBlock::Cast(FindBasicBlockAt(50));
- const BasicDataBlock* case_table = BasicDataBlock::Cast(FindBasicBlockAt(62));
+ const BasicDataBlock* jump_table = BasicDataBlock::Cast(FindBasicBlockAt(52));
+ const BasicDataBlock* case_table = BasicDataBlock::Cast(FindBasicBlockAt(64));
ASSERT_TRUE(code_bb != NULL);
ASSERT_TRUE(jump_table != NULL);
ASSERT_TRUE(case_table != NULL);
@@ -269,8 +269,8 @@
Order::OffsetVector warm;
Order::OffsetVector cold;
ASSERT_TRUE(orderer_->GetBasicBlockOrderings(&warm, &cold));
- // Note that the bb's at 50 and 62 are the jump and case tables, respectively.
- EXPECT_THAT(warm, testing::ElementsAre(0, 24, 31, 36, 50, 62));
+ // Note that the bb's at 52 and 64 are the jump and case tables, respectively.
+ EXPECT_THAT(warm, testing::ElementsAre(0, 24, 31, 36, 52, 64));
EXPECT_THAT(cold, testing::ElementsAre(23, 37, 42, 49));
}
@@ -298,8 +298,8 @@
Order::OffsetVector warm;
Order::OffsetVector cold;
ASSERT_TRUE(orderer_->GetBasicBlockOrderings(&warm, &cold));
- // Note that the bb's at 50 and 62 are the jump and case tables, respectively.
- EXPECT_THAT(warm, testing::ElementsAre(0, 24, 31, 37, 36, 50, 62));
+ // Note that the bb's at 52 and 64 are the jump and case tables, respectively.
+ EXPECT_THAT(warm, testing::ElementsAre(0, 24, 31, 37, 36, 52, 64));
EXPECT_THAT(cold, testing::ElementsAre(23, 42, 49));
}
diff --git a/reorder/transforms/basic_block_layout_transform_unittest.cc b/reorder/transforms/basic_block_layout_transform_unittest.cc
index 3da44bf..2bf96f8 100644
--- a/reorder/transforms/basic_block_layout_transform_unittest.cc
+++ b/reorder/transforms/basic_block_layout_transform_unittest.cc
@@ -77,8 +77,8 @@
ASSERT_TRUE(Insert(37, 2, 0));
ASSERT_TRUE(Insert(42, 2, 1));
ASSERT_TRUE(Insert(49, 2, 2));
- ASSERT_TRUE(Insert(50, 2, 3));
- ASSERT_TRUE(Insert(62, 2, 4));
+ ASSERT_TRUE(Insert(52, 2, 3));
+ ASSERT_TRUE(Insert(64, 2, 4));
BasicBlockSubGraphLayoutTransform tx(bb_map_);
EXPECT_FALSE(tx.TransformBasicBlockSubGraph(&block_graph_, &subgraph_));
}
@@ -94,8 +94,8 @@
ASSERT_TRUE(Insert(37, 0, 5));
ASSERT_TRUE(Insert(42, 0, 6));
ASSERT_TRUE(Insert(49, 0, 7));
- ASSERT_TRUE(Insert(50, 0, 8));
- ASSERT_TRUE(Insert(62, 0, 10));
+ ASSERT_TRUE(Insert(52, 0, 8));
+ ASSERT_TRUE(Insert(64, 0, 10));
BasicBlockSubGraphLayoutTransform tx(bb_map_);
EXPECT_FALSE(tx.TransformBasicBlockSubGraph(&block_graph_, &subgraph_));
}
@@ -109,8 +109,8 @@
ASSERT_TRUE(Insert(37, 0, 5));
ASSERT_TRUE(Insert(42, 0, 6));
ASSERT_TRUE(Insert(49, 0, 7));
- ASSERT_TRUE(Insert(50, 0, 8));
- ASSERT_TRUE(Insert(62, 0, 9));
+ ASSERT_TRUE(Insert(52, 0, 8));
+ ASSERT_TRUE(Insert(64, 0, 9));
BasicBlockSubGraphLayoutTransform tx(bb_map_);
EXPECT_TRUE(tx.TransformBasicBlockSubGraph(&block_graph_, &subgraph_));
@@ -128,8 +128,8 @@
ASSERT_TRUE(Insert(49, 0, 6));
// Data blocks.
- ASSERT_TRUE(Insert(50, 1, 0));
- ASSERT_TRUE(Insert(62, 1, 1));
+ ASSERT_TRUE(Insert(52, 1, 0));
+ ASSERT_TRUE(Insert(64, 1, 1));
// We explicitly do not specify the BB at offset 23, which consists of
// padding that can be deleted.
@@ -258,8 +258,8 @@
assembly_func_code_bbs.push_back(49);
Order::OffsetVector assembly_func_data_bbs;
- assembly_func_data_bbs.push_back(50);
- assembly_func_data_bbs.push_back(62);
+ assembly_func_data_bbs.push_back(52);
+ assembly_func_data_bbs.push_back(64);
order.sections[0].id = text_section_->id();
order.sections[0].name = text_section_->name();
