Andersens.cpp File Reference

#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Instructions.h"
#include "llvm/Module.h"
#include "llvm/Pass.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/InstIterator.h"
#include "llvm/Support/InstVisitor.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/Passes.h"
#include "llvm/Support/Debug.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/SparseBitVector.h"
#include "llvm/ADT/DenseSet.h"
#include <algorithm>
#include <set>
#include <list>
#include <map>
#include <stack>
#include <vector>
#include <queue>

Include dependency graph for Andersens.cpp:

Go to the source code of this file.

Defines
#define	DEBUG_TYPE   "anders-aa"
#define	FULL_UNIVERSAL   0
#define	DEBUG_TYPE   "anders-aa-constraints"
#define	DEBUG_TYPE   "anders-aa"
#define	DEBUG_TYPE   "anders-aa-renumber"
#define	DEBUG_TYPE   "anders-aa"
#define	DEBUG_TYPE   "anders-aa-labels"
#define	DEBUG_TYPE   "anders-aa"
#define	DEBUG_TYPE   "anders-aa-labels"
#define	DEBUG_TYPE   "anders-aa"
#define	DEBUG_TYPE   "anders-aa-constraints"
#define	DEBUG_TYPE   "anders-aa"
Functions
	STATISTIC (NumIters,"Number of iterations to reach convergence")
	STATISTIC (NumConstraints,"Number of constraints")
	STATISTIC (NumNodes,"Number of nodes")
	STATISTIC (NumUnified,"Number of variables unified")
	STATISTIC (NumErased,"Number of redundant constraints erased")
ModulePass *	llvm::createAndersensPass ()
void	dumpToDOUT (SparseBitVector<> *bitmap)
Variables
static const unsigned	SelfRep = (unsigned)-1
static const unsigned	Unvisited = (unsigned)-1
static const unsigned	CallReturnPos = 1
static const unsigned	CallFirstArgPos = 2
static RegisterPass< Andersens >	X ("anders-aa","Andersen's Interprocedural Alias Analysis", false, true)
static RegisterAnalysisGroup < AliasAnalysis >	Y (X)

---

Define Documentation

#define DEBUG_TYPE   "anders-aa"

Definition at line 56 of file Andersens.cpp.

#define DEBUG_TYPE   "anders-aa-constraints"

Definition at line 56 of file Andersens.cpp.

#define DEBUG_TYPE   "anders-aa"

Definition at line 56 of file Andersens.cpp.

#define DEBUG_TYPE   "anders-aa-labels"

Definition at line 56 of file Andersens.cpp.

#define DEBUG_TYPE   "anders-aa"

Definition at line 56 of file Andersens.cpp.

#define DEBUG_TYPE   "anders-aa-labels"

Definition at line 56 of file Andersens.cpp.

#define DEBUG_TYPE   "anders-aa"

Definition at line 56 of file Andersens.cpp.

#define DEBUG_TYPE   "anders-aa-renumber"

Definition at line 56 of file Andersens.cpp.

#define DEBUG_TYPE   "anders-aa"

Definition at line 56 of file Andersens.cpp.

#define DEBUG_TYPE   "anders-aa-constraints"

Definition at line 56 of file Andersens.cpp.

#define DEBUG_TYPE   "anders-aa"

Definition at line 56 of file Andersens.cpp.

#define FULL_UNIVERSAL   0

Definition at line 83 of file Andersens.cpp.

---

Function Documentation

void dumpToDOUT

(

SparseBitVector<> *

bitmap

)

Definition at line 1396 of file Andersens.cpp.

References DOUT, and llvm::dump().

STATISTIC	(	NumErased	,
		"Number of redundant constraints erased"
	)

STATISTIC	(	NumUnified	,
		"Number of variables unified"
	)

STATISTIC	(	NumNodes	,
		"Number of nodes"
	)

STATISTIC	(	NumConstraints	,
		"Number of constraints"
	)

STATISTIC	(	NumIters	,
		"Number of iterations to reach convergence"
	)

---

Variable Documentation

bool AddressTaken

Definition at line 241 of file Andersens.cpp.

const unsigned CallFirstArgPos = 2 [static]

Definition at line 97 of file Andersens.cpp.

const unsigned CallReturnPos = 1 [static]

Definition at line 95 of file Andersens.cpp.

std::vector<Constraint> Constraints

Constraints - This vector contains a list of all of the constraints identified by the program.

Definition at line 220 of file Andersens.cpp.

Referenced by llvm::X86TargetAsmInfo< BaseTAI >::ExpandInlineAsm(), llvm::TargetInstrDesc::getOperandConstraint(), and IsOperandAMemoryOperand().

unsigned Counter [static]

Definition at line 213 of file Andersens.cpp.

Referenced by llvm::ProfileInfoLoader::getBlockCounts(), llvm::ProfileInfoLoader::getEdgeCounts(), llvm::ProfileInfoLoader::getFunctionCounts(), and llvm::AsmPrinter::PrintSpecial().

WorkList* CurrWL

Definition at line 395 of file Andersens.cpp.

unsigned Dest

Definition at line 139 of file Andersens.cpp.

Referenced by llvm::X86InstrInfo::convertToThreeAddress(), CreateArgv(), executeFCMP_OEQ(), executeFCMP_OGE(), executeFCMP_OGT(), executeFCMP_OLE(), executeFCMP_OLT(), executeFCMP_ONE(), executeFCMP_ORD(), executeFCMP_UEQ(), executeFCMP_UGE(), executeFCMP_UGT(), executeFCMP_ULE(), executeFCMP_ULT(), executeFCMP_UNE(), executeFCMP_UNO(), executeICMP_EQ(), executeICMP_NE(), executeICMP_SGE(), executeICMP_SGT(), executeICMP_SLE(), executeICMP_SLT(), executeICMP_UGE(), executeICMP_UGT(), executeICMP_ULE(), executeICMP_ULT(), llvm::isCriticalEdge(), llvm::PIC16TargetLowering::LowerBR_CC(), LowerBR_CC(), LowerCALL(), SplitEdgeNicely(), llvm::ExecutionEngine::StoreValueToMemory(), llvm::UnrollLoop(), llvm::Interpreter::visitBranchInst(), and llvm::Interpreter::visitSwitchInst().

unsigned DFSNumber

Definition at line 391 of file Andersens.cpp.

bool Direct

Definition at line 236 of file Andersens.cpp.

SparseBitVector* Edges

Definition at line 217 of file Andersens.cpp.

unsigned FirstAdrNode

Definition at line 411 of file Andersens.cpp.

unsigned FirstRefNode

Definition at line 408 of file Andersens.cpp.

std::vector<Node> GraphNodes

GraphNodes - This vector is populated as part of the object identification stage of the analysis, which populates this vector with a node for each memory object and fills in the ValueNodes map.

Definition at line 343 of file Andersens.cpp.

std::vector<unsigned> HCDSCCRep

Definition at line 425 of file Andersens.cpp.

char ID [static]

Definition at line 433 of file Andersens.cpp.

SparseBitVector* ImplicitPredEdges

Definition at line 227 of file Andersens.cpp.

unsigned LocationEquivLabel

Definition at line 224 of file Andersens.cpp.

std::map<unsigned, unsigned> MaxK

Definition at line 370 of file Andersens.cpp.

WorkList * NextWL

Definition at line 395 of file Andersens.cpp.

Node* node

Definition at line 296 of file Andersens.cpp.

std::vector<bool> Node2Deleted

Definition at line 385 of file Andersens.cpp.

std::vector<unsigned> Node2DFS

Definition at line 383 of file Andersens.cpp.

std::vector<bool> Node2Visited

Definition at line 404 of file Andersens.cpp.

unsigned NodeRep

Definition at line 246 of file Andersens.cpp.

unsigned NumInEdges

Definition at line 232 of file Andersens.cpp.

DenseMap<Value*, unsigned> ObjectNodes

ObjectNodes - This map contains entries for each memory object in the program: globals, alloca's and mallocs.

Definition at line 351 of file Andersens.cpp.

unsigned Offset

Definition at line 141 of file Andersens.cpp.

Referenced by llvm::MachineInstrBuilder::addConstantPoolIndex(), llvm::MachineInstrBuilder::addExternalSymbol(), llvm::addFrameReference(), llvm::MachineInstrBuilder::addGlobalAddress(), llvm::MipsRegisterInfo::adjustMipsStackFrame(), CalculateTailCallArgDest(), llvm::ComputeMaskedBits(), llvm::ConstantFoldGetElementPtr(), llvm::ConstantPoolSDNode::ConstantPoolSDNode(), llvm::ARMInstrInfo::convertToThreeAddress(), llvm::XCoreRegisterInfo::eliminateFrameIndex(), llvm::X86RegisterInfo::eliminateFrameIndex(), llvm::SPURegisterInfo::eliminateFrameIndex(), llvm::SparcRegisterInfo::eliminateFrameIndex(), llvm::PPCRegisterInfo::eliminateFrameIndex(), llvm::MipsRegisterInfo::eliminateFrameIndex(), llvm::IA64RegisterInfo::eliminateFrameIndex(), llvm::ARMRegisterInfo::eliminateFrameIndex(), llvm::AlphaRegisterInfo::eliminateFrameIndex(), EmitBranchToAt(), llvm::AsmPrinter::EmitConstantValueOnly(), llvm::X86RegisterInfo::emitEpilogue(), llvm::X86RegisterInfo::emitFrameMoves(), llvm::SPURegisterInfo::emitPrologue(), llvm::PPCRegisterInfo::emitPrologue(), emitSPUpdate(), estimateStackSize(), EvaluateGEPOffsetExpression(), ExpandUnalignedLoad(), ExpandUnalignedStore(), llvm::MachineConstantPool::getConstantPoolIndex(), llvm::ExecutionEngine::getConstantValue(), llvm::X86RegisterInfo::getFrameIndexOffset(), llvm::ConstantPoolSDNode::getOffset(), llvm::GlobalAddressSDNode::getOffset(), GetOffsetFromIndex(), llvm::SelectionDAG::getTargetConstantPool(), llvm::CCState::HandleByVal(), llvm::ConstantPoolSDNode::isMachineConstantPoolEntry(), llvm::SparcTargetLowering::LowerArguments(), LowerVASTART(), mergeSPUpdates(), PPCCompilationCallbackC(), RemoveFromWorklist(), SkipWrapperHeader(), SymbolicallyEvaluateGEP(), and llvm::GraphWriter< GraphType >::writeEdge().

SparseBitVector* OldPointsTo

Definition at line 219 of file Andersens.cpp.

unsigned PEClass

Definition at line 413 of file Andersens.cpp.

std::vector<int> PEClass2Node

Definition at line 419 of file Andersens.cpp.

std::vector<int> PENLEClass2Node

Definition at line 423 of file Andersens.cpp.

SparseBitVector* PointedToBy

Definition at line 229 of file Andersens.cpp.

unsigned PointerEquivLabel

Definition at line 223 of file Andersens.cpp.

SparseBitVector* PointsTo

Definition at line 218 of file Andersens.cpp.

SparseBitVector* PredEdges

Definition at line 226 of file Andersens.cpp.

std::priority_queue<WorkListElement> Q

Definition at line 311 of file Andersens.cpp.

Referenced by llvm::SelectionDAG::AssignTopologicalOrder(), llvm::TargetLowering::BuildSDIV(), and llvm::TargetLowering::BuildUDIV().

DenseMap<Function*, unsigned> ReturnNodes

ReturnNodes - This map contains an entry for each function in the program that returns a value.

Definition at line 355 of file Andersens.cpp.

std::stack<unsigned> SCCStack

Definition at line 381 of file Andersens.cpp.

std::vector<int> SDT

Definition at line 428 of file Andersens.cpp.

bool SDTActive

Definition at line 430 of file Andersens.cpp.

const unsigned SelfRep = (unsigned)-1 [static]

Definition at line 92 of file Andersens.cpp.

BitVectorMap Set2PEClass

Definition at line 416 of file Andersens.cpp.

unsigned Src

Definition at line 140 of file Andersens.cpp.

Referenced by llvm::X86InstrInfo::convertToThreeAddress(), llvm::PIC16TargetLowering::ExpandStore(), FoldBitCast(), llvm::XCoreRegisterInfo::getInitialFrameState(), llvm::X86RegisterInfo::getInitialFrameState(), llvm::SPURegisterInfo::getInitialFrameState(), llvm::PPCRegisterInfo::getInitialFrameState(), llvm::ExecutionEngine::LoadValueFromMemory(), llvm::IntrinsicLowering::LowerIntrinsicCall(), StoreIntToMemory(), and llvm::ExecutionEngine::StoreValueToMemory().

bool StoredInHash

Definition at line 234 of file Andersens.cpp.

std::map<unsigned, bool> Tarjan2Deleted

Definition at line 389 of file Andersens.cpp.

std::map<unsigned, unsigned> Tarjan2DFS

Definition at line 388 of file Andersens.cpp.

unsigned Timestamp

Definition at line 250 of file Andersens.cpp.

enum { ... } Andersens::Constraint::ConstraintType Type

Definition at line 36 of file DerivedTypes.h.

const unsigned Unvisited = (unsigned)-1 [static]

Definition at line 93 of file Andersens.cpp.

Value* Val

Definition at line 216 of file Andersens.cpp.

Referenced by llvm::AliasSetTracker::add(), AddOne(), CanPropagatePredecessorsForPHIs(), llvm::SelectionDAG::ComputeNumSignBits(), llvm::ConstantFoldCastInstruction(), llvm::ConstantPoolSDNode::ConstantPoolSDNode(), llvm::MachOCodeEmitter::emitConstantPool(), EvaluateConstantChrecAtConstant(), EvaluateFunction(), ExpandUnalignedStore(), llvm::PPC::get_VSPLTI_elt(), llvm::MachineConstantPool::getConstantPoolIndex(), llvm::ConstantPoolSDNode::getConstVal(), getCopyFromParts(), llvm::ARMConstantPoolValue::getExistingMachineCPValue(), llvm::ConstantPoolSDNode::getMachineCPVal(), getMemsetStringVal(), getMemsetValue(), llvm::SelectionDAG::getNode(), llvm::SelectionDAGLowering::getValue(), llvm::ExecutionEngine::InitializeMemory(), llvm::UniqueVector< llvm::BasicBlock * >::insert(), isBytewiseValue(), LowerCALL(), llvm::IA64TargetLowering::LowerCallTo(), llvm::AlphaTargetLowering::LowerOperation(), LowerPartSelect(), LowerPartSet(), llvm::SPU::LowerSplat_v2i64(), llvm::make_vector(), llvm::PatternMatch::constantint_ty< Val >::match(), llvm::cl::ParseCommandLineOptions(), llvm::MachineConstantPool::print(), llvm::ConstantExpr::replaceUsesOfWithOnConstant(), llvm::ConstantVector::replaceUsesOfWithOnConstant(), llvm::ConstantStruct::replaceUsesOfWithOnConstant(), llvm::ConstantArray::replaceUsesOfWithOnConstant(), llvm::Interpreter::run(), llvm::Use::set(), llvm::TargetLowering::SimplifySetCC(), SRAGlobal(), SubOne(), llvm::Interpreter::visitStoreInst(), WriteConstantInt(), and llvm::MachineConstantPool::~MachineConstantPool().

DenseMap<Value*, unsigned> ValueNodes

ValueNodes - This map indicates the Node that a particular Value* is represented by. This contains entries for all pointers.

Definition at line 347 of file Andersens.cpp.

DenseMap<Function*, unsigned> VarargNodes

VarargNodes - This map contains the entry used to represent all pointers passed through the varargs portion of a function call for a particular function. An entry is not present in this map for functions that do not take variable arguments.

Definition at line 361 of file Andersens.cpp.

std::vector<unsigned> VSSCCRep

Definition at line 402 of file Andersens.cpp.

WorkList w1

Definition at line 394 of file Andersens.cpp.

WorkList w2

Definition at line 394 of file Andersens.cpp.

RegisterPass<Andersens> X("anders-aa","Andersen's Interprocedural Alias Analysis", false, true) [static]

RegisterAnalysisGroup<AliasAnalysis> Y(X) [static]