/*
 * SMPProgram.cpp - <see below>.
 *
 * Copyright (c) 2000, 2001, 2010 - University of Virginia 
 *
 * This file is part of the Memory Error Detection System (MEDS) infrastructure.
 * This file may be used and modified for non-commercial purposes as long as 
 * all copyright, permission, and nonwarranty notices are preserved.  
 * Redistribution is prohibited without prior written consent from the University 
 * of Virginia.
 *
 * Please contact the authors for restrictions applying to commercial use.
 *
 * THIS SOURCE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS OR IMPLIED
 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
 * MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 *
 * Author: University of Virginia
 * e-mail: jwd@virginia.com
 * URL   : http://www.cs.virginia.edu/
 *
 * Additional copyrights 2010, 2011, 2014 by Zephyr Software LLC
 * e-mail: {clc,jwd}@zephyr-software.com
 * URL   : http://www.zephyr-software.com/
 *
 */

//
// SMPProgram.cpp
//
// This module analyzes the whole program as needed for the
//   SMP project (Software Memory Protection).
//

#include <string>
#include <utility>
#include <list>
#include <set>
#include <vector>
#include <algorithm>

#include <cstring>
#include <cstdlib>

#include <pro.h>
#include <ua.hpp>
#include <assert.h>
#include <ida.hpp>
#include <idp.hpp>
#include <auto.hpp>
#include <bytes.hpp>
#include <funcs.hpp>
#include <intel.hpp>
#include <name.hpp>

#include "SMPDBInterface.h"
#include "SMPDataFlowAnalysis.h"
#include "SMPStaticAnalyzer.h"
#include "SMPFunction.h"
#include "SMPBasicBlock.h"
#include "SMPInstr.h"
#include "SMPProgram.h"

// Set to 1 for debugging output
#define SMP_DEBUG 1
#define SMP_DEBUG_GLOBAL_GRANULARITY 0
#define SMP_DEBUG_OPTIMIZATIONS 1
#define SMP_DEBUG_OPTIMIZATIONS_VERBOSE 0
#define SMP_DEBUG_FUNC 1
#define STARS_DEBUG_CALL_GRAPH_PRIORITY 1

// Compute fine-grained global static data boundaries?
#define SMP_COMPUTE_GLOBAL_GRANULARITY 1

// Distinguish between indexed and direct accesses in global granularity?
// Set to zero until we can do more precise analyses of indexed accesses.
#define SMP_DETECT_INDEXED_ACCESSES 0

// Perform interprocedural type inference and propagation?
#define STARS_INTERPROCEDURAL_TYPE_INFERENCE 1
#define STARS_INTERPROCEDURAL_ITERATION_LIMIT 7

ea_t LowestGlobalVarAddress;
ea_t HighestGlobalVarAddress;
ea_t LowestCodeAddress;
ea_t HighestCodeAddress;

#if 0
// Is Address in a data segment?
bool IsDataAddress(ea_t Address) {
	bool DataFound = false;
	segment_t *seg = SMP_getseg(Address);
	if (NULL != seg) {
		if ((seg->type == SEG_DATA) || (seg->type == SEG_BSS) || (seg->type == SEG_COMM)) {
			DataFound = true;
		}
	}
	return DataFound;
}
#endif

// Does the instruction at InstAddr access the global data offset in GlobalAddr
//  using an index register?
bool MDIsIndexedAccess(ea_t InstAddr, ea_t GlobalAddr) {
	bool DebugFlag = (InstAddr == 0x80502d3);
	ulong LocFeatures;
	insn_t LocalCmd;
#if SMP_DETECT_INDEXED_ACCESSES
	bool InstOK = SMPGetCmd(InstAddr, LocalCmd, LocFeatures);

	if (!InstOK)
#endif
		return false;

	for (int i = 0; i < UA_MAXOP; ++i) {
		op_t CurrOp = LocalCmd.Operands[i];
		if ((CurrOp.type == o_mem) || (CurrOp.type == o_displ)) {
			if (GlobalAddr == CurrOp.addr) {
				if (CurrOp.hasSIB) {
					// GlobalAddr is referenced, and SIB byte is present, so we might have
					//  an indexed access to GlobalAddr.
					regnum_t IndexReg = sib_index(CurrOp);
					if (R_sp != IndexReg) {
						// R_sp is a SIB index dummy value; means no index register
						return true;
					}
				}
				else if (o_displ == CurrOp.type) { // index reg in reg field, not in SIB byte
					return true;
				}
				else if (DebugFlag) {
					SMP_msg("Failed to find index in operand: ");
					PrintOneOperand(CurrOp, 0, -1);
					SMP_msg("\n");
				}
			}
		}
	} // end for all operands
	return false;
} // end MDIsIndexedAccess()

// *****************************************************************
// Class SMPProgram
// *****************************************************************

// Constructor
SMPProgram::SMPProgram(void) {
	this->ProfilerGranularityComplete = false;
	this->ThrowsExceptions = false;
	this->ProfInfo = NULL;
	this->AnnotationFile = NULL;
	this->InfoAnnotationFile = NULL;
	this->FuncMap.clear();
	this->TempFuncMap.clear();
	this->FuncList.clear();
	this->GlobalVarTable.clear();
	this->GlobalNameMap.clear();
	return;
}

// Destructor
SMPProgram::~SMPProgram(void) {
	map<ea_t, SMPFunction *>::iterator FuncIter;
	for (FuncIter = this->FuncMap.begin(); FuncIter != this->FuncMap.end(); ++FuncIter) {
		delete (FuncIter->second);
	}
	this->FuncMap.clear();
	this->GlobalVarTable.clear();
	this->GlobalNameMap.clear();
	this->UnsharedFragments.clear();
	return;
}

// Return SMPFunction pointer from FuncMap for FirstAddr if it exists
//  in the FuncMap, else return NULL.
SMPFunction *SMPProgram::FindFunction(ea_t FirstAddr) {
	SMPFunction *FuncPtr = NULL;
	map<ea_t, SMPFunction *>::iterator FuncMapIter = this->FuncMap.find(FirstAddr);
	if (this->FuncMap.end() != FuncMapIter) {
		FuncPtr = FuncMapIter->second;
	}
	return FuncPtr;
} // end of SMPProgram::FindFunction()

#ifdef STARS_IDA_INTERFACE

// Determine static global variable boundaries.
void SMPProgram::InitStaticDataTable(void) {
	char buf[MAXSTR];
	ea_t ea;
	flags_t ObjFlags;
	bool ReadOnlyFlag;
	size_t DummyNumber = 0; // suffix for SMP_dummy# global names

	// First, examine the data segments and collect info about static
	//   data, such as name/address/size.

	LowestGlobalVarAddress  = 0xffffffff;
	HighestGlobalVarAddress = 0x00000000;
	LowestCodeAddress  = 0xffffffff;
	HighestCodeAddress = 0x00000000;

	// Loop through all segments.
	ea_t RecentAddr = BADADDR;
#if IDA_SDK_VERSION < 600
	for (int SegIndex = 0; SegIndex < SMP_get_segm_qty(); ++SegIndex) {
		segment_t *seg = SMP_getnseg(SegIndex);
#else
	for (STARS_Segment_t *seg = SMP_get_first_seg(); NULL != seg; seg = SMP_get_next_seg(RecentAddr)) {
#endif
		char SegName[MAXSTR];
		RecentAddr = seg->get_startEA();
		ssize_t SegNameSize = SMP_get_segm_name(seg, SegName, sizeof(SegName) - 1);

		// We are only interested in the data segments of type
		// SEG_DATA, SEG_BSS and SEG_COMM.
#if SMP_DEBUG
		SMP_msg("Found segment of type <elided>" /*, seg->type */);
		if (SegNameSize > 0)
			SMP_msg(" SegName: %s", SegName);
		SMP_msg(" from %lx to %lx\n", (unsigned long) seg->get_startEA(), (unsigned long) seg->get_endEA());
		if (ReadOnlyFlag) {
			SMP_msg("Read-only segment.\n");
		}
#endif
		if ((seg->IsDataSegment() ) || (seg->IsBSSSegment())
		    || (seg->IsCommonSegment())) {
			// Loop through each of the segments we are interested in,
			//  examining all data objects (effective addresses).
			ReadOnlyFlag = ((seg->IsReadableSegment()) && (!(seg->IsWriteableSegment())));
#if SMP_DEBUG
			SMP_msg("Starting data segment of type <elided>" /*, seg->type */);
			if (SegNameSize > 0)
				SMP_msg(" SegName: %s", SegName);
			SMP_msg(" from %lx to %lx\n", (unsigned long) seg->get_startEA(), (unsigned long) seg->get_endEA());
			if (ReadOnlyFlag) {
				SMP_msg("Read-only data segment.\n");
			}
#endif
			ea = seg->get_startEA();
			while (ea < seg->get_endEA()) {
				ObjFlags = SMP_get_flags_novalue(ea);
				// Only process head bytes of data objects, i.e. isData().
				if (isData(ObjFlags)) {
				    // Compute the size of the data object.
					ea_t NextEA = SMP_next_head(ea, seg->get_endEA());
					if (NextEA == BADADDR) {
				       NextEA = seg->get_endEA();
					}
					size_t ObjSize = (size_t) (NextEA - ea);
					if (LowestGlobalVarAddress > ea)
						LowestGlobalVarAddress = ea;
					if (HighestGlobalVarAddress < NextEA)
						HighestGlobalVarAddress = NextEA - 1;
					// Get the data object name using its address.
				    char *TrueName = SMP_get_true_name(BADADDR, ea, buf, sizeof(buf));
					if (NULL == TrueName) {
						int count = SMP_snprintf(buf, sizeof(buf), "SMP_dummy%zu", DummyNumber);
						++DummyNumber;
						TrueName = buf;
					}

				    // Record the name, address, size, and type info.
					struct GlobalVar VarTemp;
					VarTemp.addr = ea;
					VarTemp.size = ObjSize;
					VarTemp.ReadOnly = ReadOnlyFlag;
					VarTemp.IndexedAccess = false;
					VarTemp.flags = ObjFlags;
					SMP_strncpy(VarTemp.name, buf, sizeof(VarTemp.name) - 1);
					// Insert name and address into name-addr map if it is
					//  not an SMP_dummy0 variable.
					if (NULL != TrueName) {
						string bufstring(buf);
						pair<string, ea_t> TempPair(bufstring, ea);
						pair<map<string, ea_t>::iterator, bool> PairIB;
						PairIB = this->GlobalNameMap.insert(TempPair);
						if (!PairIB.second) {
							SMP_msg("ERROR: Insertion into GlobalNameMap: %s\n", buf);
						}
						assert(PairIB.second);
					}
					VarTemp.FieldOffsets.clear();
#if SMP_COMPUTE_GLOBAL_GRANULARITY
					if (VarTemp.size < 1000000) { // don't waste time on monster objects
						this->ComputeGlobalFieldOffsets(VarTemp);
					}
#endif
					pair<ea_t, struct GlobalVar> TempItem(ea, VarTemp);
					this->GlobalVarTable.insert(TempItem);

					// Check for code xrefs from the data.
					// Can have a table of pointers, so iterate through large data objects.
					ea_t TempAddr = ea;
					while ((NextEA - TempAddr) >= MD_DEFAULT_RETURN_ADDRESS_SIZE) {
						SMP_xref_t xrefs;
						for (bool ok = xrefs.SMP_first_from(TempAddr, XREF_DATA); ok; ok = xrefs.SMP_next_from()) {
							ea_t TargetAddr = xrefs.GetTo();
							if ((TargetAddr != 0) && (!xrefs.GetIscode())) {
								// Found a target, with its address in xrefs.to
								//  Is the target code?
								STARS_Segment_t *SegInfo = SMP_getseg(TargetAddr);
								if ((NULL != SegInfo) && (SegInfo->IsCodeSegment())) {
									bool NewTarget = this->InsertDataToCodeXref(TargetAddr);
									if (NewTarget)
										PrintDataToCodeXref(TempAddr, TargetAddr, 0);
								}
							}
						}
#ifdef __EA64__
						uint64 DataValue = get_qword(TempAddr);
#else
						uint32 DataValue = get_long(TempAddr);
#endif
						if (DataValue != 0) {
							// Is this a code address?
							ea_t PossibleCodeAddr = (ea_t) DataValue;
							STARS_Segment_t *SegInfo = SMP_getseg(PossibleCodeAddr);
							if ((NULL != SegInfo) && (SegInfo->IsCodeSegment())) {
								bool NewTarget = this->InsertDataToCodeXref(PossibleCodeAddr);
								if (NewTarget)
									PrintDataToCodeXref(TempAddr, PossibleCodeAddr, 0);
							}
						}
						TempAddr += MD_DEFAULT_RETURN_ADDRESS_SIZE;
					}

					// Move on to next data object
					ea = NextEA;
				}
				else {
					ea = nextaddr(ea);
				}
			} // end while (ea < seg->endEA)
		} // end if (seg->type == SEG_DATA ...)
		else if (seg->IsCodeSegment()) {
			if (seg->get_startEA() < LowestCodeAddress)
				LowestCodeAddress = seg->get_startEA();
			if (seg->get_endEA() > HighestCodeAddress)
				HighestCodeAddress = seg->get_endEA() - 1;
		} // end else if (seg->type === SEG_CODE)
		else {
#if SMP_DEBUG
			SMP_msg("Not processing segment of type <elided> SegName: %s from %lx to %lx\n",
				/*seg->type,*/ SegName, (unsigned long) seg->get_startEA(), (unsigned long) seg->get_endEA());
#endif
		}
	} // end for all segments
#if SMP_COUNT_MEMORY_ALLOCATIONS
	SMPGlobalVarCount += this->GlobalVarTable.size();
#endif

	return;
} // end of SMPProgram::InitStaticDataTable()

#else
// IRDB version of InitStaticDataTable()
#endif

#ifdef STARS_IDA_INTERFACE

// Find the direct and indexed accesses to offsets within each static data table entry.
//  Record the offset and kind of access (indexed or not) and conservatively mark the
//  field boundaries based on the unindexed accesses.
void SMPProgram::ComputeGlobalFieldOffsets(struct GlobalVar &CurrGlobal) {
	SMP_xref_t xb;
	ea_t addr;
	size_t offset;
	bool DebugFlag = false;
	DebugFlag |= (0 == strcmp("spec_fd", CurrGlobal.name));
	for (addr = CurrGlobal.addr; addr < CurrGlobal.addr + CurrGlobal.size; ++addr) {
		bool Referenced = false;
		offset = addr - CurrGlobal.addr;
		pair<size_t, bool> TempOffset(offset, false); // false ==> No indexed accesses seen yet
		for (bool ok = xb.SMP_first_to(addr, XREF_ALL); ok; ok = xb.SMP_next_to()) {
			uchar XrefType = xb.GetType() & XREF_MASK;
			if (xb.GetIscode()) {
#if SMP_DEBUG_GLOBAL_GRANULARITY
				SMP_msg("WARNING: code xref to global data at %x\n", addr);
#endif
				;
			}
			else {
				ea_t FromAddr = xb.GetFrom();
				if ((XrefType == dr_O) || (XrefType == dr_W) || (XrefType == dr_R)) {
#if SMP_DEBUG_GLOBAL_GRANULARITY
					SMPInstr TempInstr(FromAddr);
					TempInstr.Analyze();
					SMP_msg("Data xref to global data %s at %x from code at %x %s\n",
						CurrGlobal.name, addr, FromAddr, TempInstr.GetDisasm());
#endif
					Referenced = true;
					TempOffset.second |= MDIsIndexedAccess(FromAddr, addr);
				}
				else {
#if SMP_DEBUG_GLOBAL_GRANULARITY
					SMP_msg("WARNING: Weird data xref type %d at %x\n", XrefType, FromAddr);
#endif
					;
				}
			}
		} // end for (bool ok = iterate through xrefs ...)
		if (Referenced) {
			CurrGlobal.FieldOffsets.insert(TempOffset);
		}
	} // end for all addrs in current global

	return;
} // end of SMPProgram::ComputeGlobalFieldOffsets()

#endif
// No need for IRDB version, as all fine-grained info computed in ComputeGlobalFieldOffsets() will
//  be written to the annotations file, read by the IRDB builder process, and then read back in
//  the IRDB version of InitStaticDataTable().


// Static data analysis driver. Called before any code analysis so
//  that memory access profiler annotations can interact with the
//  results of this analysis.
void SMPProgram::AnalyzeData(void) {
	// Collect initial info about global static data objects.
	this->InitStaticDataTable();

	return;
} // end of SMPProgram::AnalyzeData()

// Notification from ProfilerInformation that granularity inference is complete.
void SMPProgram::ProfGranularityFinished(FILE *AnnotFile, FILE *InfoAnnotFile) {
	this->ProfilerGranularityComplete = true;
	this->AnnotationFile = AnnotFile;
	this->InfoAnnotationFile = InfoAnnotFile;
	return;
}

// Add code fragment starting address to set; return false if already in set, true otherwise
bool SMPProgram::InsertUnsharedFragment(ea_t TargetAddr) {
	pair<set<ea_t>::iterator, bool> InsertResult;
	InsertResult = this->UnsharedFragments.insert(TargetAddr);
	return InsertResult.second;
} // end of SMPProgram::InsertUnsharedFragment()

// Add code fragment starting address to set; return false if already in set, true otherwise
bool SMPProgram::InsertDataToCodeXref(ea_t TargetAddr) {
	pair<set<ea_t>::iterator, bool> InsertResult;
	InsertResult = this->DataToCodeXrefTargets.insert(TargetAddr);
	return InsertResult.second;
} // end of SMPProgram::InsertUnsharedFragment()

// Add unreachable block and its instructions to containers
void SMPProgram::AddUnreachableBlock(SMPBasicBlock *DeadBlock) {
	assert(NULL != DeadBlock);

	this->UnreachableBlocks.push_back(DeadBlock);

	vector<SMPInstr *>::iterator InstIter;
	for (InstIter = DeadBlock->GetFirstInst(); InstIter != DeadBlock->GetLastInst(); ++InstIter) {
		SMPInstr *CurrInst = (*InstIter);
		ea_t InstAddr = CurrInst->GetAddr();

		// Add inst to list
		this->UnreachableInstList.push_back(CurrInst);

		// Map InstAddr to block pointer
		pair<ea_t, SMPBasicBlock *> InsertPair(InstAddr, DeadBlock);
		pair<map<ea_t, SMPBasicBlock *>::iterator, bool> InsertResult;
		InsertResult = this->UnreachableInstBlockMap.insert(InsertPair);
		assert(InsertResult.second);
	}

	return;
} // end of SMPProgram::AddUnreachableBlock()

void SMPProgram::SetProgramThrowsExceptions(void) {
	this->ThrowsExceptions = true;
	return;
}

// Add block, e.g. with "call 0" instruction, to later removal list.
void SMPProgram::AddBlockToRemovalList(SMPBasicBlock *UnreachableBlock) {
	this->BlocksPendingRemoval.push_back(UnreachableBlock);
	return;
} // end of SMPProgram::AddBlockToRemovalList()

// Is InstAddr in the set of unshared code fragments?
bool SMPProgram::IsUnsharedFragment(ea_t InstAddr) {
	bool Found = (this->UnsharedFragments.find(InstAddr) != this->UnsharedFragments.end());
	return Found;
}

// Does InstAddr have a data xref to it?
bool SMPProgram::IsCodeXrefFromData(ea_t InstAddr) const {
	bool Found = (this->DataToCodeXrefTargets.find(InstAddr) != this->DataToCodeXrefTargets.end());
	return Found;
}

// Main program analysis driver. Goes through all functions and
//  analyzes all functions and global static data.
void SMPProgram::Analyze(ProfilerInformation *pi, FILE *AnnotFile, FILE *InfoAnnotFile) {
	SMPFunction *CurrFunc;
	bool DebugFlag = false;
	long TotalTypedDefs = 0;
	long TotalUntypedDefs = 0;
	long TotalTypedPhiDefs = 0;
	long TotalUntypedPhiDefs = 0;
	long TotalSafeFuncs = 0;
	size_t TotalInstructions = 0;

	this->ProfInfo = pi;

	// Overall structure is sequential function analysis through the whole program:
	// STEP 1: Collect initial info about all functions.
	// STEP 2: LVA, SSA, and dead metadata analyses.
	// STEP 3: Safe return address analysis.
	// STEP 4: Type inference & find redundant metadata, apply profiler info, re-do.
	// Currently, we are reducing memory consumption by emitting data annotations
	//  after loop 1 and then releasing global data table memory.

	// STEP 1: Collect initial info about all functions.

#ifdef STARS_IDA_INTERFACE
	// Loop through all segments.
	ea_t RecentAddr = BADADDR;
	unsigned long long STARS_TotalCodeSize = 0;
#if IDA_SDK_VERSION < 600
	for (int SegIndex = 0; SegIndex < SMP_get_segm_qty(); ++SegIndex) {
		segment_t *seg = SMP_getnseg(SegIndex);
#else
	for (STARS_Segment_t *seg = SMP_get_first_seg(); NULL != seg; seg = SMP_get_next_seg(RecentAddr)) {
#endif
		char SegName[MAXSTR];
		RecentAddr = seg->get_startEA();
		ssize_t SegNameSize = SMP_get_segm_name(seg, SegName, sizeof(SegName) - 1);
		if (seg->IsCodeSegment()) {
			STARS_TotalCodeSize += (seg->get_endEA() - seg->get_startEA());
#if SMP_DEBUG
			SMP_msg("Starting code segment");
			if (SegNameSize > 0)
				SMP_msg(" SegName: %s", SegName);
			SMP_msg(" from %lx to %lx\n", (unsigned long) seg->get_startEA(), (unsigned long) seg->get_endEA());
#endif
		} // end if SEG_CODE segment
	} // end for all segments
#endif   // STARS_IDA_INTERFACE

	size_t NumFuncs = SMP_get_func_qty();
#if SMP_DEBUG
	SMP_msg("INFO: Number of functions: %zu Total Code Size: %llu\n", NumFuncs, STARS_TotalCodeSize);
#endif
	if (STARS_CODESIZE_FULL_ANALYSIS_LIMIT < STARS_TotalCodeSize) {
		STARS_PerformReducedAnalysis = true;
		SMP_msg("INFO: Performing reduced STARS analyses due to code size.\n");
	}

	for (size_t FuncIndex = 0; FuncIndex < NumFuncs; ++FuncIndex) {
		STARS_Function_t *FuncInfo = SMP_getn_func(FuncIndex);

		if (NULL == FuncInfo) {
			SMP_msg("ERROR: NULL FuncInfo for FuncIndex %zu \n", FuncIndex);
			continue;
		}

#if 1
		STARS_Segment_t *seg = SMP_getseg(FuncInfo->get_startEA());
		if (seg->IsXternSegment() /* ->type == SEG_XTRN */) {
			SMP_msg("Skipping SEG_XTRN func: FuncIndex %zu \n", FuncIndex);
			continue;
		}
#endif
		// Check for Unshared fragments that are not really functions.
		if (this->IsUnsharedFragment(FuncInfo->get_startEA())) {
			SMP_msg("INFO: Not creating function for unshared fragment at %lx.\n", 
				(unsigned long) FuncInfo->get_startEA());
			continue;
		}

		// Create a function object.
		CurrFunc = new SMPFunction(FuncInfo, this);
		assert(NULL != CurrFunc);
		CurrFunc->AnalyzeFunc();
		if (CurrFunc->IsFuncEmpty()) {
			SMP_msg("INFO: Empty function %s at %lx removed.\n", CurrFunc->GetFuncName(), 
				(unsigned long) FuncInfo->get_startEA());
			delete CurrFunc;
		}
		else {
			pair<ea_t, SMPFunction *> TempFunc(FuncInfo->get_startEA(), CurrFunc);
			this->FuncMap.insert(TempFunc);
			if (STARS_PerformReducedAnalysis) {
				// Not enough memory to hold all functions. Emit reduced annotations and release memory.
				CurrFunc->EmitAnnotations(AnnotFile, InfoAnnotFile);  // memory released in EmitAnnotations()
			}
		}
	} // end for (size_t FuncIndex = 0; ...) 

	// Find any unshared fragments that were added to FuncMap before it was
	//  discovered that they were unshared fragments of other functions, and
	//  remove them. Put all valid functions into the TempFuncMap copy.
	map<ea_t, SMPFunction*>::iterator MapIter = this->FuncMap.begin();
	map<ea_t, SMPFunction*>::iterator NextMapIter = MapIter;
	while (MapIter != this->FuncMap.end()) {
		++NextMapIter;
		CurrFunc = MapIter->second;
		if ((NULL != CurrFunc) && CurrFunc->IsFuncEmpty()) {
			delete CurrFunc;
			CurrFunc = NULL;
		}
		if (NULL == CurrFunc) {
			this->FuncMap.erase(MapIter);
		}
		else if (this->UnsharedFragments.find(CurrFunc->GetFirstFuncAddr()) != this->UnsharedFragments.end()) {
			this->FuncMap.erase(MapIter);
		}
		else {
			pair<map<ea_t, SMPFunction*>::iterator, bool> InsertResult;
			InsertResult = this->TempFuncMap.insert(*MapIter);  // make a copy for processing
			assert(InsertResult.second);
		}
		MapIter = NextMapIter;
	}

#if SMP_COUNT_MEMORY_ALLOCATIONS
	SMPFuncCount += this->FuncMap.size();
	SMPFuncCount += this->TempFuncMap.size();
#endif
#if SMP_DEBUG
	SMP_msg("INFO: Number of functions in FuncMap: %zu\n", this->FuncMap.size());
#endif

	if (STARS_PerformReducedAnalysis) {
		this->EmitDataAnnotations(this->AnnotationFile, this->InfoAnnotationFile);
		this->GlobalVarTable.clear();
		this->GlobalNameMap.clear();
		SMP_msg("INFO: Maximum basic block count in one function: %lu\n", STARS_MaxBlockCount);
		return;
	}

	while (!(this->TempFuncMap.empty())) {
		this->PrioritizeCallGraph();
		list<pair<ea_t, SMPFunction *> >::iterator FuncIter = this->FuncList.begin();
		while (FuncIter != this->FuncList.end()) {
			SMPFunction *TempFunc = FuncIter->second;
			TempFunc->AdvancedAnalysis();
			TempFunc->SetFuncProcessed(true);
			this->PrioritizedFuncList.push_back(TempFunc); // record processing order
			this->FuncList.pop_front();  // remove processed item
			FuncIter = this->FuncList.begin();
		} // end for all functions in FuncList
	} // end for all functions in TempFuncMap

	// In order to reduce memory consumption, emit the global data annotations now,
	//  and then release the memory for the global data. Note that this means we
	//  cannot presently apply type inference info to the global data table. If we
	//  want to do that in the future, we will have to redesign.
	assert(true == this->ProfilerGranularityComplete);
	this->EmitDataAnnotations(this->AnnotationFile, this->InfoAnnotationFile);
	this->GlobalVarTable.clear();
	this->GlobalNameMap.clear();

#ifndef SMP_REDUCED_ANALYSIS

	// STEP 2: Compute SSA form.
	list<SMPFunction *>::iterator FuncListIter;
	for (FuncListIter = this->PrioritizedFuncList.begin(); FuncListIter != this->PrioritizedFuncList.end(); ++FuncListIter) {
		CurrFunc = (*FuncListIter);
		if (NULL == CurrFunc) {
			SMP_msg("ERROR: NULL Func ptr in PrioritizedFuncList\n");
			continue;
		}
		CurrFunc->FreeUnusedMemory2(); // free memory
		if (CurrFunc->StackPtrAnalysisSucceeded() && CurrFunc->HasGoodRTLs()
			&& (!(CurrFunc->HasUnresolvedIndirectJumps() || CurrFunc->HasSharedChunks()))) {
#if 0  // LVA is now performed from Func->AdvancedAnalysis() in STEP 1 above
			if (DebugFlag) {
				SMP_msg("Performing LVA for %s.\n", CurrFunc->GetFuncName());
			}
			CurrFunc->LiveVariableAnalysis(false);
#endif
			if (DebugFlag) SMP_msg("Computing SSA.\n");
			CurrFunc->ComputeSSA();
			if (DebugFlag) SMP_msg("Finished SSA.\n");
			// Find constant-valued DEFs using SCCP algorithm
			CurrFunc->SparseConditionalConstantPropagation();

		}
		CurrFunc->MarkFunctionSafe();
		if (DebugFlag) SMP_msg("Finished MarkFunctionSafe.\n");

		CurrFunc->FreeUnusedMemory3(); // free memory
	}

#if 0  // need to debug
	// Remove any basic blocks that had a direct indication of being unreachable, e.g. "call 0" instruction.
	//  If any function becomes empty as a result, the function is unreachable, so any block calling it
	//  should also be removed.
	this->ProcessBlocksPendingRemoval();
#endif

	// LOOP 3: safe return address analysis.
	bool FuncTypeChanged;
	do {
		FuncTypeChanged = false;
		for (FuncListIter = this->PrioritizedFuncList.begin(); FuncListIter != this->PrioritizedFuncList.end(); ++FuncListIter) {
			CurrFunc = (*FuncListIter);
			if (NULL == CurrFunc) {
				SMP_msg("ERROR: NULL Func ptr in PrioritizedFuncList\n");
				continue;
			}
			if (CurrFunc->GetReturnAddressStatus() == FUNC_SAFE_IF_CALLEES_ARE_SAFE) {
				FuncType NewType = RecurseAndMarkRetAdd(CurrFunc);
				if (NewType != FUNC_SAFE_IF_CALLEES_ARE_SAFE) {
					FuncTypeChanged = true;
				}
			}
		}
	} while (FuncTypeChanged);

	// Any functions still dependent on their callees are SAFE functions in a mutually recursive state.
	for (FuncListIter = this->PrioritizedFuncList.begin(); FuncListIter != this->PrioritizedFuncList.end(); ++FuncListIter) {
		CurrFunc = (*FuncListIter);
		if (NULL == CurrFunc) {
			SMP_msg("ERROR: NULL Func ptr in PrioritizedFuncList\n");
			continue;
		}
		if (CurrFunc->GetReturnAddressStatus() == FUNC_SAFE_IF_CALLEES_ARE_SAFE) {
			CurrFunc->SetReturnAddressStatus(FUNC_SAFE);
		}
	}
	// end of step 3

	for (FuncListIter = this->PrioritizedFuncList.begin(); FuncListIter != this->PrioritizedFuncList.end(); ++FuncListIter) {
		CurrFunc = (*FuncListIter);
		if (NULL == CurrFunc) {
			SMP_msg("ERROR: NULL Func ptr in PrioritizedFuncList\n");
			continue;
		}
		bool UnsafeCallees = false;
		bool UnsafeSpecCallees = false;
		size_t NumCallTargets = CurrFunc->GetNumCallTargets();
		for (size_t i = 0; i < NumCallTargets; ++i) {
			ea_t CallAddr = CurrFunc->GetCallTargetAddr(i);
			SMPFunction *ChildInstance = this->FindFunction(CallAddr);
			if (!ChildInstance) {
#if SMP_DEBUG_FUNC
				// if a call target doesnt have a SMPFunction instance note it down
				SMP_msg("ERROR: Function does not have SMPFunction instance at %llx from %s\n", (unsigned long long) CallAddr, CurrFunc->GetFuncName());
#endif
				continue;
			}
			UnsafeCallees |= (!ChildInstance->IsSafeCallee());
			UnsafeSpecCallees |= (!ChildInstance->IsSpecSafeCallee());
		}

#if SMP_USE_SWITCH_TABLE_INFO
		if (CurrFunc->StackPtrAnalysisSucceeded() && CurrFunc->HasGoodRTLs() && !CurrFunc->HasUnresolvedIndirectJumps() && !CurrFunc->HasSharedChunks()) {
#else
		if (CurrFunc->StackPtrAnalysisSucceeded() && CurrFunc->HasGoodRTLs() && !CurrFunc->HasIndirectJumps() && !CurrFunc->HasSharedChunks()) {
#endif
#if SMP_DEBUG_OPTIMIZATIONS
			SMP_msg("Analyzing metadata for function %s\n", CurrFunc->GetFuncName());
#endif
			CurrFunc->AnalyzeMetadataLiveness();
			if (DebugFlag) SMP_msg("Finished analyzing metadata.\n");
		}

		// If callees are unsafe, we need mmStrata to allocate a memory referent for our frame.
		//  Note: Unsafe callees do not affect metadata analysis, so do metadata analysis first.
		CurrFunc->SetNeedsFrame(CurrFunc->NeedsStackFrame() || UnsafeCallees);
		CurrFunc->SetSpecNeedsFrame(CurrFunc->SpecNeedsStackFrame() || UnsafeSpecCallees);
		if (UnsafeCallees) {
#if 0   // unsafe callees should not affect safety of stack access DU-chains in caller
			CurrFunc->SetFuncSafe(false);
#endif
#if STARS_CONSERVATIVE_FAST_RETURNS
			CurrFunc->SetUnsafeForFastReturns(true, RAUNSAFE_CALLEES);
#endif
		}

#if SMP_USE_SWITCH_TABLE_INFO
		if (CurrFunc->StackPtrAnalysisSucceeded() && CurrFunc->HasGoodRTLs() && !CurrFunc->HasUnresolvedIndirectJumps() && !CurrFunc->HasSharedChunks()) {
#else
		if (CurrFunc->StackPtrAnalysisSucceeded() && CurrFunc->HasGoodRTLs() && !CurrFunc->HasIndirectJumps() && !CurrFunc->HasSharedChunks()) {
#endif
#if SMP_DEBUG_OPTIMIZATIONS
			SMP_msg("Inferring types for function %s\n", CurrFunc->GetFuncName());
#endif
			CurrFunc->AliasAnalysis();
			CurrFunc->InferTypes(true);
			CurrFunc->FindRedundantMetadata();

			// Apply profiler information.
			if (0 < pi->GetProfilerAnnotationCount()) { // If no profiler annotations are available, save time.
				CurrFunc->ApplyProfilerInformation(pi);
				CurrFunc->InferTypes(false);
				CurrFunc->FindRedundantMetadata();
			}

			TotalTypedDefs += CurrFunc->GetTypedDefs();
			TotalUntypedDefs += CurrFunc->GetUntypedDefs();
			TotalTypedPhiDefs += CurrFunc->GetTypedPhiDefs();
			TotalUntypedPhiDefs += CurrFunc->GetUntypedPhiDefs();
			if (CurrFunc->IsSafe())
				++TotalSafeFuncs;
#if 0 // move up
			// Find constant-valued DEFs using SCCP algorithm
			CurrFunc->SparseConditionalConstantPropagation();
#endif
			// Infer fine-grained info (signedness, bit widths, etc.)
			CurrFunc->InferFGInfo();

#if SMP_DEBUG_OPTIMIZATIONS_VERBOSE
			if (DebugFlag) {
				CurrFunc->Dump();
				DebugFlag = false;
			}
#endif
		}
		TotalInstructions += CurrFunc->GetInstCount();
	} // end for all functions

#if STARS_INTERPROCEDURAL_TYPE_INFERENCE
	// STEP 4: Interprocedural type inference and propagation.
	SMP_msg("Performing interprocedural type inference.\n");
	bool changed;
	size_t IterationCounter = 0;
	do {
		changed = false;
		++IterationCounter;
		for (FuncListIter = this->PrioritizedFuncList.begin(); FuncListIter != this->PrioritizedFuncList.end(); ++FuncListIter) {
			CurrFunc = (*FuncListIter);
			if (NULL == CurrFunc) {
				SMP_msg("ERROR: NULL Func ptr in PrioritizedFuncList\n");
				continue;
			}
#if SMP_USE_SWITCH_TABLE_INFO
			if (CurrFunc->StackPtrAnalysisSucceeded() && CurrFunc->HasGoodRTLs() && !CurrFunc->HasUnresolvedIndirectJumps() && !CurrFunc->HasSharedChunks()) {
#else
			if (CurrFunc->StackPtrAnalysisSucceeded() && CurrFunc->HasGoodRTLs() && !CurrFunc->HasIndirectJumps() && !CurrFunc->HasSharedChunks()) {
#endif
				changed |= CurrFunc->InferInterproceduralTypes();
			}
#if 0
			if ((!changed || (IterationCounter > STARS_INTERPROCEDURAL_ITERATION_LIMIT)) && (0 == strcmp("__mktime_internal", CurrFunc->GetFuncName()))) {
				CurrFunc->Dump();
			}
#endif		
		}
	} while (changed && (IterationCounter <= STARS_INTERPROCEDURAL_ITERATION_LIMIT));
	SMP_msg("Interprocedural type inference terminated after iteration %zu changed: %d\n", IterationCounter, changed);
#endif



				// Free memory not needed to emit annotations, now that type inference is done.
	CurrFunc->FreeUnusedMemory4();

#if SMP_COUNT_MEMORY_ALLOCATIONS
	// Emit info on major allocated objects, in case we run out of memory later.
	SMP_msg("InstCount: %lu BlockCount: %lu FuncCount: %lu GlobalVarCount: %lu LocalVarCount: %lu DUChainCount: %lu\n",
		SMPInstCount, SMPBlockCount, SMPFuncCount, SMPGlobalVarCount, SMPLocalVarCount, SMPDefUseChainCount);
	SMP_msg("InstBytes: %lu DUChainBytes: %lu \n", SMPInstBytes, SMPDefUseChainBytes);
#endif

	SMP_msg("Total instructions: %zu\n", TotalInstructions);
	SMP_msg("Total Typed DEFs: %ld\n", TotalTypedDefs);
	SMP_msg("Total Untyped DEFs: %ld\n", TotalUntypedDefs);
	SMP_msg("Total Typed Phi DEFs: %ld\n", TotalTypedPhiDefs);
	SMP_msg("Total Untyped Phi DEFs: %ld\n", TotalUntypedPhiDefs);
	SMP_msg("Total dead metadata DEFs: %lu\n", DeadMetadataCount);
	SMP_msg("Total live metadata DEFs: %lu\n", LiveMetadataCount);
	SMP_msg("Total resolved indirect jumps: %lu\n", ResolvedIndirectJumpCount);
	SMP_msg("Total unresolved indirect jumps: %lu\n", UnresolvedIndirectJumpCount);
	SMP_msg("Total Constant DEFs: %lu\n", ConstantDEFCount);
	SMP_msg("Total Branches always taken: %lu\n", AlwaysTakenBranchCount);
	SMP_msg("Total Branches never taken: %lu\n", NeverTakenBranchCount);
	SMP_msg("Total Safe Functions: %ld\n", TotalSafeFuncs);
	SMP_msg("Unused struct entries reclaimed: %lu\n", UnusedStructCount);
	SMP_msg("Unused 4-byte entries reclaimed: %lu\n", UnusedIntCount);
#if STARS_SCCP_GATHER_STATISTICS
	// Counters for analyzing Sparse Conditional Constant Propagation effectiveness.
	SMP_msg("Total function calls with outarg writes analyzed: %lu\n", SCCPFuncsWithArgWriteCount);
	SMP_msg("Total function calls with constant outarg writes analyzed: %lu\n", SCCPFuncsWithConstantArgWriteCount);
	SMP_msg("Total outarg writes analyzed: %lu\n", SCCPOutgoingArgWriteCount);
	SMP_msg("Total constant outarg writes analyzed: %lu\n", SCCPConstantOutgoingArgWriteCount);
#endif

#endif // not SMP_REDUCED_ANALYSIS
	SMP_msg("INFO: Maximum basic block count in one function: %lu\n", STARS_MaxBlockCount);

	return;
} // end of SMPProgram::Analyze()

// Does chunk at ChunkAddr belong exclusively to FuncHead?
// If so, return true and add ChunkAddr to UnsharedFragments set.
bool SMPProgram::IsChunkUnshared(ea_t ChunkAddr, ea_t FuncHeadStart, ea_t FuncHeadEnd) {
	bool Unshared = true;
	SMP_xref_t CurrXrefs;

	// See if any xref reaches this ChunkAddr from outside the FuncHead range.
	for (bool ok = CurrXrefs.SMP_first_to(ChunkAddr, XREF_ALL);	ok;	ok = CurrXrefs.SMP_next_to()) {
		ea_t FromAddr = CurrXrefs.GetFrom();
		if ((FromAddr != 0) && (CurrXrefs.GetIscode())) {
			// We found a code xref that comes to the ChunkAddr. Whether it is a fall-through or
			//  a jump/call, it is unshared only if it comes from within the FuncHead address range.
			if ((FromAddr < FuncHeadStart) || (FromAddr >= FuncHeadEnd)) {
				Unshared = false;
				break;
			}
		}
	}

	if (Unshared) {
		// We don't want unshared chunks to be considered separate funcs, as IDA Pro often does.
		(void) this->InsertUnsharedFragment(ChunkAddr);
	}

	return Unshared;
} // end of SMPProgram::IsChunkUnshared()

// Emit global data annotations.
void SMPProgram::EmitDataAnnotations(FILE *AnnotFile, FILE *InfoAnnotFile) {
	// Emit global static data annotations first.
	map<ea_t, struct GlobalVar>::iterator GlobalIter;
	for (GlobalIter = this->GlobalVarTable.begin(); GlobalIter != this->GlobalVarTable.end(); ++GlobalIter) {
	    // Output the name, address, size, and type info.
		struct GlobalVar TempGlobal = GlobalIter->second;
		// If we have an offset other than 0 but do not have offset 0, add 0 to offsets list.
		pair<size_t, bool> FirstOffset = (*(TempGlobal.FieldOffsets.begin()));
		if (0 != FirstOffset.first) {
			pair<size_t, bool> TempOffset(0, false);
			TempGlobal.FieldOffsets.insert(TempOffset);
#if SMP_DEBUG_GLOBAL_GRANULARITY
			SMP_msg("Inserted offset 0 for global var %s\n", TempGlobal.name);
#endif
		}
		unsigned long ParentReferentID = DataReferentID++;
		bool DirectAccesses = false;  // Any direct field accesses in this global?
		set<pair<size_t, bool>, LessOff>::iterator CurrOffset;
		for (CurrOffset = TempGlobal.FieldOffsets.begin(); CurrOffset != TempGlobal.FieldOffsets.end(); ++CurrOffset) {
			pair<size_t, bool> TempOffset = *CurrOffset;
			if (!TempOffset.second)
				DirectAccesses = true;
		}
		// If 0 is the only direct offset, the data is not structured.
		if (!DirectAccesses || (2 > TempGlobal.FieldOffsets.size())) {
			// No fields within object, or all fields were accessed through indices
			if (TempGlobal.ReadOnly) {
				SMP_fprintf(AnnotFile, 
					"%10x %6zu DATAREF GLOBAL %8lu %llx PARENT %s  %s RO\n",
					0, TempGlobal.size, ParentReferentID, (uint64) TempGlobal.addr,
					TempGlobal.name, DataTypes[get_optype_flags0(TempGlobal.flags) >> 20]);
			}
			else {
				SMP_fprintf(AnnotFile, 
					"%10x %6zu DATAREF GLOBAL %8lu %llx PARENT %s  %s RW\n",
					0, TempGlobal.size, ParentReferentID, (uint64) TempGlobal.addr,
					TempGlobal.name, DataTypes[get_optype_flags0(TempGlobal.flags) >> 20]);
			}
		}
		else { // structured object with fields
			// Put out annotation for whole struct first
			if (TempGlobal.ReadOnly) {
				SMP_fprintf(AnnotFile, 
					"%10x %6zu DATAREF GLOBAL %8lu %llx PARENT %s  %s RO AGGREGATE\n",
					0, TempGlobal.size, ParentReferentID, (uint64) TempGlobal.addr,
					TempGlobal.name, DataTypes[get_optype_flags0(TempGlobal.flags) >> 20]);
			}
			else {
				SMP_fprintf(AnnotFile, 
					"%10x %6zu DATAREF GLOBAL %8lu %llx PARENT %s  %s RW AGGREGATE\n",
					0, TempGlobal.size, ParentReferentID, (uint64) TempGlobal.addr,
					TempGlobal.name, DataTypes[get_optype_flags0(TempGlobal.flags) >> 20]);
			}
			// Now, emit an annotation for each field offset.
			set<pair<size_t,bool>, LessOff>::iterator FieldIter, TempIter;
			size_t counter = 1;
			size_t FieldSize;
			for (FieldIter = TempGlobal.FieldOffsets.begin(); FieldIter != TempGlobal.FieldOffsets.end(); ++FieldIter, ++counter) {
				pair<size_t,bool> CurrOffset = (*FieldIter);
				if (counter < TempGlobal.FieldOffsets.size()) {
					TempIter = FieldIter;
					++TempIter;
					pair<size_t,bool> TempOffset = (*TempIter);
					FieldSize = TempOffset.first - CurrOffset.first;
				}
				else {
					FieldSize = TempGlobal.size - CurrOffset.first;
				}
				SMP_fprintf(AnnotFile, 
					"%10x %6zu DATAREF GLOBAL %8lu %llx CHILDOF %lu OFFSET %zu %s + %zu FIELD",
					0, FieldSize, DataReferentID, (uint64) TempGlobal.addr, ParentReferentID, 
					CurrOffset.first, TempGlobal.name, CurrOffset.first);
				if (CurrOffset.second) { // indexed accesses to this field
					SMP_fprintf(AnnotFile, " INDEXED\n");
				}
				else { // only direct accesses to this field
					SMP_fprintf(AnnotFile, " DIRECT\n");
				}
				++DataReferentID;
			}
		} // end if unstructured data ... else ... 
	} // end for all globals in the global var table

	return;
} // SMPProgram::EmitDataAnnotations()

// Emit all annotations for the program.
void SMPProgram::EmitAnnotations(FILE *AnnotFile, FILE *InfoAnnotFile) {
	long TotalSafeBlocks = 0; // basic blocks with no unsafe writes
	long TotalUnsafeBlocks = 0; // basic blocks with unsafe writes

	// Mark exception-handling functions as unsafe for fast returns.
	if (this->ProgramThrowsExceptions()) {
		this->ProcessExceptionHandlingFileSections();
	}

	// Loop through all functions and emit annotations for each.
	map<ea_t, SMPFunction *>::iterator FuncIter;
	for (FuncIter = this->FuncMap.begin(); FuncIter != this->FuncMap.end(); ++FuncIter) {
		SMPFunction *TempFunc = FuncIter->second;
		if (TempFunc == NULL) continue;
		TempFunc->EmitAnnotations(AnnotFile, InfoAnnotFile);
		TotalSafeBlocks += TempFunc->GetSafeBlocks();
		TotalUnsafeBlocks += TempFunc->GetUnsafeBlocks();
#if ZST_EMIT_SPARK_ADA_TRANSLATION
		if (TempFunc->HasReducibleControlFlow()) {
			TempFunc->EmitFuncSPARKAda();
		}
#endif
	} // end for all functions

#if ZST_EMIT_SPARK_ADA_TRANSLATION
	SMP_msg("SPARK: Total subword registers translated: %lu\n", SubwordRegCount);
	SMP_msg("SPARK: Total subword memory accesses translated: %lu\n", SubwordMemCount);
	SMP_msg("SPARK: Total subword address registers translated: %lu\n", SubwordAddressRegCount);
	SMP_msg("SPARK: Total operands translated: %lu\n", SPARKOperandCount);
#endif
	SMP_msg("Total Safe Blocks: %ld\n", TotalSafeBlocks);
	SMP_msg("Total Unsafe Blocks: %ld\n", TotalUnsafeBlocks);
#if SMP_MEASURE_NUMERIC_ANNOTATIONS
	SMP_msg("INFO: NUMERIC: Add/sub overflow and underflow annotations: %lu\n", NumericAnnotationsCount12);
	SMP_msg("INFO: NUMERIC: Multiplication overflow annotations: %lu\n", NumericAnnotationsCount3);
	SMP_msg("INFO: NUMERIC: Truncation on move annotations: %lu\n", TruncationAnnotationsCount);
	SMP_msg("INFO: NUMERIC: Signedness without truncation annotations: %lu\n", SignednessWithoutTruncationCount);
	SMP_msg("INFO: NUMERIC: Load-effective-address overflow and underflow annotations: %lu\n", LeaInstOverflowCount);
	SMP_msg("INFO: NUMERIC: Width-doubling truncation annotations: %lu\n", WidthDoublingTruncationCount);
	SMP_msg("INFO: NUMERIC: Suppressions for benign overflow insts: %lu\n", BenignOverflowInstCount);
	SMP_msg("INFO: NUMERIC: Suppressions for benign overflow DEFs: %lu\n", BenignOverflowDefCount);
	SMP_msg("INFO: NUMERIC: Suppressions for benign stack ptr overflow: %lu\n", SuppressStackPtrOverflowCount);
	SMP_msg("INFO: NUMERIC: Suppressions for overflow when flags are live: %lu\n", SuppressLiveFlagsOverflowCount);
	SMP_msg("INFO: NUMERIC: Suppressions for mult. overflow when all bits are live: %lu\n", LiveMultiplyBitsCount);
	SMP_msg("INFO: NUMERIC: Suppressions for benign truncations: %lu\n", BenignTruncationCount);
	SMP_msg("INFO: NUMERIC: Suppressions for truncations when all subregs are used: %lu\n", SuppressTruncationRegPiecesAllUsed);
	SMP_msg("INFO: NUMERIC: Suppressions for signedness on truncations: %lu\n", SuppressSignednessOnTruncation);
#endif
	return;
} // end of SMPProgram::EmitAnnotations()

/**
 * If a function is still marked FUNC_UNKNOWN, this function traverses
 *  over the call graph rooted at this function and checks if all
 *  callees are marked safe.
 */  
FuncType SMPProgram::RecurseAndMarkRetAdd(SMPFunction* FuncAttrib) {
	bool UnsafeCallees = false; // might callees write into our stack frame?
	bool UnsafeSpecCallees = false; // might callees write into our stack frame?
	FuncType ReturnType = FUNC_SAFE;
	ea_t CallerAddr = FuncAttrib->GetFirstFuncAddr();

	if (FuncAttrib->IsLeaf()) {
#if SMP_DEBUG_FUNC
		if (FuncAttrib->GetReturnAddressStatus() == FUNC_UNKNOWN)
			SMP_msg("FATAL ERROR: Leaf Function %s found with status unknown", FuncAttrib->GetFuncName()); 
#endif
		assert(FuncAttrib->GetReturnAddressStatus() != FUNC_UNKNOWN);
		return FuncAttrib->GetReturnAddressStatus();
	}

	vector<ea_t> CallTargets = FuncAttrib->GetCallTargets();
	for (size_t i = 0; i < CallTargets.size(); i++) {
		ea_t CallAddr = CallTargets[i];
		SMPFunction* ChildInstance = this->FindFunction(CallAddr);
		if (!ChildInstance) {
#if SMP_DEBUG_FUNC
			// if a call target doesnt have a SMPFunction instance note it down
			SMP_msg("ERROR: Function does not have SMPFunction instance at %llx from %s\n", 
				(unsigned long long) CallAddr, FuncAttrib->GetFuncName());
#endif
			continue;
		}
		UnsafeCallees |= (!ChildInstance->IsSafeCallee());
		UnsafeSpecCallees |= (!ChildInstance->IsSpecSafeCallee());
		switch (ChildInstance->GetReturnAddressStatus()) {
			case FUNC_SAFE:
				break;

			case FUNC_UNSAFE:
			{
				FuncAttrib->SetReturnAddressStatus(FUNC_UNSAFE);
#if SMP_DEBUG_FUNC
				// if a call target is unsafe note it down
				static char StaticFuncName[MAXSMPSTR];
				qstrncpy(StaticFuncName, ChildInstance->GetFuncName(), (MAXSMPSTR-1));
				SMP_msg("Function %s marked as unsafe because %s is unsafe.\n", 
					FuncAttrib->GetFuncName(), StaticFuncName);
#endif
				ReturnType = FUNC_UNSAFE;
				break;

			}
			case FUNC_UNKNOWN:
			{
#if SMP_DEBUG_FUNC
				// if a call target is unanalyzed, assume it is UNSAFE
				static char StaticFuncName[MAXSMPSTR];
				qstrncpy(StaticFuncName, ChildInstance->GetFuncName(), (MAXSMPSTR-1));
				SMP_msg("Function %s marked as unsafe because %s is unanalyzed.\n", 
					FuncAttrib->GetFuncName(), StaticFuncName);
#endif
				ReturnType = FUNC_UNSAFE;
				break;
			}
			case FUNC_SAFE_IF_CALLEES_ARE_SAFE:
			{
				ReturnType = FUNC_SAFE_IF_CALLEES_ARE_SAFE; // back to dependent-on-callees status
				break;
			}
		} // end switch on child return address status
		if (ReturnType == FUNC_UNSAFE) {
			break; // No need to search further
		}
	} // end for all call targets
	
#if SMP_DEBUG_FUNC
	if (FUNC_SAFE == ReturnType) {
		// if a call target is safe, note it
		SMP_msg("Function marked as safe %s\n", FuncAttrib->GetFuncName());
	}
#endif

	FuncAttrib->SetReturnAddressStatus(ReturnType);

	// If callees are unsafe, we need mmStrata to
	//  allocate a memory referent for our frame.
	FuncAttrib->SetNeedsFrame(FuncAttrib->NeedsStackFrame() || UnsafeCallees);
	FuncAttrib->SetSpecNeedsFrame(FuncAttrib->SpecNeedsStackFrame() || UnsafeSpecCallees);
	if (UnsafeCallees) {
#if 0   // unsafe callees should not affect safety of stack access DU-chains in caller
		FuncAttrib->SetFuncSafe(false);
#endif
#if STARS_CONSERVATIVE_FAST_RETURNS
		FuncAttrib->SetUnsafeForFastReturns(true, RAUNSAFE_CALLEES);
#endif
	}
	if (UnsafeCallees || (FUNC_UNSAFE == ReturnType)) {
		SMP_msg("INFO: Function marked UNSAFE due solely to UNSAFE callees: %s \n", FuncAttrib->GetFuncName());
	}

	CallTargets.clear();

	return ReturnType;
} // end of SMPProgram::RecurseAndMarkRetAddr()

// If exception throwing code is detected, mark exception-handling functions as unsafe for fast returns.
void SMPProgram::ProcessExceptionHandlingFileSections(void) {
	string EHFileName(RootFileName);
	string FileSuffix(".eh_frame_addrs");
	EHFileName += FileSuffix;

	FILE *EHAddrsFile = SMP_fopen(EHFileName.c_str(), "r");
	if (EHAddrsFile == NULL) {
		SMP_msg("ERROR: Cannot open %s for reading exception handling func addrs.\n", EHFileName.c_str());
		return;
	}

	while (!SMP_feof(EHAddrsFile)) {
		ea_t ExceptionFuncAddr;
#ifdef __EA64__
		int ReadCount = SMP_fscanf(EHAddrsFile, "%llx", &ExceptionFuncAddr);
#else
		int ReadCount = SMP_fscanf(EHAddrsFile, "%x", &ExceptionFuncAddr);
#endif
		if (1 == ReadCount) { // success
			SMPFunction *EHFunc = this->FindFunction(ExceptionFuncAddr);
			if (NULL == EHFunc) {
				SMP_msg("SERIOUS WARNING: Could not find function at eh_frame address %lx\n", (unsigned long) ExceptionFuncAddr);
			}
			else {
				EHFunc->SetUnsafeForFastReturns(true, EH_FRAME_ENTRY);
			}
		}
	}
	int FCloseCode = SMP_fclose(EHAddrsFile);
	if (FCloseCode != 0) {
		SMP_msg("SERIOUS WARNING: File close failure code %d on file %s.\n", FCloseCode, EHFileName.c_str());
	}

	return;
} // end of SMPProgram::ProcessExceptionHandlingFileSections()

void SMPProgram::ResetFuncsProcessed(void) {
	map<ea_t, SMPFunction*>::iterator MapIter;
	SMPFunction *CurrFunc;
	for (MapIter = this->FuncMap.begin(); MapIter != this->FuncMap.end(); ++MapIter) {
		CurrFunc = MapIter->second;
		if (NULL == CurrFunc) {
			SMP_msg("ERROR: NULL Func ptr in FuncMap for %lx\n", (unsigned long) MapIter->first);
			continue;
		}
		CurrFunc->SetFuncProcessed(false);
	}
	return;
} // end of SMPProgram::ResetFuncsProcessed()

// Extract TempFuncMap entries into FuncList in priority order for whole progam analyses.
void SMPProgram::PrioritizeCallGraph(void) {
	map<ea_t, SMPFunction*>::iterator MapIter;
	SMPFunction *CurrFunc;
	size_t MinUnprocessedCallees = 10000; // Other than zero, what was minimum unprocessed callees.
	map<ea_t, SMPFunction*>::iterator BestMapIter = this->TempFuncMap.end(); // corresponds to first entry with MinUnprocessedCallees
	bool ReducedTempFuncMap = false; // moved TempFuncMap entries to FuncList

	MapIter = this->TempFuncMap.begin();
	while (MapIter != this->TempFuncMap.end()) {
		CurrFunc = MapIter->second;
		if (NULL == CurrFunc) {
			SMP_msg("ERROR: NULL Func ptr in TempFuncMap for %llx\n", (uint64) MapIter->first);
			++MapIter;
			continue;
		}
		size_t UnprocCalleeCount = CurrFunc->UnprocessedCalleesCount();
		if (0 == UnprocCalleeCount) {
			// Move TempFuncMap entry to FuncList.
			this->FuncList.push_back(*MapIter);
			this->TempFuncMap.erase(MapIter++);
			ReducedTempFuncMap = true;
		}
		else if (UnprocCalleeCount < MinUnprocessedCallees) {
			// New lowest non-zero unprocessed callee count.
			MinUnprocessedCallees = UnprocCalleeCount;
			BestMapIter = MapIter;
			++MapIter;
		}
		else {
			++MapIter;
		}
	} // end while (MapIter != this->TempFuncMap.end())

	if (!ReducedTempFuncMap) {
		// No success so far. Need to process the best choice available.
		if (BestMapIter != this->TempFuncMap.end()) {
			// NOTE: Experiment with using the unprocessed callees first.
			ea_t CalleeAddr = BestMapIter->second->GetFirstUnprocessedCallee();
			if (BADADDR != CalleeAddr) {
				map<ea_t, SMPFunction*>::iterator NextMapIter = this->TempFuncMap.find(CalleeAddr);
				if (NextMapIter != this->TempFuncMap.end()) {
					this->FuncList.push_back(*NextMapIter);
					this->TempFuncMap.erase(NextMapIter);
#if STARS_DEBUG_CALL_GRAPH_PRIORITY
					SMP_msg("INFO: PrioritizeCallGraph selecting unprocessed callee at %llx for func at %llx\n",
						(uint64) CalleeAddr, (uint64) BestMapIter->first);
#endif
				}
				else {
					// Work on the BestMapIter function itself.
					this->FuncList.push_back(*BestMapIter);
#if STARS_DEBUG_CALL_GRAPH_PRIORITY
					SMP_msg("INFO: PrioritizeCallGraph could not find callee at %llx; had to work on func at %llx\n",
						(uint64) CalleeAddr, (uint64) BestMapIter->first);
#endif
					this->TempFuncMap.erase(BestMapIter);
				}
			}
			else {
				// Work on the BestMapIter function itself.
				this->FuncList.push_back(*BestMapIter);
#if STARS_DEBUG_CALL_GRAPH_PRIORITY
				SMP_msg("INFO: PrioritizeCallGraph found BADADDR for callee; had to work on func at %llx\n", (uint64) BestMapIter->first);
#endif
				this->TempFuncMap.erase(BestMapIter);
			}
		}
		else {
			assert(this->TempFuncMap.empty());
		}
	}
#if STARS_DEBUG_CALL_GRAPH_PRIORITY
	else {
		SMP_msg("INFO: PrioritizeCallGraph found %zu funcs with no unprocessed callees.\n", this->FuncList.size());
	}
#endif
	return;
} // end of SMPProgram::PrioritizeCallGraph()

// Debug output dump.
void SMPProgram::Dump(void) {
	// Loop through all functions and call the debug Dump() for each.
	map<ea_t, SMPFunction *>::iterator FuncIter;
	for (FuncIter = this->FuncMap.begin(); FuncIter != this->FuncMap.end(); ++FuncIter) {
		SMPFunction *TempFunc = FuncIter->second;
		TempFunc->Dump();
	} // end for all functions
	return;
} // end of SMPProgram::Dump()

// is InstAddr still an SMPInstr inside an SMPFunction object? (not orphaned, not dead-code-removed)
bool SMPProgram::IsInstAddrStillInFunction(ea_t InstAddr, ea_t &FirstAddrInFunc) {
	bool FoundInFunc = false;

	// First question: Does IDA Pro think it is inside a function?
	STARS_Function_t *CurrFunc = SMP_get_func(InstAddr);
	if (NULL != CurrFunc) {
		// InstAddr was initially in a function. See if it was removed as unreachable code.
		map<ea_t, SMPBasicBlock *>::iterator MapIter = this->UnreachableInstBlockMap.find(InstAddr);
		// If we did not find the InstAddr in the unreachable code, then it is still in a function somewhere,
		//  else it is not in a func.
		if (MapIter == this->UnreachableInstBlockMap.end()) {
			FoundInFunc = true;
			FirstAddrInFunc = CurrFunc->get_startEA();
		}
	}

	return FoundInFunc;
} // end of SMPProgram::IsInstAddrStillInFunction()

// Remove unreachable blocks in BlocksPendingRemoval, handle calls to empty functions that result.
void SMPProgram::ProcessBlocksPendingRemoval(void) {
	list<SMPBasicBlock *>::iterator PendingIter = this->BlocksPendingRemoval.begin();
	while (PendingIter != this->BlocksPendingRemoval.end()) {
		SMPBasicBlock *CurrBlock = (*PendingIter);
		assert(NULL != CurrBlock);
		SMPFunction *CurrFunc = CurrBlock->GetFunc();
		assert(NULL != CurrFunc);
		list<SMPBasicBlock *>::iterator BlockIter = CurrFunc->GetBlockIter(CurrBlock);
		if (BlockIter != CurrFunc->GetLastBlock()) {
			CurrFunc->RemoveBlock(CurrBlock, BlockIter);
			if (CurrFunc->IsFuncEmpty()) { // func was unreachable
				// For all callers of the function, remove the calling block.
				CurrFunc->RemoveCallingBlocks();			
			}
			pair<set<SMPFunction *>::iterator, bool> InsertResult = this->FuncsWithBlocksRemoved.insert(CurrFunc);
		}
		else {
			SMP_msg("ERROR: Could not find block iter for pending removal block at %lx\n", (unsigned long) CurrBlock->GetFirstAddr());
		}
		PendingIter = this->BlocksPendingRemoval.erase(PendingIter);
	}

	// Re-compute SSA form for all functions with blocks removed.
	for (set<SMPFunction *>::iterator FuncIter = this->FuncsWithBlocksRemoved.begin(); FuncIter != this->FuncsWithBlocksRemoved.end(); ++FuncIter) {
		SMPFunction *CurrFunc = (*FuncIter);
		if (!(CurrFunc->IsFuncEmpty())) {
			CurrFunc->RecomputeSSA();
		}
	}

	return;
} // end of SMPProgram::ProcessBlocksPendingRemoval()