From 460c6dd93f5f6ba3ea20979ad9fa95a4a6f660d5 Mon Sep 17 00:00:00 2001
From: Pierre-Marie de Rodat <derodat@adacore.com>
Date: Tue, 25 Apr 2017 13:54:51 +0200
Subject: Reduce complexity of best CFA lookups

This turns a linear lookup into a logarithmic binary search, which
improves a lot DWARF to PDB conversion for big programs.
---
 src/cv2pdb.cpp    |   1 +
 src/cv2pdb.h      |   3 ++
 src/dwarf2pdb.cpp | 112 ++++++++++++++++++++++++++++++++++++++++++++++--------
 3 files changed, 101 insertions(+), 15 deletions(-)

diff --git a/src/cv2pdb.cpp b/src/cv2pdb.cpp
index 1ac48bd..d84eeb2 100644
--- a/src/cv2pdb.cpp
+++ b/src/cv2pdb.cpp
@@ -49,6 +49,7 @@ CV2PDB::CV2PDB(PEImage& image)
 	thisIsNotRef = true;
 	v3 = true;
 	countEntries = img.countCVEntries();
+	build_cfi_index();
 }
 
 CV2PDB::~CV2PDB()
diff --git a/src/cv2pdb.h b/src/cv2pdb.h
index e63ea65..cdb7e36 100644
--- a/src/cv2pdb.h
+++ b/src/cv2pdb.h
@@ -23,6 +23,7 @@ extern "C" {
 class PEImage;
 struct DWARF_InfoData;
 struct DWARF_CompilationUnit;
+class CFIIndex;
 
 class CV2PDB : public LastError
 {
@@ -182,6 +183,7 @@ public:
 		int& basetype, int& lowerBound, int& upperBound);
 	int getDWARFBasicType(int encoding, int byte_size);
 
+	void build_cfi_index();
 	bool mapTypes();
 	bool createTypes();
 
@@ -189,6 +191,7 @@ public:
 	BYTE* libraries;
 
 	PEImage& img;
+	CFIIndex* cfi_index;
 
 	mspdb::PDB* pdb;
 	mspdb::DBI *dbi;
diff --git a/src/dwarf2pdb.cpp b/src/dwarf2pdb.cpp
index 27fafd3..65f9803 100644
--- a/src/dwarf2pdb.cpp
+++ b/src/dwarf2pdb.cpp
@@ -17,6 +17,7 @@
 
 #include "dwarf.h"
 
+#include <algorithm>
 #include <assert.h>
 #include <string>
 #include <vector>
@@ -155,6 +156,41 @@ CV_X86_REG dwarf_to_amd64_reg(unsigned dwarf_reg)
 	}
 }
 
+// Index for efficient lookups in Call Frame Information entries
+class CFIIndex
+{
+public:
+	// Build the index, which will be tied to IMG.
+	CFIIndex(const PEImage& img);
+
+	// Look for a FDE whose PC range covers the PCLO/PCHI range and return a
+	// pointer to the FDE in the .debug_frame section. Return NULL if no such
+	// FDE exists.
+	byte *lookup(unsigned int pclo, unsigned pchi) const;
+
+private:
+	struct index_entry
+	{
+		// PC range for the FDE
+		unsigned int pclo, pchi;
+		// Pointer to the FDE in the .debug_frame section
+		byte *ptr;
+
+		// Sort entries by PCLO first and then by PCHI.
+		bool operator<(const index_entry& other) const {
+			if (pclo < other.pclo)
+				return true;
+			else if (pclo == other.pclo)
+				return pchi < other.pchi;
+			else
+				return false;
+		}
+
+	};
+
+	std::vector<index_entry> index;
+};
+
 // Call Frame Information entry (CIE or FDE)
 class CFIEntry
 {
@@ -447,28 +483,27 @@ public:
 	Location cfa;
 };
 
-Location findBestCFA(const PEImage& img, unsigned int pclo, unsigned int pchi)
+Location findBestCFA(const PEImage& img, const CFIIndex* index, unsigned int pclo, unsigned int pchi)
 {
 	bool x64 = img.isX64();
 	Location ebp = { Location::RegRel, x64 ? 6 : 5, x64 ? 16 : 8 };
 	if (!img.debug_frame)
 		return ebp;
 
+	byte *fde_ptr = index->lookup(pclo, pchi);
+	if (fde_ptr == NULL)
+		return ebp;
+
 	CFIEntry entry;
 	CFICursor cursor(img);
-	while(cursor.readNext(entry))
-	{
-		if (entry.type == CFIEntry::FDE &&
-			entry.initial_location <= pclo && entry.initial_location + entry.address_range >= pchi)
-		{
-			CFACursor cfa(entry, pclo);
-			while(cfa.processNext()) {}
-			cfa.setInstructions(entry.instructions, entry.instructions_length);
-			while(!cfa.beforeRestore() && cfa.processNext()) {}
-			return cfa.cfa;
-		}
-	}
-	return ebp;
+	cursor.ptr = fde_ptr;
+
+	assert(cursor.readNext(entry));
+	CFACursor cfa(entry, pclo);
+	while(cfa.processNext()) {}
+	cfa.setInstructions(entry.instructions, entry.instructions_length);
+	while(!cfa.beforeRestore() && cfa.processNext()) {}
+	return cfa.cfa;
 }
 
 // Location list entry
@@ -707,7 +742,7 @@ bool CV2PDB::addDWARFProc(DWARF_InfoData& procid, DWARF_CompilationUnit* cu, DIE
 	if (frameBase.is_abs()) // pointer into location list in .debug_loc? assume CFA
 		frameBase = findBestFBLoc(img, cu, frameBase.off);
 
-    Location cfa = findBestCFA(img, procid.pclo, procid.pchi);
+    Location cfa = findBestCFA(img, cfi_index, procid.pclo, procid.pchi);
 
 	if (cu)
 	{
@@ -1543,3 +1578,50 @@ bool CV2PDB::writeDWARFImage(const TCHAR* opath)
 
 	return true;
 }
+
+void CV2PDB::build_cfi_index()
+{
+	if (img.debug_frame == NULL)
+		return;
+	cfi_index = new CFIIndex(img);
+}
+
+CFIIndex::CFIIndex(const PEImage& img)
+{
+	CFIEntry entry;
+	CFICursor cursor(img);
+
+	// First register all FDE as index entries
+	while (cursor.readNext(entry))
+	{
+		if (entry.type != CFIEntry::FDE)
+			continue;
+
+		index_entry e = {
+			entry.initial_location,
+			entry.initial_location + entry.address_range,
+			entry.ptr
+		};
+		index.push_back(e);
+	}
+
+	// Then make them sorted so we can perform binary searches later on
+	std::sort(index.begin(), index.end());
+}
+
+byte *CFIIndex::lookup(unsigned int pclo, unsigned int pchi) const
+{
+	// TODO: here, we are just looking for the first entry whose range contains PCLO,
+	// assuming the found entry will have the same PCLO and PCHI as arguments. Maybe
+	// this is not always true.
+	index_entry e = { pclo, pclo, NULL };
+	std::vector<index_entry>::const_iterator it
+		= std::lower_bound(index.begin(), index.end(), e);
+	if (it == index.end())
+		return NULL;
+	e = *it;
+	if (e.pclo <= pclo && pchi <= e.pchi)
+		return e.ptr;
+	else
+		return NULL;
+}
\ No newline at end of file
-- 
cgit v0.12