bool SpDefUseInstrumenter::runOnModule(Module &M) {

  cerr << "instrument: --- Def-Use pair Spectrum ---\n";

  Function *Main = M.getFunction("main");
  LLVMContext &C = M.getContext();
  
  if (Main == 0) {
    cerr << "WARNING: cannot insert def-use instrumentation into a module"
         << " with no main function!\n";
    return false;  // No main, no instrumentation!
  }

  // Add library function prototype
  Constant *SpFn = M.getOrInsertFunction("_updateSpectrum", 
                          Type::getVoidTy(C), 
                          Type::getInt32Ty(C),  // spectrum index
                          Type::getInt32Ty(C),  // component index
                          NULL);


  unsigned spectrumIndex = IndexManager::getSpectrumIndex();
  unsigned nDefs = 0;
  unsigned nUses = 0;

  // Loop through all functions within module
  for (Module::iterator F = M.begin(), ME = M.end(); F != ME; ++F) {

    // skip function declarations
    if(F->isDeclaration()) 
      continue;

    // skip the _registerAll function
    if(F->getName()=="_registerAll")
      continue;
    
    // Loop through all basic blocks within function
    for (Function::iterator B = F->begin(), FE = F->end(); B != FE; ++B) {
      //skip dead blocks
      //is this really safe??
      BasicBlock *bb = B;
      if (B!=F->begin() && (pred_begin(bb)==pred_end(bb))) continue; //skip dead blocks

      // Loop through all instructions within basic block
      for (BasicBlock::iterator I = B->begin(), BE = B->end(); I != BE; I++) {
    
        if(isa<DbgDeclareInst>(*I)) {

          // extract source file information from debug intrinsic
          DbgDeclareInst &DDI = cast<DbgDeclareInst>(*I);
          std::string file, dir;
          std::string name;
          GlobalVariable *gv = cast<GlobalVariable>(DDI.getVariable());
          if(!gv->hasInitializer()) continue;
          ConstantStruct *cs = cast<ConstantStruct>(gv->getInitializer());
          llvm::GetConstantStringInfo(cs->getOperand(2), name);
          unsigned int line = unsigned(cast<ConstantInt>(cs->getOperand(4))->getZExtValue());
          Value *V = cast<Value>(cs->getOperand(3));
          GlobalVariable *gv2 = cast<GlobalVariable>(cast<ConstantExpr>(V)->getOperand(0));
          if(!gv2->hasInitializer()) continue;
          ConstantStruct *cs2 = cast<ConstantStruct>(gv2->getInitializer());
          llvm::GetConstantStringInfo(cs2->getOperand(3), file);
          llvm::GetConstantStringInfo(cs2->getOperand(4), dir);

          // get the allocation instruction of the variable definition
          AllocaInst *AI;
          if(isa<AllocaInst>(DDI.getAddress())) {
            AI = cast<AllocaInst>(DDI.getAddress());
          } else if (isa<BitCastInst>(DDI.getAddress())) {
            AI = cast<AllocaInst>(cast<BitCastInst>(DDI.getAddress())->getOperand(0));
          } else {
            continue;
          }

          nDefs++;

          // add calls to lib function for each use of the variable
          int currUses = 0;
          for(AllocaInst::use_iterator U = AI->use_begin(), UE = AI->use_end(); U != UE; ++U) {
            if(isa<Instruction>(*U)) {

              User *user = *U;
              Instruction *insertInst = (Instruction*)user;

              // find most likely context location of use
              int useline = line;
              std::string usefile = file, usedir = dir;
              BasicBlock *parent = insertInst->getParent();
              BasicBlock::iterator inst = parent->begin();
              while(((Instruction *)inst) != insertInst  &&  inst != parent->end()) {
            	  /*TODO: solve DbgStopPointInst problem*/
            	/*if(isa<DbgStopPointInst>(*inst)) {
                  DbgStopPointInst &DSPI = cast<DbgStopPointInst>(*inst);
                  llvm::GetConstantStringInfo(DSPI.getDirectory(), usedir);
                  llvm::GetConstantStringInfo(DSPI.getFileName(), usefile);
                  useline = DSPI.getLine();
                }*/
                inst++;
              }

//.........这里部分代码省略.........

/*
 * Rewrite OpenMP call sites and their associated kernel functions  -- the folloiwng pattern
   call void @GOMP_parallel_start(void (i8*)* @_Z20initialize_variablesiPfS_.omp_fn.4, i8* %.omp_data_o.5571, i32 0) nounwind
  call void @_Z20initialize_variablesiPfS_.omp_fn.4(i8* %.omp_data_o.5571) nounwind
  call void @GOMP_parallel_end() nounwind
 */
void HeteroOMPTransform::rewrite_omp_call_sites(Module &M) {
	SmallVector<Instruction *, 16> toDelete;
	DenseMap<Value *, Value *> ValueMap;
	
	for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I){
		if (!I->isDeclaration()) {
			
			for (Function::iterator BBI = I->begin(), BBE = I->end(); BBI != BBE; ++BBI) {
				bool match = false;
				for (BasicBlock::iterator INSNI = BBI->begin(), INSNE = BBI->end(); INSNI != INSNE; ++INSNI) {
					if (isa<CallInst>(INSNI)) {
						CallSite CI(cast<Instruction>(INSNI));
						if (CI.getCalledFunction() != NULL){ 
							string called_func_name = CI.getCalledFunction()->getName();
							if (called_func_name == OMP_PARALLEL_START_NAME && CI.arg_size() == 3) {
								// change alloc to malloc_shared
								// %5 = call i8* @_Z13malloc_sharedm(i64 20)       ; <i8*> [#uses=5]
								// %6 = bitcast i8* %5 to float*                   ; <float*> [#uses=2]
								AllocaInst *AllocCall;
								Value *arg_0 = CI.getArgument(0); // function
								Value *arg_1 = CI.getArgument(1);  // context
								Value *loop_ub = NULL;
								Function *function;
								BitCastInst* BCI;
								Function *kernel_function;
								BasicBlock::iterator iI(*INSNI); 
								//BasicBlock::iterator iJ = iI+1; 
								iI++; iI++;
								//BasicBlock::iterator iK = iI;  
								CallInst /**next,*/ *next_next; 
								if (arg_0 != NULL && arg_1 != NULL /*&& (next = dyn_cast<CallInst>(*iJ))*/ 
									&& (next_next = dyn_cast<CallInst>(iI)) && (next_next->getCalledFunction() != NULL) 
									&& (next_next->getCalledFunction()->getName() == OMP_PARALLEL_END_NAME)
									&& (BCI = dyn_cast<BitCastInst>(arg_1)) && (AllocCall = dyn_cast<AllocaInst>(BCI->getOperand(0))) 
									&& (function = dyn_cast<Function>(arg_0)) && (loop_ub = find_loop_upper_bound (AllocCall)) 
									&& (kernel_function=convert_to_kernel_function (M, function))){
									
										SmallVector<Value*, 16> Args;
										Args.push_back(AllocCall->getArraySize());
										Instruction *MallocCall = CallInst::Create(mallocFnTy, Args, "", AllocCall);
										CastInst *MallocCast = CastInst::Create(Instruction::BitCast, MallocCall, AllocCall->getType(), "", AllocCall);
										ValueMap[AllocCall] = MallocCast;
										//AllocCall->replaceAllUsesWith(MallocCall);
										// Add offload function
										Args.clear();
										Args.push_back(loop_ub);
										Args.push_back(BCI);
										Args.push_back(kernel_function);
										if (offloadFnTy == NULL) {
											init_offload_type(M, kernel_function);
										}
										
										Instruction *call = CallInst::Create(offloadFnTy, Args, "", INSNI);
										
										if (find(toDelete.begin(), toDelete.end(), AllocCall) == toDelete.end()){
											toDelete.push_back(AllocCall);
										}
										toDelete.push_back(&(*INSNI));
										match = true;
								}
							}
							else if (called_func_name == OMP_PARALLEL_END_NAME && CI.arg_size() == 0 && match) {
								toDelete.push_back(&(*INSNI));
								match = false;
							}
							else if (match) {
								toDelete.push_back(&(*INSNI));
							}
						}
					}
				}
			}
		}

	}

	/* Replace AllocCalls by MallocCalls */
	for(DenseMap<Value *, Value *>::iterator I = ValueMap.begin(), E = ValueMap.end(); I != E; I++) {
		I->first->replaceAllUsesWith(I->second);
	}

	/* delete the instructions for get_omp_num_thread and get_omp_thread_num */
	while(!toDelete.empty()) {
		Instruction *g = toDelete.back();
		toDelete.pop_back();
		g->eraseFromParent();
	}

}

bool PruneEH::runOnSCC(CallGraphSCC &SCC) {
  SmallPtrSet<CallGraphNode *, 8> SCCNodes;
  CallGraph &CG = getAnalysis<CallGraph>();
  bool MadeChange = false;

  // Fill SCCNodes with the elements of the SCC.  Used for quickly
  // looking up whether a given CallGraphNode is in this SCC.
  for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I)
    SCCNodes.insert(*I);

  // First pass, scan all of the functions in the SCC, simplifying them
  // according to what we know.
  for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I)
    if (Function *F = (*I)->getFunction())
      MadeChange |= SimplifyFunction(F);

  // Next, check to see if any callees might throw or if there are any external
  // functions in this SCC: if so, we cannot prune any functions in this SCC.
  // Definitions that are weak and not declared non-throwing might be 
  // overridden at linktime with something that throws, so assume that.
  // If this SCC includes the unwind instruction, we KNOW it throws, so
  // obviously the SCC might throw.
  //
  bool SCCMightUnwind = false, SCCMightReturn = false;
  for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); 
       (!SCCMightUnwind || !SCCMightReturn) && I != E; ++I) {
    Function *F = (*I)->getFunction();
    if (F == 0) {
      SCCMightUnwind = true;
      SCCMightReturn = true;
    } else if (F->isDeclaration() || F->mayBeOverridden()) {
      SCCMightUnwind |= !F->doesNotThrow();
      SCCMightReturn |= !F->doesNotReturn();
    } else {
      bool CheckUnwind = !SCCMightUnwind && !F->doesNotThrow();
      bool CheckReturn = !SCCMightReturn && !F->doesNotReturn();

      if (!CheckUnwind && !CheckReturn)
        continue;

      // Check to see if this function performs an unwind or calls an
      // unwinding function.
      for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
        if (CheckUnwind && isa<UnwindInst>(BB->getTerminator())) {
          // Uses unwind!
          SCCMightUnwind = true;
        } else if (CheckReturn && isa<ReturnInst>(BB->getTerminator())) {
          SCCMightReturn = true;
        }

        // Invoke instructions don't allow unwinding to continue, so we are
        // only interested in call instructions.
        if (CheckUnwind && !SCCMightUnwind)
          for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
            if (CallInst *CI = dyn_cast<CallInst>(I)) {
              if (CI->doesNotThrow()) {
                // This call cannot throw.
              } else if (Function *Callee = CI->getCalledFunction()) {
                CallGraphNode *CalleeNode = CG[Callee];
                // If the callee is outside our current SCC then we may
                // throw because it might.
                if (!SCCNodes.count(CalleeNode)) {
                  SCCMightUnwind = true;
                  break;
                }
              } else {
                // Indirect call, it might throw.
                SCCMightUnwind = true;
                break;
              }
            }
        if (SCCMightUnwind && SCCMightReturn) break;
      }
    }
  }

  // If the SCC doesn't unwind or doesn't throw, note this fact.
  if (!SCCMightUnwind || !SCCMightReturn)
    for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
      Attributes NewAttributes = Attribute::None;

      if (!SCCMightUnwind)
        NewAttributes |= Attribute::NoUnwind;
      if (!SCCMightReturn)
        NewAttributes |= Attribute::NoReturn;

      Function *F = (*I)->getFunction();
      const AttrListPtr &PAL = F->getAttributes();
      const AttrListPtr &NPAL = PAL.addAttr(~0, NewAttributes);
      if (PAL != NPAL) {
        MadeChange = true;
        F->setAttributes(NPAL);
      }
    }

  for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
    // Convert any invoke instructions to non-throwing functions in this node
    // into call instructions with a branch.  This makes the exception blocks
    // dead.
    if (Function *F = (*I)->getFunction())
//.........这里部分代码省略.........

/// InputFilename is a LLVM bitcode file. Read it using bitcode reader.
/// Collect global functions and symbol names in symbols vector.
/// Collect external references in references vector.
/// Return LTO_READ_SUCCESS if there is no error.
enum LTOStatus
LTO::readLLVMObjectFile(const std::string &InputFilename,
                        NameToSymbolMap &symbols,
                        std::set<std::string> &references)
{
  Module *m = getModule(InputFilename);
  if (!m)
    return LTO_READ_FAILURE;

  // Collect Target info
  getTarget(m);

  if (!Target)
    return LTO_READ_FAILURE;
  
  // Use mangler to add GlobalPrefix to names to match linker names.
  // FIXME : Instead of hard coding "-" use GlobalPrefix.
  Mangler mangler(*m, Target->getTargetAsmInfo()->getGlobalPrefix());
  modules.push_back(m);
  
  for (Module::iterator f = m->begin(), e = m->end(); f != e; ++f) {
    LTOLinkageTypes lt = getLTOLinkageType(f);
    LTOVisibilityTypes vis = getLTOVisibilityType(f);
    if (!f->isDeclaration() && lt != LTOInternalLinkage
        && strncmp (f->getName().c_str(), "llvm.", 5)) {
      int alignment = ( 16 > f->getAlignment() ? 16 : f->getAlignment());
      LLVMSymbol *newSymbol = new LLVMSymbol(lt, vis, f, f->getName(), 
                                             mangler.getValueName(f),
                                             Log2_32(alignment));
      symbols[newSymbol->getMangledName()] = newSymbol;
      allSymbols[newSymbol->getMangledName()] = newSymbol;
    }

    // Collect external symbols referenced by this function.
    for (Function::iterator b = f->begin(), fe = f->end(); b != fe; ++b) 
      for (BasicBlock::iterator i = b->begin(), be = b->end(); 
           i != be; ++i) {
        for (unsigned count = 0, total = i->getNumOperands(); 
             count != total; ++count)
          findExternalRefs(i->getOperand(count), references, mangler);
      }
  }
    
  for (Module::global_iterator v = m->global_begin(), e = m->global_end();
       v !=  e; ++v) {
    LTOLinkageTypes lt = getLTOLinkageType(v);
    LTOVisibilityTypes vis = getLTOVisibilityType(v);
    if (!v->isDeclaration() && lt != LTOInternalLinkage
        && strncmp (v->getName().c_str(), "llvm.", 5)) {
      const TargetData *TD = Target->getTargetData();
      LLVMSymbol *newSymbol = new LLVMSymbol(lt, vis, v, v->getName(), 
                                             mangler.getValueName(v),
                                             TD->getPreferredAlignmentLog(v));
      symbols[newSymbol->getMangledName()] = newSymbol;
      allSymbols[newSymbol->getMangledName()] = newSymbol;

      for (unsigned count = 0, total = v->getNumOperands(); 
           count != total; ++count)
        findExternalRefs(v->getOperand(count), references, mangler);

    }
  }
  
  return LTO_READ_SUCCESS;
}

// UnifyAllExitNodes - Unify all exit nodes of the CFG by creating a new
// BasicBlock, and converting all returns to unconditional branches to this
// new basic block.  The singular exit node is returned.
//
// If there are no return stmts in the Function, a null pointer is returned.
//
bool UnifyFunctionExitNodes::runOnFunction(Function &F) {
  // Loop over all of the blocks in a function, tracking all of the blocks that
  // return.
  //
  std::vector<BasicBlock*> ReturningBlocks;
  std::vector<BasicBlock*> UnwindingBlocks;
  std::vector<BasicBlock*> UnreachableBlocks;
  for(Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
    if (isa<ReturnInst>(I->getTerminator()))
      ReturningBlocks.push_back(I);
    else if (isa<UnwindInst>(I->getTerminator()))
      UnwindingBlocks.push_back(I);
    else if (isa<UnreachableInst>(I->getTerminator()))
      UnreachableBlocks.push_back(I);

  // Handle unwinding blocks first.
  if (UnwindingBlocks.empty()) {
    UnwindBlock = 0;
  } else if (UnwindingBlocks.size() == 1) {
    UnwindBlock = UnwindingBlocks.front();
  } else {
    UnwindBlock = BasicBlock::Create("UnifiedUnwindBlock", &F);
    new UnwindInst(UnwindBlock);

    for (std::vector<BasicBlock*>::iterator I = UnwindingBlocks.begin(),
           E = UnwindingBlocks.end(); I != E; ++I) {
      BasicBlock *BB = *I;
      BB->getInstList().pop_back();  // Remove the unwind insn
      BranchInst::Create(UnwindBlock, BB);
    }
  }

  // Then unreachable blocks.
  if (UnreachableBlocks.empty()) {
    UnreachableBlock = 0;
  } else if (UnreachableBlocks.size() == 1) {
    UnreachableBlock = UnreachableBlocks.front();
  } else {
    UnreachableBlock = BasicBlock::Create("UnifiedUnreachableBlock", &F);
    new UnreachableInst(UnreachableBlock);

    for (std::vector<BasicBlock*>::iterator I = UnreachableBlocks.begin(),
           E = UnreachableBlocks.end(); I != E; ++I) {
      BasicBlock *BB = *I;
      BB->getInstList().pop_back();  // Remove the unreachable inst.
      BranchInst::Create(UnreachableBlock, BB);
    }
  }

  // Now handle return blocks.
  if (ReturningBlocks.empty()) {
    ReturnBlock = 0;
    return false;                          // No blocks return
  } else if (ReturningBlocks.size() == 1) {
    ReturnBlock = ReturningBlocks.front(); // Already has a single return block
    return false;
  }

  // Otherwise, we need to insert a new basic block into the function, add a PHI
  // nodes (if the function returns values), and convert all of the return
  // instructions into unconditional branches.
  //
  BasicBlock *NewRetBlock = BasicBlock::Create("UnifiedReturnBlock", &F);

  SmallVector<Value *, 4> Phis;
  unsigned NumRetVals = ReturningBlocks[0]->getTerminator()->getNumOperands();
  if (NumRetVals == 0)
    ReturnInst::Create(NULL, NewRetBlock);
  else if (const StructType *STy = dyn_cast<StructType>(F.getReturnType())) {
    Instruction *InsertPt = NULL;
    if (NumRetVals == 0)
      InsertPt = NewRetBlock->getFirstNonPHI();
    PHINode *PN = NULL;
    for (unsigned i = 0; i < NumRetVals; ++i) {
      if (InsertPt)
        PN = PHINode::Create(STy->getElementType(i), "UnifiedRetVal." 
                         + utostr(i), InsertPt);
      else
        PN = PHINode::Create(STy->getElementType(i), "UnifiedRetVal." 
                         + utostr(i), NewRetBlock);
      Phis.push_back(PN);
      InsertPt = PN;
    }
    ReturnInst::Create(&Phis[0], NumRetVals, NewRetBlock);
  }
  else {
    // If the function doesn't return void... add a PHI node to the block...
    PHINode *PN = PHINode::Create(F.getReturnType(), "UnifiedRetVal");
    NewRetBlock->getInstList().push_back(PN);
    Phis.push_back(PN);
    ReturnInst::Create(PN, NewRetBlock);
  }

  // Loop over all of the blocks, replacing the return instruction with an
//.........这里部分代码省略.........

//
// Method: runOnModule()
//
// Description:
//  Entry point for this LLVM pass.
//  Clone functions that take LoadInsts as arguments
//
// Inputs:
//  M - A reference to the LLVM module to transform
//
// Outputs:
//  M - The transformed LLVM module.
//
// Return value:
//  true  - The module was modified.
//  false - The module was not modified.
//
bool LoadArgs::runOnModule(Module& M) {
  std::map<std::pair<Function*, const Type * > , Function* > fnCache;
  bool changed;
  do { 
    changed = false;
    for (Module::iterator Func = M.begin(); Func != M.end(); ++Func) {
      for (Function::iterator B = Func->begin(), FE = Func->end(); B != FE; ++B) {
        for (BasicBlock::iterator I = B->begin(), BE = B->end(); I != BE;) {
          CallInst *CI = dyn_cast<CallInst>(I++);
          if(!CI)
            continue;

          if(CI->hasByValArgument())
            continue;
          // if the CallInst calls a function, that is externally defined,
          // or might be changed, ignore this call site.
          Function *F = CI->getCalledFunction();
          if (!F || (F->isDeclaration() || F->mayBeOverridden())) 
            continue;
          if(F->hasStructRetAttr())
            continue;
          if(F->isVarArg())
            continue;

          // find the argument we must replace
          Function::arg_iterator ai = F->arg_begin(), ae = F->arg_end();
          unsigned argNum = 0;
          for(; argNum < CI->getNumArgOperands();argNum++, ++ai) {
            // do not care about dead arguments
            if(ai->use_empty())
              continue;
            if(F->getAttributes().getParamAttributes(argNum).hasAttrSomewhere(Attribute::SExt) ||
               F->getAttributes().getParamAttributes(argNum).hasAttrSomewhere(Attribute::ZExt))
              continue;
            if (isa<LoadInst>(CI->getArgOperand(argNum)))
              break;
          }

          // if no argument was a GEP operator to be changed 
          if(ai == ae)
            continue;

          LoadInst *LI = dyn_cast<LoadInst>(CI->getArgOperand(argNum));
          Instruction * InsertPt = &(Func->getEntryBlock().front());
          AllocaInst *NewVal = new AllocaInst(LI->getType(), "",InsertPt);

          StoreInst *Copy = new StoreInst(LI, NewVal);
          Copy->insertAfter(LI);
          /*if(LI->getParent() != CI->getParent())
            continue;
          // Also check that there is no store after the load.
          // TODO: Check if the load/store do not alias.
          BasicBlock::iterator bii = LI->getParent()->begin();
          Instruction *BII = bii;
          while(BII != LI) {
            ++bii;
            BII = bii;
          }
          while(BII != CI) {
            if(isa<StoreInst>(BII))
              break;
            ++bii;
            BII = bii;
          }
          if(isa<StoreInst>(bii)){
            continue;
          }*/

          // Construct the new Type
          // Appends the struct Type at the beginning
          std::vector<Type*>TP;
          for(unsigned c = 0; c < CI->getNumArgOperands();c++) {
            if(c == argNum)
              TP.push_back(LI->getPointerOperand()->getType());
            TP.push_back(CI->getArgOperand(c)->getType());
          }

          //return type is same as that of original instruction
          FunctionType *NewFTy = FunctionType::get(CI->getType(), TP, false);
          numSimplified++;
          //if(numSimplified > 1000)
          //return true;

//.........这里部分代码省略.........

bool TailCallElim::runOnFunction(Function &F) {
  // If this function is a varargs function, we won't be able to PHI the args
  // right, so don't even try to convert it...
  if (F.getFunctionType()->isVarArg()) return false;

  BasicBlock *OldEntry = 0;
  bool TailCallsAreMarkedTail = false;
  SmallVector<PHINode*, 8> ArgumentPHIs;
  bool MadeChange = false;
  bool FunctionContainsEscapingAllocas = false;

  // CannotTCETailMarkedCall - If true, we cannot perform TCE on tail calls
  // marked with the 'tail' attribute, because doing so would cause the stack
  // size to increase (real TCE would deallocate variable sized allocas, TCE
  // doesn't).
  bool CannotTCETailMarkedCall = false;

  // Loop over the function, looking for any returning blocks, and keeping track
  // of whether this function has any non-trivially used allocas.
  for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
    if (FunctionContainsEscapingAllocas && CannotTCETailMarkedCall)
      break;

    FunctionContainsEscapingAllocas |=
      CheckForEscapingAllocas(BB, CannotTCETailMarkedCall);
  }
  
  /// FIXME: The code generator produces really bad code when an 'escaping
  /// alloca' is changed from being a static alloca to being a dynamic alloca.
  /// Until this is resolved, disable this transformation if that would ever
  /// happen.  This bug is PR962.
  if (FunctionContainsEscapingAllocas)
    return false;

  // Second pass, change any tail calls to loops.
  for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
    if (ReturnInst *Ret = dyn_cast<ReturnInst>(BB->getTerminator())) {
      bool Change = ProcessReturningBlock(Ret, OldEntry, TailCallsAreMarkedTail,
                                          ArgumentPHIs,CannotTCETailMarkedCall);
      if (!Change && BB->getFirstNonPHIOrDbg() == Ret)
        Change = FoldReturnAndProcessPred(BB, Ret, OldEntry,
                                          TailCallsAreMarkedTail, ArgumentPHIs,
                                          CannotTCETailMarkedCall);
      MadeChange |= Change;
    }
  }

  // If we eliminated any tail recursions, it's possible that we inserted some
  // silly PHI nodes which just merge an initial value (the incoming operand)
  // with themselves.  Check to see if we did and clean up our mess if so.  This
  // occurs when a function passes an argument straight through to its tail
  // call.
  if (!ArgumentPHIs.empty()) {
    for (unsigned i = 0, e = ArgumentPHIs.size(); i != e; ++i) {
      PHINode *PN = ArgumentPHIs[i];

      // If the PHI Node is a dynamic constant, replace it with the value it is.
      if (Value *PNV = SimplifyInstruction(PN)) {
        PN->replaceAllUsesWith(PNV);
        PN->eraseFromParent();
      }
    }
  }

  // Finally, if this function contains no non-escaping allocas, or calls
  // setjmp, mark all calls in the function as eligible for tail calls
  //(there is no stack memory for them to access).
  if (!FunctionContainsEscapingAllocas && !F.callsFunctionThatReturnsTwice())
    for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
      for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
        if (CallInst *CI = dyn_cast<CallInst>(I)) {
          CI->setTailCall();
          MadeChange = true;
        }

  return MadeChange;
}

bool llvm::InputValues::runOnModule(Module& M) {

	module = &M;

	initializeWhiteList();

    collectMainArguments();
int one=0;
 errs()<<"\n------------------------------------------------\n";
	for(Module::iterator Fit = M.begin(), Fend = M.end(); Fit != Fend; Fit++){

		for (Function::iterator BBit = Fit->begin(), BBend = Fit->end(); BBit != BBend; BBit++) {
			
			for (BasicBlock::iterator Iit = BBit->begin(), Iend = BBit->end(); Iit != Iend; Iit++) {
			
				if(one<2)
				{
			    Value* V_in;
			     //FIXME: Temporary assignment of the tainted source for testing...
			     if(BBit->getName()=="BB_146")
			     {
			    //   errs() << "Inside BB_0";
			      if(LoadInst *LI = dyn_cast<LoadInst>(Iit))  
			       {
			     //   LI->dump();
			        V_in = LI->getPointerOperand();
			        errs() <<"\ntaint source " << LI->getName() << " ";
			        errs() << V_in;
			        insertInInputDepValues(V_in);
			        //NumInputValues++;
			        one++;
			        }
			     }
			     
			     }



				if (CallInst *CI = dyn_cast<CallInst>(Iit)) {

					if (isMarkedCallInst(CI)){

						//Values returned by marked instructions
						insertInInputDepValues(CI);

						for(unsigned int i = 0; i < CI->getNumOperands(); i++){

							if (CI->getOperand(i)->getType()->isPointerTy()){
								//Arguments with pointer type of marked functions
						//		insertInInputDepValues(CI->getOperand(i));
							}

						}

					}

				}

			}

		}

	}

 errs()<<"\n------------------------------------------------\n";
	NumInputValues = inputValues.size();

	//We don't modify anything, so we must return false;
	return false;
}

/// splitLiveRangesAcrossInvokes - Each value that is live across an unwind edge
/// we spill into a stack location, guaranteeing that there is nothing live
/// across the unwind edge.  This process also splits all critical edges
/// coming out of invoke's.
void SjLjEHPass::
splitLiveRangesLiveAcrossInvokes(SmallVector<InvokeInst*,16> &Invokes) {
  // First step, split all critical edges from invoke instructions.
  for (unsigned i = 0, e = Invokes.size(); i != e; ++i) {
    InvokeInst *II = Invokes[i];
    SplitCriticalEdge(II, 0, this);
    SplitCriticalEdge(II, 1, this);
    assert(!isa<PHINode>(II->getNormalDest()) &&
           !isa<PHINode>(II->getUnwindDest()) &&
           "critical edge splitting left single entry phi nodes?");
  }

  Function *F = Invokes.back()->getParent()->getParent();

  // To avoid having to handle incoming arguments specially, we lower each arg
  // to a copy instruction in the entry block.  This ensures that the argument
  // value itself cannot be live across the entry block.
  BasicBlock::iterator AfterAllocaInsertPt = F->begin()->begin();
  while (isa<AllocaInst>(AfterAllocaInsertPt) &&
        isa<ConstantInt>(cast<AllocaInst>(AfterAllocaInsertPt)->getArraySize()))
    ++AfterAllocaInsertPt;
  for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end();
       AI != E; ++AI) {
    // This is always a no-op cast because we're casting AI to AI->getType() so
    // src and destination types are identical. BitCast is the only possibility.
    CastInst *NC = new BitCastInst(
      AI, AI->getType(), AI->getName()+".tmp", AfterAllocaInsertPt);
    AI->replaceAllUsesWith(NC);
    // Normally its is forbidden to replace a CastInst's operand because it
    // could cause the opcode to reflect an illegal conversion. However, we're
    // replacing it here with the same value it was constructed with to simply
    // make NC its user.
    NC->setOperand(0, AI);
  }

  // Finally, scan the code looking for instructions with bad live ranges.
  for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
    for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E; ++II) {
      // Ignore obvious cases we don't have to handle.  In particular, most
      // instructions either have no uses or only have a single use inside the
      // current block.  Ignore them quickly.
      Instruction *Inst = II;
      if (Inst->use_empty()) continue;
      if (Inst->hasOneUse() &&
          cast<Instruction>(Inst->use_back())->getParent() == BB &&
          !isa<PHINode>(Inst->use_back())) continue;

      // If this is an alloca in the entry block, it's not a real register
      // value.
      if (AllocaInst *AI = dyn_cast<AllocaInst>(Inst))
        if (isa<ConstantInt>(AI->getArraySize()) && BB == F->begin())
          continue;

      // Avoid iterator invalidation by copying users to a temporary vector.
      SmallVector<Instruction*,16> Users;
      for (Value::use_iterator UI = Inst->use_begin(), E = Inst->use_end();
           UI != E; ++UI) {
        Instruction *User = cast<Instruction>(*UI);
        if (User->getParent() != BB || isa<PHINode>(User))
          Users.push_back(User);
      }

      // Find all of the blocks that this value is live in.
      std::set<BasicBlock*> LiveBBs;
      LiveBBs.insert(Inst->getParent());
      while (!Users.empty()) {
        Instruction *U = Users.back();
        Users.pop_back();

        if (!isa<PHINode>(U)) {
          MarkBlocksLiveIn(U->getParent(), LiveBBs);
        } else {
          // Uses for a PHI node occur in their predecessor block.
          PHINode *PN = cast<PHINode>(U);
          for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
            if (PN->getIncomingValue(i) == Inst)
              MarkBlocksLiveIn(PN->getIncomingBlock(i), LiveBBs);
        }
      }

      // Now that we know all of the blocks that this thing is live in, see if
      // it includes any of the unwind locations.
      bool NeedsSpill = false;
      for (unsigned i = 0, e = Invokes.size(); i != e; ++i) {
        BasicBlock *UnwindBlock = Invokes[i]->getUnwindDest();
        if (UnwindBlock != BB && LiveBBs.count(UnwindBlock)) {
          NeedsSpill = true;
        }
      }

      // If we decided we need a spill, do it.
      if (NeedsSpill) {
        ++NumSpilled;
        DemoteRegToStack(*Inst, true);
      }
    }
//.........这里部分代码省略.........

// RemoveDeadStuffFromFunction - Remove any arguments and return values from F
// that are not in LiveValues. Transform the function and all of the callees of
// the function to not have these arguments and return values.
//
bool DAE::RemoveDeadStuffFromFunction(Function *F) {
  // Don't modify fully live functions
  if (LiveFunctions.count(F))
    return false;

  // Start by computing a new prototype for the function, which is the same as
  // the old function, but has fewer arguments and a different return type.
  FunctionType *FTy = F->getFunctionType();
  std::vector<Type*> Params;

  // Keep track of if we have a live 'returned' argument
  bool HasLiveReturnedArg = false;

  // Set up to build a new list of parameter attributes.
  SmallVector<AttributeSet, 8> AttributesVec;
  const AttributeSet &PAL = F->getAttributes();

  // Remember which arguments are still alive.
  SmallVector<bool, 10> ArgAlive(FTy->getNumParams(), false);
  // Construct the new parameter list from non-dead arguments. Also construct
  // a new set of parameter attributes to correspond. Skip the first parameter
  // attribute, since that belongs to the return value.
  unsigned i = 0;
  for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end();
       I != E; ++I, ++i) {
    RetOrArg Arg = CreateArg(F, i);
    if (LiveValues.erase(Arg)) {
      Params.push_back(I->getType());
      ArgAlive[i] = true;

      // Get the original parameter attributes (skipping the first one, that is
      // for the return value.
      if (PAL.hasAttributes(i + 1)) {
        AttrBuilder B(PAL, i + 1);
        if (B.contains(Attribute::Returned))
          HasLiveReturnedArg = true;
        AttributesVec.
          push_back(AttributeSet::get(F->getContext(), Params.size(), B));
      }
    } else {
      ++NumArgumentsEliminated;
      DEBUG(dbgs() << "DAE - Removing argument " << i << " (" << I->getName()
            << ") from " << F->getName() << "\n");
    }
  }

  // Find out the new return value.
  Type *RetTy = FTy->getReturnType();
  Type *NRetTy = NULL;
  unsigned RetCount = NumRetVals(F);

  // -1 means unused, other numbers are the new index
  SmallVector<int, 5> NewRetIdxs(RetCount, -1);
  std::vector<Type*> RetTypes;

  // If there is a function with a live 'returned' argument but a dead return
  // value, then there are two possible actions:
  // 1) Eliminate the return value and take off the 'returned' attribute on the
  //    argument.
  // 2) Retain the 'returned' attribute and treat the return value (but not the
  //    entire function) as live so that it is not eliminated.
  // 
  // It's not clear in the general case which option is more profitable because,
  // even in the absence of explicit uses of the return value, code generation
  // is free to use the 'returned' attribute to do things like eliding
  // save/restores of registers across calls. Whether or not this happens is
  // target and ABI-specific as well as depending on the amount of register
  // pressure, so there's no good way for an IR-level pass to figure this out.
  //
  // Fortunately, the only places where 'returned' is currently generated by
  // the FE are places where 'returned' is basically free and almost always a
  // performance win, so the second option can just be used always for now.
  //
  // This should be revisited if 'returned' is ever applied more liberally.
  if (RetTy->isVoidTy() || HasLiveReturnedArg) {
    NRetTy = RetTy;
  } else {
    StructType *STy = dyn_cast<StructType>(RetTy);
    if (STy)
      // Look at each of the original return values individually.
      for (unsigned i = 0; i != RetCount; ++i) {
        RetOrArg Ret = CreateRet(F, i);
        if (LiveValues.erase(Ret)) {
          RetTypes.push_back(STy->getElementType(i));
          NewRetIdxs[i] = RetTypes.size() - 1;
        } else {
          ++NumRetValsEliminated;
          DEBUG(dbgs() << "DAE - Removing return value " << i << " from "
                << F->getName() << "\n");
        }
      }
    else
      // We used to return a single value.
      if (LiveValues.erase(CreateRet(F, 0))) {
        RetTypes.push_back(RetTy);
        NewRetIdxs[0] = 0;
//.........这里部分代码省略.........

/// DeleteDeadVarargs - If this is an function that takes a ... list, and if
/// llvm.vastart is never called, the varargs list is dead for the function.
bool DAE::DeleteDeadVarargs(Function &Fn) {
  assert(Fn.getFunctionType()->isVarArg() && "Function isn't varargs!");
  if (Fn.isDeclaration() || !Fn.hasLocalLinkage()) return false;

  // Ensure that the function is only directly called.
  if (Fn.hasAddressTaken())
    return false;

  // Okay, we know we can transform this function if safe.  Scan its body
  // looking for calls to llvm.vastart.
  for (Function::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) {
    for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
      if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
        if (II->getIntrinsicID() == Intrinsic::vastart)
          return false;
      }
    }
  }

  // If we get here, there are no calls to llvm.vastart in the function body,
  // remove the "..." and adjust all the calls.

  // Start by computing a new prototype for the function, which is the same as
  // the old function, but doesn't have isVarArg set.
  FunctionType *FTy = Fn.getFunctionType();

  std::vector<Type*> Params(FTy->param_begin(), FTy->param_end());
  FunctionType *NFTy = FunctionType::get(FTy->getReturnType(),
                                                Params, false);
  unsigned NumArgs = Params.size();

  // Create the new function body and insert it into the module...
  Function *NF = Function::Create(NFTy, Fn.getLinkage());
  NF->copyAttributesFrom(&Fn);
  Fn.getParent()->getFunctionList().insert(&Fn, NF);
  NF->takeName(&Fn);

  // Loop over all of the callers of the function, transforming the call sites
  // to pass in a smaller number of arguments into the new function.
  //
  std::vector<Value*> Args;
  for (Value::use_iterator I = Fn.use_begin(), E = Fn.use_end(); I != E; ) {
    CallSite CS(*I++);
    if (!CS)
      continue;
    Instruction *Call = CS.getInstruction();

    // Pass all the same arguments.
    Args.assign(CS.arg_begin(), CS.arg_begin() + NumArgs);

    // Drop any attributes that were on the vararg arguments.
    AttributeSet PAL = CS.getAttributes();
    if (!PAL.isEmpty() && PAL.getSlotIndex(PAL.getNumSlots() - 1) > NumArgs) {
      SmallVector<AttributeSet, 8> AttributesVec;
      for (unsigned i = 0; PAL.getSlotIndex(i) <= NumArgs; ++i)
        AttributesVec.push_back(PAL.getSlotAttributes(i));
      if (PAL.hasAttributes(AttributeSet::FunctionIndex))
        AttributesVec.push_back(AttributeSet::get(Fn.getContext(),
                                                  PAL.getFnAttributes()));
      PAL = AttributeSet::get(Fn.getContext(), AttributesVec);
    }

    Instruction *New;
    if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) {
      New = InvokeInst::Create(NF, II->getNormalDest(), II->getUnwindDest(),
                               Args, "", Call);
      cast<InvokeInst>(New)->setCallingConv(CS.getCallingConv());
      cast<InvokeInst>(New)->setAttributes(PAL);
    } else {
      New = CallInst::Create(NF, Args, "", Call);
      cast<CallInst>(New)->setCallingConv(CS.getCallingConv());
      cast<CallInst>(New)->setAttributes(PAL);
      if (cast<CallInst>(Call)->isTailCall())
        cast<CallInst>(New)->setTailCall();
    }
    New->setDebugLoc(Call->getDebugLoc());

    Args.clear();

    if (!Call->use_empty())
      Call->replaceAllUsesWith(New);

    New->takeName(Call);

    // Finally, remove the old call from the program, reducing the use-count of
    // F.
    Call->eraseFromParent();
  }

  // Since we have now created the new function, splice the body of the old
  // function right into the new function, leaving the old rotting hulk of the
  // function empty.
  NF->getBasicBlockList().splice(NF->begin(), Fn.getBasicBlockList());

  // Loop over the argument list, transferring uses of the old arguments over to
  // the new arguments, also transferring over the names as well.  While we're at
  // it, remove the dead arguments from the DeadArguments list.
  //
//.........这里部分代码省略.........

bool GCOVProfiler::emitProfileArcs() {
  NamedMDNode *CU_Nodes = M->getNamedMetadata("llvm.dbg.cu");
  if (!CU_Nodes) return false;

  bool Result = false;  
  bool InsertIndCounterIncrCode = false;
  for (unsigned i = 0, e = CU_Nodes->getNumOperands(); i != e; ++i) {
    DICompileUnit CU(CU_Nodes->getOperand(i));
    DIArray SPs = CU.getSubprograms();
    SmallVector<std::pair<GlobalVariable *, MDNode *>, 8> CountersBySP;
    for (unsigned i = 0, e = SPs.getNumElements(); i != e; ++i) {
      DISubprogram SP(SPs.getElement(i));
      if (!SP.Verify()) continue;
      Function *F = SP.getFunction();
      if (!F) continue;
      if (!Result) Result = true;
      unsigned Edges = 0;
      for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
        TerminatorInst *TI = BB->getTerminator();
        if (isa<ReturnInst>(TI))
          ++Edges;
        else
          Edges += TI->getNumSuccessors();
      }
      
      ArrayType *CounterTy =
        ArrayType::get(Type::getInt64Ty(*Ctx), Edges);
      GlobalVariable *Counters =
        new GlobalVariable(*M, CounterTy, false,
                           GlobalValue::InternalLinkage,
                           Constant::getNullValue(CounterTy),
                           "__llvm_gcov_ctr");
      CountersBySP.push_back(std::make_pair(Counters, (MDNode*)SP));
      
      UniqueVector<BasicBlock *> ComplexEdgePreds;
      UniqueVector<BasicBlock *> ComplexEdgeSuccs;
      
      unsigned Edge = 0;
      for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
        TerminatorInst *TI = BB->getTerminator();
        int Successors = isa<ReturnInst>(TI) ? 1 : TI->getNumSuccessors();
        if (Successors) {
          IRBuilder<> Builder(TI);
          
          if (Successors == 1) {
            Value *Counter = Builder.CreateConstInBoundsGEP2_64(Counters, 0,
                                                                Edge);
            Value *Count = Builder.CreateLoad(Counter);
            Count = Builder.CreateAdd(Count, Builder.getInt64(1));
            Builder.CreateStore(Count, Counter);
          } else if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
            Value *Sel = Builder.CreateSelect(BI->getCondition(),
                                              Builder.getInt64(Edge),
                                              Builder.getInt64(Edge + 1));
            SmallVector<Value *, 2> Idx;
            Idx.push_back(Builder.getInt64(0));
            Idx.push_back(Sel);
            Value *Counter = Builder.CreateInBoundsGEP(Counters, Idx);
            Value *Count = Builder.CreateLoad(Counter);
            Count = Builder.CreateAdd(Count, Builder.getInt64(1));
            Builder.CreateStore(Count, Counter);
          } else {
            ComplexEdgePreds.insert(BB);
            for (int i = 0; i != Successors; ++i)
              ComplexEdgeSuccs.insert(TI->getSuccessor(i));
          }
          Edge += Successors;
        }
      }
      
      if (!ComplexEdgePreds.empty()) {
        GlobalVariable *EdgeTable =
          buildEdgeLookupTable(F, Counters,
                               ComplexEdgePreds, ComplexEdgeSuccs);
        GlobalVariable *EdgeState = getEdgeStateValue();
        
        for (int i = 0, e = ComplexEdgePreds.size(); i != e; ++i) {
          IRBuilder<> Builder(ComplexEdgePreds[i+1]->getTerminator());
          Builder.CreateStore(Builder.getInt32(i), EdgeState);
        }
        for (int i = 0, e = ComplexEdgeSuccs.size(); i != e; ++i) {
          // call runtime to perform increment
          BasicBlock::iterator InsertPt =
            ComplexEdgeSuccs[i+1]->getFirstInsertionPt();
          IRBuilder<> Builder(InsertPt);
          Value *CounterPtrArray =
            Builder.CreateConstInBoundsGEP2_64(EdgeTable, 0,
                                               i * ComplexEdgePreds.size());

          // Build code to increment the counter.
          InsertIndCounterIncrCode = true;
          Builder.CreateCall2(getIncrementIndirectCounterFunc(),
                              EdgeState, CounterPtrArray);
        }
      }
    }

    Function *WriteoutF = insertCounterWriteout(CountersBySP);
    Function *FlushF = insertFlush(CountersBySP);

//.........这里部分代码省略.........