syzygy/block_graph/analysis/memory_access_analysis_unittest.cc - external/sawbuck - Git at Google

 // Copyright 2013 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.
 // 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.
 //
 // Unittests for memory access analysis.

 #include "syzygy/block_graph/analysis/memory_access_analysis.h"

 #include "gtest/gtest.h"
 #include "mnemonics.h"  // NOLINT

 namespace block_graph {
 namespace analysis {

 namespace {

 typedef block_graph::analysis::MemoryAccessAnalysis::State State;
 typedef block_graph::BasicBlockSubGraph::BasicBlock BasicBlock;
 typedef block_graph::BasicBlockSubGraph::BasicBlock::Instructions Instructions;
 typedef BasicBlockSubGraph::BlockDescription BlockDescription;

 // _asm add eax, ecx
 const uint8 kClearEax[] = { 0x03, 0xC1 };
 // _asm add ecx, [eax]
 const uint8 kReadEax[] = { 0x03, 0x08 };
 // _asm add ecx, [eax + 42]
 const uint8 kReadEax42[] = { 0x03, 0x48, 0x2A };
 // _asm add eax, ecx
 const uint8 kRegsOnly[] = { 0x03, 0xC1 };
 // _asm add [eax + ebx*2 + 42], ecx
 const uint8 kWriteWithScale[] = { 0x01, 0x4C, 0x58, 0x2A };
 // _asm add DWORD PTR [X], ecx
 const uint8 kWriteDispl[] = { 0x01, 0x0D, 0x80, 0x1E, 0xF2, 0x00 };
 // _asm add [eax + 42], ecx
 const uint8 kWriteEax42[] = { 0x01, 0x48, 0x2A };
 // _asm lea ecx, [eax]
 const uint8 kLeaEax[] = { 0x8D, 0x08 };
 // _asm lea ecx, [eax + 42]
 const uint8 kLeaEax42[] = { 0x8D, 0x48, 0x2A };

 // _asm repnz movsb
 const uint8 kRepMovsb[] = { 0xF2, 0xA4 };

 // _asm add ecx, [eax + C]
 const uint8 kReadEax10[] = { 0x03, 0x48, 0x0A };
 const uint8 kReadEax11[] = { 0x03, 0x48, 0x0B };
 const uint8 kReadEax12[] = { 0x03, 0x48, 0x0C };
 const uint8 kReadEax13[] = { 0x03, 0x48, 0x0D };
 const uint8 kReadEax14[] = { 0x03, 0x48, 0x0E };
 const uint8 kReadEax15[] = { 0x03, 0x48, 0x0F };

 // _asm ret
 const uint8 kRet[] = { 0xC3 };
 // _asm call <FFFFFFFF>
 const uint8 kCall[] = { 0xE8, 0xFF, 0xD7, 0xFF, 0xFF };
 // _asm rdtsc
 const uint8 kRdtsc[] = { 0x0F, 0x31 };

 void AddSuccessorBetween(Successor::Condition condition,
                          BasicCodeBlock* from,
                          BasicCodeBlock* to) {
   from->successors().push_back(
       Successor(condition,
                 BasicBlockReference(BlockGraph::RELATIVE_REF,
                                     BlockGraph::Reference::kMaximumSize,
                                     to),
                 0));
 }

 }  // namespace

 class TestMemoryAccessAnalysisState: public MemoryAccessAnalysis::State {
  public:
   bool IsEmpty(const core::Register32& reg) const;
   bool IsEmpty() const;
   bool Contains(const core::Register32& reg, int32 displ) const;

   template<size_t N>
   bool HasNonRedundantAccess(const uint8 (& data)[N]) const;

   template<size_t N>
   void Execute(const uint8 (& data)[N]);

   using MemoryAccessAnalysis::State::Clear;
 };

 class TestMemoryAccessAnalysis: public MemoryAccessAnalysis {
  public:
   using MemoryAccessAnalysis::Intersect;
 };

 class MemoryAccessAnalysisTest : public testing::Test {
  public:
   MemoryAccessAnalysisTest() : bb_(NULL) {
     bb_ = subgraph_.AddBasicCodeBlock("Dummy");
   }

   bool Intersect(const block_graph::BasicBlock* bb, const State& state) {
     return memory_access_.Intersect(bb, state);
   }

   void GetStateAtEntryOf(const BasicBlock* bb, State* state) const {
     return memory_access_.GetStateAtEntryOf(bb, state);
   }

   template<size_t N>
   void PropagateForward(const uint8 (& data)[N]);

  protected:
   TestMemoryAccessAnalysis memory_access_;
   TestMemoryAccessAnalysisState state_;
   BasicBlockSubGraph subgraph_;
   BasicCodeBlock* bb_;
 };

 bool TestMemoryAccessAnalysisState::IsEmpty(const core::Register32& reg) const {
   return active_memory_accesses_[reg.id() - core::kRegister32Min].empty();
 }

 bool TestMemoryAccessAnalysisState::IsEmpty() const {
   for (int r = 0; r < core::kRegister32Count; ++r) {
     if (!IsEmpty(core::kRegisters32[r]))
       return false;
   }
   return true;
 }

 bool TestMemoryAccessAnalysisState::Contains(
     const core::Register32& reg, int32 displ) const {
   const std::set<int32>& offsets = active_memory_accesses_[
       reg.id() - core::kRegister32Min];
   return offsets.find(displ) != offsets.end();
 }

 template<size_t N>
 bool TestMemoryAccessAnalysisState::HasNonRedundantAccess(
     const uint8 (& data)[N]) const {
   // Decode an instruction.
   DCHECK_GT(core::AssemblerImpl::kMaxInstructionLength, N);

   block_graph::Instruction temp;
   bool decoded = block_graph::Instruction::FromBuffer(&data[0], N, &temp);
   DCHECK(decoded);

   // Expect to decode the entire buffer.
   DCHECK_EQ(N, temp.size());

   // Execute the decoded instruction, and modify the current state.
   return MemoryAccessAnalysis::State::HasNonRedundantAccess(temp);
 }

 template<size_t N>
 void TestMemoryAccessAnalysisState::Execute(const uint8 (& data)[N]) {
   // Decode an instruction.
   DCHECK_GT(core::AssemblerImpl::kMaxInstructionLength, N);

   block_graph::Instruction temp;
   bool decoded = block_graph::Instruction::FromBuffer(&data[0], N, &temp);
   DCHECK(decoded);

   // Expect to decode the entire buffer.
   DCHECK_EQ(N, temp.size());

   // Execute the decoded instruction, and modify the current state.
   MemoryAccessAnalysis::State::Execute(temp);
 }

 template<size_t N>
 void MemoryAccessAnalysisTest::PropagateForward(
     const uint8 (& data)[N]) {
   // Decode an instruction.
   DCHECK_GT(core::AssemblerImpl::kMaxInstructionLength, N);

   block_graph::Instruction temp;
   bool decoded = block_graph::Instruction::FromBuffer(&data[0], N, &temp);
   ASSERT_TRUE(decoded);

   // Expect to decode the entire buffer.
   ASSERT_EQ(N, temp.size());

   // Execute the decoded instruction, and modify the current state.
   MemoryAccessAnalysis::PropagateForward(temp, &state_);
 }

 TEST(MemoryAccessAnalysisStateTest, Constructor) {
   // Initial state is empty.
   TestMemoryAccessAnalysisState state;
   EXPECT_TRUE(state.IsEmpty());
 }

 TEST(MemoryAccessAnalysisStateTest, CopyConstructor) {
   TestMemoryAccessAnalysisState state1;

   state1.Execute(kReadEax);
   state1.Execute(kWriteEax42);

   EXPECT_TRUE(state1.Contains(core::eax, 0));
   EXPECT_TRUE(state1.Contains(core::eax, 42));

   // Expect memory accesses to be copied into state2.
   TestMemoryAccessAnalysisState state2(state1);
   EXPECT_TRUE(state2.Contains(core::eax, 0));
   EXPECT_TRUE(state2.Contains(core::eax, 42));
 }

 TEST(MemoryAccessAnalysisStateTest, Clear) {
   TestMemoryAccessAnalysisState state;

   state.Execute(kWriteEax42);
   EXPECT_TRUE(!state.IsEmpty());
   state.Clear();
   EXPECT_TRUE(state.IsEmpty());
 }

 TEST(MemoryAccessAnalysisStateTest, ExecuteOperandKind) {
   TestMemoryAccessAnalysisState state;

   state.Execute(kRegsOnly);
   EXPECT_TRUE(state.IsEmpty());

   state.Execute(kWriteWithScale);
   EXPECT_TRUE(state.IsEmpty());

   state.Execute(kWriteDispl);
   EXPECT_TRUE(state.IsEmpty());

   state.Execute(kReadEax);
   EXPECT_TRUE(state.Contains(core::eax, 0));

   state.Execute(kReadEax42);
   EXPECT_TRUE(state.Contains(core::eax, 42));
 }

 TEST(MemoryAccessAnalysisStateTest, LeaOperand) {
   TestMemoryAccessAnalysisState state;

   // LEA do not perform a memory access.
   state.Execute(kLeaEax);
   EXPECT_FALSE(state.Contains(core::eax, 0));
   state.Execute(kLeaEax42);
   EXPECT_FALSE(state.Contains(core::eax, 42));
 }

 TEST(MemoryAccessAnalysisStateTest, ExecuteWithPrefix) {
   TestMemoryAccessAnalysisState state;

   state.Execute(kRepMovsb);
   EXPECT_TRUE(state.IsEmpty());
 }

 TEST(MemoryAccessAnalysisStateTest, HasNonRedundantAccess) {
   TestMemoryAccessAnalysisState state;

   // Initial state is empty, and accesses are not redundant.
   bool redundant_read1 = state.HasNonRedundantAccess(kReadEax42);
   bool redundant_write1 = state.HasNonRedundantAccess(kWriteEax42);
   EXPECT_TRUE(redundant_read1);
   EXPECT_TRUE(redundant_write1);

   // Perform a read of [eax + 42].
   state.Execute(kReadEax42);
   EXPECT_TRUE(state.Contains(core::eax, 42));

   // After the read, accesses are redundant.
   bool redundant_read2 = state.HasNonRedundantAccess(kReadEax42);
   bool redundant_write2 = state.HasNonRedundantAccess(kWriteEax42);
   EXPECT_FALSE(redundant_read2);
   EXPECT_FALSE(redundant_write2);
 }

 TEST(MemoryAccessAnalysisStateTest, HasNonRedundantAccessOperandKind) {
   TestMemoryAccessAnalysisState state;

   // Instructions without memory access, on empty state.
   EXPECT_FALSE(state.HasNonRedundantAccess(kRegsOnly));
   EXPECT_FALSE(state.HasNonRedundantAccess(kLeaEax));
   EXPECT_FALSE(state.HasNonRedundantAccess(kLeaEax42));

   // Initial state is empty, and accesses are not redundant.
   EXPECT_TRUE(state.HasNonRedundantAccess(kReadEax));
   EXPECT_TRUE(state.HasNonRedundantAccess(kReadEax42));
   EXPECT_TRUE(state.HasNonRedundantAccess(kWriteWithScale));
   EXPECT_TRUE(state.HasNonRedundantAccess(kWriteDispl));
   EXPECT_TRUE(state.HasNonRedundantAccess(kWriteEax42));
 }

 TEST(MemoryAccessAnalysisStateTest, HasNonRedundantAccessWithPrefix) {
   TestMemoryAccessAnalysisState state;
   state.Execute(kRepMovsb);
   bool redundant = state.HasNonRedundantAccess(kRepMovsb);
   EXPECT_TRUE(redundant);
 }

 TEST_F(MemoryAccessAnalysisTest, GetStateOf) {
   // It is valid to get the state of a NULL block.
   GetStateAtEntryOf(NULL, &state_);
   EXPECT_TRUE(state_.IsEmpty());

   // Get an non-existing basic block.
   GetStateAtEntryOf(bb_, &state_);
   EXPECT_TRUE(state_.IsEmpty());
 }

 TEST_F(MemoryAccessAnalysisTest, IntersectEmpty) {
   memory_access_.GetStateAtEntryOf(bb_, &state_);
   EXPECT_TRUE(state_.IsEmpty());

   // Perform an initial intersection with an empty set.
   TestMemoryAccessAnalysisState state;
   Intersect(bb_, state);

   state.Execute(kReadEax10);
   state.Execute(kReadEax11);

   // Perform an second intersection with a non empty set.
   Intersect(bb_, state_);
   GetStateAtEntryOf(bb_, &state_);

   // The results must be empty.
   EXPECT_TRUE(state_.IsEmpty());
 }

 TEST_F(MemoryAccessAnalysisTest, IntersectStates) {
   // Intersection with displacements [10, 11, 12, 13, 14, 15].
   TestMemoryAccessAnalysisState state1;
   state1.Execute(kReadEax10);
   state1.Execute(kReadEax11);
   state1.Execute(kReadEax12);
   state1.Execute(kReadEax13);
   state1.Execute(kReadEax14);
   state1.Execute(kReadEax15);
   Intersect(bb_, state1);

   // Intersection with displacements [10, 11, 12, 14].
   TestMemoryAccessAnalysisState state2;
   state2.Execute(kReadEax10);
   state2.Execute(kReadEax11);
   state2.Execute(kReadEax12);
   state2.Execute(kReadEax14);
   Intersect(bb_, state2);

   // Check current state [10, 11, 12, 14].
   GetStateAtEntryOf(bb_, &state_);
   EXPECT_TRUE(state_.Contains(core::eax, 10));
   EXPECT_TRUE(state_.Contains(core::eax, 11));
   EXPECT_TRUE(state_.Contains(core::eax, 12));
   EXPECT_FALSE(state_.Contains(core::eax, 13));
   EXPECT_TRUE(state_.Contains(core::eax, 14));
   EXPECT_FALSE(state_.Contains(core::eax, 15));

   // Intersection with displacements [10, 11, 15].
   TestMemoryAccessAnalysisState state3;
   state3.Execute(kReadEax10);
   state3.Execute(kReadEax11);
   state3.Execute(kReadEax15);
   Intersect(bb_, state3);

   // Check current state [10, 11].
   GetStateAtEntryOf(bb_, &state_);
   EXPECT_TRUE(state_.Contains(core::eax, 10));
   EXPECT_TRUE(state_.Contains(core::eax, 11));
   EXPECT_FALSE(state_.Contains(core::eax, 12));
   EXPECT_FALSE(state_.Contains(core::eax, 13));
   EXPECT_FALSE(state_.Contains(core::eax, 14));
   EXPECT_FALSE(state_.Contains(core::eax, 15));

   // Intersection with displacements [15].
   TestMemoryAccessAnalysisState state4;
   state4.Execute(kReadEax15);
   Intersect(bb_, state4);

   // The state must be empty.
   GetStateAtEntryOf(bb_, &state_);
   EXPECT_TRUE(state_.IsEmpty());
 }

 TEST_F(MemoryAccessAnalysisTest, PropagateForwardSimple) {
   ASSERT_NO_FATAL_FAILURE(PropagateForward(kReadEax10));
   EXPECT_TRUE(state_.Contains(core::eax, 10));

   ASSERT_NO_FATAL_FAILURE(PropagateForward(kReadEax));
   EXPECT_TRUE(state_.Contains(core::eax, 0));
   EXPECT_TRUE(state_.Contains(core::eax, 10));

   ASSERT_NO_FATAL_FAILURE(PropagateForward(kClearEax));
   EXPECT_TRUE(state_.IsEmpty());

   ASSERT_NO_FATAL_FAILURE(PropagateForward(kLeaEax));
   EXPECT_TRUE(state_.IsEmpty());
 }

 TEST_F(MemoryAccessAnalysisTest, PropagateForwardWithCallRet) {
   ASSERT_NO_FATAL_FAILURE(PropagateForward(kReadEax10));
   EXPECT_TRUE(state_.Contains(core::eax, 10));
   ASSERT_NO_FATAL_FAILURE(PropagateForward(kCall));
   EXPECT_TRUE(state_.IsEmpty());

   ASSERT_NO_FATAL_FAILURE(PropagateForward(kReadEax10));
   EXPECT_TRUE(state_.Contains(core::eax, 10));
   ASSERT_NO_FATAL_FAILURE(PropagateForward(kRet));
   EXPECT_TRUE(state_.IsEmpty());
 }

 TEST_F(MemoryAccessAnalysisTest, UnknownInstruction) {
   // Ensure unknown instructions are processed correctly.
   ASSERT_NO_FATAL_FAILURE(PropagateForward(kReadEax10));
   EXPECT_TRUE(state_.Contains(core::eax, 10));
   ASSERT_NO_FATAL_FAILURE(PropagateForward(kRdtsc));
   EXPECT_TRUE(state_.IsEmpty());
 }

 TEST_F(MemoryAccessAnalysisTest, Analyze) {
   BasicBlockSubGraph subgraph;

   BlockDescription* block = subgraph.AddBlockDescription(
       "b1", "b1.obj", BlockGraph::CODE_BLOCK, 7, 2, 42);

   BasicCodeBlock* bb_if = subgraph.AddBasicCodeBlock("if");
   BasicCodeBlock* bb_true = subgraph.AddBasicCodeBlock("true");
   BasicCodeBlock* bb_false = subgraph.AddBasicCodeBlock("false");
   BasicCodeBlock* bb_end = subgraph.AddBasicCodeBlock("end");

   ASSERT_TRUE(bb_if != NULL);
   ASSERT_TRUE(bb_true != NULL);
   ASSERT_TRUE(bb_false != NULL);
   ASSERT_TRUE(bb_end != NULL);

   block->basic_block_order.push_back(bb_if);
   block->basic_block_order.push_back(bb_true);
   block->basic_block_order.push_back(bb_end);
   block->basic_block_order.push_back(bb_false);

   AddSuccessorBetween(Successor::kConditionEqual, bb_if, bb_true);
   AddSuccessorBetween(Successor::kConditionNotEqual, bb_if, bb_false);
   AddSuccessorBetween(Successor::kConditionTrue, bb_true, bb_end);
   AddSuccessorBetween(Successor::kConditionTrue, bb_false, bb_end);

   BasicBlockAssembler asm_if(bb_if->instructions().end(),
                              &bb_if->instructions());
   asm_if.mov(core::ecx, Operand(core::eax, Immediate(1, core::kSize32Bit)));
   asm_if.mov(core::edx, Operand(core::ecx, Immediate(12, core::kSize32Bit)));
   asm_if.mov(core::edx, Operand(core::eax, Immediate(42, core::kSize32Bit)));

   BasicBlockAssembler asm_true(bb_true->instructions().end(),
                                &bb_true->instructions());
   asm_true.mov(core::ecx, Operand(core::eax, Immediate(1, core::kSize32Bit)));
   asm_true.mov(core::edx, Operand(core::eax, Immediate(12, core::kSize32Bit)));
   asm_true.mov(core::ecx, Operand(core::eax, Immediate(24, core::kSize32Bit)));

   BasicBlockAssembler asm_false(bb_false->instructions().end(),
                                 &bb_false->instructions());
   asm_false.mov(core::ecx, Operand(core::eax, Immediate(24, core::kSize32Bit)));
   asm_false.mov(core::edx, Operand(core::eax, Immediate(48, core::kSize32Bit)));

   // Analyze the flow graph.
   memory_access_.Analyze(&subgraph);

   // State of first basic block is empty.
   GetStateAtEntryOf(bb_if, &state_);
   EXPECT_TRUE(state_.IsEmpty());

   // Get entry state of bb_true.
   GetStateAtEntryOf(bb_true, &state_);
   EXPECT_TRUE(state_.Contains(core::eax, 1));
   EXPECT_TRUE(state_.Contains(core::ecx, 12));
   EXPECT_TRUE(state_.Contains(core::eax, 42));

   // Get entry state of bb_false.
   GetStateAtEntryOf(bb_false, &state_);
   EXPECT_TRUE(state_.Contains(core::eax, 1));
   EXPECT_TRUE(state_.Contains(core::ecx, 12));
   EXPECT_TRUE(state_.Contains(core::eax, 42));

   // Get entry state of bb_end. Intersection of bb_true and bb_false.
   GetStateAtEntryOf(bb_end, &state_);
   EXPECT_TRUE(state_.Contains(core::eax, 1));
   EXPECT_FALSE(state_.Contains(core::eax, 12));
   EXPECT_FALSE(state_.Contains(core::ecx, 12));
   EXPECT_TRUE(state_.Contains(core::eax, 24));
   EXPECT_TRUE(state_.Contains(core::eax, 42));
 }

 TEST_F(MemoryAccessAnalysisTest, AnalyzeWithData) {
   BasicBlockSubGraph subgraph;
   const uint8 raw_data[] = { 0, 1, 2, 3, 4 };
   const size_t raw_data_len = ARRAYSIZE(raw_data);

   BlockDescription* block = subgraph.AddBlockDescription(
       "b1", "b1.obj", BlockGraph::CODE_BLOCK, 7, 2, 42);

   BasicCodeBlock* bb = subgraph.AddBasicCodeBlock("bb");
   BasicDataBlock* data =
       subgraph.AddBasicDataBlock("data", raw_data_len, &raw_data[0]);

   block->basic_block_order.push_back(bb);
   block->basic_block_order.push_back(data);

   BasicBlockAssembler asm_bb(bb->instructions().end(), &bb->instructions());
   asm_bb.ret();

   // Analyze the flow graph.
   memory_access_.Analyze(&subgraph);

   // Expect empty state.
   GetStateAtEntryOf(bb, &state_);
   EXPECT_TRUE(state_.IsEmpty());

   GetStateAtEntryOf(data, &state_);
   EXPECT_TRUE(state_.IsEmpty());
 }

 }  // namespace analysis
 }  // namespace block_graph
	// Copyright 2013 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.
	// 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.
	//
	// Unittests for memory access analysis.

	#include "syzygy/block_graph/analysis/memory_access_analysis.h"

	#include "gtest/gtest.h"
	#include "mnemonics.h" // NOLINT

	namespace block_graph {
	namespace analysis {

	namespace {

	typedef block_graph::analysis::MemoryAccessAnalysis::State State;
	typedef block_graph::BasicBlockSubGraph::BasicBlock BasicBlock;
	typedef block_graph::BasicBlockSubGraph::BasicBlock::Instructions Instructions;
	typedef BasicBlockSubGraph::BlockDescription BlockDescription;

	// _asm add eax, ecx
	const uint8 kClearEax[] = { 0x03, 0xC1 };
	// _asm add ecx, [eax]
	const uint8 kReadEax[] = { 0x03, 0x08 };
	// _asm add ecx, [eax + 42]
	const uint8 kReadEax42[] = { 0x03, 0x48, 0x2A };
	// _asm add eax, ecx
	const uint8 kRegsOnly[] = { 0x03, 0xC1 };
	// _asm add [eax + ebx*2 + 42], ecx
	const uint8 kWriteWithScale[] = { 0x01, 0x4C, 0x58, 0x2A };
	// _asm add DWORD PTR [X], ecx
	const uint8 kWriteDispl[] = { 0x01, 0x0D, 0x80, 0x1E, 0xF2, 0x00 };
	// _asm add [eax + 42], ecx
	const uint8 kWriteEax42[] = { 0x01, 0x48, 0x2A };
	// _asm lea ecx, [eax]
	const uint8 kLeaEax[] = { 0x8D, 0x08 };
	// _asm lea ecx, [eax + 42]
	const uint8 kLeaEax42[] = { 0x8D, 0x48, 0x2A };

	// _asm repnz movsb
	const uint8 kRepMovsb[] = { 0xF2, 0xA4 };

	// _asm add ecx, [eax + C]
	const uint8 kReadEax10[] = { 0x03, 0x48, 0x0A };
	const uint8 kReadEax11[] = { 0x03, 0x48, 0x0B };
	const uint8 kReadEax12[] = { 0x03, 0x48, 0x0C };
	const uint8 kReadEax13[] = { 0x03, 0x48, 0x0D };
	const uint8 kReadEax14[] = { 0x03, 0x48, 0x0E };
	const uint8 kReadEax15[] = { 0x03, 0x48, 0x0F };

	// _asm ret
	const uint8 kRet[] = { 0xC3 };
	// _asm call <FFFFFFFF>
	const uint8 kCall[] = { 0xE8, 0xFF, 0xD7, 0xFF, 0xFF };
	// _asm rdtsc
	const uint8 kRdtsc[] = { 0x0F, 0x31 };

	void AddSuccessorBetween(Successor::Condition condition,
	BasicCodeBlock* from,
	BasicCodeBlock* to) {
	from->successors().push_back(
	Successor(condition,
	BasicBlockReference(BlockGraph::RELATIVE_REF,
	BlockGraph::Reference::kMaximumSize,
	to),
	0));
	}

	} // namespace

	class TestMemoryAccessAnalysisState: public MemoryAccessAnalysis::State {
	public:
	bool IsEmpty(const core::Register32& reg) const;
	bool IsEmpty() const;
	bool Contains(const core::Register32& reg, int32 displ) const;

	template<size_t N>
	bool HasNonRedundantAccess(const uint8 (& data)[N]) const;

	template<size_t N>
	void Execute(const uint8 (& data)[N]);

	using MemoryAccessAnalysis::State::Clear;
	};

	class TestMemoryAccessAnalysis: public MemoryAccessAnalysis {
	public:
	using MemoryAccessAnalysis::Intersect;
	};

	class MemoryAccessAnalysisTest : public testing::Test {
	public:
	MemoryAccessAnalysisTest() : bb_(NULL) {
	bb_ = subgraph_.AddBasicCodeBlock("Dummy");
	}

	bool Intersect(const block_graph::BasicBlock* bb, const State& state) {
	return memory_access_.Intersect(bb, state);
	}

	void GetStateAtEntryOf(const BasicBlock* bb, State* state) const {
	return memory_access_.GetStateAtEntryOf(bb, state);
	}

	template<size_t N>
	void PropagateForward(const uint8 (& data)[N]);

	protected:
	TestMemoryAccessAnalysis memory_access_;
	TestMemoryAccessAnalysisState state_;
	BasicBlockSubGraph subgraph_;
	BasicCodeBlock* bb_;
	};

	bool TestMemoryAccessAnalysisState::IsEmpty(const core::Register32& reg) const {
	return active_memory_accesses_[reg.id() - core::kRegister32Min].empty();
	}

	bool TestMemoryAccessAnalysisState::IsEmpty() const {
	for (int r = 0; r < core::kRegister32Count; ++r) {
	if (!IsEmpty(core::kRegisters32[r]))
	return false;
	}
	return true;
	}

	bool TestMemoryAccessAnalysisState::Contains(
	const core::Register32& reg, int32 displ) const {
	const std::set<int32>& offsets = active_memory_accesses_[
	reg.id() - core::kRegister32Min];
	return offsets.find(displ) != offsets.end();
	}

	template<size_t N>
	bool TestMemoryAccessAnalysisState::HasNonRedundantAccess(
	const uint8 (& data)[N]) const {
	// Decode an instruction.
	DCHECK_GT(core::AssemblerImpl::kMaxInstructionLength, N);

	block_graph::Instruction temp;
	bool decoded = block_graph::Instruction::FromBuffer(&data[0], N, &temp);
	DCHECK(decoded);

	// Expect to decode the entire buffer.
	DCHECK_EQ(N, temp.size());

	// Execute the decoded instruction, and modify the current state.
	return MemoryAccessAnalysis::State::HasNonRedundantAccess(temp);
	}

	template<size_t N>
	void TestMemoryAccessAnalysisState::Execute(const uint8 (& data)[N]) {
	// Decode an instruction.
	DCHECK_GT(core::AssemblerImpl::kMaxInstructionLength, N);

	block_graph::Instruction temp;
	bool decoded = block_graph::Instruction::FromBuffer(&data[0], N, &temp);
	DCHECK(decoded);

	// Expect to decode the entire buffer.
	DCHECK_EQ(N, temp.size());

	// Execute the decoded instruction, and modify the current state.
	MemoryAccessAnalysis::State::Execute(temp);
	}

	template<size_t N>
	void MemoryAccessAnalysisTest::PropagateForward(
	const uint8 (& data)[N]) {
	// Decode an instruction.
	DCHECK_GT(core::AssemblerImpl::kMaxInstructionLength, N);

	block_graph::Instruction temp;
	bool decoded = block_graph::Instruction::FromBuffer(&data[0], N, &temp);
	ASSERT_TRUE(decoded);

	// Expect to decode the entire buffer.
	ASSERT_EQ(N, temp.size());

	// Execute the decoded instruction, and modify the current state.
	MemoryAccessAnalysis::PropagateForward(temp, &state_);
	}

	TEST(MemoryAccessAnalysisStateTest, Constructor) {
	// Initial state is empty.
	TestMemoryAccessAnalysisState state;
	EXPECT_TRUE(state.IsEmpty());
	}

	TEST(MemoryAccessAnalysisStateTest, CopyConstructor) {
	TestMemoryAccessAnalysisState state1;

	state1.Execute(kReadEax);
	state1.Execute(kWriteEax42);

	EXPECT_TRUE(state1.Contains(core::eax, 0));
	EXPECT_TRUE(state1.Contains(core::eax, 42));

	// Expect memory accesses to be copied into state2.
	TestMemoryAccessAnalysisState state2(state1);
	EXPECT_TRUE(state2.Contains(core::eax, 0));
	EXPECT_TRUE(state2.Contains(core::eax, 42));
	}

	TEST(MemoryAccessAnalysisStateTest, Clear) {
	TestMemoryAccessAnalysisState state;

	state.Execute(kWriteEax42);
	EXPECT_TRUE(!state.IsEmpty());
	state.Clear();
	EXPECT_TRUE(state.IsEmpty());
	}

	TEST(MemoryAccessAnalysisStateTest, ExecuteOperandKind) {
	TestMemoryAccessAnalysisState state;

	state.Execute(kRegsOnly);
	EXPECT_TRUE(state.IsEmpty());

	state.Execute(kWriteWithScale);
	EXPECT_TRUE(state.IsEmpty());

	state.Execute(kWriteDispl);
	EXPECT_TRUE(state.IsEmpty());

	state.Execute(kReadEax);
	EXPECT_TRUE(state.Contains(core::eax, 0));

	state.Execute(kReadEax42);
	EXPECT_TRUE(state.Contains(core::eax, 42));
	}

	TEST(MemoryAccessAnalysisStateTest, LeaOperand) {
	TestMemoryAccessAnalysisState state;

	// LEA do not perform a memory access.
	state.Execute(kLeaEax);
	EXPECT_FALSE(state.Contains(core::eax, 0));
	state.Execute(kLeaEax42);
	EXPECT_FALSE(state.Contains(core::eax, 42));
	}

	TEST(MemoryAccessAnalysisStateTest, ExecuteWithPrefix) {
	TestMemoryAccessAnalysisState state;

	state.Execute(kRepMovsb);
	EXPECT_TRUE(state.IsEmpty());
	}

	TEST(MemoryAccessAnalysisStateTest, HasNonRedundantAccess) {
	TestMemoryAccessAnalysisState state;

	// Initial state is empty, and accesses are not redundant.
	bool redundant_read1 = state.HasNonRedundantAccess(kReadEax42);
	bool redundant_write1 = state.HasNonRedundantAccess(kWriteEax42);
	EXPECT_TRUE(redundant_read1);
	EXPECT_TRUE(redundant_write1);

	// Perform a read of [eax + 42].
	state.Execute(kReadEax42);
	EXPECT_TRUE(state.Contains(core::eax, 42));

	// After the read, accesses are redundant.
	bool redundant_read2 = state.HasNonRedundantAccess(kReadEax42);
	bool redundant_write2 = state.HasNonRedundantAccess(kWriteEax42);
	EXPECT_FALSE(redundant_read2);
	EXPECT_FALSE(redundant_write2);
	}

	TEST(MemoryAccessAnalysisStateTest, HasNonRedundantAccessOperandKind) {
	TestMemoryAccessAnalysisState state;

	// Instructions without memory access, on empty state.
	EXPECT_FALSE(state.HasNonRedundantAccess(kRegsOnly));
	EXPECT_FALSE(state.HasNonRedundantAccess(kLeaEax));
	EXPECT_FALSE(state.HasNonRedundantAccess(kLeaEax42));

	// Initial state is empty, and accesses are not redundant.
	EXPECT_TRUE(state.HasNonRedundantAccess(kReadEax));
	EXPECT_TRUE(state.HasNonRedundantAccess(kReadEax42));
	EXPECT_TRUE(state.HasNonRedundantAccess(kWriteWithScale));
	EXPECT_TRUE(state.HasNonRedundantAccess(kWriteDispl));
	EXPECT_TRUE(state.HasNonRedundantAccess(kWriteEax42));
	}

	TEST(MemoryAccessAnalysisStateTest, HasNonRedundantAccessWithPrefix) {
	TestMemoryAccessAnalysisState state;
	state.Execute(kRepMovsb);
	bool redundant = state.HasNonRedundantAccess(kRepMovsb);
	EXPECT_TRUE(redundant);
	}

	TEST_F(MemoryAccessAnalysisTest, GetStateOf) {
	// It is valid to get the state of a NULL block.
	GetStateAtEntryOf(NULL, &state_);
	EXPECT_TRUE(state_.IsEmpty());

	// Get an non-existing basic block.
	GetStateAtEntryOf(bb_, &state_);
	EXPECT_TRUE(state_.IsEmpty());
	}

	TEST_F(MemoryAccessAnalysisTest, IntersectEmpty) {
	memory_access_.GetStateAtEntryOf(bb_, &state_);
	EXPECT_TRUE(state_.IsEmpty());

	// Perform an initial intersection with an empty set.
	TestMemoryAccessAnalysisState state;
	Intersect(bb_, state);

	state.Execute(kReadEax10);
	state.Execute(kReadEax11);

	// Perform an second intersection with a non empty set.
	Intersect(bb_, state_);
	GetStateAtEntryOf(bb_, &state_);

	// The results must be empty.
	EXPECT_TRUE(state_.IsEmpty());
	}

	TEST_F(MemoryAccessAnalysisTest, IntersectStates) {
	// Intersection with displacements [10, 11, 12, 13, 14, 15].
	TestMemoryAccessAnalysisState state1;
	state1.Execute(kReadEax10);
	state1.Execute(kReadEax11);
	state1.Execute(kReadEax12);
	state1.Execute(kReadEax13);
	state1.Execute(kReadEax14);
	state1.Execute(kReadEax15);
	Intersect(bb_, state1);

	// Intersection with displacements [10, 11, 12, 14].
	TestMemoryAccessAnalysisState state2;
	state2.Execute(kReadEax10);
	state2.Execute(kReadEax11);
	state2.Execute(kReadEax12);
	state2.Execute(kReadEax14);
	Intersect(bb_, state2);

	// Check current state [10, 11, 12, 14].
	GetStateAtEntryOf(bb_, &state_);
	EXPECT_TRUE(state_.Contains(core::eax, 10));
	EXPECT_TRUE(state_.Contains(core::eax, 11));
	EXPECT_TRUE(state_.Contains(core::eax, 12));
	EXPECT_FALSE(state_.Contains(core::eax, 13));
	EXPECT_TRUE(state_.Contains(core::eax, 14));
	EXPECT_FALSE(state_.Contains(core::eax, 15));

	// Intersection with displacements [10, 11, 15].
	TestMemoryAccessAnalysisState state3;
	state3.Execute(kReadEax10);
	state3.Execute(kReadEax11);
	state3.Execute(kReadEax15);
	Intersect(bb_, state3);

	// Check current state [10, 11].
	GetStateAtEntryOf(bb_, &state_);
	EXPECT_TRUE(state_.Contains(core::eax, 10));
	EXPECT_TRUE(state_.Contains(core::eax, 11));
	EXPECT_FALSE(state_.Contains(core::eax, 12));
	EXPECT_FALSE(state_.Contains(core::eax, 13));
	EXPECT_FALSE(state_.Contains(core::eax, 14));
	EXPECT_FALSE(state_.Contains(core::eax, 15));

	// Intersection with displacements [15].
	TestMemoryAccessAnalysisState state4;
	state4.Execute(kReadEax15);
	Intersect(bb_, state4);

	// The state must be empty.
	GetStateAtEntryOf(bb_, &state_);
	EXPECT_TRUE(state_.IsEmpty());
	}

	TEST_F(MemoryAccessAnalysisTest, PropagateForwardSimple) {
	ASSERT_NO_FATAL_FAILURE(PropagateForward(kReadEax10));
	EXPECT_TRUE(state_.Contains(core::eax, 10));

	ASSERT_NO_FATAL_FAILURE(PropagateForward(kReadEax));
	EXPECT_TRUE(state_.Contains(core::eax, 0));
	EXPECT_TRUE(state_.Contains(core::eax, 10));

	ASSERT_NO_FATAL_FAILURE(PropagateForward(kClearEax));
	EXPECT_TRUE(state_.IsEmpty());

	ASSERT_NO_FATAL_FAILURE(PropagateForward(kLeaEax));
	EXPECT_TRUE(state_.IsEmpty());
	}

	TEST_F(MemoryAccessAnalysisTest, PropagateForwardWithCallRet) {
	ASSERT_NO_FATAL_FAILURE(PropagateForward(kReadEax10));
	EXPECT_TRUE(state_.Contains(core::eax, 10));
	ASSERT_NO_FATAL_FAILURE(PropagateForward(kCall));
	EXPECT_TRUE(state_.IsEmpty());

	ASSERT_NO_FATAL_FAILURE(PropagateForward(kReadEax10));
	EXPECT_TRUE(state_.Contains(core::eax, 10));
	ASSERT_NO_FATAL_FAILURE(PropagateForward(kRet));
	EXPECT_TRUE(state_.IsEmpty());
	}

	TEST_F(MemoryAccessAnalysisTest, UnknownInstruction) {
	// Ensure unknown instructions are processed correctly.
	ASSERT_NO_FATAL_FAILURE(PropagateForward(kReadEax10));
	EXPECT_TRUE(state_.Contains(core::eax, 10));
	ASSERT_NO_FATAL_FAILURE(PropagateForward(kRdtsc));
	EXPECT_TRUE(state_.IsEmpty());
	}

	TEST_F(MemoryAccessAnalysisTest, Analyze) {
	BasicBlockSubGraph subgraph;

	BlockDescription* block = subgraph.AddBlockDescription(
	"b1", "b1.obj", BlockGraph::CODE_BLOCK, 7, 2, 42);

	BasicCodeBlock* bb_if = subgraph.AddBasicCodeBlock("if");
	BasicCodeBlock* bb_true = subgraph.AddBasicCodeBlock("true");
	BasicCodeBlock* bb_false = subgraph.AddBasicCodeBlock("false");
	BasicCodeBlock* bb_end = subgraph.AddBasicCodeBlock("end");

	ASSERT_TRUE(bb_if != NULL);
	ASSERT_TRUE(bb_true != NULL);
	ASSERT_TRUE(bb_false != NULL);
	ASSERT_TRUE(bb_end != NULL);

	block->basic_block_order.push_back(bb_if);
	block->basic_block_order.push_back(bb_true);
	block->basic_block_order.push_back(bb_end);
	block->basic_block_order.push_back(bb_false);

	AddSuccessorBetween(Successor::kConditionEqual, bb_if, bb_true);
	AddSuccessorBetween(Successor::kConditionNotEqual, bb_if, bb_false);
	AddSuccessorBetween(Successor::kConditionTrue, bb_true, bb_end);
	AddSuccessorBetween(Successor::kConditionTrue, bb_false, bb_end);

	BasicBlockAssembler asm_if(bb_if->instructions().end(),
	&bb_if->instructions());
	asm_if.mov(core::ecx, Operand(core::eax, Immediate(1, core::kSize32Bit)));
	asm_if.mov(core::edx, Operand(core::ecx, Immediate(12, core::kSize32Bit)));
	asm_if.mov(core::edx, Operand(core::eax, Immediate(42, core::kSize32Bit)));

	BasicBlockAssembler asm_true(bb_true->instructions().end(),
	&bb_true->instructions());
	asm_true.mov(core::ecx, Operand(core::eax, Immediate(1, core::kSize32Bit)));
	asm_true.mov(core::edx, Operand(core::eax, Immediate(12, core::kSize32Bit)));
	asm_true.mov(core::ecx, Operand(core::eax, Immediate(24, core::kSize32Bit)));

	BasicBlockAssembler asm_false(bb_false->instructions().end(),
	&bb_false->instructions());
	asm_false.mov(core::ecx, Operand(core::eax, Immediate(24, core::kSize32Bit)));
	asm_false.mov(core::edx, Operand(core::eax, Immediate(48, core::kSize32Bit)));

	// Analyze the flow graph.
	memory_access_.Analyze(&subgraph);

	// State of first basic block is empty.
	GetStateAtEntryOf(bb_if, &state_);
	EXPECT_TRUE(state_.IsEmpty());

	// Get entry state of bb_true.
	GetStateAtEntryOf(bb_true, &state_);
	EXPECT_TRUE(state_.Contains(core::eax, 1));
	EXPECT_TRUE(state_.Contains(core::ecx, 12));
	EXPECT_TRUE(state_.Contains(core::eax, 42));

	// Get entry state of bb_false.
	GetStateAtEntryOf(bb_false, &state_);
	EXPECT_TRUE(state_.Contains(core::eax, 1));
	EXPECT_TRUE(state_.Contains(core::ecx, 12));
	EXPECT_TRUE(state_.Contains(core::eax, 42));

	// Get entry state of bb_end. Intersection of bb_true and bb_false.
	GetStateAtEntryOf(bb_end, &state_);
	EXPECT_TRUE(state_.Contains(core::eax, 1));
	EXPECT_FALSE(state_.Contains(core::eax, 12));
	EXPECT_FALSE(state_.Contains(core::ecx, 12));
	EXPECT_TRUE(state_.Contains(core::eax, 24));
	EXPECT_TRUE(state_.Contains(core::eax, 42));
	}

	TEST_F(MemoryAccessAnalysisTest, AnalyzeWithData) {
	BasicBlockSubGraph subgraph;
	const uint8 raw_data[] = { 0, 1, 2, 3, 4 };
	const size_t raw_data_len = ARRAYSIZE(raw_data);

	BlockDescription* block = subgraph.AddBlockDescription(
	"b1", "b1.obj", BlockGraph::CODE_BLOCK, 7, 2, 42);

	BasicCodeBlock* bb = subgraph.AddBasicCodeBlock("bb");
	BasicDataBlock* data =
	subgraph.AddBasicDataBlock("data", raw_data_len, &raw_data[0]);

	block->basic_block_order.push_back(bb);
	block->basic_block_order.push_back(data);

	BasicBlockAssembler asm_bb(bb->instructions().end(), &bb->instructions());
	asm_bb.ret();

	// Analyze the flow graph.
	memory_access_.Analyze(&subgraph);

	// Expect empty state.
	GetStateAtEntryOf(bb, &state_);
	EXPECT_TRUE(state_.IsEmpty());

	GetStateAtEntryOf(data, &state_);
	EXPECT_TRUE(state_.IsEmpty());
	}

	} // namespace analysis
	} // namespace block_graph