/*
 * 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, 2012, 2013, 2014, 2015 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 <map>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>

#include <cstdint>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <ctime>

#include "interfaces/SMPDBInterface.h"
#include "base/SMPDataFlowAnalysis.h"
#include "base/SMPFunction.h"
#include "base/SMPBasicBlock.h"
#include "base/SMPInstr.h"
#include "base/SMPProgram.h"

using namespace std;

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

// Did SCCP find an indirect call target that is constant?
#define STARS_DEBUG_INDIR_CALL_SCCP_SUCCESS 1

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

STARS_ea_t LowestGlobalVarAddress = STARS_BADADDR;
STARS_ea_t HighestGlobalVarAddress = 0;
STARS_ea_t LowestCodeAddress = STARS_BADADDR;
STARS_ea_t HighestCodeAddress = 0;

// The types of data objects based on their first operand flags.
static const char *DataTypes[] = { "VOID", "NUMHEX", "NUMDEC", "CHAR",
"SEG", "OFFSET", "NUMBIN", "NUMOCT", "ENUM", "FORCED", 
"STRUCTOFFSET", "STACKVAR", "NUMFLOAT", "UNKNOWN", 
"UNKNOWN", "UNKNOWN", 0};

// Imitate IDA Pro get_optype_flags0() from <bytes.hpp>
#define STARS_get_optype_flags0(flags) (flags & 0x00F00000LU)

#if 0
// Is Address in a data segment?
bool IsDataAddress(STARS_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

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

// Constructor
SMPProgram::SMPProgram(void) {
	this->ProfilerGranularityComplete = false;
	this->ThrowsExceptions = false;
	this->FoundMutuallyRecursiveFuncs = 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<STARS_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(STARS_ea_t FirstAddr) {
	SMPFunction *FuncPtr = NULL;
	map<STARS_ea_t, SMPFunction *>::iterator FuncMapIter = this->FuncMap.find(FirstAddr);
	if (this->FuncMap.end() != FuncMapIter) {
		FuncPtr = FuncMapIter->second;
	}
	return FuncPtr;
} // end of SMPProgram::FindFunction()



// 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.
	global_STARS_program->InitStaticDataTable(this);

	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(STARS_ea_t TargetAddr) {
	pair<set<STARS_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(STARS_ea_t TargetAddr) {
	pair<set<STARS_ea_t>::iterator, bool> InsertResult;
	InsertResult = this->DataToCodeXrefTargets.insert(TargetAddr);
	return InsertResult.second;
} // end of SMPProgram::InsertDataToCodeXref()

// TargetAddr is called from orphaned code
void SMPProgram::SetFuncAddrCalledFromOrphanedCode(STARS_ea_t TargetAddr) {
	this->FuncAddrsCalledFromOrphanedCode.insert(TargetAddr);
	return;
}

// 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);
		STARS_ea_t InstAddr = CurrInst->GetAddr();

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

		// Map InstAddr to block pointer
		pair<STARS_ea_t, SMPBasicBlock *> InsertPair(InstAddr, DeadBlock);
		pair<map<STARS_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(STARS_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(STARS_ea_t InstAddr) const {
	bool Found = (this->DataToCodeXrefTargets.find(InstAddr) != this->DataToCodeXrefTargets.end());
	return Found;
}

// Look up in address set of targets from orphaned code
bool SMPProgram::IsFuncAddrCalledFromOrphanedCode(STARS_ea_t InstAddr) const {
	bool Found = (this->FuncAddrsCalledFromOrphanedCode.find(InstAddr) != this->FuncAddrsCalledFromOrphanedCode.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;
	time_t StartTime = time(NULL), EndTime, Time1, Time2, Time3, Time4, Time5;
	double Analysis1, Analysis2, Analysis3, Analysis4;

	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.
	STARS_ea_t RecentAddr = STARS_BADADDR;
	unsigned long long STARS_TotalCodeSize = 0;
	for (STARS_Segment_t *seg = SMP_get_first_seg(); NULL != seg; seg = SMP_get_next_seg(RecentAddr)) {
		char SegName[STARS_MAXSTR];
		RecentAddr = seg->get_startEA();
		STARS_ssize_t SegNameSize = SMP_get_segm_name(seg, SegName, sizeof(SegName) - 1);
		if (seg->IsCodeSegment()) {
			STARS_TotalCodeSize += (seg->get_seg_size());
#if SMP_DEBUG
			SMP_msg("Starting code segment");
			if (SegNameSize > 0)
				SMP_msg(" SegName: %s", SegName);
			SMP_msg(" from %llx to %llx\n", (unsigned long long) seg->get_startEA(), (unsigned long 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
	global_STARS_program->ReportTotalCodeSize(STARS_TotalCodeSize);
	if (global_STARS_program->ShouldSTARSPerformReducedAnalysis()) {
		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   // IRDB functions might not map to segments, might return NULL seg.
		//  Might want an XTRN attribute for Functions instead of segments.
		STARS_Segment_t *seg = SMP_getseg(FuncInfo->get_startEA());
		if ((NULL != seg) && seg->IsXternSegment() /* ->type == SEG_XTRN */) {
			SMP_msg("Skipping SEG_XTRN func: FuncIndex %zu \n", FuncIndex);
			continue;
		}
#endif
#if STARS_INTEGRATE_UNSHARED_FRAGMENTS
		// 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 %llx.\n", 
				(unsigned long long) FuncInfo->get_startEA());
			continue;
		}
#endif
		// Create a function object.
		CurrFunc = new SMPFunction(FuncInfo, this);
		assert(NULL != CurrFunc);
		CurrFunc->AnalyzeFunc();
		if (CurrFunc->IsFuncEmpty()) {
			SMP_msg("INFO: Empty function %s at %llx removed.\n", CurrFunc->GetFuncName(), 
				(unsigned long long) FuncInfo->get_startEA());
			delete CurrFunc;
		}
		else {
			pair<STARS_ea_t, SMPFunction *> TempFunc(FuncInfo->get_startEA(), CurrFunc);
			this->FuncMap.insert(TempFunc);
			if (global_STARS_program->ShouldSTARSPerformReducedAnalysis()) {
				// 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<STARS_ea_t, SMPFunction*>::iterator MapIter = this->FuncMap.begin();
	map<STARS_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);
		}
#if STARS_INTEGRATE_UNSHARED_FRAGMENTS
		else if (this->IsUnsharedFragment(CurrFunc->GetFirstFuncAddr())) {
			this->FuncMap.erase(MapIter);
		}
#endif
		else {
			pair<map<STARS_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

	EndTime = time(NULL);
	double TimeDiff = difftime(EndTime, StartTime);
	SMP_msg("INFO: TIME: Phase 1: AnalyzeFunc: %7.2f\n", TimeDiff);
	StartTime = time(NULL);

	if (global_STARS_program->ShouldSTARSPerformReducedAnalysis()) {
		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<STARS_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

	bool ProgramChanged;
	list<SMPFunction *>::iterator FuncListIter;
	do {
		ProgramChanged = 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;
			}
			bool FuncChanged = CurrFunc->AdvancedAnalysis2();
			ProgramChanged |= FuncChanged;
		}
	} while (ProgramChanged);

	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->AdvancedAnalysis3();
	}

	EndTime = time(NULL);
	TimeDiff = difftime(EndTime, StartTime);
	SMP_msg("INFO: TIME: Phase 2: AdvancedAnalysis: %7.2f\n", TimeDiff);
	StartTime = time(NULL);

	// 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();

	EndTime = time(NULL);
	TimeDiff = difftime(EndTime, StartTime);
	SMP_msg("INFO: TIME: Phase 3: EmitDataAnnotations: %7.2f\n", TimeDiff);
	StartTime = time(NULL);

#ifndef SMP_REDUCED_ANALYSIS

	// STEP 2: Compute SSA form.
	Analysis1 = Analysis2 = Analysis3 = Analysis4 = 0.0;
	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())) {
#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");
			Time1 = time(NULL);
			CurrFunc->ComputeSSA();
			Time2 = time(NULL);
			Analysis1 += difftime(Time2, Time1);
			if (DebugFlag) SMP_msg("Finished SSA.\n");
			if (!CurrFunc->HasSharedChunks()) {
				// Find constant-valued DEFs using SCCP algorithm
				CurrFunc->SparseConditionalConstantPropagation();
#if STARS_DEBUG_INDIR_CALL_SCCP_SUCCESS
				CurrFunc->AuditSCCPForIndirectTargets();
#endif
			}
			Time3 = time(NULL);
			Analysis2 += difftime(Time3, Time2);
			CurrFunc->AliasAnalysis();
			Time4 = time(NULL);
			Analysis3 += difftime(Time4, Time3);

		}
		Time4 = time(NULL);
		CurrFunc->MarkFunctionSafe();
		Time5 = time(NULL);
		Analysis4 += difftime(Time5, Time4);
		if (DebugFlag) SMP_msg("Finished MarkFunctionSafe.\n");

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

	EndTime = time(NULL);
	TimeDiff = difftime(EndTime, StartTime);
	SMP_msg("INFO: TIME: Phase 4: SSA+SCCP+FuncSafe+AliasAnalysis: %7.2f SSA: %7.2f SCCP: %7.2f AliasAnalysis: %7.2f FuncSafe: %7.2f\n", 
		TimeDiff, Analysis1, Analysis2, Analysis3, Analysis4);
	StartTime = time(NULL);

#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

	EndTime = time(NULL);
	TimeDiff = difftime(EndTime, StartTime);
	SMP_msg("INFO: TIME: Phase 5: RetAddrStatus: %7.2f\n", TimeDiff);
	StartTime = time(NULL);

	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) {
			STARS_ea_t CallAddr = CurrFunc->GetCallTargetAddr(i);
			SMPFunction *ChildInstance = this->FindFunction(CallAddr);
			if (!ChildInstance) {
#if SMP_DEBUG_FUNC
				// if a call target doesn't have a SMPFunction instance note it down
				if (!CurrFunc->IsLinkerStub() && (STARS_BADADDR != CallAddr)) {
					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()) {
#else
		if (CurrFunc->StackPtrAnalysisSucceeded() && CurrFunc->HasGoodRTLs() && !CurrFunc->HasIndirectJumps()) {
#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()) {
#else
		if (CurrFunc->StackPtrAnalysisSucceeded() && CurrFunc->HasGoodRTLs() && !CurrFunc->HasIndirectJumps()) {
#endif
#if SMP_DEBUG_OPTIMIZATIONS
			SMP_msg("Inferring types for function %s\n", CurrFunc->GetFuncName());
#endif
			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;
			// 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

	EndTime = time(NULL);
	TimeDiff = difftime(EndTime, StartTime);
	SMP_msg("INFO: TIME: Phase 6: MetaData+InferTypes+InferFG: %7.2f\n", TimeDiff);
	StartTime = time(NULL);

	// STEP 4A: Interprocedural CFG return target analysis.
	SMP_msg("Performing interprocedural CFG return target analysis.\n");
	bool changed;
	size_t IterationCounter = 0;
	list<SMPFunction *>::reverse_iterator RevFuncListIter;
	do {
		changed = false;
		++IterationCounter;
		for (RevFuncListIter = this->PrioritizedFuncList.rbegin(); RevFuncListIter != this->PrioritizedFuncList.rend(); ++RevFuncListIter) {
			CurrFunc = (*RevFuncListIter);
			if (NULL == CurrFunc) {
				SMP_msg("ERROR: NULL Func ptr in PrioritizedFuncList\n");
				continue;
			}
			if (CurrFunc->HasGoodRTLs()) {
				changed |= CurrFunc->ComputeReturnTargets(1 == IterationCounter);
			}
		}
	} while (changed);
	SMP_msg("Interprocedural CFG return target analysis terminated after iteration %zu\n", IterationCounter);

#if STARS_INTERPROCEDURAL_TYPE_INFERENCE
	// STEP 4B: Interprocedural type inference and propagation.
	SMP_msg("Performing interprocedural type inference.\n");
	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()) {
#else
			if (CurrFunc->StackPtrAnalysisSucceeded() && CurrFunc->HasGoodRTLs() && !CurrFunc->HasIndirectJumps()) {
#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);

	for (FuncListIter = this->PrioritizedFuncList.begin(); FuncListIter != this->PrioritizedFuncList.end(); ++FuncListIter) {
		CurrFunc = (*FuncListIter);
		if (NULL == CurrFunc) {
			continue;
		}
#if SMP_USE_SWITCH_TABLE_INFO
		if (CurrFunc->StackPtrAnalysisSucceeded() && CurrFunc->HasGoodRTLs() && !CurrFunc->HasUnresolvedIndirectJumps()) {
#else
		if (CurrFunc->StackPtrAnalysisSucceeded() && CurrFunc->HasGoodRTLs() && !CurrFunc->HasIndirectJumps()) {
#endif
			CurrFunc->GatherIncomingArgTypes();
#if ZST_SHADOW_FUNCTION_POINTERS
#if 0
			CurrFunc->TraceIncomingArgs();
#endif
#endif
		}
	}

#endif

	EndTime = time(NULL);
	TimeDiff = difftime(EndTime, StartTime);
	SMP_msg("INFO: TIME: Phase 7: ReturnTargets + InterproceduralTypes + InArgTypes + TraceInArgs: %7.2f\n", TimeDiff);

	// Free memory not needed to emit annotations, now that type inference is done.
	for (FuncListIter = this->PrioritizedFuncList.begin(); FuncListIter != this->PrioritizedFuncList.end(); ++FuncListIter) {
		CurrFunc = (*FuncListIter);
		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 loop-invariant DEFs: %lu\n", LoopInvariantDEFCount);
	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
	SMP_msg("Total safe indirect memory write instructions analyzed: %lu\n", STARS_SafeIndirectMemWriteCount);
	SMP_msg("Total unsafe indirect memory write instructions analyzed: %lu\n", STARS_UnsafeIndirectMemWriteCount);

#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(STARS_ea_t ChunkAddr, STARS_ea_t FuncHeadStart, STARS_ea_t FuncHeadEnd) {
	STARS_Function_t *CurrFunc = SMP_get_func(ChunkAddr);
	assert(NULL != CurrFunc);
	bool Unshared = CurrFunc->IsChunkUnshared(ChunkAddr, FuncHeadStart, FuncHeadEnd);

	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<STARS_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 = global_STARS_program->GetDataReferentID();
		global_STARS_program->IncrementDataReferentID();
		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, 
					"%18llx %6zu DATAREF GLOBAL %8lu %llx PARENT %s  %s RO\n",
					(unsigned long long)0, TempGlobal.size, ParentReferentID, (unsigned long long) TempGlobal.addr,
					TempGlobal.name, DataTypes[STARS_get_optype_flags0(TempGlobal.flags) >> 20]);
			}
			else {
				SMP_fprintf(AnnotFile, 
					"%18llx %6zu DATAREF GLOBAL %8lu %llx PARENT %s  %s RW\n",
					(unsigned long long)0, TempGlobal.size, ParentReferentID, (unsigned long long) TempGlobal.addr,
					TempGlobal.name, DataTypes[STARS_get_optype_flags0(TempGlobal.flags) >> 20]);
			}
		}
		else { // structured object with fields
			// Put out annotation for whole struct first
			if (TempGlobal.ReadOnly) {
				SMP_fprintf(AnnotFile, 
					"%18llx %6zu DATAREF GLOBAL %8lu %llx PARENT %s  %s RO AGGREGATE\n",
					(unsigned long long)0, TempGlobal.size, ParentReferentID, (unsigned long long) TempGlobal.addr,
					TempGlobal.name, DataTypes[STARS_get_optype_flags0(TempGlobal.flags) >> 20]);
			}
			else {
				SMP_fprintf(AnnotFile, 
					"%18llx %6zu DATAREF GLOBAL %8lu %llx PARENT %s  %s RW AGGREGATE\n",
					(unsigned long long)0, TempGlobal.size, ParentReferentID, (unsigned long long) TempGlobal.addr,
					TempGlobal.name, DataTypes[STARS_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, 
					"%18llx %6zu DATAREF GLOBAL %8lu %llx CHILDOF %lu OFFSET %zu %s + %zu FIELD",
					(unsigned long long)0, FieldSize, global_STARS_program->GetDataReferentID(), (unsigned long long) 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");
				}
				global_STARS_program->IncrementDataReferentID();
			}
		} // end if unstructured data ... else ... 
	} // end for all globals in the global var table

	return;
} // SMPProgram::EmitDataAnnotations()

bool SMPProgram::EmitProgramSPARKAda(void) {
	FILE *BodyFile = global_STARS_program->GetSPARKSourceFile(); // SPARK Ada *.adb implementation
	FILE *SpecFile = global_STARS_program->GetSPARKHeaderFile(); // SPARK Ada *.ads specification
	size_t ByteWidth = global_STARS_program->GetSTARS_ISA_Bytewidth();

	string PackageName = global_STARS_program->GetAdaPackageName();

	// Emit the package body.
	SMP_fprintf(BodyFile, "Package body %s\n", PackageName.c_str());
	SMP_fprintf(BodyFile, "with SPARK_Mode \nis\n\n");

	// Emit the package specification.
	SMP_fprintf(SpecFile, "with Interfaces;\nuse Interfaces;\nwith X86;\n\n");
	SMP_fprintf(SpecFile, "Package %s\n", PackageName.c_str());
	SMP_fprintf(SpecFile, "with SPARK_Mode \nis\n\n");
	SMP_fprintf(SpecFile, "\tsubtype Unsigned64 is X86.Unsigned64;\n");
	SMP_fprintf(SpecFile, "\tsubtype Unsigned32 is X86.Unsigned32;\n");
	SMP_fprintf(SpecFile, "\tsubtype Unsigned16 is X86.Unsigned16;\n");
	SMP_fprintf(SpecFile, "\tsubtype Unsigned8  is X86.Unsigned8;\n\n");
	SMP_fprintf(SpecFile, "\tDummy_Var : Unsigned64 := 0;\n\n");

	// Loop through all functions and perform look-ahead pre-processing needed for later annotation emission.
	map<STARS_ea_t, SMPFunction *>::iterator FuncIter;
	for (FuncIter = this->FuncMap.begin(); FuncIter != this->FuncMap.end(); ++FuncIter) {
		SMPFunction *TempFunc = FuncIter->second;
		if (TempFunc == NULL) continue;
		if (TempFunc->HasStructuredControlFlow()) {
			TempFunc->PreProcessForSPARKAdaTranslation();
		}
	} // end for all functions

	// Emit procedure specifications and bodies for library functions
	for (set<string>::iterator NameIter = this->LibraryCallTargetNames.begin(); NameIter != this->LibraryCallTargetNames.end(); ++NameIter) {
		string LibFuncName = (*NameIter);
		SMP_fprintf(SpecFile, "procedure %s with\n", LibFuncName.c_str());
		SMP_fprintf(BodyFile, "procedure %s is\nbegin\n\tX86.RSP := X86.RSP + %u;\n", LibFuncName.c_str(), ByteWidth);
		if (0 != LibFuncName.compare("setuid")) {
			// Emit minimal stub
			SMP_fprintf(SpecFile, "\tGlobal => (In_Out => X86.RSP),\n");
			SMP_fprintf(SpecFile, "\tPost => (X86.RSP = X86.RSP'Old + 8);\n\n");
		}
		else { // emit setuid stub
			SMP_fprintf(SpecFile, "\tGlobal => (Input  => (X86.RDI),\n");
			SMP_fprintf(SpecFile, "\t\tIn_Out => (Dummy_Var, X86.RSP)),\n");
			SMP_fprintf(SpecFile, "\tPre => (X86.RDI /= 0),\n");
			SMP_fprintf(SpecFile, "\tPost => ((Dummy_Var = Dummy_Var'Old + Unsigned64(X86.EDI)) and\n");
			SMP_fprintf(SpecFile, "\t\t(X86.RSP = X86.RSP'Old + 8));\n\n");
			SMP_fprintf(BodyFile, "\tDummy_Var := Dummy_Var + Unsigned64(X86.EDI);\n");
		}
		SMP_fprintf(BodyFile, "end %s;\n\n", LibFuncName.c_str());
	}

	// Loop through all functions and emit SPARK Ada for each.
	for (FuncIter = this->FuncMap.begin(); FuncIter != this->FuncMap.end(); ++FuncIter) {
		SMPFunction *TempFunc = FuncIter->second;
		if (TempFunc == NULL) continue;
		if (TempFunc->HasStructuredControlFlow()) {
			TempFunc->EmitFuncSPARKAda();
		}
	} // end for all functions

	// Wrap up the package files.
	SMP_fprintf(BodyFile, "\nend %s;\n", PackageName.c_str());
	SMP_fprintf(SpecFile, "\nend %s;\n", PackageName.c_str());

	return true;
} // end of SMPProgram::EmitProgramSPARKAda()

// 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
	time_t StartTime = time(NULL), EndTime;

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

	// Loop through all functions and emit annotations for each.
	map<STARS_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();
	} // end for all functions

#if ZST_EMIT_SPARK_ADA_TRANSLATION
	(void) this->EmitProgramSPARKAda();
#endif

	EndTime = time(NULL);
	double TimeDiff = difftime(EndTime, StartTime);
	SMP_msg("INFO: TIME: Phase 8: EmitAnnotations: %7.2f\n", TimeDiff);

#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;
	STARS_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<STARS_ea_t> CallTargets = FuncAttrib->GetCallTargets();
	for (size_t i = 0; i < CallTargets.size(); i++) {
		STARS_ea_t CallAddr = CallTargets[i];
		SMPFunction* ChildInstance = this->FindFunction(CallAddr);
		if (!ChildInstance && (STARS_BADADDR != CallAddr)) {
#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];
				SMP_strncpy(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];
				SMP_strncpy(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(global_STARS_program->GetRootFileName());
	string FileSuffix(".eh_frame_addrs");
	EHFileName += FileSuffix;
	bool mode64 = (global_STARS_program->GetSTARS_ISA_Bitwidth() == 64);

	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)) {
		STARS_ea_t ExceptionFuncAddr;
		int ReadCount;
		if (mode64)
			ReadCount = SMP_fscanf(EHAddrsFile, "%Lx", &ExceptionFuncAddr);
		else
			ReadCount = SMP_fscanf(EHAddrsFile, "%x", &ExceptionFuncAddr);

		if (1 == ReadCount) { // success
			SMPFunction *EHFunc = this->FindFunction(ExceptionFuncAddr);
			if (NULL == EHFunc) {
				SMP_msg("SERIOUS WARNING: Could not find function at eh_frame address %llx\n", (unsigned long 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<STARS_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 %llx\n", (unsigned long 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<STARS_ea_t, SMPFunction*>::iterator MapIter;
	SMPFunction *CurrFunc;
	size_t MinUnprocessedCallees = 10000; // Other than zero, what was minimum unprocessed callees.
	map<STARS_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_t) 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 (!this->FoundMutuallyRecursiveFuncs) {
			this->FoundMutuallyRecursiveFuncs = true;
			// Mark unprocessed funcs as mutually recursive. Could me more precise with program call graph analysis.
			for (MapIter = this->TempFuncMap.begin(); MapIter != this->TempFuncMap.end(); ++MapIter) {
				CurrFunc = MapIter->second;
				CurrFunc->SetIsMutuallyRecursive();
			}
		}
		if (BestMapIter != this->TempFuncMap.end()) {
			// NOTE: Experiment with using the unprocessed callees first.
			STARS_ea_t CalleeAddr = BestMapIter->second->GetFirstUnprocessedCallee();
			if (STARS_BADADDR != CalleeAddr) {
				map<STARS_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_t) CalleeAddr, (uint64_t) 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_t) CalleeAddr, (uint64_t) 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 STARS_BADADDR for callee; had to work on func at %llx\n", (uint64_t) 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<STARS_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(STARS_ea_t InstAddr, STARS_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<STARS_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()