safecode/lib/InsertPoolChecks/RegisterStackObjPass.cpp - llvm-archive - Git at Google

 //===- RegisterStackObjPass.cpp - Pass to Insert Stack Object Registration ---//
 //
 //                          The SAFECode Compiler
 //
 // This file was developed by the LLVM research group and is distributed under
 // the University of Illinois Open Source License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This pass instruments code to register stack objects with the appropriate
 // pool.
 //
 //===----------------------------------------------------------------------===//

 #define DEBUG_TYPE "stackreg"

 #include "safecode/SAFECode.h"

 #include "SCUtils.h"
 #include "InsertPoolChecks.h"
 #include "llvm/Instruction.h"
 #include "llvm/Module.h"
 #include "llvm/ADT/VectorExtras.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Transforms/Utils/PromoteMemToReg.h"

 #include "safecode/VectorListHelper.h"

 NAMESPACE_SC_BEGIN

 char RegisterStackObjPass::ID = 0;

 static RegisterPass<RegisterStackObjPass> passRegStackObj ("reg-stack-obj", "register stack objects into pools");

 // Pass Statistics
 namespace {
   // Object registration statistics
   STATISTIC (StackRegisters,      "Stack registrations");
   STATISTIC (SavedRegAllocs,      "Stack registrations avoided");
 }

 ////////////////////////////////////////////////////////////////////////////
 // Static Functions
 ////////////////////////////////////////////////////////////////////////////

 // Prototypes of the poolunregister function
 static Constant * StackFree = 0;

 //
 // Function: insertPoolFrees()
 //
 // Description:
 //  This function takes a list of alloca instructions and inserts code to
 //  unregister them at every unwind and return instruction.
 //
 // Inputs:
 //  PoolRegisters - The list of calls to poolregister() inserted for stack
 //                  objects.
 //  ExitPoints    - The list of instructions that can cause the function to
 //                  return.
 //  Context       - The LLVM Context in which to insert instructions.
 //
 void
 RegisterStackObjPass::insertPoolFrees
   (const std::vector<CallInst *> & PoolRegisters,
    const std::vector<Instruction *> & ExitPoints,
    LLVMContext * Context) {
   // List of alloca instructions we create to store the pointers to be
   // deregistered.
   std::vector<AllocaInst *> PtrList;

   // List of pool handles; this is a parallel array to PtrList
   std::vector<Value *> PHList;

   // The infamous void pointer type
   PointerType * VoidPtrTy = getVoidPtrType();

   //
   // Create alloca instructions for every registered alloca.  These will hold
   // a pointer to the registered stack objects and will be referenced by
   // poolunregister().
   //
   for (unsigned index = 0; index < PoolRegisters.size(); ++index) {
     //
     // Take the first element off of the worklist.
     //
     CallInst * CI = PoolRegisters[index];

     //
     // Get the pool handle and allocated pointer from the poolregister() call.
     //
     Value * PH  = CI->getOperand(1);
     Value * Ptr = CI->getOperand(2);

     //
     // Create a place to store the pointer returned from alloca.  Initialize it
     // with a null pointer.
     //
     BasicBlock & EntryBB = CI->getParent()->getParent()->getEntryBlock();
     Instruction * InsertPt = &(EntryBB.front());
     AllocaInst * PtrLoc = new AllocaInst (VoidPtrTy,
                                           Ptr->getName() + ".st",
                                           InsertPt);
     Value * NullPointer = ConstantPointerNull::get(VoidPtrTy);
     new StoreInst (NullPointer, PtrLoc, InsertPt);

     //
     // Store the registered pointer into the memory we allocated in the entry
     // block.
     //
     new StoreInst (Ptr, PtrLoc, CI);

     //
     // Record the alloca that stores the pointer to deregister.
     // Record the pool handle with it.
     //
     PtrList.push_back (PtrLoc);
     PHList.push_back (PH);
   }

   //
   // For each point where the function can exit, insert code to deregister all
   // stack objects.
   //
   for (unsigned index = 0; index < ExitPoints.size(); ++index) {
     //
     // Take the first element off of the worklist.
     //
     Instruction * Return = ExitPoints[index];

     //
     // Deregister each registered stack object.
     //
     for (unsigned i = 0; i < PtrList.size(); ++i) {
       //
       // Get the location holding the pointer and the pool handle associated
       // with it.
       //
       AllocaInst * PtrLoc = PtrList[i];
       Value * PH = PHList[i];

       //
       // Generate a load instruction to get the registered pointer.
       //
       LoadInst * Ptr = new LoadInst (PtrLoc, "", Return);

       //
       // Create the call to poolunregister().
       //
       std::vector<Value *> args;
       args.push_back (PH);
       args.push_back (Ptr);
       CallInst::Create (StackFree, args.begin(), args.end(), "", Return);
     }
   }

   //
   // Lastly, promote the allocas we created into LLVM virtual registers.
   //
   PromoteMemToReg(PtrList, *DT, *DF);
 }

 ////////////////////////////////////////////////////////////////////////////
 // RegisterStackObjPass Methods
 ////////////////////////////////////////////////////////////////////////////

 //
 // Method: runOnFunction()
 //
 // Description:
 //  This is the entry point for this LLVM function pass.  The pass manager will
 //  call this method for every function in the Module that will be transformed.
 //
 // Inputs:
 //  F - A reference to the function to transform.
 //
 // Outputs:
 //  F - The function will be modified to register and unregister stack objects.
 //
 // Return value:
 //  true  - The function was modified.
 //  false - The function was not modified.
 //
 bool
 RegisterStackObjPass::runOnFunction(Function & F) {
   //
   // Get prerequisite analysis information.
   //
   TD = &getAnalysis<TargetData>();
   LI = &getAnalysis<LoopInfo>();
   DT = &getAnalysis<DominatorTree>();
   DF = &getAnalysis<DominanceFrontier>();
   intrinsic = &getAnalysis<InsertSCIntrinsic>();
   dsnPass = &getAnalysis<DSNodePass>();
   paPass = dsnPass->paPass;

   //
   // Get pointers to the functions for registering and unregistering pointers.
   //
   PoolRegister = intrinsic->getIntrinsic("sc.pool_register_stack").F;
   StackFree = intrinsic->getIntrinsic("sc.pool_unregister_stack").F;

   // The set of registered stack objects
   std::vector<CallInst *> PoolRegisters;

   // The set of stack objects within the function.
   std::vector<AllocaInst *> AllocaList;

   // The set of instructions that can cause the function to return to its
   // caller.
   std::vector<Instruction *> ExitPoints;

   //
   // Scan the function to register allocas and find locations where registered
   // allocas to be deregistered.
   //
   for (Function::iterator BI = F.begin(); BI != F.end(); ++BI) {
     //
     // Create a list of alloca instructions to register.  Note that we create
     // the list ahead of time because registerAllocaInst() will create new
     // alloca instructions.
     //
     for (BasicBlock::iterator I = BI->begin(); I != BI->end(); ++I) {
       if (AllocaInst * AI = dyn_cast<AllocaInst>(I)) {
         //
         // Ensure that the alloca is not within a loop; we don't support yet.
         //
         if (LI->getLoopFor (BI)) {
           assert (0 &&
                   "Register Stack Objects: No support for alloca in loop!\n");
           abort();
         }
         AllocaList.push_back (AI);
       }
     }

     //
     // Add calls to register the allocated stack objects.
     //
     while (AllocaList.size()) {
       AllocaInst * AI = AllocaList.back();
       AllocaList.pop_back();
       if (CallInst * CI = registerAllocaInst (AI))
         PoolRegisters.push_back(CI);
     }

     //
     // If the terminator instruction of this basic block can return control
     // flow back to the caller, mark it as a place where a deregistration
     // is needed.
     //
     Instruction * Terminator = BI->getTerminator();
     if ((isa<ReturnInst>(Terminator)) || (isa<UnwindInst>(Terminator))) {
       ExitPoints.push_back (Terminator);
     }
   }

   //
   // Insert poolunregister calls for all of the registered allocas.
   //
   insertPoolFrees (PoolRegisters, ExitPoints, &getGlobalContext());

   //
   // Conservatively assume that we've changed the function.
   //
   return true;
 }

 //
 // Method: registerAllocaInst()
 //
 // Description:
 //  Register a single alloca instruction.
 //
 // Inputs:
 //  AI - The alloca which requires registration.
 //
 // Return value:
 //  NULL - The alloca was not registered.
 //  Otherwise, the call to poolregister() is returned.
 //
 CallInst *
 RegisterStackObjPass::registerAllocaInst (AllocaInst *AI) {
   //
   // Get the function information for this function.
   //
   Function *F = AI->getParent()->getParent();
   PA::FuncInfo *FI = paPass->getFuncInfoOrClone(*F);
   Value *temp = FI->MapValueToOriginal(AI);
   AllocaInst *AIOrig = AI;
   if (temp)
     AIOrig = dyn_cast<AllocaInst>(temp);

   //
   // Get the pool handle for the node that this contributes to...
   //
   Function *FOrig  = AIOrig->getParent()->getParent();
   DSNode *Node = dsnPass->getDSNode(AIOrig, FOrig);
   assert (Node && "Alloca does not have DSNode!\n");
   assert ((Node->isAllocaNode()) && "DSNode for alloca is missing stack flag!");

   //
   // Only register the stack allocation if it may be the subject of a
   // run-time check.  This can only occur when the object is used like an
   // array because:
   //  1) GEP checks are only done when accessing arrays.
   //  2) Load/Store checks are only done on collapsed nodes (which appear to
   //     be used like arrays).
   //
 #if 0
   if (!(Node->isArray()))
     return 0;
 #endif

   //
   // Determine if we have ever done a check on this alloca or a pointer
   // aliasing this alloca.  If not, then we can forego the check (even if we
   // can't trace through all the data flow).
   //
   // FIXME:
   //  This implementation is incorrect.  A node in the DSGraph will have
   //  different DSNodes in different functions (because each function has its
   //  own copy of the DSGraph).  We will need to find another way to do this
   //  optimization.
   //
   if (dsnPass->isDSNodeChecked(Node)) {
     ++SavedRegAllocs;
     return 0;
   }

   //
   // Determine if any use (direct or indirect) escapes this function.  If
   // not, then none of the checks will consult the MetaPool, and we can
   // forego registering the alloca.
   //
   bool MustRegisterAlloca = false;
   std::vector<Value *> AllocaWorkList;
   AllocaWorkList.push_back (AI);
   while ((!MustRegisterAlloca) && (AllocaWorkList.size())) {
     Value * V = AllocaWorkList.back();
     AllocaWorkList.pop_back();
     Value::use_iterator UI = V->use_begin();
     for (; UI != V->use_end(); ++UI) {
       // We cannot handle PHI nodes or Select instructions
       if (isa<PHINode>(UI) || isa<SelectInst>(UI)) {
         MustRegisterAlloca = true;
         continue;
       }

       // The pointer escapes if it's stored to memory somewhere.
       StoreInst * SI;
       if ((SI = dyn_cast<StoreInst>(UI)) && (SI->getOperand(0) == V)) {
         MustRegisterAlloca = true;
         continue;
       }

       // GEP instructions are okay, but need to be added to the worklist
       if (isa<GetElementPtrInst>(UI)) {
         AllocaWorkList.push_back (*UI);
         continue;
       }

       // Cast instructions are okay as long as they cast to another pointer
       // type
       if (CastInst * CI = dyn_cast<CastInst>(UI)) {
         if (isa<PointerType>(CI->getType())) {
           AllocaWorkList.push_back (*UI);
           continue;
         } else {
           MustRegisterAlloca = true;
           continue;
         }
       }

 #if 0
       if (ConstantExpr *cExpr = dyn_cast<ConstantExpr>(UI)) {
         if (cExpr->getOpcode() == Instruction::Cast) {
           AllocaWorkList.push_back (*UI);
           continue;
         } else {
           MustRegisterAlloca = true;
           continue;
         }
       }
 #endif

       CallInst * CI1;
       if ((CI1 = dyn_cast<CallInst>(UI))) {
         if (!(CI1->getCalledFunction())) {
           MustRegisterAlloca = true;
           continue;
         }

         std::string FuncName = CI1->getCalledFunction()->getName();
         if (FuncName == "exactcheck3") {
           AllocaWorkList.push_back (*UI);
           continue;
         } else if ((FuncName == "llvm.memcpy.i32")    ||
                    (FuncName == "llvm.memcpy.i64")    ||
                    (FuncName == "llvm.memset.i32")    ||
                    (FuncName == "llvm.memset.i64")    ||
                    (FuncName == "llvm.memmove.i32")   ||
                    (FuncName == "llvm.memmove.i64")   ||
                    (FuncName == "llva_memcpy")        ||
                    (FuncName == "llva_memset")        ||
                    (FuncName == "llva_strncpy")       ||
                    (FuncName == "llva_invokememcpy")  ||
                    (FuncName == "llva_invokestrncpy") ||
                    (FuncName == "llva_invokememset")  ||
                    (FuncName == "memcmp")) {
           continue;
         } else {
           MustRegisterAlloca = true;
           continue;
         }
       }
     }
   }

   if (!MustRegisterAlloca) {
     ++SavedRegAllocs;
     return 0;
   }

   //
   // Insert the alloca registration.
   //
   Value *PH = dsnPass->getPoolHandle(AIOrig, FOrig, *FI);
   if (PH == 0 || isa<ConstantPointerNull>(PH)) return 0;

   //
   // Create an LLVM Value for the allocation size.  Insert a multiplication
   // instruction if the allocation allocates an array.
   //
   const Type * Int32Type = IntegerType::getInt32Ty(getGlobalContext());
   unsigned allocsize = TD->getTypeAllocSize(AI->getAllocatedType());
   Value *AllocSize = ConstantInt::get (Int32Type, allocsize);
   if (AI->isArrayAllocation())
     AllocSize = BinaryOperator::Create(Instruction::Mul, AllocSize,
                                        AI->getOperand(0), "sizetmp", AI);

   //
   // Attempt to insert the call to register the alloca'ed object after all of
   // the alloca instructions in the basic block.
   //
   Instruction *iptI = AI;
   BasicBlock::iterator InsertPt = AI;
   iptI = ++InsertPt;
   if (AI->getParent() == (&(AI->getParent()->getParent()->getEntryBlock()))) {
     InsertPt = AI->getParent()->begin();
     while (&(*(InsertPt)) != AI)
       ++InsertPt;
     while (isa<AllocaInst>(InsertPt))
       ++InsertPt;
     iptI = InsertPt;
   }

   //
   // Insert a call to register the object.
   //
   PointerType * VoidPtrTy = getVoidPtrType();
   Instruction *Casted = castTo (AI, VoidPtrTy, AI->getName()+".casted", iptI);
   Value * CastedPH    = castTo (PH, VoidPtrTy, PH->getName() + "casted", iptI);
   std::vector<Value *> args;
   args.push_back (CastedPH);
   args.push_back (Casted);
   args.push_back (AllocSize);

   // Update statistics
   ++StackRegisters;
   return CallInst::Create (PoolRegister, args.begin(), args.end(), "", iptI);
 }

 NAMESPACE_SC_END
	//===- RegisterStackObjPass.cpp - Pass to Insert Stack Object Registration ---//
	//
	// The SAFECode Compiler
	//
	// This file was developed by the LLVM research group and is distributed under
	// the University of Illinois Open Source License. See LICENSE.TXT for details.
	//
	//===----------------------------------------------------------------------===//
	//
	// This pass instruments code to register stack objects with the appropriate
	// pool.
	//
	//===----------------------------------------------------------------------===//

	#define DEBUG_TYPE "stackreg"

	#include "safecode/SAFECode.h"

	#include "SCUtils.h"
	#include "InsertPoolChecks.h"
	#include "llvm/Instruction.h"
	#include "llvm/Module.h"
	#include "llvm/ADT/VectorExtras.h"
	#include "llvm/ADT/Statistic.h"
	#include "llvm/Transforms/Utils/PromoteMemToReg.h"

	#include "safecode/VectorListHelper.h"

	NAMESPACE_SC_BEGIN

	char RegisterStackObjPass::ID = 0;

	static RegisterPass<RegisterStackObjPass> passRegStackObj ("reg-stack-obj", "register stack objects into pools");

	// Pass Statistics
	namespace {
	// Object registration statistics
	STATISTIC (StackRegisters, "Stack registrations");
	STATISTIC (SavedRegAllocs, "Stack registrations avoided");
	}

	////////////////////////////////////////////////////////////////////////////
	// Static Functions
	////////////////////////////////////////////////////////////////////////////

	// Prototypes of the poolunregister function
	static Constant * StackFree = 0;

	//
	// Function: insertPoolFrees()
	//
	// Description:
	// This function takes a list of alloca instructions and inserts code to
	// unregister them at every unwind and return instruction.
	//
	// Inputs:
	// PoolRegisters - The list of calls to poolregister() inserted for stack
	// objects.
	// ExitPoints - The list of instructions that can cause the function to
	// return.
	// Context - The LLVM Context in which to insert instructions.
	//
	void
	RegisterStackObjPass::insertPoolFrees
	(const std::vector<CallInst *> & PoolRegisters,
	const std::vector<Instruction *> & ExitPoints,
	LLVMContext * Context) {
	// List of alloca instructions we create to store the pointers to be
	// deregistered.
	std::vector<AllocaInst *> PtrList;

	// List of pool handles; this is a parallel array to PtrList
	std::vector<Value *> PHList;

	// The infamous void pointer type
	PointerType * VoidPtrTy = getVoidPtrType();

	//
	// Create alloca instructions for every registered alloca. These will hold
	// a pointer to the registered stack objects and will be referenced by
	// poolunregister().
	//
	for (unsigned index = 0; index < PoolRegisters.size(); ++index) {
	//
	// Take the first element off of the worklist.
	//
	CallInst * CI = PoolRegisters[index];

	//
	// Get the pool handle and allocated pointer from the poolregister() call.
	//
	Value * PH = CI->getOperand(1);
	Value * Ptr = CI->getOperand(2);

	//
	// Create a place to store the pointer returned from alloca. Initialize it
	// with a null pointer.
	//
	BasicBlock & EntryBB = CI->getParent()->getParent()->getEntryBlock();
	Instruction * InsertPt = &(EntryBB.front());
	AllocaInst * PtrLoc = new AllocaInst (VoidPtrTy,
	Ptr->getName() + ".st",
	InsertPt);
	Value * NullPointer = ConstantPointerNull::get(VoidPtrTy);
	new StoreInst (NullPointer, PtrLoc, InsertPt);

	//
	// Store the registered pointer into the memory we allocated in the entry
	// block.
	//
	new StoreInst (Ptr, PtrLoc, CI);

	//
	// Record the alloca that stores the pointer to deregister.
	// Record the pool handle with it.
	//
	PtrList.push_back (PtrLoc);
	PHList.push_back (PH);
	}

	//
	// For each point where the function can exit, insert code to deregister all
	// stack objects.
	//
	for (unsigned index = 0; index < ExitPoints.size(); ++index) {
	//
	// Take the first element off of the worklist.
	//
	Instruction * Return = ExitPoints[index];

	//
	// Deregister each registered stack object.
	//
	for (unsigned i = 0; i < PtrList.size(); ++i) {
	//
	// Get the location holding the pointer and the pool handle associated
	// with it.
	//
	AllocaInst * PtrLoc = PtrList[i];
	Value * PH = PHList[i];

	//
	// Generate a load instruction to get the registered pointer.
	//
	LoadInst * Ptr = new LoadInst (PtrLoc, "", Return);

	//
	// Create the call to poolunregister().
	//
	std::vector<Value *> args;
	args.push_back (PH);
	args.push_back (Ptr);
	CallInst::Create (StackFree, args.begin(), args.end(), "", Return);
	}
	}

	//
	// Lastly, promote the allocas we created into LLVM virtual registers.
	//
	PromoteMemToReg(PtrList, DT, DF);
	}

	////////////////////////////////////////////////////////////////////////////
	// RegisterStackObjPass Methods
	////////////////////////////////////////////////////////////////////////////

	//
	// Method: runOnFunction()
	//
	// Description:
	// This is the entry point for this LLVM function pass. The pass manager will
	// call this method for every function in the Module that will be transformed.
	//
	// Inputs:
	// F - A reference to the function to transform.
	//
	// Outputs:
	// F - The function will be modified to register and unregister stack objects.
	//
	// Return value:
	// true - The function was modified.
	// false - The function was not modified.
	//
	bool
	RegisterStackObjPass::runOnFunction(Function & F) {
	//
	// Get prerequisite analysis information.
	//
	TD = &getAnalysis<TargetData>();
	LI = &getAnalysis<LoopInfo>();
	DT = &getAnalysis<DominatorTree>();
	DF = &getAnalysis<DominanceFrontier>();
	intrinsic = &getAnalysis<InsertSCIntrinsic>();
	dsnPass = &getAnalysis<DSNodePass>();
	paPass = dsnPass->paPass;

	//
	// Get pointers to the functions for registering and unregistering pointers.
	//
	PoolRegister = intrinsic->getIntrinsic("sc.pool_register_stack").F;
	StackFree = intrinsic->getIntrinsic("sc.pool_unregister_stack").F;

	// The set of registered stack objects
	std::vector<CallInst *> PoolRegisters;

	// The set of stack objects within the function.
	std::vector<AllocaInst *> AllocaList;

	// The set of instructions that can cause the function to return to its
	// caller.
	std::vector<Instruction *> ExitPoints;

	//
	// Scan the function to register allocas and find locations where registered
	// allocas to be deregistered.
	//
	for (Function::iterator BI = F.begin(); BI != F.end(); ++BI) {
	//
	// Create a list of alloca instructions to register. Note that we create
	// the list ahead of time because registerAllocaInst() will create new
	// alloca instructions.
	//
	for (BasicBlock::iterator I = BI->begin(); I != BI->end(); ++I) {
	if (AllocaInst * AI = dyn_cast<AllocaInst>(I)) {
	//
	// Ensure that the alloca is not within a loop; we don't support yet.
	//
	if (LI->getLoopFor (BI)) {
	assert (0 &&
	"Register Stack Objects: No support for alloca in loop!\n");
	abort();
	}
	AllocaList.push_back (AI);
	}
	}

	//
	// Add calls to register the allocated stack objects.
	//
	while (AllocaList.size()) {
	AllocaInst * AI = AllocaList.back();
	AllocaList.pop_back();
	if (CallInst * CI = registerAllocaInst (AI))
	PoolRegisters.push_back(CI);
	}

	//
	// If the terminator instruction of this basic block can return control
	// flow back to the caller, mark it as a place where a deregistration
	// is needed.
	//
	Instruction * Terminator = BI->getTerminator();
	if ((isa<ReturnInst>(Terminator)) \|\| (isa<UnwindInst>(Terminator))) {
	ExitPoints.push_back (Terminator);
	}
	}

	//
	// Insert poolunregister calls for all of the registered allocas.
	//
	insertPoolFrees (PoolRegisters, ExitPoints, &getGlobalContext());

	//
	// Conservatively assume that we've changed the function.
	//
	return true;
	}

	//
	// Method: registerAllocaInst()
	//
	// Description:
	// Register a single alloca instruction.
	//
	// Inputs:
	// AI - The alloca which requires registration.
	//
	// Return value:
	// NULL - The alloca was not registered.
	// Otherwise, the call to poolregister() is returned.
	//
	CallInst *
	RegisterStackObjPass::registerAllocaInst (AllocaInst *AI) {
	//
	// Get the function information for this function.
	//
	Function *F = AI->getParent()->getParent();
	PA::FuncInfo FI = paPass->getFuncInfoOrClone(F);
	Value *temp = FI->MapValueToOriginal(AI);
	AllocaInst *AIOrig = AI;
	if (temp)
	AIOrig = dyn_cast<AllocaInst>(temp);

	//
	// Get the pool handle for the node that this contributes to...
	//
	Function *FOrig = AIOrig->getParent()->getParent();
	DSNode *Node = dsnPass->getDSNode(AIOrig, FOrig);
	assert (Node && "Alloca does not have DSNode!\n");
	assert ((Node->isAllocaNode()) && "DSNode for alloca is missing stack flag!");

	//
	// Only register the stack allocation if it may be the subject of a
	// run-time check. This can only occur when the object is used like an
	// array because:
	// 1) GEP checks are only done when accessing arrays.
	// 2) Load/Store checks are only done on collapsed nodes (which appear to
	// be used like arrays).
	//
	#if 0
	if (!(Node->isArray()))
	return 0;
	#endif

	//
	// Determine if we have ever done a check on this alloca or a pointer
	// aliasing this alloca. If not, then we can forego the check (even if we
	// can't trace through all the data flow).
	//
	// FIXME:
	// This implementation is incorrect. A node in the DSGraph will have
	// different DSNodes in different functions (because each function has its
	// own copy of the DSGraph). We will need to find another way to do this
	// optimization.
	//
	if (dsnPass->isDSNodeChecked(Node)) {
	++SavedRegAllocs;
	return 0;
	}

	//
	// Determine if any use (direct or indirect) escapes this function. If
	// not, then none of the checks will consult the MetaPool, and we can
	// forego registering the alloca.
	//
	bool MustRegisterAlloca = false;
	std::vector<Value *> AllocaWorkList;
	AllocaWorkList.push_back (AI);
	while ((!MustRegisterAlloca) && (AllocaWorkList.size())) {
	Value * V = AllocaWorkList.back();
	AllocaWorkList.pop_back();
	Value::use_iterator UI = V->use_begin();
	for (; UI != V->use_end(); ++UI) {
	// We cannot handle PHI nodes or Select instructions
	if (isa<PHINode>(UI) \|\| isa<SelectInst>(UI)) {
	MustRegisterAlloca = true;
	continue;
	}

	// The pointer escapes if it's stored to memory somewhere.
	StoreInst * SI;
	if ((SI = dyn_cast<StoreInst>(UI)) && (SI->getOperand(0) == V)) {
	MustRegisterAlloca = true;
	continue;
	}

	// GEP instructions are okay, but need to be added to the worklist
	if (isa<GetElementPtrInst>(UI)) {
	AllocaWorkList.push_back (*UI);
	continue;
	}

	// Cast instructions are okay as long as they cast to another pointer
	// type
	if (CastInst * CI = dyn_cast<CastInst>(UI)) {
	if (isa<PointerType>(CI->getType())) {
	AllocaWorkList.push_back (*UI);
	continue;
	} else {
	MustRegisterAlloca = true;
	continue;
	}
	}

	#if 0
	if (ConstantExpr *cExpr = dyn_cast<ConstantExpr>(UI)) {
	if (cExpr->getOpcode() == Instruction::Cast) {
	AllocaWorkList.push_back (*UI);
	continue;
	} else {
	MustRegisterAlloca = true;
	continue;
	}
	}
	#endif

	CallInst * CI1;
	if ((CI1 = dyn_cast<CallInst>(UI))) {
	if (!(CI1->getCalledFunction())) {
	MustRegisterAlloca = true;
	continue;
	}

	std::string FuncName = CI1->getCalledFunction()->getName();
	if (FuncName == "exactcheck3") {
	AllocaWorkList.push_back (*UI);
	continue;
	} else if ((FuncName == "llvm.memcpy.i32") \|\|
	(FuncName == "llvm.memcpy.i64") \|\|
	(FuncName == "llvm.memset.i32") \|\|
	(FuncName == "llvm.memset.i64") \|\|
	(FuncName == "llvm.memmove.i32") \|\|
	(FuncName == "llvm.memmove.i64") \|\|
	(FuncName == "llva_memcpy") \|\|
	(FuncName == "llva_memset") \|\|
	(FuncName == "llva_strncpy") \|\|
	(FuncName == "llva_invokememcpy") \|\|
	(FuncName == "llva_invokestrncpy") \|\|
	(FuncName == "llva_invokememset") \|\|
	(FuncName == "memcmp")) {
	continue;
	} else {
	MustRegisterAlloca = true;
	continue;
	}
	}
	}
	}

	if (!MustRegisterAlloca) {
	++SavedRegAllocs;
	return 0;
	}

	//
	// Insert the alloca registration.
	//
	Value PH = dsnPass->getPoolHandle(AIOrig, FOrig, FI);
	if (PH == 0 \|\| isa<ConstantPointerNull>(PH)) return 0;

	//
	// Create an LLVM Value for the allocation size. Insert a multiplication
	// instruction if the allocation allocates an array.
	//
	const Type * Int32Type = IntegerType::getInt32Ty(getGlobalContext());
	unsigned allocsize = TD->getTypeAllocSize(AI->getAllocatedType());
	Value *AllocSize = ConstantInt::get (Int32Type, allocsize);
	if (AI->isArrayAllocation())
	AllocSize = BinaryOperator::Create(Instruction::Mul, AllocSize,
	AI->getOperand(0), "sizetmp", AI);

	//
	// Attempt to insert the call to register the alloca'ed object after all of
	// the alloca instructions in the basic block.
	//
	Instruction *iptI = AI;
	BasicBlock::iterator InsertPt = AI;
	iptI = ++InsertPt;
	if (AI->getParent() == (&(AI->getParent()->getParent()->getEntryBlock()))) {
	InsertPt = AI->getParent()->begin();
	while (&(*(InsertPt)) != AI)
	++InsertPt;
	while (isa<AllocaInst>(InsertPt))
	++InsertPt;
	iptI = InsertPt;
	}

	//
	// Insert a call to register the object.
	//
	PointerType * VoidPtrTy = getVoidPtrType();
	Instruction *Casted = castTo (AI, VoidPtrTy, AI->getName()+".casted", iptI);
	Value * CastedPH = castTo (PH, VoidPtrTy, PH->getName() + "casted", iptI);
	std::vector<Value *> args;
	args.push_back (CastedPH);
	args.push_back (Casted);
	args.push_back (AllocSize);

	// Update statistics
	++StackRegisters;
	return CallInst::Create (PoolRegister, args.begin(), args.end(), "", iptI);
	}

	NAMESPACE_SC_END