/*
 * SMPBasicBlock.h - <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 by Zephyr Software LLC
 * e-mail: {clc,jwd}@zephyr-software.com
 * URL   : http://www.zephyr-software.com/
 *
 */

#ifndef SMPBASICBLOCK_H
#define SMPBASICBLOCK_H 1

// SMPBasicBlock.h
//
// This header defines the interfaces needed for analyzing basic blocks.

#include <list>
#include <set>
#include <string>

#include <cstddef>

#include <pro.h>
#include <ida.hpp>
#include <ua.hpp>

#include "SMPDataFlowAnalysis.h"
#include "SMPInstr.h"

using namespace std;

// We can use less memory if we don't build explicit def-use chains.
#define STARS_BUILD_DEF_USE_CHAINS 0

// Value for a block number before it is initialized.
#define SMP_BLOCKNUM_UNINIT (-1)

// Value for an SSA subscript number before it is initialized by SSA renaming.
#define SMP_SSA_UNINIT  (-1)

// Masks to set bits to use as booleans1 in SMPBasicBlock.
#define BLOCK_SET_PROCESSED 0x01
#define BLOCK_SET_INDIRECT_JUMP 0x02
#define BLOCK_SET_RETURNS 0x04
#define BLOCK_SET_SHARED_TAIL_CHUNK 0x08
#define BLOCK_SET_LIVE_IN_STALE 0x10
#define BLOCK_SET_UNREACHABLE_BLOCK 0x20
#define BLOCK_SET_FLAGS_DEAD_BEFORE_FIRST_KILL 0x40
#define BLOCK_SET_ALIASED_WRITE 0x80
#define BLOCK_RESET_PROCESSED 0xfe
#define BLOCK_RESET_INDIRECT_JUMP 0xfd
#define BLOCK_RESET_RETURNS 0xfb
#define BLOCK_RESET_SHARED_TAIL_CHUNK 0xf7
#define BLOCK_RESET_LIVE_IN_STALE 0xef
#define BLOCK_RESET_UNREACHABLE_BLOCK 0xdf
#define BLOCK_RESET_FLAGS_DEAD_BEFORE_FIRST_KILL 0xbf
#define BLOCK_RESET_ALIASED_WRITE 0x7f

// Masks to set bits to use as booleans2 in SMPBasicBlock.
#define BLOCK_SET_REACHES_OUT_STALE 0x01
#define BLOCK_SET_LOOP_TAIL_BLOCK 0x02
#define BLOCK_SET_LOOP_HEADER_BLOCK 0x04
#define BLOCK_SET_CALLS_UNSIGNED_ARG_FUNC 0x08
#define BLOCK_SET_SCCP_VISITED 0x10
#define BLOCK_SET_UNUSED6 0x20
#define BLOCK_SET_UNUSED7 0x40
#define BLOCK_SET_UNUSED8 0x80
#define BLOCK_RESET_REACHES_OUT_STALE 0xfe
#define BLOCK_RESET_LOOP_TAIL_BLOCK 0xfd
#define BLOCK_RESET_LOOP_HEADER_BLOCK 0xfb
#define BLOCK_RESET_CALLS_UNSIGNED_ARG_FUNC 0xf7
#define BLOCK_RESET_SCCP_VISITED 0xef
#define BLOCK_RESET_UNUSED6 0xdf
#define BLOCK_RESET_UNUSED7 0xbf
#define BLOCK_RESET_UNUSED8 0x7f

// Class defining basic blocks.
class SMPBasicBlock {
public:
	// Constructors
	SMPBasicBlock(SMPFunction *Func, list<SMPInstr *>::iterator FirstInstr, list<SMPInstr *>::iterator LastInstr);

	// Operators
	int operator==(const SMPBasicBlock &rhs) const;

	// Get methods
	ea_t GetFirstAddr(void) const;
	inline int GetNumber(void) const { return BlockNum; };
	inline SMPBasicBlock *GetThisBlock(void) { return this; };
	inline SMPFunction *GetFunc(void) { return MyFunc; };
#if 0
	inline sval_t GetIncomingStackPtrDelta(void) const { return IncomingStackPtrDelta; };
#endif
	inline vector<SMPInstr *>::iterator GetFirstInst(void) { return InstVec.begin(); };
	inline vector<SMPInstr *>::iterator GetLastInst(void) { return InstVec.end(); };
	inline vector<SMPInstr *>::reverse_iterator GetRevInstBegin(void) { return InstVec.rbegin(); };
	inline vector<SMPInstr *>::reverse_iterator GetRevInstEnd(void) { return InstVec.rend(); }
	inline list<SMPBasicBlock *>::iterator GetFirstPred(void) {
		return Predecessors.begin();
	};
	inline list<SMPBasicBlock *>::iterator GetLastPred(void) {
		return Predecessors.end();
	};
	inline list<SMPBasicBlock *>::iterator GetFirstSucc(void) {
		return Successors.begin();
	};
	inline list<SMPBasicBlock *>::iterator GetLastSucc(void) {
		return Successors.end();
	};
	list<SMPBasicBlock *>::iterator GetFallThroughSucc(void); // Search successors for fall-through block, if any
	inline size_t GetNumPreds(void) const { return Predecessors.size(); };
	inline size_t GetNumSuccessors(void) const { return Successors.size(); };
	inline int GetLoopHeaderNumber(void) const { return LoopHeaderNumber; };
	size_t GetBlockSize(void); // returns size in bytes
	set<op_t, LessOp>::iterator GetFirstLiveIn(void); // LiveInSet.begin()
	set<op_t, LessOp>::iterator GetLastLiveIn(void); // LiveInSet.end()
	set<op_t, LessOp>::iterator GetFirstLiveOut(void); // LiveOutSet.begin()
	set<op_t, LessOp>::iterator GetLastLiveOut(void); // LiveOutSet.end()
	set<op_t, LessOp>::iterator GetFirstVarKill(void); // KillSet.begin()
	set<op_t, LessOp>::iterator GetLastVarKill(void); // KillSet.end()
	set<op_t, LessOp>::iterator GetFirstUpExposed(void); // UpExposedSet.begin()
	set<op_t, LessOp>::iterator GetLastUpExposed(void); // UpExposedSet.end()
	inline size_t GetUpExposedSetSize(void) const { return UpExposedSet.size(); };
	inline set<pair<op_t, ea_t>, LessDefinition>::iterator GetFirstReachesIn(void) { return ReachesInSet.begin(); };
	inline set<pair<op_t, ea_t>, LessDefinition>::iterator GetLastReachesIn(void) { return ReachesInSet.end(); };
	inline set<pair<op_t, ea_t>, LessDefinition>::iterator GetFirstReachesOut(void) { return ReachesOutSet.begin(); };
	inline set<pair<op_t, ea_t>, LessDefinition>::iterator GetLastReachesOut(void) { return ReachesOutSet.end(); };
	inline set<pair<op_t, ea_t>, LessDefinition>::iterator GetFirstDownExposedDefn(void) { return DownExposedDefnSet.begin(); };
	inline set<pair<op_t, ea_t>, LessDefinition>::iterator GetLastDownExposedDefn(void) { return DownExposedDefnSet.end(); };
	set<op_t, LessOp>::iterator GetFirstLocalName(void); // LocalNames.begin()
	set<op_t, LessOp>::iterator GetLastLocalName(void); // LocalNames.end()
	set<int>::iterator GetFirstDomFrontier(void); // DomFrontier.begin()
	set<int>::iterator GetLastDomFrontier(void); // DomFrontier.end()
	set<SMPPhiFunction, LessPhi>::iterator GetFirstPhi(void); // PhiFunctions.begin()
	set<SMPPhiFunction, LessPhi>::iterator GetLastPhi(void); // PhiFunctions.end()
	int GetPredPosition(int BlockNum); // What is position # within Preds of BlockNum?
	set<SMPPhiFunction, LessPhi>::iterator FindPhi(op_t FindOp);
	set<op_t, LessOp>::iterator FindLocalName(op_t FindOp);
	inline map<int, struct STARS_SCCP_Const_Struct>::iterator FindLocalConstValue(int DefHashValue) { return ConstantLocalDefs.find(DefHashValue); };
	inline map<int, struct STARS_SCCP_Const_Struct>::iterator GetLastLocalConstValueIter(void) { return ConstantLocalDefs.end(); };
#if 0
	// Given a USE operand and the address of its instr, return DEF from DU chains or Phi func.
	set<DefOrUse, LessDefUse>::iterator GetDefFromOpAddr(op_t UseOp, ea_t InstAddr, int SSANum);
#endif
	set<DefOrUse, LessDefUse>::iterator GetGlobalDefIterFromDefAddr(op_t DefOp, ea_t DefAddr);
	ea_t GetDefAddrFromUseAddr(op_t UseOp, ea_t InstAddr, int SSANum, bool LocalName); // return DefAddr, block # for Phi Defs, or UpExposed address.
	ea_t GetUltimateDefAddr(op_t UseOp, ea_t InstAddr, int SSANum, bool LocalName); // trace into predecessors if necessary

	bool IsOpDestTruncatedWrite(op_t DefOp, int DefSSANum, ea_t DefAddr); // Does DefOp get written out in truncated form (lower bits only)?
	SMPInstr *FindInstr(ea_t InstAddr);
	vector<SMPInstr *>::iterator GetInstIterFromAddr(ea_t InstAddr);
	inline SMPInstr *GetInstFromIndex(size_t VecIndex) const { return InstVec.at(VecIndex); };
	size_t GetIndexFromInstAddr(ea_t InstAddr) const; // Get the InstVec index for the instruction at InstAddr. Assert if not found.
	inline sval_t GetOutgoingStackDelta(void) const { return OutgoingStackDelta; };

	// Six methods to get values from the maps of local reg/SSA to FG info.
	//  For global names, see corresponding methods in SMPFunction.
	unsigned short GetDefSignMiscInfo(int DefHashValue);
	unsigned short GetUseSignMiscInfo(int UseHashValue);
	unsigned short GetDefWidthTypeInfo(int DefHashValue);
	unsigned short GetUseWidthTypeInfo(int UseHashValue);
	struct FineGrainedInfo GetDefFGInfo(int DefHashValue);
	struct FineGrainedInfo GetUseFGInfo(int UseHashValue);

	// Set methods
#if 0
	inline void SetIncomingStackPtrDelta(sval_t delta) { IncomingStackPtrDelta = delta; };
#endif
	inline void SetProcessed(bool flag) { flag ? (booleans1 |= BLOCK_SET_PROCESSED) : (booleans1 &= BLOCK_RESET_PROCESSED); };
	inline void SetMaybeAliased(bool flag) { flag ? (booleans1 |= BLOCK_SET_ALIASED_WRITE) : (booleans1 &= BLOCK_RESET_ALIASED_WRITE); };
	inline void SetIndirectJump(bool flag) { flag ? (booleans1 |= BLOCK_SET_INDIRECT_JUMP) : (booleans1 &= BLOCK_RESET_INDIRECT_JUMP); };
	inline void SetReturns(bool flag) { flag ? (booleans1 |= BLOCK_SET_RETURNS) : (booleans1 &= BLOCK_RESET_RETURNS); };
	inline void SetShared(void) { booleans1 |= BLOCK_SET_SHARED_TAIL_CHUNK; };
	inline void ResetShared(void) { booleans1 &= BLOCK_RESET_SHARED_TAIL_CHUNK; };
	inline void SetLiveInStale(bool flag) { flag ? (booleans1 |= BLOCK_SET_LIVE_IN_STALE) : (booleans1 &= BLOCK_RESET_LIVE_IN_STALE); };
	inline void SetUnreachableBlock(bool flag) { flag ? (booleans1 |= BLOCK_SET_UNREACHABLE_BLOCK) : (booleans1 &= BLOCK_RESET_UNREACHABLE_BLOCK); };
	inline void SetFlagsDeadBeforeFirstKill(bool flag) { flag ? (booleans1 |= BLOCK_SET_FLAGS_DEAD_BEFORE_FIRST_KILL) : (booleans1 &= BLOCK_RESET_FLAGS_DEAD_BEFORE_FIRST_KILL); };
	inline void SetReachesOutStale(void) { booleans2 |= BLOCK_SET_REACHES_OUT_STALE; };
	inline void SetLoopHeaderBlock(void) { booleans2 |= BLOCK_SET_LOOP_HEADER_BLOCK; };
	inline void SetCallsUnsignedArgFunc(void) { booleans2 |= BLOCK_SET_CALLS_UNSIGNED_ARG_FUNC; };
	inline void SetSCCPVisited(bool flag) { flag ? (booleans2 |= BLOCK_SET_SCCP_VISITED) : (booleans2 &= BLOCK_RESET_SCCP_VISITED); };
	inline void SetNumber(int Num) { BlockNum = Num; };
	inline void SetOutgoingStackDelta(sval_t OutDelta) { OutgoingStackDelta = OutDelta; };
	void LinkToPred(SMPBasicBlock *Predecessor);
	void LinkToSucc(SMPBasicBlock *Successor);
	inline void AddLiveIn(op_t LiveOp) { LiveInSet.insert(LiveOp); };
	inline void AddLiveOut(op_t LiveOp) { LiveOutSet.insert(LiveOp); };
	inline void AddVarKill(op_t KillOp) { KillSet.insert(KillOp); };
	inline void AddUpExposed(op_t UseOp) { UpExposedSet.insert(UseOp); };
	void AddReachesIn(pair<op_t, ea_t> ReachInDefn);
	void AddReachesOut(pair<op_t, ea_t> ReachOutDefn);
	inline void AddDownExposedDefn(pair<op_t, ea_t> DEDefn) { DownExposedDefnSet.insert(DEDefn); };
	bool ErasePhi(op_t OldOp); // erase() from phi function list
	void ErasePred(ea_t FirstAddr); // erase() block starting at FirstAddr from Preds list
	void EraseSucc(ea_t FirstAddr); // erase() block starting at FirstAddr from Successors list
	bool AddPhi(SMPPhiFunction NewPhi);
	bool SetPhiDefSSA(op_t DefOp, int SSANum);
	bool SetPhiUseSSA(op_t UseOp, size_t index, int SSANum);
	set<SMPPhiFunction, LessPhi>::iterator SetPhiDefType(op_t DefOp, SMPOperandType Type);
	bool SetPhiUseType(op_t DefOp, size_t index, SMPOperandType Type);
	set<SMPPhiFunction, LessPhi>::iterator SetPhiDefMetadata(op_t DefOp, SMPMetadataType Status);
	map<int, struct STARS_SCCP_Const_Struct>::iterator InsertLocalConstValue(int DefHashValue, struct STARS_SCCP_Const_Struct NewConstEntry); 
		// Insert SCCP value for local name; change if already found.

	// Six methods to set values into the maps of local reg/SSA to FG info.
	//  For global names, see corresponding methods in SMPFunction.
	void UpdateDefSignMiscInfo(int DefHashValue, unsigned short NewInfo);
	void UpdateUseSignMiscInfo(int UseHashValue, unsigned short NewInfo);
	void UpdateDefWidthTypeInfo(int DefHashValue, unsigned short NewInfo);
	void UpdateUseWidthTypeInfo(int UseHashValue, unsigned short NewInfo);
	void UpdateDefFGInfo(int DefHashValue, struct FineGrainedInfo NewFG);
	void UpdateUseFGInfo(int UseHashValue, struct FineGrainedInfo NewFG);

	void ClearDefSignedness(int DefHashValue);

	// Query methods
	inline bool IsProcessed(void) const { return (booleans1 & BLOCK_SET_PROCESSED); };
	inline bool HasIndirectJump(void) const { return (booleans1 & BLOCK_SET_INDIRECT_JUMP); };
	inline bool HasReturn(void) const { return (booleans1 & BLOCK_SET_RETURNS); };
	inline bool IsShared(void) const { return (booleans1 & BLOCK_SET_SHARED_TAIL_CHUNK); };
	inline bool IsLiveInStale(void) const { return (booleans1 & BLOCK_SET_LIVE_IN_STALE); };
	inline bool IsUnreachableBlock(void) const { return (booleans1 & BLOCK_SET_UNREACHABLE_BLOCK); };
#if 0
	inline bool AreFlagsDeadAfterLastUse(void) const { return (booleans1 & BLOCK_SET_FLAGS_DEAD_AFTER_LAST_USE); };
#endif
	inline bool AreFlagsDeadBeforeFirstKill(void) const { return (booleans1 & BLOCK_SET_FLAGS_DEAD_BEFORE_FIRST_KILL); };
	bool AllNops(void); // Are all instructions in the block no-ops?
	inline bool MaybeAliasedWrite(void) const { return (booleans1 & BLOCK_SET_ALIASED_WRITE); };
	inline bool IsReachesOutStale(void) const { return (booleans2 & BLOCK_SET_REACHES_OUT_STALE); };
	inline bool IsLoopTailBlock(void) const { return (booleans2 & BLOCK_SET_LOOP_TAIL_BLOCK); };
	inline bool IsLoopHeaderBlock(void) const { return (booleans2 & BLOCK_SET_LOOP_HEADER_BLOCK); };
	inline bool CallsUnsignedArgFunc(void) const { return (booleans2 & BLOCK_SET_CALLS_UNSIGNED_ARG_FUNC); };
	inline bool IsSCCPVisited(void) const { return (booleans2 & BLOCK_SET_SCCP_VISITED); };
	inline bool IsSelfLoop(void) const { return (IsLoopHeaderBlock() && (GetNumber() == GetLoopHeaderNumber())); };
	inline bool IsLiveIn(op_t CurrOp) const {
		return (LiveInSet.end() != LiveInSet.find(CurrOp));
	}
	inline bool IsLiveOut(op_t CurrOp) const {
		return (LiveOutSet.end() != LiveOutSet.find(CurrOp));
	}
	inline bool IsUpExposed(op_t CurrOp) const {
		return (UpExposedSet.end() != UpExposedSet.find(CurrOp));
	}
	inline bool IsVarKill(op_t CurrOp) const {
		return (KillSet.end() != KillSet.find(CurrOp));
	}
	bool MDAlreadyKilled(op_t) const; // Was op_t killed by something already in KillSet?
	inline bool IsReachesIn(pair<op_t, ea_t> CurrDefn) const {
		return (ReachesInSet.end() != ReachesInSet.find(CurrDefn));
	}
	inline bool IsReachesOut(pair<op_t, ea_t> CurrDefn) const {
		return (ReachesOutSet.end() != ReachesOutSet.find(CurrDefn));
	}
	inline bool IsDownExposedDefn(pair<op_t, ea_t> CurrDefn) const {
		return (DownExposedDefnSet.end() != DownExposedDefnSet.find(CurrDefn));
	}
	bool IsLocalName(op_t CurrOp) const;
#if STARS_BUILD_DEF_USE_CHAINS
	bool HasGlobalDUChain(op_t DefOp, ea_t DefAddr); // Any global DU chains for DefOp?
	bool IsGlobalReferenced(unsigned int DUIndex); // Any USEs or DEFs for global with DUIndex?
#endif
	bool HasCallInstruction(void); // true if function call instruction is present
	bool HasIndirJumpInstruction(void); // true if indirect jump instruction is present
	bool HasConditionalBranch(void); // true if (last) instruction is conditional branch

	// Printing methods
	void Dump(void);

	// Analysis methods
	bool AllPredecessorsNumbered(void);
	void DepthFirstMark(void); // Depth-first traversal, mark as processed
	ea_t GetUltimateOperandSource(ea_t UseAddr, op_t UseOp, int UseSSANum); // trace through move and Phi defs to some defining operation.
	void Analyze();
	void InitKilledExposed(bool UseFP); // Initialize KilledSet and UpExposedSet
	bool UpdateLiveOut(void); // Iterate once on updating LiveOutSet; return true if changed
	void SetLiveOutSSANums(void); // Set the SSA numbers for the DEFs in the LiveOut set.
	void AddToDomFrontier(int); // Add RPO block number to DomFrontier set.
	void SetLocalNames(void); // Fill the LocalNames member set
	void SSALocalRenumber(void); // Renumber references to local names
#if STARS_BUILD_DEF_USE_CHAINS
	void CreateGlobalChains(void); // Create DEF-USE chains for global names used here
#endif
	bool FindLoopHeadsAndTails(void); // Determine if block is loop tail, also set loop header flag for dominating back-edge successor; return false otherwise
	void FreeReachingDefsMemory(void); // Free memory for reaching defs sets after they are no longer needed
	void FreeSSAMemory(void); // After SSA #s are in DEFs and USEs, free SSA data structures.
	void FreeUnusedMemory4(void); // After loop 4 (type inference) in SMPProgram::Analyze(), free memory
#if STARS_BUILD_DEF_USE_CHAINS
	size_t GetNumDUChains(bool GlobalName) const; // Return total number of global or local DU chains, depending on GlobalName.
	size_t GetNumLocalChains(unsigned int RegIndex, bool GlobalName) const; // number of DU chains for RegIndex in this block
	size_t GetNumLocalUses(unsigned int RegIndex, size_t ChainIndex, bool GlobalName) const; // number of uses for RegIndex in ChainIndex in this block
	ea_t GetFirstDefAddr(unsigned int RegIndex, size_t ChainIndex, bool GlobalName) const; // DefAddr of DU chain #ChainIndex for RegIndex in block
	ea_t GetLastUseAddr(unsigned int RegIndex, size_t ChainIndex, bool GlobalName) const; // Last Use of RegIndex/ChainIndex in block
	ea_t GetDUChainUse(unsigned int NameIndex, int SSANum, size_t UseIndex, bool GlobalName) const; //fetch USE addr #UseIndex from DU chain.
	op_t GetDUName(unsigned int NameIndex, bool GlobalName); // Get global or local name for DU chain for NameIndex
	void SetIndWrite(unsigned int NameIndex, size_t ChainIndex, bool GlobalName, bool FlagValue);
#endif
	bool IsGlobalNameUsedLiveIn(op_t GlobalOp); // Is GlobalOp used as a LiveIn value anywhere in this block, including as a Phi USE?
	bool IsGlobalRegDead(ea_t InstAddr, op_t Operand, unsigned int RegIndex); // Is global reg dead at InstAddr?
	bool IsRegDead(ea_t InstAddr, uint16 RegNo); // Is local reg dead at InstAddr?
	void MarkDeadRegs(void); // Find dead registers for each mmStrata-instrumented instruction
	bool IsDefDead(ea_t DefAddr, op_t DefOp); // Does DefOp at DefAddr never get used?
	bool IsDefInvolvedInAddition(ea_t DefAddr, op_t DefOp, ea_t &AdditionAddr); // true if DefOp at DefAddr is used in or redefined by addition; pass back AdditionAddr
	bool DoesDefReachBlockEnd(ea_t DefAddr, op_t DefOp, int DefSSANum, set<int> &NonEscapingRegisterHashes); // Does value of DefOp/DefSSANum reach block end in any DEF at all?
	bool IsDefOnlyUsedAsAddressReg(ea_t DefAddr, op_t DefOp, size_t LoopNum, size_t &AddrUseCounter, SMPOperandType &MemType); // DefOp/DefSSANum is only used in LoopNum (outside of DefAddr) as address reg or Phi USE
	bool PropagateLocalDefType(op_t DefOp, SMPOperandType DefType, ea_t DefAddr, int SSANum, bool IsMemOp); // to all uses
	bool InferLocalDefType(op_t DefOp, unsigned int LocIndex, ea_t DefAddr); // Can DEF type be inferred from all USEs?
	void InferGlobalDefType(op_t DefOp, int SSANum, ea_t DefAddr, bool &FoundNumeric, bool &FoundPointer,
		bool &FoundUnknown, bool &FoundUninit, SMPOperandType &PtrType);  // Can DEF type be inferred from all USEs? Recursive helper for SMPFunction::InferGlobal...
	bool PropagateGlobalDefType(op_t DefOp, SMPOperandType DefType, int SSANum, bool IsMemOp); // to all uses
	bool InferAllPhiDefTypes(void); // infer, propagate to all uses
	bool PropagateLocalMetadata(op_t UseOp, SMPMetadataType Status, int SSANum, ea_t UseAddr);
	bool FindRedundantLocalMetadata(bool SafeFunc); // consecutive DEFs, same type => redundant
#if STARS_BUILD_DEF_USE_CHAINS
	void MarkIndWriteChains(ea_t InstAddr); // Mark chains that include the indirect mem write addr
	bool GetLocalDUChainIndWrite(op_t DefOp, int SSANum); // Get IndWrite flag for DefOp chain
	bool GetGlobalDUChainIndWrite(op_t DefOp, ea_t DefAddr); // Get IndWrite flag for DefOp chain
	bool IsLastGlobalChain(op_t DefOp, ea_t DefAddr); // DU-chain is last one for global DefOp
#endif
	bool HasUseAfterIndWrite(op_t MemDefOp, vector<SMPInstr *>::iterator InstIter, bool &IndWriteSeen, bool &ReDef); // MemDefOp starting at InstIter has DU chain overlapping an indirect mem write
	void MarkBranchSignedness(void); // If branch at block end is signed/unsigned, propagate to operands that set flags before it.
	void PropagatePhiFGInfo(void);
	void PropagateBranchSignedness(ea_t DefAddr, op_t SearchOp, unsigned short SignMask);
	bool PropagateDEFSignedness(void); // propagate DEF signedness to USE if USE has no signedness info.
	void MarkUnsignedArgs(ea_t CallAddr, unsigned int ArgPosBits); // backtrack from CallAddr and mark unsigned args based on bitset
	bool ComputeReachesInSet(void); // return true if changes were made to the ReachesInSet
	bool ComputeReachesOutSet(void); // return true if changes were made to the ReachesOutSet
	void UpdateDownExposedDefs(op_t DefOp, ea_t InstAddr); // Add DefOp, remove previous defs of DefOp that now do not reach the end of the block.

	void SCCPEvaluateConstants(enum STARSBranchConst &BranchEval, list<pair<int, int> > &CFGWorkList, list<pair<int, int> > &SSAWorkList); // Evaluate constants for all instructions as part of SCCP algorithm at SMPFunction level.
	void SCCPGlobalPropagationHelper(op_t GlobalOp, int DefSSANum, vector<STARSBitSet> ExecutedEdgeBitSet, list<pair<int, int> > &CFGWorkList, list<pair<int, int> > &SSAWorkList); // Propagate GlobalOp/DefSSANum const value
	void SCCPHandleSuccessors(enum STARSBranchConst &BranchEval, list<pair<int, int> > &CFGWorkList); // Based on BranchEval, push successors onto CFGWorkList
	void SCCPNullifyUnreachableBlock(void); // Patch binary to make this block into nops.
	void SCCPGatherStatistics(void); // Gather statistics on SCCP effectiveness

	// Find the stack target of a call to memset() and the size in bytes of the memset() region.
	//  If the memset() target is not on the stack, or the size is not a constant, return false.
	bool AnalyzeMemSet(ea_t MemSetAddr, op_t &MemSetTarget, size_t &MemSetSize, int &SignedOffset, bool &FPRelativeTarget);
	
	bool IsInfiniteSelfLoop(void); // return true if block loops infinitely to itself
	bool IsBenignOverflowDEF(op_t DefOp, int DefSSANum, size_t DefAddr, bool UnderflowOpcode, int &IdiomCode); // Do we not care if DEF overflowed, due to how it is used?
	bool IsDEFWrittenWithTruncation(op_t DefOp, int DefSSANum, ea_t DefAddr, ea_t TruncAddr, bool PhiDEF); // Is subword of DefOp written later, before TruncAddr?
	bool IsBenignTruncationDEF(op_t DefOp, int DefSSANum, size_t DefAddr, int &IdiomCode); // Do we not care if DEF overflowed, due to how it is used?
	bool IsDefMasked(op_t DefOp, int DefSSANum, ea_t DefAddr); // Does DefOp+DefSSANum get subreg masked before it gets re-DEFined?
	bool IsCriticalSink(op_t DefOp, int DefSSANum, string &SinkString); // What is ultimate use of DEF that might have integer error?
	bool IsStackOpNextUsedWithSignedness(op_t StackDefOp, ea_t DefAddr, int SSANum); // Is next use of stack DEF a sign- or zero-extended load?
	void SuppressAnnotOnSignChangingAddition(op_t DefOp, int DefSSANum, size_t DefAddr); // Find inc/add that makes small negative back into positive
	void AnalyzePrepForNumericAnnotations(void); // Last-minute prep before emitting numeric annotations

	sval_t ComputeStackAdjustmentAfterCall(ea_t CallAddr); // find stack pointer adjustment code after call, return stack delta or zero

private:
	// Data
	ea_t FirstAddr;
	int BlockNum;  // Number for block ordering algorithms
	int LoopHeaderNumber; // Number of block that is loop header for this block
	SMPFunction *MyFunc; // function containing this block
	sval_t OutgoingStackDelta; // Incoming stack ptr delta for all successor blocks
#if 0
	sval_t IncomingStackPtrDelta; // Incoming stack pointer delta for this block
#endif
	unsigned char booleans1; // hold bools as bits
#if 0  // now in booleans1
	bool Processed; // Set to true to prevent infinite recursions in CFG traversals

	// cached query results
	bool IndirectJump; // contains an indirect jump instruction
	bool Returns;      // contains a return instruction
	bool SharedTailChunk; // is part of a code chunk shared among functions
	bool IsLiveInStale; // Has LiveOutSet changed since LiveInSet was computed?
	bool FlagsDeadAfterLastUse; // flags global, dead after last use in the block
	bool FlagsDeadBeforeFirstKill; // flags global, dead before first DEF in block
	bool AliasedWrite; // A memory write in the block may be aliased by other writes
#endif
	unsigned char booleans2; // hold bools as bits
#if 0 // now in booleans2
	bool ReachesOutStale; // ReachesIn has been updated since last ReachesOut update
	bool LoopTailBlock; // block has back edge to loop header block
#endif

	vector<SMPInstr *> InstVec; //NOTE: Copies of pointers from SMPFunction::Instrs.
	map<ea_t, size_t> AddrInstMap; // map InstAddr to InstVec index.
	list<SMPBasicBlock *> Predecessors;
	list<SMPBasicBlock *> Successors;
		// Four sets used in live variable analysis
	set<op_t, LessOp> KillSet;   // variables killed in this block
	set<op_t, LessOp> UpExposedSet; // upward exposed variables in this block
	set<op_t, LessOp> LiveOutSet; // Live-Out variables in this block
	set<op_t, LessOp> LiveInSet; // contribution to predecessor's live-out iteration
		// Three sets used in reaching definitions analysis
	set<pair<op_t, ea_t>, LessDefinition> ReachesInSet; // definitions live on entry to block
	set<pair<op_t, ea_t>, LessDefinition> ReachesOutSet; // definitions live on exit from block, either passing through or DEFed inside block
	set<pair<op_t, ea_t>, LessDefinition> DownExposedDefnSet; // definitions within block that are live on exit
		// SSA data structures
	set<int> DomFrontier; // Dominance frontier for block, as set of RPO block numbers
	set<SMPPhiFunction, LessPhi> PhiFunctions; // SSA incoming edge phi functions
	set<op_t, LessOp> LocalNames; // non-global names referenced in this block
#if STARS_BUILD_DEF_USE_CHAINS
	SMPCompleteDUChains LocalDUChains; // def-use chains for local names
	SMPCompleteDUChains GlobalDUChains; // def-use chains for global names
		// NOTE: The GlobalChains.ChainsByName.at(GlobalIndex).DUChains are indexed
		//  starting at zero. The indices into the DUChains have nothing to do
		//  with the SSA Numbers, unlike the LocalDUChains.
#endif

	map<int, struct FineGrainedInfo> LocalDefFGInfoBySSA; // map hash of local name & SSANum to DEF FG info.
		// NOTE: We are currently limiting this map to registers, not all local names.

	map<int, struct FineGrainedInfo> LocalUseFGInfoBySSA; // map hash of local name & SSANum to USE FG info.
		// NOTE: We are currently limiting this map to registers, not all local names.

	map<int, struct STARS_SCCP_Const_Struct> ConstantLocalDefs; // map hash of local name & SSANum to constant value from SCCP.
		// NOTE: We are currently limiting this map to registers, not all local names. 

	// Methods
	inline void ResetReachesOutStale(void) { booleans2 &= BLOCK_RESET_REACHES_OUT_STALE; };
	inline void SetLoopTailBlock(void) { booleans2 |= BLOCK_SET_LOOP_TAIL_BLOCK; };
	set<SMPPhiFunction, LessPhi>::iterator InferPhiDefType(set<SMPPhiFunction, LessPhi>::iterator DefPhi, bool &changed); // infer, propagate to all uses
	unsigned int GetLocalDUIndex(op_t DefOp, int SSANum);
	unsigned int GetGlobalDUIndex(op_t DefOp, ea_t DefAddr);
	bool UseHasCriticalSink(op_t DefOp, int DefSSANum, op_t DefOp2, int DefSSANum2, string &SinkString); // DefOp or DefOp2 is passed as arg to critical system or lib call
	bool IsBranchSignednessUnreliable(void); // Is branch signedness misleading due to odd code generation idiom or hand coding?
}; 

#endif