//===-- FreeRemoval.cpp - EmbeC transformation that removes frees ------------//
// 
//                          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.
// 
//===----------------------------------------------------------------------===//
//
// FIXME:
//  This pass needs to be cleaned up and better understood.  Some of the
//  functionality seems to be addressed with poolcheckalign() in the Check
//  Insertion pass; we should ensure that the functionality there is present in
//  mainline and supercedes what is implemented here.  Also, the checking of
//  pool operations should be understood and updated/corrected if needed.
//
// This pass appears to do two things:
//
//  o) It ensures that there are load/store checks on pointers that point to
//     type-known data but are loaded from type-unknown partitions.
//
//  o) It seems to perform some sort of sanity/correctness checking of pool
//     creation/destruction.
//
//===----------------------------------------------------------------------===//
//
// Original comment from initial implementation:
//
// Implementation of FreeRemoval.h : an EmbeC pass
// 
// Some assumptions:
// * Correctness of pool allocation
// * Destroys at end of functions.
// Pool pointer aliasing assumptions
// -pool pointer copies via gep's are removed
// -no phinode takes two pool pointers because then they would be the same pool
// Result: If we look at pool pointer defs and look for their uses... we check 
// that their only uses are calls to pool_allocs, pool_frees and pool_destroys.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "FreeRemoval"

#include "llvm/Module.h"
#include "llvm/Pass.h"
#include "llvm/Instructions.h"
#include "SafeDynMemAlloc.h"
#include "SCUtils.h"
#include <iostream>
using namespace llvm;


namespace llvm {
  RegisterPass<EmbeCFreeRemoval> Y("EmbeC", "EmbeC pass that removes all frees and issues warnings if behaviour has changed");
  
char EmbeCFreeRemoval::ID = 0;

// Check if SSA pool pointer variable V has uses other than alloc, free and 
// destroy
void
EmbeCFreeRemoval::checkPoolSSAVarUses(Function *F, Value *V, 
                         map<Value *, set<Instruction *> > &FuncPoolAllocs,
                         map<Value *, set<Instruction *> > &FuncPoolFrees, 
                         map<Value *, set<Instruction *> > &FuncPoolDestroys) {
  if (V->use_begin() != V->use_end()) {
    for (Value::use_iterator UI = V->use_begin(), UE = V->use_end();
         UI != UE; ++UI) {
      // Check that the use is nothing except a call to pool_alloc, pool_free
      // or pool_destroy
      if (Instruction *I = dyn_cast<Instruction>(*UI)) {
        // For global pools, we need to check that only uses within the
        // function under consideration are checked.
        if (I->getParent()->getParent() != F)
          continue;
      } else {
        continue;
      }

      if (CallInst *CI = dyn_cast<CallInst>(*UI)) {
        if (Function *calledF = dyn_cast<Function>(CI->getOperand(0))) {
          if (calledF == F) {
            int operandNo = 0;
            for (unsigned int i = 1; i < CI->getNumOperands(); i++)
              if (CI->getOperand(i) == V) {
                operandNo = i;
                break;
              }
            
            Value *formalParam = 0;
            int opi = 0;
            for (Function::arg_iterator I = calledF->arg_begin(), 
                                        E = calledF->arg_end();
                  I != E && opi < operandNo; ++I, ++opi)
              if (opi == operandNo - 1) 
                formalParam = I;

            if (formalParam == V) {
              ;
            } else {
              std::cerr << "EmbeC: " << F->getName() 
                << ": Recursion not supported for case classification\n";
              continue;
            }
          }

          if (!calledF->isDeclaration()) {
            // the pool pointer is passed to the called function
      
            // Find the formal parameter corresponding to the parameter V
            int operandNo = 0;
            unsigned int limit = CI->getNumOperands();
            for (unsigned int i = 1; i < limit; i++)
              if (CI->getOperand(i) == V) {
                operandNo = i;
                break;
              }
      
            Value *formalParam;
            int opi = 0;
            for (Function::arg_iterator I = calledF->arg_begin(), 
                                        E = calledF->arg_end();
                 I != E && opi < operandNo; ++I, ++opi)
              if (opi == operandNo - 1) 
                formalParam = I;
      
            // if the called function has undestroyed frees in pool formalParam
            if (FuncFreedPools[calledF].find(formalParam) != 
                FuncFreedPools[calledF].end() && 
                FuncDestroyedPools[calledF].find(formalParam) == 
                FuncDestroyedPools[calledF].end()) {
              FuncPoolFrees[V].insert(cast<Instruction>(*UI));
            }

            // if the called function has undestroyed allocs in formalParam
            if (FuncAllocedPools[calledF].find(formalParam) != 
                FuncAllocedPools[calledF].end()) {
              FuncPoolAllocs[V].insert(cast<Instruction>(*UI));
            }
      
            // if the called function has a destroy in formalParam
            if (FuncDestroyedPools[calledF].find(formalParam) != 
                FuncDestroyedPools[calledF].end()) {
              FuncPoolDestroys[V].insert(cast<Instruction>(*UI));
            }
          } else {
            // external function
            if (calledF->getName() == PoolI) {
              // Insert call to poolmakeunfreeable after every poolinit since 
              // we do not free memory to the system for safety in all cases.
              //CallInst::Create(PoolMakeUnfreeable, make_vector(V, 0), "", 
              //             CI->getNext()); //taken care of in runtime library
              moduleChanged = true;
            } else if (calledF->getName() == PoolA) {
              FuncPoolAllocs[V].insert(cast<Instruction>(*UI));
            } else if (calledF->getName() == PoolF) {
              FuncPoolFrees[V].insert(cast<Instruction>(*UI));
            } else if (calledF->getName() == PoolD) {
              FuncPoolDestroys[V].insert(cast<Instruction>(*UI));
            } else if (calledF->getName() == PoolMUF) {
              // Ignore
            } else if (calledF->getName() == PoolCh) {
              // Ignore
            } else if (calledF->getName() == PoolAA) {
                BasicBlock::iterator it(CI);
                FuncPoolAllocs[V].insert(cast<Instruction>(++it));
            } else {
              hasError = true;
              std::cerr << "EmbeC: " << F->getName() << ": Unrecognized pool variable use \n";
              //        abort();
            }
          }
        } else {
          // Find the formal parameter corresponding to the parameter V
          int operandNo = 0;
          for (unsigned int i = 1; i < CI->getNumOperands(); i++)
            if (CI->getOperand(i) == V)
              operandNo = i;

          EQTDDataStructures::callee_iterator CalleesI =
            PoolInfo->callee_begin(CI), CalleesE = PoolInfo->callee_end(CI);

          for (; CalleesI != CalleesE; ++CalleesI) {
            Function *calledF = (Function *)(*CalleesI);
            
            PoolInfo->getFuncInfoOrClone(*calledF);
            
            /*
              if (PAFI->PoolArgFirst == PAFI->PoolArgLast ||
              operandNo-1 < PAFI->PoolArgFirst ||
              operandNo-1 >= PAFI->PoolArgLast)
              continue;
            */

            Value *formalParam;
            int opi = 0;
            for (Function::arg_iterator I = calledF->arg_begin(), 
                                        E = calledF->arg_end();
                 I != E && opi < operandNo; ++I, ++opi)
              if (opi == operandNo-1) 
                formalParam = I;
            
            // if the called function has undestroyed frees in pool formalParam
            if (FuncFreedPools[calledF].find(formalParam) != 
                FuncFreedPools[calledF].end() && 
                FuncDestroyedPools[calledF].find(formalParam) == 
                FuncDestroyedPools[calledF].end()) {
              FuncPoolFrees[V].insert(cast<Instruction>(*UI));
            }

            // if the called function has undestroyed allocs in formalParam
            if (FuncAllocedPools[calledF].find(formalParam) != 
                FuncAllocedPools[calledF].end()) {
              FuncPoolAllocs[V].insert(cast<Instruction>(*UI));
            }
            
            // if the called function has a destroy in formalParam
            if (FuncDestroyedPools[calledF].find(formalParam) != 
                FuncDestroyedPools[calledF].end()) {
              FuncPoolDestroys[V].insert(cast<Instruction>(*UI));
            }
          }
        }
      } else {
        hasError = true;
        std::cerr << "EmbeC: " << F->getName() << ": Unrecognized pool variable use \n";
      }   
    }
  }
}

// Propagate that the pool V is a collapsed pool to each of the callees of F
// that have V as argument
void
EmbeCFreeRemoval::propagateCollapsedInfo (Function *F, Value *V) {
  for (Value::use_iterator UI = V->use_begin(), UE = V->use_end();
       UI != UE; ++UI) {
    if (CallInst *CI = dyn_cast<CallInst>(*UI)) {
      if (Function *calledF = dyn_cast<Function>(CI->getOperand(0))) {
        if (calledF == F) {
          // Quick check for the common case
          // Find the formal parameter corresponding to the parameter V
          int operandNo = 0;
          for (unsigned int i = 1; i < CI->getNumOperands(); i++)
            if (CI->getOperand(i) == V) {
              operandNo = i;
              break;
            }
          
          Value *formalParam;
          int opi = 0;
          for (Function::arg_iterator I = calledF->arg_begin(), 
                                      E = calledF->arg_end();
               I != E && opi < operandNo; ++I, ++opi)
            if (opi == operandNo - 1) 
              formalParam = I; 

          if (formalParam == V) {
            // This is the common case.
          } else {
            std::cerr << "EmbeC: " << F->getName() 
              << ": Recursion not supported\n";
            abort();
            continue;
          }
        }

        if (!calledF->isDeclaration()) {
          // the pool pointer is passed to the called function
    
          // Find the formal parameter corresponding to the parameter V
          int operandNo = 0;
          for (unsigned int i = 1; i < CI->getNumOperands(); i++)
            if (CI->getOperand(i) == V) {
              operandNo = i;
              break;
            }
          
          Value *formalParam;
          int opi = 0;
          for (Function::arg_iterator I = calledF->arg_begin(), 
           E = calledF->arg_end();
               I != E && opi < operandNo; ++I, ++opi)
            if (opi == operandNo - 1) 
              formalParam = I;
          
          CollapsedPoolPtrs[calledF].insert(formalParam);
        } 
      } else {
        // indirect function call
  
        //  std::pair<EQTDDataStructures::ActualCalleesTy::const_iterator, EQTDDataStructures::ActualCalleesTy::const_iterator> Callees = AC.equal_range(CI);
  
        // Find the formal parameter corresponding to the parameter V
        int operandNo = 0;
        for (unsigned int i = 1; i < CI->getNumOperands(); i++)
          if (CI->getOperand(i) == V)
            operandNo = i;
        
        EQTDDataStructures::callee_iterator CalleesI =
          PoolInfo->callee_begin(CI),  CalleesE = PoolInfo->callee_end(CI);
        
        for (; CalleesI != CalleesE; ++CalleesI) {
          Function *calledF = (Function *)(*CalleesI);
          
          PoolInfo->getFuncInfoOrClone(*calledF);
          
          /*
            if (PAFI->PoolArgFirst == PAFI->PoolArgLast ||
            operandNo-1 < PAFI->PoolArgFirst ||
            operandNo-1 >= PAFI->PoolArgLast)
            continue;
          */
          
          Value *formalParam;
          int opi = 0;
          for (Function::arg_iterator I = calledF->arg_begin(), 
                                      E = calledF->arg_end();
               I != E && opi < operandNo; ++I, ++opi)
            if (opi == operandNo-1) 
              formalParam = I;

          CollapsedPoolPtrs[calledF].insert(formalParam);
        }
      }
    } 
  }
}

// Returns true if BB1 follows BB2 in some path in F
static bool
followsBlock(BasicBlock *BB1, BasicBlock *BB2, Function *F,
             set<BasicBlock *> visitedBlocks) {
  for (succ_iterator BBSI = succ_begin(BB2),
                     BBSE = succ_end(BB2); BBSI != BBSE; ++BBSI) {
    if (visitedBlocks.find(*BBSI) == visitedBlocks.end()) {
      if (*BBSI == BB1) {
        return true;
      } else {
        visitedBlocks.insert(*BBSI);
        if (followsBlock(BB1, *BBSI, F, visitedBlocks))
          return true;
      }
    }
  }

  return false;
}

#if 0
// Checks if Inst1 follows Inst2 in any path in the function F.
static bool followsInst(Instruction *Inst1, Instruction *Inst2, Function *F) {
  if (Inst1->getParent() == Inst2->getParent()) {
    for (BasicBlock::iterator BBI = Inst2, BBE = Inst2->getParent()->end();
   BBI != BBE; ++BBI)
      if (Inst1 == &(*BBI))
  return true;
  }
  set<BasicBlock *> visitedBlocks;
  return followsBlock(Inst1->getParent(), Inst2->getParent(), F, 
          visitedBlocks);
}
#endif

#if 0
static void printSets(set<Value *> &FuncPoolPtrs,
          map<Value *, set<Instruction *> > &FuncPoolFrees,
          map<Value *, set<Instruction *> > &FuncPoolAllocs) {
  for (set<Value *>::iterator I = FuncPoolPtrs.begin(), E = FuncPoolPtrs.end();
       I != E; ++I) {
    std::cerr << "Pool Variable: " << *I << "\n";
    if (FuncPoolFrees[*I].size()) {
      std::cerr << "Frees :" << "\n";
      for (set<Instruction *>::iterator FreeI = 
       FuncPoolFrees[*I].begin(), FreeE = FuncPoolFrees[*I].end();
     FreeI != FreeE; ++FreeI) {
  CallInst *CInst = dyn_cast<CallInst>(*FreeI);
  Function *CIF = dyn_cast<Function>(CInst->getOperand(0));
  std::cerr << CIF->getName() << "\n";
      }
    }
    if (FuncPoolAllocs[*I].size()) {
      std::cerr << "Allocs :" << "\n";
      for (set<Instruction *>::iterator AllocI = 
       FuncPoolAllocs[*I].begin(), AllocE = FuncPoolAllocs[*I].end();
     AllocI != AllocE; ++AllocI) {  
  CallInst *CInst = dyn_cast<CallInst>(*AllocI);
  Function *CIF = dyn_cast<Function>(CInst->getOperand(0));
  std::cerr << CIF->getName() << "\n";  
      }
    }
  }
}
#endif

DSNode *
EmbeCFreeRemoval::guessDSNode (Value *v, DSGraph &G, PA::FuncInfo *PAFI) {
  if (std::find(Visited.begin(), Visited.end(), v) != Visited.end())
    return 0;
  Visited.push_back(v);
  if (isa<PointerType>(v->getType())) {
    DSNode *r = G.getNodeForValue(v).getNode();
    if (r && PAFI->PoolDescriptors.count(r))
      return r;
  }
  DSNode *retDSNode = 0;
  if (BinaryOperator *Bop = dyn_cast<BinaryOperator>(v)) {
    retDSNode = guessDSNode(Bop->getOperand(0), G, PAFI);
    if (!retDSNode) retDSNode = guessDSNode(Bop->getOperand(0), G, PAFI);
  } else if (CastInst *CI = dyn_cast<CastInst>(v)) {
    retDSNode = guessDSNode(CI->getOperand(0), G, PAFI);
  } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(v)) {
    retDSNode = guessDSNode(GEP->getPointerOperand(), G, PAFI);
  } else if (LoadInst *LI = dyn_cast<LoadInst>(v)) {
    //hope its collapsed node ...
    retDSNode = guessDSNode(LI->getOperand(0), G, PAFI);
  } else if (PHINode* PN =dyn_cast<PHINode>(v)) {
    for (unsigned idx = 0; idx < PN->getNumIncomingValues(); ++idx) {
      if (!retDSNode) {
        retDSNode = guessDSNode(PN->getIncomingValue(idx), G, PAFI);
      } else {
        break;
      }
    }
  } else if (CallInst* CI =dyn_cast<CallInst>(v)) {
    for (unsigned idx = 1; idx < CI->getNumOperands(); ++idx) {
      if (!retDSNode) {
        retDSNode = guessDSNode(CI->getOperand(idx), G, PAFI);
      } else {
        break;
      }
    }
  }
  return retDSNode;
}

//
// Disabled guessPoolPtrAndInsertCheck(); no one seems to use it right now.
//
#if 0
  void EmbeCFreeRemoval::guessPoolPtrAndInsertCheck(PA::FuncInfo *PAFI, Value *oldI, Instruction  *I, Value *pOpI, DSGraph *oldG) {
    Visited.clear();
    //follow up v through the ssa def0use chains
    DSNode *DSN = guessDSNode(oldI, oldG, PAFI);
    //    assert(DSN && "can not guess the pool ptr");
    //    assert(PAFI->PoolDescriptors.count(DSN) && "no pool descriptor found \n");
    CastInst *CastI = 
      new CastInst(pOpI, 
       PointerType::getUnqual(Type::Int8Ty), "casted", I);
    if (DSN) {

    CallInst::Create(PoolCheck, 
     make_vector(PAFI->PoolDescriptors[DSN], CastI, 0),
     "", I);
    } else {
      Type *VoidPtrTy = PointerType::getUnqual(Type::Int8Ty); 
      const Type *PoolDescType = 
  ArrayType::get(VoidPtrTy, 50);

      const PointerType *PoolDescPtr = PointerType::getUnqual(PoolDescType);      
      Value *PH = Constant::getNullValue(PoolDescPtr);
      CallInst::Create(PoolCheck, 
     make_vector(PH, CastI, 0),
     "", I);
      
    }
    DEBUG(std::cerr << "inserted a pool check for unknown node \n");

  }
#endif
  
void
EmbeCFreeRemoval::insertNonCollapsedChecks (Function *Forig, Function *F,
                                            DSNode *DSN) {
  assert(!DSN->isNodeCompletelyFolded() && "its collapsed! \n");
  if (DSN->isUnknownNode()) return; //we'll handle it separately
  //Assuming alignment is the beginning of a node, owise its runtime failure
  bool isClonedFunc;
  PA::FuncInfo* PAFI = PoolInfo->getFuncInfoOrClone(*F);
  if (PoolInfo->getFuncInfo(*F))
    isClonedFunc = false;
  else
    isClonedFunc = true;
  
  DSGraph* oldG = PoolInfo->getDSGraph(*Forig);
  
  // For each scalar pointer in the original function
  for (DSGraph::ScalarMapTy::iterator SMI = oldG->getScalarMap().begin(), 
   SME = oldG->getScalarMap().end(); SMI != SME; ++SMI) {
    DSNodeHandle &GH = SMI->second;

    //We need to insert checks to all the uses of this ptr
    if (DSN == GH.getNode()) {
      // We are any way checking all arrays
      if ((GH.getOffset()) && (DSN->isArray())) return;
      Value * Offset = getGlobalContext().getConstantInt(Type::Int32Ty, GH.getOffset());

      Value *NewPtr = (Value *)(SMI->first);
      if (isClonedFunc) {
        NewPtr = PAFI->ValueMap[SMI->first];
      }
      if (!NewPtr)
        continue;

      const Type *VoidPtrTy = PointerType::getUnqual(Type::Int8Ty);

      for (Value::use_iterator UI = NewPtr->use_begin(), UE = NewPtr->use_end();
           UI != UE; ++UI) {
        // If the use is the 2nd operand of store, insert a runtime check
        if (StoreInst *StI = dyn_cast<StoreInst>(*UI)) {
          if (StI->getOperand(1) == NewPtr) {
            moduleChanged = true;
            Value * CastPH = castTo(PAFI->PoolDescriptors[DSN], VoidPtrTy, "", StI);
            Value * CastI  = castTo(StI->getOperand(1), VoidPtrTy, "casted", StI);
            std::vector<Value *> args = make_vector(CastPH, CastI, Offset, 0);
            CallInst::Create(PoolCheck, args.begin(), args.end(), "", StI);
            std::cerr << " inserted poolcheck for noncollapsed pool\n";
          }
        } else if (CallInst *CallI = dyn_cast<CallInst>(*UI)) {
          // If this is a function pointer read from a collapsed node,
          // reject the code
          if (CallI->getOperand(0) == NewPtr) {
            std::cerr << 
              "EmbeC: Error - Function pointer read from collapsed node\n";
            abort();
          }
        } else if (LoadInst *LdI = dyn_cast<LoadInst>(*UI)) {
          if (LdI->getOperand(0) == NewPtr) {
            moduleChanged = true;
            Value *CastPH = castTo (PAFI->PoolDescriptors[DSN], VoidPtrTy, "", LdI);
            Value *CastI  = castTo (LdI->getOperand(0), VoidPtrTy, "casted", LdI);
            std::vector<Value *> args = make_vector(CastPH, CastI, Offset, 0);
            CallInst::Create(PoolCheck, args.begin(), args.end(), "", LdI);
            std::cerr << " inserted poolcheck for noncollpased pool\n";
          }
        }
      }
    }
  }
}

// Insert runtime checks. Called on the functions in the existing program
void
EmbeCFreeRemoval::addRuntimeChecks(Function *F, Function *Forig) {
  //The  following code is phased out, a newer version is insert.cpp 
  
#if 0
  bool isClonedFunc;
  PA::FuncInfo* PAFI = PoolInfo->getFuncInfoOrClone(*F);

  if (PoolInfo->getFuncInfo(*F))
    isClonedFunc = false;
  else
    isClonedFunc = true;
  
  if (!PAFI->PoolDescriptors.empty()) {
  // For each scalar pointer in the original function
    for (DSGraph::ScalarMapTy::iterator SMI = oldG->getScalarMap().begin(), 
     SME = oldG->getScalarMap().end(); SMI != SME; ++SMI) {
      DSNodeHandle &GH = SMI->second;
      DSNode *DSN = GH.getNode();
      if (!DSN) 
  continue;
      if (DSN->isUnknownNode()) {
  // Report an error if we see loads or stores on the pointer
  Value *NewPtr = SMI->first;
  if (isClonedFunc) {
    if (PAFI->ValueMap.count(SMI->first))
      NewPtr = PAFI->ValueMap[SMI->first];
    else continue;
  }
  if (!NewPtr)
    continue;
  for (Value::use_iterator UI = NewPtr->use_begin(), 
         UE = NewPtr->use_end(); UI != UE; ++UI) {
    if (StoreInst *StI = dyn_cast<StoreInst>(*UI)) {
      if (StI->getOperand(1) == NewPtr) {
        guessPoolPtrAndInsertCheck(PAFI, SMI->first, StI, NewPtr, oldG);
        std::cerr << 
    "EmbeC: In function " << F->getName() << ": Presence of an unknown node can invalidate pool allocation\n";
        break;
      }
    } else if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) {
      //We'll try to guess a pool descriptor and insert a check
      //if it fails then ok too bad ;)
      //Add guess the pool handle
      guessPoolPtrAndInsertCheck(PAFI, SMI->first, LI, NewPtr, oldG);
      std::cerr << 
        "EmbeC: In function " << F->getName() << ": Presence of an unknown node can invalidate pool allocation\n";
      break;
    } else if (CallInst *CallI = dyn_cast<CallInst>(*UI)) {
        // If this is a function pointer read from a collapsed node,
        // reject the code
        if (CallI->getOperand(0) == NewPtr) {
    std::cerr << 
      "EmbeC: Error - Function pointer read from Unknown node\n";
    abort();
    
        }
    }
  }
      }
      if (PAFI->PoolDescriptors.count(DSN)) {
  // If the node pointed to, corresponds to a collapsed pool 
  if (CollapsedPoolPtrs[F].find(PAFI->PoolDescriptors[DSN]) !=
      CollapsedPoolPtrs[F].end()) {
    // find uses of the coresponding new pointer
    Value *NewPtr = SMI->first;
    if (isClonedFunc) {
      if (PAFI->ValueMap.count(SMI->first)) {
        NewPtr = PAFI->ValueMap[SMI->first];
        if (!PAFI->NewToOldValueMap.count(NewPtr)) {
    std::cerr << "WARNING : checks for NewPtr are not inserted\n";
    abort();
    continue;
        }
      } else {
        std::cerr << "WARNING : checks for NewPtr are not inserted\n";
        abort();
        continue;
      }
    }
    if (!NewPtr)
      continue;
    for (Value::use_iterator UI = NewPtr->use_begin(), 
     UE = NewPtr->use_end(); UI != UE; ++UI) {
      // If the use is the 2nd operand of store, insert a runtime check
      if (StoreInst *StI = dyn_cast<StoreInst>(*UI)) {
        if (StI->getOperand(1) == NewPtr) {
    if (!isa<GlobalVariable>(StI->getOperand(1))) { 
      moduleChanged = true;
      CastInst *CastI = 
        new CastInst(StI->getOperand(1), 
         PointerType::getUnqual(Type::Int8Ty), "casted", StI);
      CallInst::Create(PoolCheck, 
             make_vector(PAFI->PoolDescriptors[DSN], CastI, 0),
             "", StI);
      DEBUG(std::cerr << " inserted poolcheck for collpased pool\n";);
    } else {
      std::cerr << "WARNING DID not insert a check for collapsed global store";
    }
        }
      } else if (CallInst *CallI = dyn_cast<CallInst>(*UI)) {
        // If this is a function pointer read from a collapsed node,
        // reject the code
        if (CallI->getOperand(0) == NewPtr) {
    std::cerr << 
      "EmbeC: Error - Function pointer read from collapsed node\n";
    abort();
        }
      } else if (LoadInst *LdI = dyn_cast<LoadInst>(*UI)) {
        if (LdI->getOperand(0) == NewPtr) {
    if (!isa<GlobalVariable>(LdI->getOperand(0))) { 
      moduleChanged = true;
      CastInst *CastI = 
        new CastInst(LdI->getOperand(0), 
         PointerType::getUnqual(Type::Int8Ty), "casted", LdI);
      CallInst::Create(PoolCheck, 
           make_vector(PAFI->PoolDescriptors[DSN], CastI, 0),
             "", LdI);
      std::cerr << " inserted poolcheck for collpased pool\n";
    } else {
      std::cerr << "WARNING DID not insert a check for collapsed global load";
    }
        }
      }
    }
  }
      }
    }
  }
#endif  
}

bool
EmbeCFreeRemoval::runOnModule(Module &M) {
#if 1
  //
  // FIXME:
  //  Currently, we do not need this pass.  However, removing it from the sc
  //  tool causes other passes to fail for reasons unknown.  So, for now, leave
  //  this pass in the sc tool, but don't let it do anything.
  //
  std::cerr << "WARNING: EmbeCFreeRemoval Pass Executed, but it does NOTHING!"
            << std::endl;
  return false;
#endif
  CurModule = &M;
  moduleChanged = false;
  hasError = false;
  // Insert prototypes in the module
  // NB: This has to be in sync with the types in PoolAllocate.cpp
  const Type *VoidPtrTy = PointerType::getUnqual(Type::Int8Ty);

  const Type *PoolDescType = 
    //    StructType::get(make_vector<const Type*>(VoidPtrTy, VoidPtrTy, 
    //               Type::Int32Ty, Type::Int32Ty, 0));
    ArrayType::get(VoidPtrTy, 50);

  const PointerType *PoolDescPtr = PointerType::getUnqual(PoolDescType);
  FunctionType *PoolMakeUnfreeableTy = 
    FunctionType::get(Type::VoidTy,
          make_vector<const Type*>(PoolDescPtr, 0),
          false);

  FunctionType *PoolCheckTy = 
    FunctionType::get(Type::VoidTy,
          make_vector<const Type*>(VoidPtrTy, VoidPtrTy, Type::Int32Ty, 0),
          false);
  
  PoolMakeUnfreeable = CurModule->getOrInsertFunction("poolmakeunfreeable", 
                  PoolMakeUnfreeableTy);
  
  PoolCheck = CurModule->getOrInsertFunction("poolcheckalign", PoolCheckTy);
  
  moduleChanged = true;

  Function *mainF = M.getFunction("main");
  
  if (!mainF) {
    mainF = M.getFunction("MAIN__");
    if (!mainF) {
      hasError = true;
      std::cerr << "EmbeC: Function main required\n";
      return false;
    }
  }

  // Bottom up on the call graph
  // TODO: Take care of recursion/mutual recursion
  PoolInfo = &getAnalysis<PoolAllocateGroup>();
  assert (PoolInfo && "Must run Pool Allocation Pass first!\n");
  CallGraph &CG = getAnalysis<CallGraph>();
  //  BUDS = &getAnalysis<EQTDDataStructures>();
  //  BUDS = PoolInfo->getDataStructures();
  //  TDDS = &getAnalysis<TDDataStructures>();
  // For each function, all its pool SSA variables including its arguments
  map<Function *, set<Value *> > FuncPoolPtrs;

  for (po_iterator<CallGraph*> CGI = po_begin(&CG), 
                               CGE = po_end(&CG); CGI != CGE; ++CGI) {
    Function *F = (*CGI)->getFunction();
    
    // Ignore nodes representing external functions in the call graph
    if (!F)
      continue;
    
    // Pool SSA variables that are used in allocs, destroy and free or calls 
    // to functions that escaped allocs, destroys and frees respectively.
    map<Value *, set<Instruction *> > FuncPoolAllocs, FuncPoolFrees, 
                                      FuncPoolDestroys;
    
    // Traverse the function finding poolfrees and calls to functions that
    // have poolfrees without pooldestroys on all paths in that function.
    
    if (!F->isDeclaration()) {
      // For each pool pointer def check its uses and ensure that there are 
      // no uses other than the pool_alloc, pool_free or pool_destroy calls
      
      PA::FuncInfo* PAFI = PoolInfo->getFuncInfoOrClone(*F);
      
      // If the function has no pool pointers (args or SSA), ignore the 
      // function.
      if (!PAFI) continue;
      
      if (PAFI->Clone && PAFI->Clone != F) continue;

      if (!PAFI->PoolDescriptors.empty()) {
        for (std::map<const DSNode*, Value*>::iterator PoolDI = 
         PAFI->PoolDescriptors.begin(), PoolDE = 
         PAFI->PoolDescriptors.end(); PoolDI != PoolDE; ++PoolDI) {
          checkPoolSSAVarUses(F, PoolDI->second, FuncPoolAllocs, 
          FuncPoolFrees, FuncPoolDestroys);
          FuncPoolPtrs[F].insert(PoolDI->second);
        }
      }
      else
        continue;

      /*
      if (F->getName() == "main") {
  std::cerr << "In Function " << F->getName() << "\n";
  printSets(FuncPoolPtrs[F], FuncPoolFrees, FuncPoolAllocs);
      }
      */

      /*
      // Implementing the global analysis that checks that
      // - For each poolfree, if there is a poolallocate on another pool
      //   before a pooldestroy on any path, then this is a case 3 pool.
      //   If there is a poolallocate on the same pool before a pooldestroy
      //   on any path, then it is a case 2 pool.
     
      // Do a local analysis on these and update the pool variables that escape
      // the function (poolfrees without pooldestroys, poolallocs)
      // For each instruction in the list of free/calls to free, do
      // the following: go down to the bottom of the function looking for 
      // allocs till you see destroy. If you don't see destroy on some path, 
      // update escape list.
      // Update escape list with allocs without destroys for arguments
      // as well as arguments that are destroyed.
      // TODO: Modify implementation so you are not checking that there is no
      // alloc to other pools follows a free in the function, but to see that 
      // there is a destroy on pool between a free and an alloc to another pool
      // Current Assumption: destroys are at the end of a function.
      if (!FuncPoolFrees.empty()) {
  std::cerr << "In Function " << F->getName() << "\n";
  for (map<Value *, set<Instruction *> >::iterator ValueI = 
         FuncPoolFrees.begin(), ValueE = FuncPoolFrees.end();
       ValueI != ValueE; ++ValueI) {
    bool case3found = false, case2found = false;
    for (set<Instruction *>::iterator FreeInstI = 
     (*ValueI).second.begin(), 
     FreeInstE = (*ValueI).second.end();
         FreeInstI != FreeInstE && !case3found; ++FreeInstI) {
      // For each free instruction or call to a function which escapes
      // a free in pool (*ValueI).first
      for (set<Value *>::iterator PoolPtrsI = FuncPoolPtrs[F].begin(), 
       PoolPtrsE = FuncPoolPtrs[F].end(); 
     PoolPtrsI != PoolPtrsE && !case3found; 
     ++PoolPtrsI) {
        // For each pool pointer other than the one in the free 
        // instruction under consideration, check that allocs to it
        // don't follow the free on any path.
        if (*PoolPtrsI !=  (*ValueI).first) {
    map<Value *, set<Instruction *> >::iterator AllocSet= 
      FuncPoolAllocs.find(*PoolPtrsI);
    if (AllocSet != FuncPoolAllocs.end())
      for (set<Instruction *>::iterator AllocInstI = 
       (*AllocSet).second.begin(), 
       AllocInstE = (*AllocSet).second.end();
           AllocInstI != AllocInstE && !case3found; ++AllocInstI)
        if (followsInst(*AllocInstI, *FreeInstI, F) &&
      *AllocInstI != *FreeInstI)
          case3found = true;
        } else {
    map<Value *, set<Instruction *> >::iterator AllocSet= 
      FuncPoolAllocs.find(*PoolPtrsI);
    if (AllocSet != FuncPoolAllocs.end())
      for (set<Instruction *>::iterator AllocInstI = 
       (*AllocSet).second.begin(), 
       AllocInstE = (*AllocSet).second.end();
           AllocInstI != AllocInstE && !case3found; ++AllocInstI)
        if (followsInst(*AllocInstI, *FreeInstI, F) &&
      *AllocInstI != *FreeInstI)
          case2found = true;
        }
      }
    }
    if (case3found && case2found)
      std::cerr << (*ValueI).first->getName() 
          << ": Case 2 and 3 detected\n";
    else if (case3found)
      std::cerr << (*ValueI).first->getName() 
          << ": Case 3 detected\n";
    else if (case2found)
      std::cerr << (*ValueI).first->getName() 
          << ": Case 2 detected\n";
    else
      std::cerr << (*ValueI).first->getName() 
          << ": Case 1 detected\n";
  }
      }
      */
      
      // Assumption: if we have pool_destroy on a pool in a function, then it
      // is on all exit paths of the function
      // TODO: correct later. 
      // Therefore, all pool ptr arguments that have frees but no destroys
      // escape the function. Similarly all pool ptr arguments that have
      // allocs but no destroys escape the function      
      for (set<Value *>::iterator PoolPtrsI = FuncPoolPtrs[F].begin(), 
       PoolPtrsE = FuncPoolPtrs[F].end(); PoolPtrsI != PoolPtrsE; 
     ++PoolPtrsI) {
        if (isa<Argument>(*PoolPtrsI)) {
          // Only for pool pointers that are arguments
          if (FuncPoolFrees.find(*PoolPtrsI) != FuncPoolFrees.end() &&
              FuncPoolFrees[*PoolPtrsI].size())
            FuncFreedPools[F].insert(*PoolPtrsI);
          if (FuncPoolAllocs.find(*PoolPtrsI) != FuncPoolAllocs.end() &&
              FuncPoolAllocs[*PoolPtrsI].size())
            FuncAllocedPools[F].insert(*PoolPtrsI);
          if (FuncPoolDestroys.find(*PoolPtrsI) != FuncPoolDestroys.end() &&
              FuncPoolDestroys[*PoolPtrsI].size()) {
            FuncDestroyedPools[F].insert(*PoolPtrsI);
          }
        } 
      }
      
      // TODO
      // For each function, check that the frees in the function are case 1 
      // i.e. there are no mallocs between the free and its corresponding 
      // pool_destroy and then remove the pool free call.
    }
  }
    
  // Now, traverse the call graph top-down, updating information about pool 
  // pointers that may be collapsed and inserting runtime checks
  ReversePostOrderTraversal<CallGraph*> RPOT(&CG); 
  for (ReversePostOrderTraversal<CallGraph*>::rpo_iterator CGI = RPOT.begin(),
   CGE = RPOT.end(); CGI != CGE; ++CGI) {
    Function *F = (*CGI)->getFunction();
    
    if (!F)
      continue;
    
    // Ignore nodes representing external functions in the call graph
    if (!F->isDeclaration()) {
      // For each pool pointer def check its uses and ensure that there are 
      // no uses other than the pool_alloc, pool_free or pool_destroy calls
      
      PA::FuncInfo* PAFI = PoolInfo->getFuncInfoOrClone(*F);

      if (!PAFI) continue;

      if (PAFI->Clone && PAFI->Clone != F) continue;

      Function *Forig;
      if (PAFI->Clone) {
        for(Module::iterator MI = M.begin(), ME = M.end(); MI != ME; ++MI)
          if (PoolInfo->getFuncInfo(*MI))
            if (PoolInfo->getFuncInfo(*MI) == PAFI) {
              Forig = &*MI;
              break;
            }
      } else
        Forig = F;

      if (FuncPoolPtrs.count(F)) {
        for (set<Value *>::iterator PDI = FuncPoolPtrs[F].begin(), 
                                    PDE = FuncPoolPtrs[F].end();
             PDI != PDE; ++PDI) {
          if (isa<Argument>(*PDI)) {
            if (CollapsedPoolPtrs[F].find(*PDI) != CollapsedPoolPtrs[F].end())
              propagateCollapsedInfo(F, *PDI);
          } else {
            // This pool is poolinit'ed in this function or is a global pool
            const DSNode *PDINode;
            
            for (std::map<const DSNode*, Value*>::iterator PDMI = 
                 PAFI->PoolDescriptors.begin(), 
                 PDME = PAFI->PoolDescriptors.end(); PDMI != PDME; ++PDMI)
              if (PDMI->second == *PDI) {
                PDINode = PDMI->first;
                break;
              }
      
            if (PDINode->isNodeCompletelyFolded()) {
              CollapsedPoolPtrs[F].insert(*PDI);
        
              for (unsigned i = 0 ; i < PDINode->getNumLinks(); ++i)
                if (PDINode->getLink(i).getNode())
                  if (!PDINode->getLink(i).getNode()->isNodeCompletelyFolded()){
                    //Collapsed to non-collapsed, so insert a check
#if 1
                    //
                    // FIXME:
                    //  We need to ensure that these checks are performed by
                    //  the check insertion pass.
                    //
                    insertNonCollapsedChecks (Forig, F,
                                              PDINode->getLink(i).getNode());
#endif
                    //        abort();
                    break;
                  }

              // Propagate this information to all the callees only if this
              // is not a global pool
              if (!isa<GlobalVariable>(*PDI))
                propagateCollapsedInfo(F, *PDI);
            }
          }
        }

        // At this point, we know all the collapsed pools in this function
        // Add run-time checks before all stores to pointers pointing to 
        // collapsed pools
        addRuntimeChecks(F, Forig);  
      }
    }
  }
  return moduleChanged;
}

}
Pass *createEmbeCFreeRemovalPass() { return new EmbeCFreeRemoval(); }