// Collect allocas
void AllocaManager::collectMarkedAllocas() {
  NamedRegionTimer Timer("Collect Marked Allocas", "AllocaManager",
                         TimePassesIsEnabled);

  // Weird semantics: If an alloca *ever* appears in a lifetime start or end
  // within the same function, its lifetime begins only at the explicit lifetime
  // starts and ends only at the explicit lifetime ends and function exit
  // points. Otherwise, its lifetime begins in the entry block and it is live
  // everywhere.
  //
  // And so, instead of just walking the entry block to find all the static
  // allocas, we walk the whole body to find the intrinsics so we can find the
  // set of static allocas referenced in the intrinsics.
  for (Function::const_iterator FI = F->begin(), FE = F->end();
       FI != FE; ++FI) {
    for (BasicBlock::const_iterator BI = FI->begin(), BE = FI->end();
         BI != BE; ++BI) {
      const CallInst *CI = dyn_cast<CallInst>(BI);
      if (!CI) continue;

      const Value *Callee = CI->getCalledValue();
      if (Callee == LifetimeStart || Callee == LifetimeEnd) {
        if (const Value *Ptr = getPointerFromIntrinsic(CI)) {
          if (const AllocaInst *AI = isFavorableAlloca(Ptr))
            Allocas.insert(std::make_pair(AI, 0));
        } else if (isa<Instruction>(CI->getArgOperand(1)->stripPointerCasts())) {
          // Oh noes, There's a lifetime intrinsics with something that
          // doesn't appear to resolve to an alloca. This means that it's
          // possible that it may be declaring a lifetime for some escaping
          // alloca. Look out!
          Allocas.clear();
          assert(AllocasByIndex.empty());
          return;
        }
      }
    }
  }

  // All that said, we still want the intrinsics in the order they appear in the
  // block, so that we can represent later ones with earlier ones and skip
  // worrying about dominance, so run through the entry block and index those
  // allocas which we identified above.
  AllocasByIndex.reserve(Allocas.size());
  const BasicBlock *EntryBB = &F->getEntryBlock();
  for (BasicBlock::const_iterator BI = EntryBB->begin(), BE = EntryBB->end();
       BI != BE; ++BI) {
    const AllocaInst *AI = dyn_cast<AllocaInst>(BI);
    if (!AI || !AI->isStaticAlloca()) continue;

    AllocaMap::iterator I = Allocas.find(AI);
    if (I != Allocas.end()) {
      I->second = AllocasByIndex.size();
      AllocasByIndex.push_back(getInfo(AI));
    }
  }
  assert(AllocasByIndex.size() == Allocas.size());
}

set<Strator::StratorWorker::LockSet>& Strator::StratorWorker::traverseFunction(const Function& f, LockSet lockSet){
	#ifdef DETAILED_DEBUG
	cerr << " Traversing: " << f.getName().str() << endl;
	#endif
	if("signal_threads" == f.getName().str())
		cerr << "signal" << endl;
	/// This should be OK even if not thread safe
	//TODO: Ali: why OK if not thread safe ?!
	parent->functionMap[f.getName().str()] = true;
	/// If the size of a basic block is 0, then we are in a function declaration.
	if (f.size() == 0){
		set<StratorWorker::LockSet>* emptySet = new set<StratorWorker::LockSet>();
		return *emptySet;
	}

	StratorFunction* sFunc = getStratorFunction(&f);

	/// Check if the function is in the cache
	vector<FunctionCacheEntry>::iterator it;
	for(it = sFunc->functionCache.functionCacheEntries.begin();
			it != sFunc->functionCache.functionCacheEntries.end(); ++it){
		if(it->entryLockSet == lockSet){
			return it->exitLockSets;
		}
	}
	/// Simply ignore recursion
	if(sFunc->onStack){
		set<StratorWorker::LockSet>* emptySet = new set<StratorWorker::LockSet>();
		return *emptySet;
	}

	sFunc->onStack= true;

	/// The function was not in the cache, so a new cache entry is being created for it
	FunctionCacheEntry* functionCacheEntry = new FunctionCacheEntry();
	functionCacheEntry->entryLockSet = lockSet;

	/// Start traversing the statements with the beginning statement of the function
	Function::const_iterator firstBB = f.begin();
	BasicBlock::const_iterator firstInstr = firstBB->begin();
	functionCacheEntry->exitLockSets = traverseStatement(f, firstInstr, lockSet, lockSet);

	/// We processes the current function, it is no longer on the stack
	sFunc->onStack= false;

	/// Add the exit lockset to the summary cache
	sFunc->functionCache.functionCacheEntries.push_back(*functionCacheEntry);

	return functionCacheEntry->exitLockSets;
}

void TypeFinder::Run(const Module &M) {

	AddModuleTypesToPrinter(TP,&M);

    // Get types from the type symbol table.  This gets opaque types referened
    // only through derived named types.
    const TypeSymbolTable &ST = M.getTypeSymbolTable();
    for (TypeSymbolTable::const_iterator TI = ST.begin(), E = ST.end();
           TI != E; ++TI)
		IncorporateType(TI->second);

    // Get types from global variables.
	for (Module::const_global_iterator I = M.global_begin(),
           E = M.global_end(); I != E; ++I) {
        IncorporateType(I->getType());
        if (I->hasInitializer())
          IncorporateValue(I->getInitializer());
    }

    // Get types from aliases.
    for (Module::const_alias_iterator I = M.alias_begin(),
         E = M.alias_end(); I != E; ++I) {
		IncorporateType(I->getType());
        IncorporateValue(I->getAliasee());
    }

    // Get types from functions.
    for (Module::const_iterator FI = M.begin(), E = M.end(); FI != E; ++FI) {
        IncorporateType(FI->getType());

		for (Function::const_iterator BB = FI->begin(), E = FI->end();
             BB != E;++BB)
			for (BasicBlock::const_iterator II = BB->begin(),
               E = BB->end(); II != E; ++II) {
				const Instruction &I = *II;
				// Incorporate the type of the instruction and all its operands.
				IncorporateType(I.getType());
				for (User::const_op_iterator OI = I.op_begin(), OE = I.op_end();
					OI != OE; ++OI)
					IncorporateValue(*OI);
			}
      }
}

void buildCallMaps(Module const& M, FunctionsMap& F,
		CallsMap& C) {
    for (Module::const_iterator f = M.begin(); f != M.end(); ++f) {
	if (!f->isDeclaration())
	    F.insert(std::make_pair(f->getFunctionType(), &*f));
	for (Function::const_iterator b = f->begin(); b != f->end(); ++b) {
	    for (BasicBlock::const_iterator i = b->begin(); i != b->end(); ++i)
		if (const CallInst *CI = dyn_cast<CallInst>(&*i)) {
		    if (!isInlineAssembly(CI) && !callToMemoryManStuff(CI))
			C.insert(std::make_pair(getCalleePrototype(CI), CI));
		} else if (const StoreInst *SI = dyn_cast<StoreInst>(&*i)) {
		    const Value *r = SI->getValueOperand();
		    if (hasExtraReference(r) && memoryManStuff(r)) {
			const Function *fn = dyn_cast<Function>(r);
			F.insert(std::make_pair(fn->getFunctionType(), fn));
		    }
		}
	}
    }
}

void ModuleSummaryIndexBuilder::computeFunctionSummary(
    const Function &F, BlockFrequencyInfo *BFI) {
  // Summary not currently supported for anonymous functions, they must
  // be renamed.
  if (!F.hasName())
    return;

  unsigned NumInsts = 0;
  // Map from callee ValueId to profile count. Used to accumulate profile
  // counts for all static calls to a given callee.
  DenseMap<const Value *, CalleeInfo> CallGraphEdges;
  DenseSet<const Value *> RefEdges;

  SmallPtrSet<const User *, 8> Visited;
  for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
    for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I != E;
         ++I) {
      if (!isa<DbgInfoIntrinsic>(I))
        ++NumInsts;

      if (auto CS = ImmutableCallSite(&*I)) {
        auto *CalledFunction = CS.getCalledFunction();
        if (CalledFunction && CalledFunction->hasName() &&
            !CalledFunction->isIntrinsic()) {
          auto ScaledCount = BFI ? BFI->getBlockProfileCount(&*BB) : None;
          auto *CalleeId =
              M->getValueSymbolTable().lookup(CalledFunction->getName());
          CallGraphEdges[CalleeId] +=
              (ScaledCount ? ScaledCount.getValue() : 0);
        }
      }
      findRefEdges(&*I, RefEdges, Visited);
    }

  GlobalValueSummary::GVFlags Flags(F);
  std::unique_ptr<FunctionSummary> FuncSummary =
      llvm::make_unique<FunctionSummary>(Flags, NumInsts);
  FuncSummary->addCallGraphEdges(CallGraphEdges);
  FuncSummary->addRefEdges(RefEdges);
  Index->addGlobalValueSummary(F.getName(), std::move(FuncSummary));
}

/// WriteFunction - Emit a function body to the module stream.
static void WriteFunction(const Function &F, NaClValueEnumerator &VE,
                          NaClBitstreamWriter &Stream) {
  Stream.EnterSubblock(naclbitc::FUNCTION_BLOCK_ID);
  VE.incorporateFunction(F);

  SmallVector<unsigned, 64> Vals;

  // Emit the number of basic blocks, so the reader can create them ahead of
  // time.
  Vals.push_back(VE.getBasicBlocks().size());
  Stream.EmitRecord(naclbitc::FUNC_CODE_DECLAREBLOCKS, Vals);
  Vals.clear();

  // If there are function-local constants, emit them now.
  unsigned CstStart, CstEnd;
  VE.getFunctionConstantRange(CstStart, CstEnd);
  WriteConstants(CstStart, CstEnd, VE, Stream);

  // Keep a running idea of what the instruction ID is.
  unsigned InstID = CstEnd;

  // Finally, emit all the instructions, in order.
  for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
    for (BasicBlock::const_iterator I = BB->begin(), E = BB->end();
         I != E; ++I) {
      if (WriteInstruction(*I, InstID, VE, Stream, Vals) &&
          !I->getType()->isVoidTy())
        ++InstID;
    }

  // Emit names for instructions etc.
  if (PNaClAllowLocalSymbolTables)
    WriteValueSymbolTable(F.getValueSymbolTable(), VE, Stream);

  VE.purgeFunction();
  Stream.ExitBlock();
}

void ValueEnumerator::incorporateFunction(const Function &F) {
  InstructionCount = 0;
  NumModuleValues = Values.size();
  NumModuleMDs = MDs.size();

  // Adding function arguments to the value table.
  for (Function::const_arg_iterator I = F.arg_begin(), E = F.arg_end();
       I != E; ++I)
    EnumerateValue(I);

  FirstFuncConstantID = Values.size();

  // Add all function-level constants to the value table.
  for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
    for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I)
      for (User::const_op_iterator OI = I->op_begin(), E = I->op_end();
           OI != E; ++OI) {
        if ((isa<Constant>(*OI) && !isa<GlobalValue>(*OI)) ||
            isa<InlineAsm>(*OI))
          EnumerateValue(*OI);
      }
    BasicBlocks.push_back(BB);
    ValueMap[BB] = BasicBlocks.size();
  }

  // Optimize the constant layout.
  OptimizeConstants(FirstFuncConstantID, Values.size());

  // Add the function's parameter attributes so they are available for use in
  // the function's instruction.
  EnumerateAttributes(F.getAttributes());

  FirstInstID = Values.size();

  SmallVector<LocalAsMetadata *, 8> FnLocalMDVector;
  // Add all of the instructions.
  for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
    for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I) {
      for (User::const_op_iterator OI = I->op_begin(), E = I->op_end();
           OI != E; ++OI) {
        if (auto *MD = dyn_cast<MetadataAsValue>(&*OI))
          if (auto *Local = dyn_cast<LocalAsMetadata>(MD->getMetadata()))
            // Enumerate metadata after the instructions they might refer to.
            FnLocalMDVector.push_back(Local);
      }

      if (!I->getType()->isVoidTy())
        EnumerateValue(I);
    }
  }

  // Add all of the function-local metadata.
  for (unsigned i = 0, e = FnLocalMDVector.size(); i != e; ++i)
    EnumerateFunctionLocalMetadata(FnLocalMDVector[i]);
}

void NaClValueEnumerator::incorporateFunction(const Function &F) {
  InstructionCount = 0;
  NumModuleValues = Values.size();

  // Make sure no insertions outside of a function.
  assert(FnForwardTypeRefs.empty());

  // Adding function arguments to the value table.
  for (Function::const_arg_iterator I = F.arg_begin(), E = F.arg_end();
       I != E; ++I)
    EnumerateValue(I);

  FirstFuncConstantID = Values.size();

  // Add all function-level constants to the value table.
  for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
    for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I) {
      if (const SwitchInst *SI = dyn_cast<SwitchInst>(I)) {
        // Handle switch instruction specially, so that we don't write
        // out unnecessary vector/array constants used to model case selectors.
        if (isa<Constant>(SI->getCondition())) {
          EnumerateValue(SI->getCondition());
        }
      } else {
        for (User::const_op_iterator OI = I->op_begin(), E = I->op_end();
             OI != E; ++OI) {
          if ((isa<Constant>(*OI) && !isa<GlobalValue>(*OI)) ||
              isa<InlineAsm>(*OI))
            EnumerateValue(*OI);
        }
      }
    }
    BasicBlocks.push_back(BB);
    ValueMap[BB] = BasicBlocks.size();
  }

  // Optimize the constant layout.
  OptimizeConstants(FirstFuncConstantID, Values.size());

  FirstInstID = Values.size();

  // Add all of the instructions.
  for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
    for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I) {
      if (!I->getType()->isVoidTy())
        EnumerateValue(I);
    }
  }
}

void ValueEnumerator::incorporateFunction(const Function &F) {
  NumModuleValues = Values.size();

  // Adding function arguments to the value table.
  for(Function::const_arg_iterator I = F.arg_begin(), E = F.arg_end();
      I != E; ++I)
    EnumerateValue(I);

  FirstFuncConstantID = Values.size();

  // Add all function-level constants to the value table.
  for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
    for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I)
      for (User::const_op_iterator OI = I->op_begin(), E = I->op_end();
           OI != E; ++OI) {
        if ((isa<Constant>(*OI) && !isa<GlobalValue>(*OI)) ||
            isa<InlineAsm>(*OI))
          EnumerateValue(*OI);
      }
    BasicBlocks.push_back(BB);
    ValueMap[BB] = BasicBlocks.size();
  }

  // Optimize the constant layout.
  OptimizeConstants(FirstFuncConstantID, Values.size());

  // Add the function's parameter attributes so they are available for use in
  // the function's instruction.
  EnumerateAttributes(F.getAttributes());

  FirstInstID = Values.size();

  // Add all of the instructions.
  for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
    for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I) {
      if (I->getType() != Type::getVoidTy(F.getContext()))
        EnumerateValue(I);
    }
  }
}

void FunctionLoweringInfo::set(const Function &fn, MachineFunction &mf,
                               SelectionDAG *DAG) {
  Fn = &fn;
  MF = &mf;
  TLI = MF->getSubtarget().getTargetLowering();
  RegInfo = &MF->getRegInfo();
  MachineModuleInfo &MMI = MF->getMMI();

  // Check whether the function can return without sret-demotion.
  SmallVector<ISD::OutputArg, 4> Outs;
  GetReturnInfo(Fn->getReturnType(), Fn->getAttributes(), Outs, *TLI);
  CanLowerReturn = TLI->CanLowerReturn(Fn->getCallingConv(), *MF,
                                       Fn->isVarArg(), Outs, Fn->getContext());

  // Initialize the mapping of values to registers.  This is only set up for
  // instruction values that are used outside of the block that defines
  // them.
  Function::const_iterator BB = Fn->begin(), EB = Fn->end();
  for (; BB != EB; ++BB)
    for (BasicBlock::const_iterator I = BB->begin(), E = BB->end();
         I != E; ++I) {
      if (const AllocaInst *AI = dyn_cast<AllocaInst>(I)) {
        // Static allocas can be folded into the initial stack frame adjustment.
        if (AI->isStaticAlloca()) {
          const ConstantInt *CUI = cast<ConstantInt>(AI->getArraySize());
          Type *Ty = AI->getAllocatedType();
          uint64_t TySize = TLI->getDataLayout()->getTypeAllocSize(Ty);
          unsigned Align =
              std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty),
                       AI->getAlignment());

          TySize *= CUI->getZExtValue();   // Get total allocated size.
          if (TySize == 0) TySize = 1; // Don't create zero-sized stack objects.

          StaticAllocaMap[AI] =
            MF->getFrameInfo()->CreateStackObject(TySize, Align, false, AI);

        } else {
          unsigned Align = std::max(
              (unsigned)TLI->getDataLayout()->getPrefTypeAlignment(
                AI->getAllocatedType()),
              AI->getAlignment());
          unsigned StackAlign =
              MF->getSubtarget().getFrameLowering()->getStackAlignment();
          if (Align <= StackAlign)
            Align = 0;
          // Inform the Frame Information that we have variable-sized objects.
          MF->getFrameInfo()->CreateVariableSizedObject(Align ? Align : 1, AI);
        }
      }

      // Look for inline asm that clobbers the SP register.
      if (isa<CallInst>(I) || isa<InvokeInst>(I)) {
        ImmutableCallSite CS(I);
        if (isa<InlineAsm>(CS.getCalledValue())) {
          unsigned SP = TLI->getStackPointerRegisterToSaveRestore();
          const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
          std::vector<TargetLowering::AsmOperandInfo> Ops =
              TLI->ParseConstraints(TRI, CS);
          for (size_t I = 0, E = Ops.size(); I != E; ++I) {
            TargetLowering::AsmOperandInfo &Op = Ops[I];
            if (Op.Type == InlineAsm::isClobber) {
              // Clobbers don't have SDValue operands, hence SDValue().
              TLI->ComputeConstraintToUse(Op, SDValue(), DAG);
              std::pair<unsigned, const TargetRegisterClass *> PhysReg =
                  TLI->getRegForInlineAsmConstraint(TRI, Op.ConstraintCode,
                                                    Op.ConstraintVT);
              if (PhysReg.first == SP)
                MF->getFrameInfo()->setHasInlineAsmWithSPAdjust(true);
            }
          }
        }
      }

      // Look for calls to the @llvm.va_start intrinsic. We can omit some
      // prologue boilerplate for variadic functions that don't examine their
      // arguments.
      if (const auto *II = dyn_cast<IntrinsicInst>(I)) {
        if (II->getIntrinsicID() == Intrinsic::vastart)
          MF->getFrameInfo()->setHasVAStart(true);
      }

      // If we have a musttail call in a variadic funciton, we need to ensure we
      // forward implicit register parameters.
      if (const auto *CI = dyn_cast<CallInst>(I)) {
        if (CI->isMustTailCall() && Fn->isVarArg())
          MF->getFrameInfo()->setHasMustTailInVarArgFunc(true);
      }

      // Mark values used outside their block as exported, by allocating
      // a virtual register for them.
      if (isUsedOutsideOfDefiningBlock(I))
        if (!isa<AllocaInst>(I) ||
            !StaticAllocaMap.count(cast<AllocaInst>(I)))
          InitializeRegForValue(I);

      // Collect llvm.dbg.declare information. This is done now instead of
      // during the initial isel pass through the IR so that it is done
      // in a predictable order.
      if (const DbgDeclareInst *DI = dyn_cast<DbgDeclareInst>(I)) {
//.........这里部分代码省略.........

/// ValueEnumerator - Enumerate module-level information.
ValueEnumerator::ValueEnumerator(const Module *M) {
  // Enumerate the global variables.
  for (Module::const_global_iterator I = M->global_begin(),
         E = M->global_end(); I != E; ++I)
    EnumerateValue(I);

  // Enumerate the functions.
  for (Module::const_iterator I = M->begin(), E = M->end(); I != E; ++I) {
    EnumerateValue(I);
    EnumerateAttributes(cast<Function>(I)->getAttributes());
  }

  // Enumerate the aliases.
  for (Module::const_alias_iterator I = M->alias_begin(), E = M->alias_end();
       I != E; ++I)
    EnumerateValue(I);

  // Remember what is the cutoff between globalvalue's and other constants.
  unsigned FirstConstant = Values.size();

  // Enumerate the global variable initializers.
  for (Module::const_global_iterator I = M->global_begin(),
         E = M->global_end(); I != E; ++I)
    if (I->hasInitializer())
      EnumerateValue(I->getInitializer());

  // Enumerate the aliasees.
  for (Module::const_alias_iterator I = M->alias_begin(), E = M->alias_end();
       I != E; ++I)
    EnumerateValue(I->getAliasee());

  // Insert constants and metadata that are named at module level into the slot
  // pool so that the module symbol table can refer to them...
  EnumerateValueSymbolTable(M->getValueSymbolTable());
  EnumerateNamedMetadata(M);

  SmallVector<std::pair<unsigned, MDNode*>, 8> MDs;

  // Enumerate types used by function bodies and argument lists.
  for (Module::const_iterator F = M->begin(), E = M->end(); F != E; ++F) {

    for (Function::const_arg_iterator I = F->arg_begin(), E = F->arg_end();
         I != E; ++I)
      EnumerateType(I->getType());

    for (Function::const_iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
      for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E;++I){
        for (User::const_op_iterator OI = I->op_begin(), E = I->op_end();
             OI != E; ++OI) {
          if (MDNode *MD = dyn_cast<MDNode>(*OI))
            if (MD->isFunctionLocal() && MD->getFunction())
              // These will get enumerated during function-incorporation.
              continue;
          EnumerateOperandType(*OI);
        }
        EnumerateType(I->getType());
        if (const CallInst *CI = dyn_cast<CallInst>(I))
          EnumerateAttributes(CI->getAttributes());
        else if (const InvokeInst *II = dyn_cast<InvokeInst>(I))
          EnumerateAttributes(II->getAttributes());

        // Enumerate metadata attached with this instruction.
        MDs.clear();
        I->getAllMetadataOtherThanDebugLoc(MDs);
        for (unsigned i = 0, e = MDs.size(); i != e; ++i)
          EnumerateMetadata(MDs[i].second);

        if (!I->getDebugLoc().isUnknown()) {
          MDNode *Scope, *IA;
          I->getDebugLoc().getScopeAndInlinedAt(Scope, IA, I->getContext());
          if (Scope) EnumerateMetadata(Scope);
          if (IA) EnumerateMetadata(IA);
        }
      }
  }

  // Optimize constant ordering.
  OptimizeConstants(FirstConstant, Values.size());
}

static Error ReduceInsts(BugDriver &BD,
                        bool (*TestFn)(const BugDriver &, Module *)) {
  // Attempt to delete instructions using bisection. This should help out nasty
  // cases with large basic blocks where the problem is at one end.
  if (!BugpointIsInterrupted) {
    std::vector<const Instruction *> Insts;
    for (const Function &F : *BD.getProgram())
      for (const BasicBlock &BB : F)
        for (const Instruction &I : BB)
          if (!isa<TerminatorInst>(&I))
            Insts.push_back(&I);

    Expected<bool> Result =
        ReduceCrashingInstructions(BD, TestFn).reduceList(Insts);
    if (Error E = Result.takeError())
      return E;
  }

  unsigned Simplification = 2;
  do {
    if (BugpointIsInterrupted)
      // TODO: Should we distinguish this with an "interrupted error"?
      return Error::success();
    --Simplification;
    outs() << "\n*** Attempting to reduce testcase by deleting instruc"
           << "tions: Simplification Level #" << Simplification << '\n';

    // Now that we have deleted the functions that are unnecessary for the
    // program, try to remove instructions that are not necessary to cause the
    // crash.  To do this, we loop through all of the instructions in the
    // remaining functions, deleting them (replacing any values produced with
    // nulls), and then running ADCE and SimplifyCFG.  If the transformed input
    // still triggers failure, keep deleting until we cannot trigger failure
    // anymore.
    //
    unsigned InstructionsToSkipBeforeDeleting = 0;
  TryAgain:

    // Loop over all of the (non-terminator) instructions remaining in the
    // function, attempting to delete them.
    unsigned CurInstructionNum = 0;
    for (Module::const_iterator FI = BD.getProgram()->begin(),
                                E = BD.getProgram()->end();
         FI != E; ++FI)
      if (!FI->isDeclaration())
        for (Function::const_iterator BI = FI->begin(), E = FI->end(); BI != E;
             ++BI)
          for (BasicBlock::const_iterator I = BI->begin(), E = --BI->end();
               I != E; ++I, ++CurInstructionNum) {
            if (InstructionsToSkipBeforeDeleting) {
              --InstructionsToSkipBeforeDeleting;
            } else {
              if (BugpointIsInterrupted)
                // TODO: Should this be some kind of interrupted error?
                return Error::success();

              if (I->isEHPad() || I->getType()->isTokenTy())
                continue;

              outs() << "Checking instruction: " << *I;
              std::unique_ptr<Module> M =
                  BD.deleteInstructionFromProgram(&*I, Simplification);

              // Find out if the pass still crashes on this pass...
              if (TestFn(BD, M.get())) {
                // Yup, it does, we delete the old module, and continue trying
                // to reduce the testcase...
                BD.setNewProgram(M.release());
                InstructionsToSkipBeforeDeleting = CurInstructionNum;
                goto TryAgain; // I wish I had a multi-level break here!
              }
            }
          }

    if (InstructionsToSkipBeforeDeleting) {
      InstructionsToSkipBeforeDeleting = 0;
      goto TryAgain;
    }

  } while (Simplification);
  BD.EmitProgressBitcode(BD.getProgram(), "reduced-instructions");
  return Error::success();
}

void externalsAndGlobalsCheck(const Module *m) {
  std::map<std::string, bool> externals;
  std::set<std::string> modelled(modelledExternals,
                                 modelledExternals+NELEMS(modelledExternals));
  std::set<std::string> dontCare(dontCareExternals,
                                 dontCareExternals+NELEMS(dontCareExternals));
  std::set<std::string> unsafe(unsafeExternals,
                               unsafeExternals+NELEMS(unsafeExternals));

  switch (Libc) {
  case KleeLibc:
    dontCare.insert(dontCareKlee, dontCareKlee+NELEMS(dontCareKlee));
    break;
  case UcLibc:
    dontCare.insert(dontCareUclibc,
                    dontCareUclibc+NELEMS(dontCareUclibc));
    break;
  case NoLibc: /* silence compiler warning */
    break;
  }

  if (WithPOSIXRuntime)
    dontCare.insert("syscall");

  for (Module::const_iterator fnIt = m->begin(), fn_ie = m->end();
       fnIt != fn_ie; ++fnIt) {
    if (fnIt->isDeclaration() && !fnIt->use_empty())
      externals.insert(std::make_pair(fnIt->getName(), false));
    for (Function::const_iterator bbIt = fnIt->begin(), bb_ie = fnIt->end();
         bbIt != bb_ie; ++bbIt) {
      for (BasicBlock::const_iterator it = bbIt->begin(), ie = bbIt->end();
           it != ie; ++it) {
        if (const CallInst *ci = dyn_cast<CallInst>(it)) {
          if (isa<InlineAsm>(ci->getCalledValue())) {
            klee_warning_once(&*fnIt,
                              "function \"%s\" has inline asm",
                              fnIt->getName().data());
          }
        }
      }
    }
  }
  for (Module::const_global_iterator
         it = m->global_begin(), ie = m->global_end();
       it != ie; ++it)
    if (it->isDeclaration() && !it->use_empty())
      externals.insert(std::make_pair(it->getName(), true));
  // and remove aliases (they define the symbol after global
  // initialization)
  for (Module::const_alias_iterator
         it = m->alias_begin(), ie = m->alias_end();
       it != ie; ++it) {
    std::map<std::string, bool>::iterator it2 =
      externals.find(it->getName());
    if (it2!=externals.end())
      externals.erase(it2);
  }

  std::map<std::string, bool> foundUnsafe;
  for (std::map<std::string, bool>::iterator
         it = externals.begin(), ie = externals.end();
       it != ie; ++it) {
    const std::string &ext = it->first;
    if (!modelled.count(ext) && (WarnAllExternals ||
                                 !dontCare.count(ext))) {
      if (unsafe.count(ext)) {
        foundUnsafe.insert(*it);
      } else {
        klee_warning("undefined reference to %s: %s",
                     it->second ? "variable" : "function",
                     ext.c_str());
      }
    }
  }

  for (std::map<std::string, bool>::iterator
         it = foundUnsafe.begin(), ie = foundUnsafe.end();
       it != ie; ++it) {
    const std::string &ext = it->first;
    klee_warning("undefined reference to %s: %s (UNSAFE)!",
                 it->second ? "variable" : "function",
                 ext.c_str());
  }
}

/// CloneAndPruneFunctionInto - This works exactly like CloneFunctionInto,
/// except that it does some simple constant prop and DCE on the fly.  The
/// effect of this is to copy significantly less code in cases where (for
/// example) a function call with constant arguments is inlined, and those
/// constant arguments cause a significant amount of code in the callee to be
/// dead.  Since this doesn't produce an exact copy of the input, it can't be
/// used for things like CloneFunction or CloneModule.
void llvm::CloneAndPruneFunctionInto(Function *NewFunc, const Function *OldFunc,
                                     ValueToValueMapTy &VMap,
                                     bool ModuleLevelChanges,
                                     SmallVectorImpl<ReturnInst*> &Returns,
                                     const char *NameSuffix, 
                                     ClonedCodeInfo *CodeInfo,
                                     const TargetData *TD,
                                     Instruction *TheCall) {
  assert(NameSuffix && "NameSuffix cannot be null!");
  
#ifndef NDEBUG
  for (Function::const_arg_iterator II = OldFunc->arg_begin(), 
       E = OldFunc->arg_end(); II != E; ++II)
    assert(VMap.count(II) && "No mapping from source argument specified!");
#endif

  PruningFunctionCloner PFC(NewFunc, OldFunc, VMap, ModuleLevelChanges,
                            Returns, NameSuffix, CodeInfo, TD);

  // Clone the entry block, and anything recursively reachable from it.
  std::vector<const BasicBlock*> CloneWorklist;
  CloneWorklist.push_back(&OldFunc->getEntryBlock());
  while (!CloneWorklist.empty()) {
    const BasicBlock *BB = CloneWorklist.back();
    CloneWorklist.pop_back();
    PFC.CloneBlock(BB, CloneWorklist);
  }
  
  // Loop over all of the basic blocks in the old function.  If the block was
  // reachable, we have cloned it and the old block is now in the value map:
  // insert it into the new function in the right order.  If not, ignore it.
  //
  // Defer PHI resolution until rest of function is resolved.
  SmallVector<const PHINode*, 16> PHIToResolve;
  for (Function::const_iterator BI = OldFunc->begin(), BE = OldFunc->end();
       BI != BE; ++BI) {
    Value *V = VMap[BI];
    BasicBlock *NewBB = cast_or_null<BasicBlock>(V);
    if (NewBB == 0) continue;  // Dead block.

    // Add the new block to the new function.
    NewFunc->getBasicBlockList().push_back(NewBB);
    
    // Loop over all of the instructions in the block, fixing up operand
    // references as we go.  This uses VMap to do all the hard work.
    //
    BasicBlock::iterator I = NewBB->begin();

    DebugLoc TheCallDL;
    if (TheCall) 
      TheCallDL = TheCall->getDebugLoc();
    
    // Handle PHI nodes specially, as we have to remove references to dead
    // blocks.
    if (PHINode *PN = dyn_cast<PHINode>(I)) {
      // Skip over all PHI nodes, remembering them for later.
      BasicBlock::const_iterator OldI = BI->begin();
      for (; (PN = dyn_cast<PHINode>(I)); ++I, ++OldI)
        PHIToResolve.push_back(cast<PHINode>(OldI));
    }
    
    // Otherwise, remap the rest of the instructions normally.
    for (; I != NewBB->end(); ++I)
      RemapInstruction(I, VMap,
                       ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges);
  }
  
  // Defer PHI resolution until rest of function is resolved, PHI resolution
  // requires the CFG to be up-to-date.
  for (unsigned phino = 0, e = PHIToResolve.size(); phino != e; ) {
    const PHINode *OPN = PHIToResolve[phino];
    unsigned NumPreds = OPN->getNumIncomingValues();
    const BasicBlock *OldBB = OPN->getParent();
    BasicBlock *NewBB = cast<BasicBlock>(VMap[OldBB]);

    // Map operands for blocks that are live and remove operands for blocks
    // that are dead.
    for (; phino != PHIToResolve.size() &&
         PHIToResolve[phino]->getParent() == OldBB; ++phino) {
      OPN = PHIToResolve[phino];
      PHINode *PN = cast<PHINode>(VMap[OPN]);
      for (unsigned pred = 0, e = NumPreds; pred != e; ++pred) {
        Value *V = VMap[PN->getIncomingBlock(pred)];
        if (BasicBlock *MappedBlock = cast_or_null<BasicBlock>(V)) {
          Value *InVal = MapValue(PN->getIncomingValue(pred),
                                  VMap, 
                        ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges);
          assert(InVal && "Unknown input value?");
          PN->setIncomingValue(pred, InVal);
          PN->setIncomingBlock(pred, MappedBlock);
        } else {
          PN->removeIncomingValue(pred, false);
          --pred, --e;  // Revisit the next entry.
//.........这里部分代码省略.........

/// ValueEnumerator - Enumerate module-level information.
ValueEnumerator::ValueEnumerator(const Module *M) {
  // Enumerate the global variables.
  for (Module::const_global_iterator I = M->global_begin(),
         E = M->global_end(); I != E; ++I)
    EnumerateValue(I);

  // Enumerate the functions.
  for (Module::const_iterator I = M->begin(), E = M->end(); I != E; ++I) {
    EnumerateValue(I);
    EnumerateAttributes(cast<Function>(I)->getAttributes());
  }

  // Enumerate the aliases.
  for (Module::const_alias_iterator I = M->alias_begin(), E = M->alias_end();
       I != E; ++I)
    EnumerateValue(I);

  // Remember what is the cutoff between globalvalue's and other constants.
  unsigned FirstConstant = Values.size();

  // Enumerate the global variable initializers.
  for (Module::const_global_iterator I = M->global_begin(),
         E = M->global_end(); I != E; ++I)
    if (I->hasInitializer())
      EnumerateValue(I->getInitializer());

  // Enumerate the aliasees.
  for (Module::const_alias_iterator I = M->alias_begin(), E = M->alias_end();
       I != E; ++I)
    EnumerateValue(I->getAliasee());

  // Enumerate types used by the type symbol table.
  EnumerateTypeSymbolTable(M->getTypeSymbolTable());

  // Insert constants and metadata that are named at module level into the slot 
  // pool so that the module symbol table can refer to them...
  EnumerateValueSymbolTable(M->getValueSymbolTable());
  EnumerateNamedMetadata(M);

  SmallVector<std::pair<unsigned, MDNode*>, 8> MDs;

  // Enumerate types used by function bodies and argument lists.
  for (Module::const_iterator F = M->begin(), E = M->end(); F != E; ++F) {

    for (Function::const_arg_iterator I = F->arg_begin(), E = F->arg_end();
         I != E; ++I)
      EnumerateType(I->getType());

    for (Function::const_iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
      for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E;++I){
        for (User::const_op_iterator OI = I->op_begin(), E = I->op_end();
             OI != E; ++OI) {
          if (MDNode *MD = dyn_cast<MDNode>(*OI))
            if (MD->isFunctionLocal() && MD->getFunction())
              // These will get enumerated during function-incorporation.
              continue;
          EnumerateOperandType(*OI);
        }
        EnumerateType(I->getType());
        if (const CallInst *CI = dyn_cast<CallInst>(I))
          EnumerateAttributes(CI->getAttributes());
        else if (const InvokeInst *II = dyn_cast<InvokeInst>(I))
          EnumerateAttributes(II->getAttributes());

        // Enumerate metadata attached with this instruction.
        MDs.clear();
        I->getAllMetadataOtherThanDebugLoc(MDs);
        for (unsigned i = 0, e = MDs.size(); i != e; ++i)
          EnumerateMetadata(MDs[i].second);
        
        if (!I->getDebugLoc().isUnknown()) {
          MDNode *Scope, *IA;
          I->getDebugLoc().getScopeAndInlinedAt(Scope, IA, I->getContext());
          if (Scope) EnumerateMetadata(Scope);
          if (IA) EnumerateMetadata(IA);
        }
      }
  }

  // Optimize constant ordering.
  OptimizeConstants(FirstConstant, Values.size());

  // Sort the type table by frequency so that most commonly used types are early
  // in the table (have low bit-width).
  std::stable_sort(Types.begin(), Types.end(), CompareByFrequency);

  // Partition the Type ID's so that the single-value types occur before the
  // aggregate types.  This allows the aggregate types to be dropped from the
  // type table after parsing the global variable initializers.
  std::partition(Types.begin(), Types.end(), isSingleValueType);

  // Now that we rearranged the type table, rebuild TypeMap.
  for (unsigned i = 0, e = Types.size(); i != e; ++i)
    TypeMap[Types[i].first] = i+1;
}

//.........这里部分代码省略.........
      for (BasicBlock &BB : F)
        Blocks.push_back(&BB);
    unsigned OldSize = Blocks.size();
    ReduceCrashingBlocks(BD, TestFn).reduceList(Blocks, Error);
    if (Blocks.size() < OldSize)
      BD.EmitProgressBitcode(BD.getProgram(), "reduced-blocks");
  }

  // Attempt to delete instructions using bisection. This should help out nasty
  // cases with large basic blocks where the problem is at one end.
  if (!BugpointIsInterrupted) {
    std::vector<const Instruction*> Insts;
    for (const Function &F : *BD.getProgram())
      for (const BasicBlock &BB : F)
        for (const Instruction &I : BB)
          if (!isa<TerminatorInst>(&I))
            Insts.push_back(&I);

    ReduceCrashingInstructions(BD, TestFn).reduceList(Insts, Error);
  }

  // FIXME: This should use the list reducer to converge faster by deleting
  // larger chunks of instructions at a time!
  unsigned Simplification = 2;
  do {
    if (BugpointIsInterrupted) break;
    --Simplification;
    outs() << "\n*** Attempting to reduce testcase by deleting instruc"
           << "tions: Simplification Level #" << Simplification << '\n';

    // Now that we have deleted the functions that are unnecessary for the
    // program, try to remove instructions that are not necessary to cause the
    // crash.  To do this, we loop through all of the instructions in the
    // remaining functions, deleting them (replacing any values produced with
    // nulls), and then running ADCE and SimplifyCFG.  If the transformed input
    // still triggers failure, keep deleting until we cannot trigger failure
    // anymore.
    //
    unsigned InstructionsToSkipBeforeDeleting = 0;
  TryAgain:

    // Loop over all of the (non-terminator) instructions remaining in the
    // function, attempting to delete them.
    unsigned CurInstructionNum = 0;
    for (Module::const_iterator FI = BD.getProgram()->begin(),
           E = BD.getProgram()->end(); FI != E; ++FI)
      if (!FI->isDeclaration())
        for (Function::const_iterator BI = FI->begin(), E = FI->end(); BI != E;
             ++BI)
          for (BasicBlock::const_iterator I = BI->begin(), E = --BI->end();
               I != E; ++I, ++CurInstructionNum) {
            if (InstructionsToSkipBeforeDeleting) {
              --InstructionsToSkipBeforeDeleting;
            } else {
              if (BugpointIsInterrupted) goto ExitLoops;

              if (isa<LandingPadInst>(I))
                continue;

              outs() << "Checking instruction: " << *I;
              std::unique_ptr<Module> M =
                  BD.deleteInstructionFromProgram(&*I, Simplification);

              // Find out if the pass still crashes on this pass...
              if (TestFn(BD, M.get())) {