Implement function rewriting to use offsets instead of pointers in programs.

This now works with treeadd at least, and perhaps other programs as well.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@2233 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 569 insertions, 217 deletions

diff --git a/lib/Transforms/IPO/OldPoolAllocate.cpp b/lib/Transforms/IPO/OldPoolAllocate.cpp
index 4b5c830870..fc7bc5e7d6 100644
--- a/lib/Transforms/IPO/OldPoolAllocate.cpp
+++ b/lib/Transforms/IPO/OldPoolAllocate.cpp
@@ -16,7 +16,9 @@
 #include "llvm/BasicBlock.h"
 #include "llvm/iMemory.h"
 #include "llvm/iTerminators.h"
+#include "llvm/iPHINode.h"
 #include "llvm/iOther.h"
+#include "llvm/DerivedTypes.h"
 #include "llvm/ConstantVals.h"
 #include "llvm/Target/TargetData.h"
 #include "llvm/Support/InstVisitor.h"
@@ -25,22 +27,65 @@
 #include "Support/STLExtras.h"
 #include <algorithm>
 
+// DEBUG_CREATE_POOLS - Enable this to turn on debug output for the pool
+// creation phase in the top level function of a transformed data structure.
+//
+#define DEBUG_CREATE_POOLS 1
+
+const Type *POINTERTYPE;
 
 // FIXME: This is dependant on the sparc backend layout conventions!!
 static TargetData TargetData("test");
 
 namespace {
+  struct PoolInfo {
+    DSNode *Node;           // The node this pool allocation represents
+    Value  *Handle;         // LLVM value of the pool in the current context
+    const Type *NewType;    // The transformed type of the memory objects
+    const Type *PoolType;   // The type of the pool
+
+    const Type *getOldType() const { return Node->getType(); }
+
+    PoolInfo() {  // Define a default ctor for map::operator[]
+      cerr << "Map subscript used to get element that doesn't exist!\n";
+      abort();  // Invalid
+    }
+
+    PoolInfo(DSNode *N, Value *H, const Type *NT, const Type *PT)
+      : Node(N), Handle(H), NewType(NT), PoolType(PT) {
+      // Handle can be null...
+      assert(N && NT && PT && "Pool info null!");
+    }
+
+    PoolInfo(DSNode *N) : Node(N), Handle(0), NewType(0), PoolType(0) {
+      assert(N && "Invalid pool info!");
+
+      // The new type of the memory object is the same as the old type, except
+      // that all of the pointer values are replaced with POINTERTYPE values.
+      assert(isa<StructType>(getOldType()) && "Can only handle structs!");
+      StructType *OldTy = cast<StructType>(getOldType());
+      vector<const Type *> NewElTypes;
+      NewElTypes.reserve(OldTy->getElementTypes().size());
+      for (StructType::ElementTypes::const_iterator
+             I = OldTy->getElementTypes().begin(),
+             E = OldTy->getElementTypes().end(); I != E; ++I)
+        if (PointerType *PT = dyn_cast<PointerType>(I->get()))
+          NewElTypes.push_back(POINTERTYPE);
+        else
+          NewElTypes.push_back(*I);
+      NewType = StructType::get(NewElTypes);
+    }
+  };
+
   // ScalarInfo - Information about an LLVM value that we know points to some
   // datastructure we are processing.
   //
   struct ScalarInfo {
     Value  *Val;            // Scalar value in Current Function
-    DSNode *Node;           // DataStructure node it points to
-    Value  *PoolHandle;     // PoolTy* LLVM value
+    PoolInfo Pool;          // The pool the scalar points into
     
-    ScalarInfo(Value *V, DSNode *N, Value *PH)
-      : Val(V), Node(N), PoolHandle(PH) {
-      assert(V && N && PH && "Null value passed to ScalarInfo ctor!");
+    ScalarInfo(Value *V, const PoolInfo &PI) : Val(V), Pool(PI) {
+      assert(V && "Null value passed to ScalarInfo ctor!");
     }
   };
 
@@ -66,9 +111,8 @@ namespace {
   //
   struct TransformFunctionInfo {
     // ArgInfo - Maintain information about the arguments that need to be
-    // processed.  Each pair corresponds to an argument (whose number is the
-    // first element) that needs to have a pool pointer (the second element)
-    // passed into the transformed function with it.
+    // processed.  Each CallArgInfo corresponds to an argument that needs to
+    // have a pool pointer passed into the transformed function with it.
     //
     // As a special case, "argument" number -1 corresponds to the return value.
     //
@@ -103,23 +147,27 @@ namespace {
 
 
   // Define the pass class that we implement...
-  class PoolAllocate : public Pass {
-    // PoolTy - The type of a scalar value that contains a pool pointer.
-    PointerType *PoolTy;
-  public:
-
+  struct PoolAllocate : public Pass {
     PoolAllocate() {
-      // Initialize the PoolTy instance variable, since the type never changes.
-      vector<const Type*> PoolElements;
-      PoolElements.push_back(PointerType::get(Type::SByteTy));
-      PoolElements.push_back(Type::UIntTy);
-      PoolTy = PointerType::get(StructType::get(PoolElements));
-      // PoolTy = { sbyte*, uint }*
+      POINTERTYPE = Type::UShortTy;
 
       CurModule = 0; DS = 0;
       PoolInit = PoolDestroy = PoolAlloc = PoolFree = 0;
     }
 
+    // getPoolType - Get the type used by the backend for a pool of a particular
+    // type.  This pool record is used to allocate nodes of type NodeType.
+    //
+    // Here, PoolTy = { NodeType*, sbyte*, uint }*
+    //
+    const StructType *getPoolType(const Type *NodeType) {
+      vector<const Type*> PoolElements;
+      PoolElements.push_back(PointerType::get(NodeType));
+      PoolElements.push_back(PointerType::get(Type::SByteTy));
+      PoolElements.push_back(Type::UIntTy);
+      return StructType::get(PoolElements);
+    }
+
     bool run(Module *M);
 
     // getAnalysisUsageInfo - This function requires data structure information
@@ -157,8 +205,9 @@ namespace {
     }
 
 
-    // addPoolPrototypes - Add prototypes for the pool methods to the specified
-    // module and update the Pool* instance variables to point to them.
+    // addPoolPrototypes - Add prototypes for the pool functions to the
+    // specified module and update the Pool* instance variables to point to
+    // them.
     //
     void addPoolPrototypes(Module *M);
 
@@ -166,10 +215,10 @@ namespace {
     // CreatePools - Insert instructions into the function we are processing to
     // create all of the memory pool objects themselves.  This also inserts
     // destruction code.  Add an alloca for each pool that is allocated to the
-    // PoolDescriptors map.
+    // PoolDescs map.
     //
     void CreatePools(Function *F, const vector<AllocDSNode*> &Allocs,
-                     map<DSNode*, Value*> &PoolDescriptors);
+                     map<DSNode*, PoolInfo> &PoolDescs);
 
     // processFunction - Convert a function to use pool allocation where
     // available.
@@ -177,26 +226,25 @@ namespace {
     bool processFunction(Function *F);
 
     // transformFunctionBody - This transforms the instruction in 'F' to use the
-    // pools specified in PoolDescriptors when modifying data structure nodes
-    // specified in the PoolDescriptors map.  IPFGraph is the closed data
-    // structure graph for F, of which the PoolDescriptor nodes come from.
+    // pools specified in PoolDescs when modifying data structure nodes
+    // specified in the PoolDescs map.  IPFGraph is the closed data structure
+    // graph for F, of which the PoolDescriptor nodes come from.
     //
     void transformFunctionBody(Function *F, FunctionDSGraph &IPFGraph,
-                               map<DSNode*, Value*> &PoolDescriptors);
+                               map<DSNode*, PoolInfo> &PoolDescs);
 
     // transformFunction - Transform the specified function the specified way.
     // It we have already transformed that function that way, don't do anything.
     // The nodes in the TransformFunctionInfo come out of callers data structure
-    // graph.
+    // graph, and the PoolDescs passed in are the caller's.
     //
     void transformFunction(TransformFunctionInfo &TFI,
-                           FunctionDSGraph &CallerIPGraph);
+                           FunctionDSGraph &CallerIPGraph,
+                           map<DSNode*, PoolInfo> &PoolDescs);
 
   };
 }
 
-
-
 // isNotPoolableAlloc - This is a predicate that returns true if the specified
 // allocation node in a data structure graph is eligable for pool allocation.
 //
@@ -239,108 +287,218 @@ bool PoolAllocate::processFunction(Function *F) {
 
   // Insert instructions into the function we are processing to create all of
   // the memory pool objects themselves.  This also inserts destruction code.
-  // This fills in the PoolDescriptors map to associate the alloc node with the
+  // This fills in the PoolDescs map to associate the alloc node with the
   // allocation of the memory pool corresponding to it.
   // 
-  map<DSNode*, Value*> PoolDescriptors;
-  CreatePools(F, Allocs, PoolDescriptors);
+  map<DSNode*, PoolInfo> PoolDescs;
+  CreatePools(F, Allocs, PoolDescs);
 
-  // Now we need to figure out what called methods we need to transform, and
+  cerr << "Transformed Entry Function: \n" << F;
+
+  // Now we need to figure out what called functions we need to transform, and
   // how.  To do this, we look at all of the scalars, seeing which functions are
   // either used as a scalar value (so they return a data structure), or are
   // passed one of our scalar values.
   //
-  transformFunctionBody(F, IPGraph, PoolDescriptors);
+  transformFunctionBody(F, IPGraph, PoolDescs);
 
   return true;
 }
 
 
-class FunctionBodyTransformer : public InstVisitor<FunctionBodyTransformer> {
+//===----------------------------------------------------------------------===//
+//
+// NewInstructionCreator - This class is used to traverse the function being
+// modified, changing each instruction visit'ed to use and provide pointer
+// indexes instead of real pointers.  This is what changes the body of a
+// function to use pool allocation.
+//
+class NewInstructionCreator : public InstVisitor<NewInstructionCreator> {
   PoolAllocate &PoolAllocator;
   vector<ScalarInfo> &Scalars;
   map<CallInst*, TransformFunctionInfo> &CallMap;
+  map<Value*, Value*> &XFormMap;   // Map old pointers to new indexes
+
+  struct RefToUpdate {
+    Instruction *I;       // Instruction to update
+    unsigned     OpNum;   // Operand number to update
+    Value       *OldVal;  // The old value it had
 
-  const ScalarInfo &getScalar(const Value *V) {
+    RefToUpdate(Instruction *i, unsigned o, Value *ov)
+      : I(i), OpNum(o), OldVal(ov) {}
+  };
+  vector<RefToUpdate> ReferencesToUpdate;
+
+  const ScalarInfo &getScalarRef(const Value *V) {
     for (unsigned i = 0, e = Scalars.size(); i != e; ++i)
       if (Scalars[i].Val == V) return Scalars[i];
     assert(0 && "Scalar not found in getScalar!");
     abort();
     return Scalars[0];
   }
-
-  // updateScalars - Map the scalars array entries that look like 'From' to look
-  // like 'To'.
-  //
-  void updateScalars(Value *From, Value *To) {
+  
+  const ScalarInfo *getScalar(const Value *V) {
     for (unsigned i = 0, e = Scalars.size(); i != e; ++i)
-      if (Scalars[i].Val == From) Scalars[i].Val = To;
+      if (Scalars[i].Val == V) return &Scalars[i];
+    return 0;
   }
 
-public:
-  FunctionBodyTransformer(PoolAllocate &PA, vector<ScalarInfo> &S,
-                          map<CallInst*, TransformFunctionInfo> &C)
-    : PoolAllocator(PA), Scalars(S), CallMap(C) {}
+  BasicBlock::iterator ReplaceInstWith(Instruction *I, Instruction *New) {
+    BasicBlock *BB = I->getParent();
+    BasicBlock::iterator RI = find(BB->begin(), BB->end(), I);
+    BB->getInstList().replaceWith(RI, New);
+    XFormMap[I] = New;
+    return RI;
+  }
 
-  void visitMemAccessInst(MemAccessInst *MAI) {
-    // Don't do anything to load, store, or GEP yet...
+  LoadInst *createPoolBaseInstruction(Value *PtrVal) {
+    const ScalarInfo &SC = getScalarRef(PtrVal);
+    vector<Value*> Args(3);
+    Args[0] = ConstantUInt::get(Type::UIntTy, 0);  // No pointer offset
+    Args[1] = ConstantUInt::get(Type::UByteTy, 0); // Field #0 of pool descriptr
+    Args[2] = ConstantUInt::get(Type::UByteTy, 0); // Field #0 of poolalloc val
+    return new LoadInst(SC.Pool.Handle, Args, PtrVal->getName()+".poolbase");
   }
 
-  // Convert a malloc instruction into a call to poolalloc
-  void visitMallocInst(MallocInst *I) {
-    const ScalarInfo &SC = getScalar(I);
-    BasicBlock *BB = I->getParent();
-    BasicBlock::iterator MI = find(BB->begin(), BB->end(), I);
-    BB->getInstList().remove(MI);  // Remove the Malloc instruction from the BB
 
-    // Create a new call to poolalloc before the malloc instruction
-    vector<Value*> Args;
-    Args.push_back(SC.PoolHandle);
-    CallInst *Call = new CallInst(PoolAllocator.PoolAlloc, Args, I->getName());
-    MI = BB->getInstList().insert(MI, Call)+1;
-
-    // If the type desired is not void*, cast it now...
-    Value *Ptr = Call;
-    if (Call->getType() != I->getType()) {
-      CastInst *CI = new CastInst(Ptr, I->getType(), I->getName());
-      BB->getInstList().insert(MI, CI);
-      Ptr = CI;
+public:
+  NewInstructionCreator(PoolAllocate &PA, vector<ScalarInfo> &S,
+                        map<CallInst*, TransformFunctionInfo> &C,
+                        map<Value*, Value*> &X)
+    : PoolAllocator(PA), Scalars(S), CallMap(C), XFormMap(X) {}
+
+
+  // updateReferences - The NewInstructionCreator is responsible for creating
+  // new instructions to replace the old ones in the function, and then link up
+  // references to values to their new values.  For it to do this, however, it
+  // keeps track of information about the value mapping of old values to new
+  // values that need to be patched up.  Given this value map and a set of
+  // instruction operands to patch, updateReferences performs the updates.
+  //
+  void updateReferences() {
+    for (unsigned i = 0, e = ReferencesToUpdate.size(); i != e; ++i) {
+      RefToUpdate &Ref = ReferencesToUpdate[i];
+      Value *NewVal = XFormMap[Ref.OldVal];
+
+      if (NewVal == 0) {
+        if (isa<Constant>(Ref.OldVal) &&  // Refering to a null ptr?
+            cast<Constant>(Ref.OldVal)->isNullValue()) {
+          // Transform the null pointer into a null index... caching in XFormMap
+          XFormMap[Ref.OldVal] = NewVal =Constant::getNullConstant(POINTERTYPE);
+          //} else if (isa<Argument>(Ref.OldVal)) {
+        } else {
+          cerr << "Unknown reference to: " << Ref.OldVal << "\n";
+          assert(XFormMap[Ref.OldVal] &&
+                 "Reference to value that was not updated found!");
+        }
+      }
+        
+      Ref.I->setOperand(Ref.OpNum, NewVal);
     }
+    ReferencesToUpdate.clear();
+  }
+
+  //===--------------------------------------------------------------------===//
+  // Transformation methods:
+  //   These methods specify how each type of instruction is transformed by the
+  // NewInstructionCreator instance...
+  //===--------------------------------------------------------------------===//
+
+  void visitGetElementPtrInst(GetElementPtrInst *I) {
+    assert(0 && "Cannot transform get element ptr instructions yet!");
+  }
+
+  // Replace the load instruction with a new one.
+  void visitLoadInst(LoadInst *I) {
+    Instruction *PoolBase = createPoolBaseInstruction(I->getOperand(0));
+
+    // Cast our index to be a UIntTy so we can use it to index into the pool...
+    CastInst *Index = new CastInst(Constant::getNullConstant(POINTERTYPE),
+                                   Type::UIntTy, I->getOperand(0)->getName());
+
+    ReferencesToUpdate.push_back(RefToUpdate(Index, 0, I->getOperand(0)));
+
+    vector<Value*> Indices(I->idx_begin(), I->idx_end());
+    assert(Indices[0] == ConstantUInt::get(Type::UIntTy, 0) &&
+           "Cannot handle array indexing yet!");
+    Indices[0] = Index;
+    Instruction *NewLoad = new LoadInst(PoolBase, Indices, I->getName());
 
-    // Change everything that used the malloc to now use the pool alloc...
-    I->replaceAllUsesWith(Ptr);
+    // Replace the load instruction with the new load instruction...
+    BasicBlock::iterator II = ReplaceInstWith(I, NewLoad);
 
-    // Update the scalars array...
-    updateScalars(I, Ptr);
+    // Add the pool base calculator instruction before the load...
+    II = NewLoad->getParent()->getInstList().insert(II, PoolBase) + 1;
 
-    // Delete the instruction now.
-    delete I;
+    // Add the cast before the load instruction...
+    NewLoad->getParent()->getInstList().insert(II, Index);
+
+    // If not yielding a pool allocated pointer, use the new load value as the
+    // value in the program instead of the old load value...
+    //
+    if (!getScalar(I))
+      I->replaceAllUsesWith(NewLoad);
   }
 
-  // Convert the free instruction into a call to poolfree
-  void visitFreeInst(FreeInst *I) {
-    Value *Ptr = I->getOperand(0);
-    const ScalarInfo &SC = getScalar(Ptr);
-    BasicBlock *BB = I->getParent();
-    BasicBlock::iterator FI = find(BB->begin(), BB->end(), I);
-
-    // If the value is not an sbyte*, convert it now!
-    if (Ptr->getType() != PointerType::get(Type::SByteTy)) {
-      CastInst *CI = new CastInst(Ptr, PointerType::get(Type::SByteTy),
-                                  Ptr->getName());
-      FI = BB->getInstList().insert(FI, CI)+1;
-      Ptr = CI;
-    }
+  // Replace the store instruction with a new one.  In the store instruction,
+  // the value stored could be a pointer type, meaning that the new store may
+  // have to change one or both of it's operands.
+  //
+  void visitStoreInst(StoreInst *I) {
+    assert(getScalar(I->getOperand(1)) &&
+           "Store inst found only storing pool allocated pointer.  "
+           "Not imp yet!");
 
-    // Create a new call to poolfree before the free instruction
+    Value *Val = I->getOperand(0);  // The value to store...
+    // Check to see if the value we are storing is a data structure pointer...
+    if (const ScalarInfo *ValScalar = getScalar(I->getOperand(0)))
+      Val = Constant::getNullConstant(POINTERTYPE);  // Yes, store a dummy
+
+    Instruction *PoolBase = createPoolBaseInstruction(I->getOperand(1));
+
+    // Cast our index to be a UIntTy so we can use it to index into the pool...
+    CastInst *Index = new CastInst(Constant::getNullConstant(POINTERTYPE),
+                                   Type::UIntTy, I->getOperand(1)->getName());
+    ReferencesToUpdate.push_back(RefToUpdate(Index, 0, I->getOperand(1)));
+
+    vector<Value*> Indices(I->idx_begin(), I->idx_end());
+    assert(Indices[0] == ConstantUInt::get(Type::UIntTy, 0) &&
+           "Cannot handle array indexing yet!");
+    Indices[0] = Index;
+    Instruction *NewStore = new StoreInst(Val, PoolBase, Indices);
+
+    if (Val != I->getOperand(0))    // Value stored was a pointer?
+      ReferencesToUpdate.push_back(RefToUpdate(NewStore, 0, I->getOperand(0)));
+
+
+    // Replace the store instruction with the cast instruction...
+    BasicBlock::iterator II = ReplaceInstWith(I, Index);
+
+    // Add the pool base calculator instruction before the index...
+    II = Index->getParent()->getInstList().insert(II, PoolBase) + 2;
+
+    // Add the store after the cast instruction...
+    Index->getParent()->getInstList().insert(II, NewStore);
+  }
+
+
+  // Create call to poolalloc for every malloc instruction
+  void visitMallocInst(MallocInst *I) {
     vector<Value*> Args;
-    Args.push_back(SC.PoolHandle);
-    Args.push_back(Ptr);
-    CallInst *Call = new CallInst(PoolAllocator.PoolFree, Args);
-    FI = BB->getInstList().insert(FI, Call)+1;
+    Args.push_back(getScalarRef(I).Pool.Handle);
+    CallInst *Call = new CallInst(PoolAllocator.PoolAlloc, Args, I->getName());
+    ReplaceInstWith(I, Call);
+  }
 
-    // Remove the old free instruction...
-    delete BB->getInstList().remove(FI);
+  // Convert a call to poolfree for every free instruction...
+  void visitFreeInst(FreeInst *I) {
+    // Create a new call to poolfree before the free instruction
+    vector<Value*> Args;
+    Args.push_back(Constant::getNullConstant(POINTERTYPE));
+    Args.push_back(getScalarRef(I->getOperand(0)).Pool.Handle);
+    Instruction *NewCall = new CallInst(PoolAllocator.PoolFree, Args);
+    ReplaceInstWith(I, NewCall);
+    ReferencesToUpdate.push_back(RefToUpdate(NewCall, 0, I->getOperand(0)));
   }
 
   // visitCallInst - Create a new call instruction with the extra arguments for
@@ -348,56 +506,89 @@ public:
   //
   void visitCallInst(CallInst *I) {
     TransformFunctionInfo &TI = CallMap[I];
-    BasicBlock *BB = I->getParent();
-    BasicBlock::iterator CI = find(BB->begin(), BB->end(), I);
-    BB->getInstList().remove(CI);  // Remove the old call instruction
 
     // Start with all of the old arguments...
     vector<Value*> Args(I->op_begin()+1, I->op_end());
 
-    // Add all of the pool arguments...
-    for (unsigned i = 0, e = TI.ArgInfo.size(); i != e; ++i)
+    for (unsigned i = 0, e = TI.ArgInfo.size(); i != e; ++i) {
+      // Replace all of the pointer arguments with our new pointer typed values.
+      if (TI.ArgInfo[i].ArgNo != -1)
+        Args[TI.ArgInfo[i].ArgNo] = Constant::getNullConstant(POINTERTYPE);
+
+      // Add all of the pool arguments...
       Args.push_back(TI.ArgInfo[i].PoolHandle);
+    }
     
     Function *NF = PoolAllocator.getTransformedFunction(TI);
-    CallInst *NewCall = new CallInst(NF, Args, I->getName());
-    BB->getInstList().insert(CI, NewCall);
-
-    // Change everything that used the malloc to now use the pool alloc...
-    if (I->getType() != Type::VoidTy) {
-      I->replaceAllUsesWith(NewCall);
-
-      // Update the scalars array...
-      updateScalars(I, NewCall);
-    }
+    Instruction *NewCall = new CallInst(NF, Args, I->getName());
+    ReplaceInstWith(I, NewCall);
 
-    delete I;  // Delete the old call instruction now...
+    // Keep track of the mapping of operands so that we can resolve them to real
+    // values later.
+    Value *RetVal = NewCall;
+    for (unsigned i = 0, e = TI.ArgInfo.size(); i != e; ++i)
+      if (TI.ArgInfo[i].ArgNo != -1)
+        ReferencesToUpdate.push_back(RefToUpdate(NewCall, TI.ArgInfo[i].ArgNo+1,
+                                        I->getOperand(TI.ArgInfo[i].ArgNo+1)));
+      else
+        RetVal = 0;   // If returning a pointer, don't change retval...
+
+    // If not returning a pointer, use the new call as the value in the program
+    // instead of the old call...
+    //
+    if (RetVal)
+      I->replaceAllUsesWith(RetVal);
   }
 
+  // visitPHINode - Create a new PHI node of POINTERTYPE for all of the old Phi
+  // nodes...
+  //
   void visitPHINode(PHINode *PN) {
-    // Handle PHI Node
+    Value *DummyVal = Constant::getNullConstant(POINTERTYPE);
+    PHINode *NewPhi = new PHINode(POINTERTYPE, PN->getName());
+    for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
+      NewPhi->addIncoming(DummyVal, PN->getIncomingBlock(i));
+      ReferencesToUpdate.push_back(RefToUpdate(NewPhi, i*2, 
+                                               PN->getIncomingValue(i)));
+    }
+
+    ReplaceInstWith(PN, NewPhi);
   }
 
+  // visitReturnInst - Replace ret instruction with a new return...
   void visitReturnInst(ReturnInst *I) {
-    // Nothing of interest
+    Instruction *Ret = new ReturnInst(Constant::getNullConstant(POINTERTYPE));
+    ReplaceInstWith(I, Ret);
+    ReferencesToUpdate.push_back(RefToUpdate(Ret, 0, I->getOperand(0)));
   }
 
+  // visitSetCondInst - Replace a conditional test instruction with a new one
   void visitSetCondInst(SetCondInst *SCI) {
-    // hrm, notice a pattern?
+    BinaryOperator *I = (BinaryOperator*)SCI;
+    Value *DummyVal = Constant::getNullConstant(POINTERTYPE);
+    BinaryOperator *New = BinaryOperator::create(I->getOpcode(), DummyVal,
+                                                 DummyVal, I->getName());
+    ReplaceInstWith(I, New);
+
+    ReferencesToUpdate.push_back(RefToUpdate(New, 0, I->getOperand(0)));
+    ReferencesToUpdate.push_back(RefToUpdate(New, 1, I->getOperand(1)));
+
+    // Make sure branches refer to the new condition...
+    I->replaceAllUsesWith(New);
   }
 
   void visitInstruction(Instruction *I) {
-    cerr << "Unknown instruction to FunctionBodyTransformer:\n";
-    I->dump();
+    cerr << "Unknown instruction to FunctionBodyTransformer:\n" << I;
   }
-
 };
 
 
+
+
 static void addCallInfo(DataStructure *DS,
                         TransformFunctionInfo &TFI, CallInst *CI, int Arg, 
                         DSNode *GraphNode,
-                        map<DSNode*, Value*> &PoolDescriptors) {
+                        map<DSNode*, PoolInfo> &PoolDescs) {
   assert(CI->getCalledFunction() && "Cannot handle indirect calls yet!");
   assert(TFI.Func == 0 || TFI.Func == CI->getCalledFunction() &&
          "Function call record should always call the same function!");
@@ -413,20 +604,19 @@ static void addCallInfo(DataStructure *DS,
   // are providing.
   //
   for (df_iterator<DSNode*> I = df_begin(GraphNode), E = df_end(GraphNode);
-       I != E; ++I) {
-    TFI.ArgInfo.push_back(CallArgInfo(Arg, *I, PoolDescriptors[*I]));
-  }
+       I != E; ++I)
+    TFI.ArgInfo.push_back(CallArgInfo(Arg, *I, PoolDescs[*I].Handle));
 }
 
 
 // transformFunctionBody - This transforms the instruction in 'F' to use the
-// pools specified in PoolDescriptors when modifying data structure nodes
-// specified in the PoolDescriptors map.  Specifically, scalar values specified
-// in the Scalars vector must be remapped.  IPFGraph is the closed data
-// structure graph for F, of which the PoolDescriptor nodes come from.
+// pools specified in PoolDescs when modifying data structure nodes specified in
+// the PoolDescs map.  Specifically, scalar values specified in the Scalars
+// vector must be remapped.  IPFGraph is the closed data structure graph for F,
+// of which the PoolDescriptor nodes come from.
 //
 void PoolAllocate::transformFunctionBody(Function *F, FunctionDSGraph &IPFGraph,
-                                       map<DSNode*, Value*> &PoolDescriptors) {
+                                         map<DSNode*, PoolInfo> &PoolDescs) {
 
   // Loop through the value map looking for scalars that refer to nonescaping
   // allocations.  Add them to the Scalars vector.  Note that we may have
@@ -442,17 +632,17 @@ void PoolAllocate::transformFunctionBody(Function *F, FunctionDSGraph &IPFGraph,
          E = ValMap.end(); I != E; ++I) {
     const PointerValSet &PVS = I->second;  // Set of things pointed to by scalar
 
-    cerr << "Scalar Mapping from:"; I->first->dump();
-    cerr << "\nScalar Mapping to: "; PVS.print(cerr);
-
     // Check to see if the scalar points to a data structure node...
     for (unsigned i = 0, e = PVS.size(); i != e; ++i) {
       assert(PVS[i].Index == 0 && "Nonzero not handled yet!");
         
       // If the allocation is in the nonescaping set...
-      map<DSNode*, Value*>::iterator AI = PoolDescriptors.find(PVS[i].Node);
-      if (AI != PoolDescriptors.end()) // Add it to the list of scalars
-        Scalars.push_back(ScalarInfo(I->first, PVS[i].Node, AI->second));
+      map<DSNode*, PoolInfo>::iterator AI = PoolDescs.find(PVS[i].Node);
+      if (AI != PoolDescs.end()) {              // Add it to the list of scalars
+        Scalars.push_back(ScalarInfo(I->first, AI->second));
+        cerr << "\nScalar Mapping from:" << I->first
+             << "Scalar Mapping to: "; PVS.print(cerr);
+      }
     }
   }
 
@@ -462,7 +652,8 @@ void PoolAllocate::transformFunctionBody(Function *F, FunctionDSGraph &IPFGraph,
        << "': Found the following values that point to poolable nodes:\n";
 
   for (unsigned i = 0, e = Scalars.size(); i != e; ++i)
-    Scalars[i].Val->dump();
+    cerr << Scalars[i].Val;
+  cerr << "\n";
 
   // CallMap - Contain an entry for every call instruction that needs to be
   // transformed.  Each entry in the map contains information about what we need
@@ -470,7 +661,7 @@ void PoolAllocate::transformFunctionBody(Function *F, FunctionDSGraph &IPFGraph,
   //
   map<CallInst*, TransformFunctionInfo> CallMap;
 
-  // Now we need to figure out what called methods we need to transform, and
+  // Now we need to figure out what called functions we need to transform, and
   // how.  To do this, we look at all of the scalars, seeing which functions are
   // either used as a scalar value (so they return a data structure), or are
   // passed one of our scalar values.
@@ -481,7 +672,7 @@ void PoolAllocate::transformFunctionBody(Function *F, FunctionDSGraph &IPFGraph,
     // Check to see if the scalar _IS_ a call...
     if (CallInst *CI = dyn_cast<CallInst>(ScalarVal))
       // If so, add information about the pool it will be returning...
-      addCallInfo(DS, CallMap[CI], CI, -1, Scalars[i].Node, PoolDescriptors);
+      addCallInfo(DS, CallMap[CI], CI, -1, Scalars[i].Pool.Node, PoolDescs);
 
     // Check to see if the scalar is an operand to a call...
     for (Value::use_iterator UI = ScalarVal->use_begin(),
@@ -496,8 +687,8 @@ void PoolAllocate::transformFunctionBody(Function *F, FunctionDSGraph &IPFGraph,
         // than once!  It will get multiple entries for the first pointer.
 
         // Add the operand number and pool handle to the call table...
-        addCallInfo(DS, CallMap[CI], CI, OI-CI->op_begin()-1, Scalars[i].Node,
-                    PoolDescriptors);
+        addCallInfo(DS, CallMap[CI], CI, OI-CI->op_begin()-1,
+                    Scalars[i].Pool.Node, PoolDescs);
       }
     }
   }
@@ -505,13 +696,12 @@ void PoolAllocate::transformFunctionBody(Function *F, FunctionDSGraph &IPFGraph,
   // Print out call map...
   for (map<CallInst*, TransformFunctionInfo>::iterator I = CallMap.begin();
        I != CallMap.end(); ++I) {
-    cerr << "\nFor call: ";
-    I->first->dump();
+    cerr << "For call: " << I->first;
     I->second.finalizeConstruction();
     cerr << I->second.Func->getName() << " must pass pool pointer for args #";
     for (unsigned i = 0; i < I->second.ArgInfo.size(); ++i)
       cerr << I->second.ArgInfo[i].ArgNo << ", ";
-    cerr << "\n";
+    cerr << "\n\n";
   }
 
   // Loop through all of the call nodes, recursively creating the new functions
@@ -525,11 +715,11 @@ void PoolAllocate::transformFunctionBody(Function *F, FunctionDSGraph &IPFGraph,
 
     // Transform all of the functions we need, or at least ensure there is a
     // cached version available.
-    transformFunction(I->second, IPFGraph);
+    transformFunction(I->second, IPFGraph, PoolDescs);
   }
 
   // Now that all of the functions that we want to call are available, transform
-  // the local method so that it uses the pools locally and passes them to the
+  // the local function so that it uses the pools locally and passes them to the
   // functions that we just hacked up.
   //
 
@@ -545,18 +735,66 @@ void PoolAllocate::transformFunctionBody(Function *F, FunctionDSGraph &IPFGraph,
     // All all of the instructions that use the scalar as an operand...
     for (Value::use_iterator UI = ScalarVal->use_begin(),
            UE = ScalarVal->use_end(); UI != UE; ++UI)
-      InstToFix.push_back(dyn_cast<Instruction>(*UI));
+      InstToFix.push_back(cast<Instruction>(*UI));
   }
 
   // Eliminate duplicates by sorting, then removing equal neighbors.
   sort(InstToFix.begin(), InstToFix.end());
   InstToFix.erase(unique(InstToFix.begin(), InstToFix.end()), InstToFix.end());
 
-  // Use a FunctionBodyTransformer to transform all of the involved instructions
-  FunctionBodyTransformer FBT(*this, Scalars, CallMap);
-  for (unsigned i = 0, e = InstToFix.size(); i != e; ++i)
-    FBT.visit(InstToFix[i]);
+  // Loop over all of the instructions to transform, creating the new
+  // replacement instructions for them.  This also unlinks them from the
+  // function so they can be safely deleted later.
+  //
+  map<Value*, Value*> XFormMap;  
+  NewInstructionCreator NIC(*this, Scalars, CallMap, XFormMap);
+
+  // Visit all instructions... creating the new instructions that we need and
+  // unlinking the old instructions from the function...
+  //
+  for (unsigned i = 0, e = InstToFix.size(); i != e; ++i) {
+    cerr << "Fixing: " << InstToFix[i];
+    NIC.visit(InstToFix[i]);
+  }
+  //NIC.visit(InstToFix.begin(), InstToFix.end());
+
+  // Make all instructions we will delete "let go" of their operands... so that
+  // we can safely delete Arguments whose types have changed...
+  //
+  for_each(InstToFix.begin(), InstToFix.end(),
+           mem_fun(&Instruction::dropAllReferences));
+
+  // Loop through all of the pointer arguments coming into the function,
+  // replacing them with arguments of POINTERTYPE to match the function type of
+  // the function.
+  //
+  FunctionType::ParamTypes::const_iterator TI =
+    F->getFunctionType()->getParamTypes().begin();
+  for (Function::ArgumentListType::iterator I = F->getArgumentList().begin(),
+         E = F->getArgumentList().end(); I != E; ++I, ++TI) {
+    Argument *Arg = *I;
+    if (Arg->getType() != *TI) {
+      assert(isa<PointerType>(Arg->getType()) && *TI == POINTERTYPE);
+      Argument *NewArg = new Argument(*TI, Arg->getName());
+      XFormMap[Arg] = NewArg;  // Map old arg into new arg...
+
+
+      // Replace the old argument and then delete it...
+      delete F->getArgumentList().replaceWith(I, NewArg);
+    }
+  }
+
+  // Now that all of the new instructions have been created, we can update all
+  // of the references to dummy values to be references to the actual values
+  // that are computed.
+  //
+  NIC.updateReferences();
+
+  cerr << "TRANSFORMED FUNCTION:\n" << F;
+
 
+  // Delete all of the "instructions to fix"
+  for_each(InstToFix.begin(), InstToFix.end(), deleter<Instruction>);
 
   // Since we have liberally hacked the function to pieces, we want to inform
   // the datastructure pass that its internal representation is out of date.
@@ -635,41 +873,54 @@ static void CalculateNodeMapping(Function *F, TransformFunctionInfo &TFI,
 // nodes in the TransformFunctionInfo come out of callers data structure graph.
 //
 void PoolAllocate::transformFunction(TransformFunctionInfo &TFI,
-                                     FunctionDSGraph &CallerIPGraph) {
+                                     FunctionDSGraph &CallerIPGraph,
+                                     map<DSNode*, PoolInfo> &CallerPoolDesc) {
   if (getTransformedFunction(TFI)) return;  // Function xformation already done?
 
-  cerr << "**********\nEntering transformFunction for "
+  cerr << "********** Entering transformFunction for "
        << TFI.Func->getName() << ":\n";
   for (unsigned i = 0, e = TFI.ArgInfo.size(); i != e; ++i)
     cerr << "  ArgInfo[" << i << "] = " << TFI.ArgInfo[i].ArgNo << "\n";
   cerr << "\n";
 
-
   const FunctionType *OldFuncType = TFI.Func->getFunctionType();
 
   assert(!OldFuncType->isVarArg() && "Vararg functions not handled yet!");
 
   // Build the type for the new function that we are transforming
   vector<const Type*> ArgTys;
+  ArgTys.reserve(OldFuncType->getNumParams()+TFI.ArgInfo.size());
   for (unsigned i = 0, e = OldFuncType->getNumParams(); i != e; ++i)
     ArgTys.push_back(OldFuncType->getParamType(i));
 
+  const Type *RetType = OldFuncType->getReturnType();
+  
   // Add one pool pointer for every argument that needs to be supplemented.
-  ArgTys.insert(ArgTys.end(), TFI.ArgInfo.size(), PoolTy);
+  for (unsigned i = 0, e = TFI.ArgInfo.size(); i != e; ++i) {
+    if (TFI.ArgInfo[i].ArgNo == -1)
+      RetType = POINTERTYPE;  // Return a pointer
+    else
+      ArgTys[TFI.ArgInfo[i].ArgNo] = POINTERTYPE; // Pass a pointer
+    ArgTys.push_back(PointerType::get(CallerPoolDesc.find(TFI.ArgInfo[i].Node)
+                                        ->second.PoolType));
+  }
 
   // Build the new function type...
-  const // FIXME when types are not const
-  FunctionType *NewFuncType = FunctionType::get(OldFuncType->getReturnType(),
-                                                ArgTys,OldFuncType->isVarArg());
+  const FunctionType *NewFuncType = FunctionType::get(RetType, ArgTys,
+                                                      OldFuncType->isVarArg());
 
   // The new function is internal, because we know that only we can call it.
   // This also helps subsequent IP transformations to eliminate duplicated pool
-  // pointers. [in the future when they are implemented].
+  // pointers (which look like the same value is always passed into a parameter,
+  // allowing it to be easily eliminated).
   //
   Function *NewFunc = new Function(NewFuncType, true,
                                    TFI.Func->getName()+".poolxform");
   CurModule->getFunctionList().push_back(NewFunc);
 
+
+  cerr << "Created function prototype: " << NewFunc << "\n";
+
   // Add the newly formed function to the TransformedFunctions table so that
   // infinite recursion does not occur!
   //
@@ -686,12 +937,14 @@ void PoolAllocate::transformFunction(TransformFunctionInfo &TFI,
 
   // Now add all of the arguments corresponding to pools passed in...
   for (unsigned i = 0, e = TFI.ArgInfo.size(); i != e; ++i) {
+    CallArgInfo &AI = TFI.ArgInfo[i];
     string Name;
-    if (TFI.ArgInfo[i].ArgNo == -1)
-      Name = "retpool";
+    if (AI.ArgNo == -1)
+      Name = "ret";
     else
-      Name = ArgMap[TFI.ArgInfo[i].ArgNo]->getName();  // Get the arg name
-    Argument *NFA = new Argument(PoolTy, Name+".pool");
+      Name = ArgMap[AI.ArgNo]->getName();  // Get the arg name
+    const Type *Ty = PointerType::get(CallerPoolDesc[AI.Node].PoolType);
+    Argument *NFA = new Argument(Ty, Name+".pool");
     NewFunc->getArgumentList().push_back(NFA);
   }
 
@@ -705,7 +958,13 @@ void PoolAllocate::transformFunction(TransformFunctionInfo &TFI,
   //
   FunctionDSGraph &DSGraph = DS->getClosedDSGraph(NewFunc);  
 
-  // NodeMapping - Multimap