/// Are all available values identicalTo each other.
static bool areIdentical(llvm::DenseMap<SILBasicBlock *, SILValue> &Avails) {
  if (auto *First = dyn_cast<SingleValueInstruction>(Avails.begin()->second)) {
    for (auto Avail : Avails) {
      auto *Inst = dyn_cast<SingleValueInstruction>(Avail.second);
      if (!Inst)
        return false;
      if (!Inst->isIdenticalTo(First))
        return false;
    }
    return true;
  }

  auto *MVIR = dyn_cast<MultipleValueInstructionResult>(Avails.begin()->second);
  if (!MVIR)
    return false;

  for (auto Avail : Avails) {
    auto *Result = dyn_cast<MultipleValueInstructionResult>(Avail.second);
    if (!Result)
      return false;
    if (!Result->getParent()->isIdenticalTo(MVIR->getParent()) ||
        Result->getIndex() != MVIR->getIndex()) {
      return false;
    }
  }
  return true;
}

 // a function which searches for the key in the map passed in. Returns 0 if unsuccessful or the instruction number on success
 int findKey(llvm::DenseMap<llvm::Instruction*, int>& map, llvm::Instruction* key){
     llvm::DenseMap<llvm::Instruction*, int>::iterator iter = map.find(key);
     if(iter == map.end())
         return 0;    
     else
         return iter->second;
 }

static
llvm::MDNode *myGetType(const Type *type) {
  typedef llvm::DenseMap<const Type*, llvm::MDNode *>::const_iterator TypeNodeIter;
  TypeNodeIter i = myTypeDescriptors.find(type);
  if(i != myTypeDescriptors.end())
    return i->second;
  return NULL;
}

static void
updateSSAForUseOfInst(SILSSAUpdater &Updater,
                      SmallVectorImpl<SILArgument*> &InsertedPHIs,
                      const llvm::DenseMap<ValueBase *, SILValue> &ValueMap,
                      SILBasicBlock *Header, SILBasicBlock *EntryCheckBlock,
                      ValueBase *Inst) {
    if (Inst->use_empty())
        return;

    // Find the mapped instruction.
    assert(ValueMap.count(Inst) && "Expected to find value in map!");
    SILValue MappedValue = ValueMap.find(Inst)->second;
    assert(MappedValue);

    // For each use of a specific result value of the instruction.
    if (Inst->hasValue()) {
        SILValue Res(Inst);
        assert(Res->getType() == MappedValue->getType() && "The types must match");

        InsertedPHIs.clear();
        Updater.Initialize(Res->getType());
        Updater.AddAvailableValue(Header, Res);
        Updater.AddAvailableValue(EntryCheckBlock, MappedValue);


        // Because of the way that phi nodes are represented we have to collect all
        // uses before we update SSA. Modifying one phi node can invalidate another
        // unrelated phi nodes operands through the common branch instruction (that
        // has to be modified). This would invalidate a plain ValueUseIterator.
        // Instead we collect uses wrapping uses in branches specially so that we
        // can reconstruct the use even after the branch has been modified.
        SmallVector<UseWrapper, 8> StoredUses;
        for (auto *U : Res->getUses())
            StoredUses.push_back(UseWrapper(U));
        for (auto U : StoredUses) {
            Operand *Use = U;
            SILInstruction *User = Use->getUser();
            assert(User && "Missing user");

            // Ignore uses in the same basic block.
            if (User->getParent() == Header)
                continue;

            assert(User->getParent() != EntryCheckBlock &&
                   "The entry check block should dominate the header");
            Updater.RewriteUse(*Use);
        }
        // Canonicalize inserted phis to avoid extra BB Args.
        for (SILArgument *Arg : InsertedPHIs) {
            if (SILInstruction *Inst = replaceBBArgWithCast(Arg)) {
                Arg->replaceAllUsesWith(Inst);
                // DCE+SimplifyCFG runs as a post-pass cleanup.
                // DCE replaces dead arg values with undef.
                // SimplifyCFG deletes the dead BB arg.
            }
        }
    }
}

static void mapOperands(SILInstruction *I,
                        const llvm::DenseMap<ValueBase *, SILValue> &ValueMap) {
  for (auto &Opd : I->getAllOperands()) {
    SILValue OrigVal = Opd.get();
    ValueBase *OrigDef = OrigVal;
    auto Found = ValueMap.find(OrigDef);
    if (Found != ValueMap.end()) {
      SILValue MappedVal = Found->second;
      Opd.set(MappedVal);
    }
  }
}

  void addDecl(llvm::DenseMap<K, FoundDecl> &Map, K Key, FoundDecl FD) {
    // Add the declaration if we haven't found an equivalent yet, otherwise
    // replace the equivalent if the found decl has a higher access level.
    auto existingDecl = Map.find(Key);

    if ((existingDecl == Map.end()) ||
        (Map[Key].first->getFormalAccess() < FD.first->getFormalAccess())) {
      if (existingDecl != Map.end())
        declsToReport.erase({existingDecl->getSecond().first});
      Map[Key] = FD;
      declsToReport.insert(FD);
    }
  }

int Graph::getTaintedEdges () {
	int countEdges=0;

	for (llvm::DenseMap<GraphNode*, bool>::iterator it = taintedMap.begin(); it != taintedMap.end(); ++it) {
		std::map<GraphNode*, edgeType> succs = it->first->getSuccessors();
		for (std::map<GraphNode*, edgeType>::iterator succ = succs.begin(), s_end = succs.end(); succ != s_end; succ++) {
			if (taintedMap.count(succ->first) > 0) {
				countEdges++;
			}
		}
	}
	return (countEdges);
}

static void mapOperands(SILInstruction *I,
                        const llvm::DenseMap<ValueBase *, SILValue> &ValueMap) {
  for (auto &Opd : I->getAllOperands()) {
    SILValue OrigVal = Opd.get();
    ValueBase *OrigDef = OrigVal.getDef();
    auto Found = ValueMap.find(OrigDef);
    if (Found != ValueMap.end()) {
      SILValue MappedVal = Found->second;
      unsigned ResultIdx = OrigVal.getResultNumber();
      // All mapped instructions have their result number set to zero. Except
      // for arguments that we followed along one edge to their incoming value
      // on that edge.
      if (isa<SILArgument>(OrigDef))
        ResultIdx = MappedVal.getResultNumber();
      Opd.set(SILValue(MappedVal.getDef(), ResultIdx));
    }
  }
}

void CGObjCJit::AddMethodsToClass(void *theClass) {

  // Methods need to be added at runtime. Method function pointers (IMP)
  // are not available until then.

  CGBuilderTy Builder(JitInitBlock);
  CodeGen::CodeGenFunction CGF(CGM);

  void *theMetaclass = _object_getClass(theClass);

  llvm::DenseMap<const ObjCMethodDecl*, llvm::Function*>::iterator I =
      MethodDefinitions.begin();

  while (I != MethodDefinitions.end()) {
    const ObjCMethodDecl *D = I->first;
    std::string TypeStr;
    CGM.getContext().getObjCEncodingForMethodDecl(const_cast<ObjCMethodDecl*>(D),
        TypeStr);
    const char* TypeCStr = // keep in a set
      MethodTypeStrings.insert(MethodTypeStrings.begin(), TypeStr)->c_str();
    void *ClassObject = D->isClassMethod() ? theMetaclass : theClass;
    llvm::Value *ClassArg =
      llvm::Constant::getIntegerValue(ObjCTypes.ClassPtrTy,
                                      llvm::APInt(sizeof(void*) * 8,
                                          (uint64_t)ClassObject));
    llvm::Value *SelectorArg = GetSelector(CGF, D->getSelector());
    llvm::Value *TypeArg =
      llvm::Constant::getIntegerValue(ObjCTypes.Int8PtrTy,
                                      llvm::APInt(sizeof(void*) * 8,
                                          (uint64_t)TypeCStr));

    llvm::Value *MethodArg = Builder.CreateBitCast(I->second, ImpPtrTy);

    Builder.CreateCall4(fn_class_addMethod,
                        ClassArg,
                        SelectorArg,
                        MethodArg,
                        TypeArg);
    I++;
  }

  // Done with list for this implementation, so clear it
  MethodDefinitions.clear();
}

bool ClangASTImporter::LayoutRecordType(
    const clang::RecordDecl *record_decl, uint64_t &bit_size,
    uint64_t &alignment,
    llvm::DenseMap<const clang::FieldDecl *, uint64_t> &field_offsets,
    llvm::DenseMap<const clang::CXXRecordDecl *, clang::CharUnits>
        &base_offsets,
    llvm::DenseMap<const clang::CXXRecordDecl *, clang::CharUnits>
        &vbase_offsets) {
  RecordDeclToLayoutMap::iterator pos =
      m_record_decl_to_layout_map.find(record_decl);
  bool success = false;
  base_offsets.clear();
  vbase_offsets.clear();
  if (pos != m_record_decl_to_layout_map.end()) {
    bit_size = pos->second.bit_size;
    alignment = pos->second.alignment;
    field_offsets.swap(pos->second.field_offsets);
    base_offsets.swap(pos->second.base_offsets);
    vbase_offsets.swap(pos->second.vbase_offsets);
    m_record_decl_to_layout_map.erase(pos);
    success = true;
  } else {
    bit_size = 0;
    alignment = 0;
    field_offsets.clear();
  }
  return success;
}

namespace pyston {

using namespace pyston::assembler;

#define MAX_RETRY_BACKOFF 1024

// TODO not right place for this...
int64_t ICInvalidator::version() {
    return cur_version;
}

void ICInvalidator::addDependent(ICSlotInfo* entry_info) {
    dependents.insert(entry_info);
}

void ICInvalidator::invalidateAll() {
    cur_version++;
    for (ICSlotInfo* slot : dependents) {
        slot->clear();
    }
    dependents.clear();
}

void ICSlotInfo::clear() {
    ic->clear(this);
}

ICSlotRewrite::ICSlotRewrite(ICInfo* ic, const char* debug_name)
    : ic(ic), debug_name(debug_name), buf((uint8_t*)malloc(ic->getSlotSize())), assembler(buf, ic->getSlotSize()) {
    assembler.nop();

    if (VERBOSITY() >= 4)
        printf("starting %s icentry\n", debug_name);
}

ICSlotRewrite::~ICSlotRewrite() {
    free(buf);
}

void ICSlotRewrite::abort() {
    ic->retry_backoff = std::min(MAX_RETRY_BACKOFF, 2 * ic->retry_backoff);
    ic->retry_in = ic->retry_backoff;
}

ICSlotInfo* ICSlotRewrite::prepareEntry() {
    this->ic_entry = ic->pickEntryForRewrite(debug_name);
    return this->ic_entry;
}

uint8_t* ICSlotRewrite::getSlotStart() {
    assert(ic_entry != NULL);
    return (uint8_t*)ic->start_addr + ic_entry->idx * ic->getSlotSize();
}

// Map of gc pointers -> number of ics that point tot hem.
static llvm::DenseMap<void*, int> ic_gc_references;

void ICSlotRewrite::commit(CommitHook* hook, std::vector<void*> gc_references) {
    bool still_valid = true;
    for (int i = 0; i < dependencies.size(); i++) {
        int orig_version = dependencies[i].second;
        ICInvalidator* invalidator = dependencies[i].first;
        if (orig_version != invalidator->version()) {
            still_valid = false;
            break;
        }
    }
    if (!still_valid) {
        if (VERBOSITY() >= 3)
            printf("not committing %s icentry since a dependency got updated before commit\n", debug_name);
        return;
    }

    uint8_t* slot_start = getSlotStart();
    uint8_t* continue_point = (uint8_t*)ic->continue_addr;

    bool do_commit = hook->finishAssembly(continue_point - slot_start);

    if (!do_commit)
        return;

    assert(!assembler.hasFailed());

    for (int i = 0; i < dependencies.size(); i++) {
        ICInvalidator* invalidator = dependencies[i].first;
        invalidator->addDependent(ic_entry);
    }

    ic->next_slot_to_try++;

    // if (VERBOSITY()) printf("Commiting to %p-%p\n", start, start + ic->slot_size);
    memcpy(slot_start, buf, ic->getSlotSize());

    for (auto p : ic_entry->gc_references) {
        int& i = ic_gc_references[p];
        if (i == 1)
            ic_gc_references.erase(p);
        else
            --i;
    }
//.........这里部分代码省略.........

 // a function which iterates over the map passed in, printing the key & value fields of the map
 int printMap(llvm::DenseMap<llvm::Instruction*, int>&map){
     llvm::DenseMap<llvm::Instruction*, int>::iterator i = map.begin();
     for(; i!= map.end(); ++i)
         std::cerr << "Key: " << i->first << "\tValue: " << i->second << "\n";
     return 0;
 }

    bool isDeclCandidate(FunctionDecl * FDecl) {
      if (m_NonNullArgIndexs.count(FDecl))
        return true;

      if (llvm::isa<CXXRecordDecl>(FDecl))
        return true;

      std::bitset<32> ArgIndexs;
      for (specific_attr_iterator<NonNullAttr>
             I = FDecl->specific_attr_begin<NonNullAttr>(),
             E = FDecl->specific_attr_end<NonNullAttr>(); I != E; ++I) {

        NonNullAttr *NonNull = *I;
        for (NonNullAttr::args_iterator i = NonNull->args_begin(),
               e = NonNull->args_end(); i != e; ++i) {
          ArgIndexs.set(*i);
        }
      }

      if (ArgIndexs.any()) {
        m_NonNullArgIndexs.insert(std::make_pair(FDecl, ArgIndexs));
        return true;
      }
      return false;
    }

ICInfo* getICInfo(void* rtn_addr) {
    // TODO: load this from the CF instead of tracking it separately
    auto&& it = ics_by_return_addr.find(rtn_addr);
    if (it == ics_by_return_addr.end())
        return NULL;
    return it->second;
}

 // Return a range of scopes for the given closure. The elements of the
 // returned range have type `SILFunction *` and are non-null. Return an empty
 // range for a SILFunction that is not a closure or is a dead closure.
 ScopeRange getClosureScopes(SILFunction *ClosureF) {
   IndexRange indexRange(nullptr, nullptr);
   auto closureScopesPos = closureToScopesMap.find(ClosureF);
   if (closureScopesPos != closureToScopesMap.end()) {
     auto &indexedScopes = closureScopesPos->second;
     indexRange = IndexRange(indexedScopes.begin(), indexedScopes.end());
   }
   return makeOptionalTransformRange(indexRange,
                                     IndexLookupFunc(indexedScopes));
 }

  int lookupScopeIndex(SILFunction *scopeFunc) {
    auto indexPos = scopeToIndexMap.find(scopeFunc);
    if (indexPos != scopeToIndexMap.end())
      return indexPos->second;

    int scopeIdx = indexedScopes.size();
    scopeToIndexMap[scopeFunc] = scopeIdx;
    indexedScopes.push_back(scopeFunc);
    return scopeIdx;
  }

 void erase(SILFunction *F) {
   // If this function is a mapped closure scope, remove it, leaving a nullptr
   // sentinel.
   auto indexPos = scopeToIndexMap.find(F);
   if (indexPos != scopeToIndexMap.end()) {
     indexedScopes[indexPos->second] = nullptr;
     scopeToIndexMap.erase(F);
   }
   // If this function is a closure, remove it.
   closureToScopesMap.erase(F);
 }

llvm::Function *CGObjCJit::GenerateMethod(const ObjCMethodDecl *OMD,
                                          const ObjCContainerDecl *CD) {

  assert(CD && "Missing container decl in GetNameForMethod");

  llvm::SmallString<256> Name;
  llvm::raw_svector_ostream OS(Name);

  OS << '\01' << (OMD->isInstanceMethod() ? '-' : '+')
     << '[' << CD->getName();
  if (const ObjCCategoryImplDecl *CID =
        dyn_cast<ObjCCategoryImplDecl>(OMD->getDeclContext())) {
    OS << '(' << CID << ')';
  }
  OS << ' ' << OMD->getSelector().getAsString() << ']';

  CodeGenTypes &Types = CGM.getTypes();
  llvm::FunctionType *MethodTy =
    Types.GetFunctionType(Types.arrangeObjCMethodDeclaration(OMD));
  llvm::Function *Method =
    llvm::Function::Create(MethodTy,
                           llvm::GlobalValue::InternalLinkage,
                           Name.str(),
                           &CGM.getModule());
  MethodDefinitions.insert(std::make_pair(OMD, Method));

  return Method;
}

 /// Insert a block into the worklist and set its stack depth.
 void insert(SILBasicBlock *BB, int StackDepth) {
   auto Iter = Block2StackDepth.find(BB);
   if (Iter != Block2StackDepth.end()) {
     // We already handled the block.
     assert(StackDepth >= 0);
     if (Iter->second < 0) {
       // Update the stack depth if we didn't set it yet for the block.
       Iter->second = StackDepth;
     } else {
       assert(Iter->second == StackDepth &&
                "inconsistent stack depth at a CFG merge point");
     }
   } else {
     Block2StackDepth[BB] = StackDepth;
     ToHandle.push_back(BB);
   }
 }

void ICSlotRewrite::commit(CommitHook* hook, std::vector<void*> gc_references) {
    bool still_valid = true;
    for (int i = 0; i < dependencies.size(); i++) {
        int orig_version = dependencies[i].second;
        ICInvalidator* invalidator = dependencies[i].first;
        if (orig_version != invalidator->version()) {
            still_valid = false;
            break;
        }
    }
    if (!still_valid) {
        if (VERBOSITY() >= 3)
            printf("not committing %s icentry since a dependency got updated before commit\n", debug_name);
        return;
    }

    uint8_t* slot_start = getSlotStart();
    uint8_t* continue_point = (uint8_t*)ic->continue_addr;

    bool do_commit = hook->finishAssembly(continue_point - slot_start);

    if (!do_commit)
        return;

    assert(!assembler.hasFailed());

    for (int i = 0; i < dependencies.size(); i++) {
        ICInvalidator* invalidator = dependencies[i].first;
        invalidator->addDependent(ic_entry);
    }

    ic->next_slot_to_try++;

    // if (VERBOSITY()) printf("Commiting to %p-%p\n", start, start + ic->slot_size);
    memcpy(slot_start, buf, ic->getSlotSize());

    for (auto p : ic_entry->gc_references) {
        int& i = ic_gc_references[p];
        if (i == 1)
            ic_gc_references.erase(p);
        else
            --i;
    }
    ic_entry->gc_references = std::move(gc_references);
    for (auto p : ic_entry->gc_references)
        ic_gc_references[p]++;

    ic->times_rewritten++;

    if (ic->times_rewritten == IC_MEGAMORPHIC_THRESHOLD) {
        static StatCounter megamorphic_ics("megamorphic_ics");
        megamorphic_ics.log();
    }

    llvm::sys::Memory::InvalidateInstructionCache(slot_start, ic->getSlotSize());
}