//
// This method binds the parameter to a specified value, updating the worklist
// Binding a value updates any combination zeros it completes as a side effect
// Binding a value also adds items to work list as a side effect
//
bool Parameter::Bind(int value, WorkList& worklist)
{
    DOUT(L"Binding " << m_name << L" to value " << value << L".\n");
    assert(!m_bound);
    assert(value < m_valueCount);

    m_result.push_back(value);
    m_currentValue = value;
    m_bound = true;

    for( auto & combination : m_combinations )
    {
        if( combination->AddBinding() == combination->GetParameterCount() - 1 )
        {
            // Add any parameter that completes a combination to work list
            for( int n = 0; n < combination->GetParameterCount(); ++n )
            {
                if( !( (*combination)[ n ] ).GetBoundCount() )
                {
                    worklist.AddItem( &( *combination )[ n ] );
                }
            }
        }
    }

    worklist.Print();
    
    return true;
}

int main()
{

	CPlateJudge cplatejudge;
	WorkList wlist;
	string file_path = "D:/workspace/nocolor3/";
	string file_result = "D:/workspace/onlycolor/";
	string file_error = "D:/workspace/noplate/";
	int index = 1;
	int flagerr = 0;
	wlist.Wlist(file_path, file_result, file_error, index, flagerr);
	
	
	//waitKey(0);
	system("pause");
	return 0;
}

/*!
 * Get the reverse topo order of scc call graph
 */
void MRGenerator::getCallGraphSCCRevTopoOrder(WorkList& worklist) {

    NodeStack& topoOrder = callGraphSCC->topoNodeStack();
    while(!topoOrder.empty()) {
        NodeID callgraphNodeID = topoOrder.top();
        topoOrder.pop();
        worklist.push(callgraphNodeID);
    }
}

/*!
 * Generate memory regions for calls
 */
void MRGenerator::collectModRefForCall() {

    DBOUT(DGENERAL, outs() << pasMsg("\t\tCollect Callsite PointsTo \n"));

    /// collect points-to information for callsites
    NodeToPTSSMap cachedPtsMap;
    for(PAG::CallSiteSet::const_iterator it =  pta->getPAG()->getCallSiteSet().begin(),
            eit = pta->getPAG()->getCallSiteSet().end(); it!=eit; ++it)
        collectCallSitePts(*it,cachedPtsMap);

    DBOUT(DGENERAL, outs() << pasMsg("\t\tPerform Callsite Mod-Ref \n"));

    WorkList worklist;
    getCallGraphSCCRevTopoOrder(worklist);

    while(!worklist.empty()) {
        NodeID callGraphNodeID = worklist.pop();
        /// handle all sub scc nodes of this rep node
        const NodeBS& subNodes = callGraphSCC->subNodes(callGraphNodeID);
        for(NodeBS::iterator it = subNodes.begin(), eit = subNodes.end(); it!=eit; ++it) {
            PTACallGraphNode* subCallGraphNode = callGraph->getCallGraphNode(*it);
            /// Get mod-ref of all callsites calling callGraphNode
            modRefAnalysis(subCallGraphNode,worklist);
        }
    }

    DBOUT(DGENERAL, outs() << pasMsg("\t\tAdd PointsTo to Callsites \n"));

    for(PAG::CallSiteSet::const_iterator it =  pta->getPAG()->getCallSiteSet().begin(),
            eit = pta->getPAG()->getCallSiteSet().end(); it!=eit; ++it) {
        if(hasRefSideEffectOfCallSite(*it)) {
            NodeBS refs = getRefSideEffectOfCallSite(*it);
            PointsTo rcpts(refs);
            addCPtsToCallSiteRefs(rcpts,*it);
        }
        if(hasModSideEffectOfCallSite(*it)) {
            NodeBS mods = getModSideEffectOfCallSite(*it);
            PointsTo mcpts(mods);
            addCPtsToCallSiteMods(mcpts,*it);
        }
    }
}

/*!
 * Get all objects might pass into callee from a callsite
 */
void MRGenerator::collectCallSitePts(CallSite cs,NodeToPTSSMap& cachedPtsMap) {
    NodeBS& pts = csToCallPtsMap[cs];
    WorkList worklist;
    if (pta->getPAG()->hasCallSiteArgsMap(cs)) {
        const PAG::PAGNodeList& args = pta->getPAG()->getCallSiteArgsList(cs);
        for(PAG::PAGNodeList::const_iterator itA = args.begin(), ieA = args.end(); itA!=ieA; ++itA) {
            const PAGNode* node = *itA;
            if(node->isPointer())
                worklist.push(node->getId());
        }
    }

    while(!worklist.empty()) {
        NodeID nodeId = worklist.pop();
        PointsTo& tmp = pta->getPts(nodeId);
        for(PointsTo::iterator it = tmp.begin(), eit = tmp.end(); it!=eit; ++it) {
            pts |= CollectPtsChain(*it,cachedPtsMap);
        }
    }
}

  Profiler::~Profiler() {
    for(MethodMap::iterator i = methods_.begin();
        i != methods_.end();
        i++) {
      delete i->second;
    }

    WorkList work;

    work.push_back(root_);

    while(work.size() > 0) {
      Node* node = work.back();
      work.pop_back();

      Node* sub = node->sub_nodes();

      while(sub) {
        work.push_back(sub);
        sub = sub->sibling();
      }

      delete node;
    }
  }

/*!
 * Call site mod-ref analysis
 * Compute mod-ref of all callsites invoking this call graph node
 */
void MRGenerator::modRefAnalysis(PTACallGraphNode* callGraphNode, WorkList& worklist) {

    /// add ref/mod set of callee to its invocation callsites at caller
    for(PTACallGraphNode::iterator it = callGraphNode->InEdgeBegin(), eit = callGraphNode->InEdgeEnd();
            it!=eit; ++it) {
        PTACallGraphEdge* edge = *it;

        /// handle direct callsites
        for(PTACallGraphEdge::CallInstSet::iterator cit = edge->getDirectCalls().begin(),
                ecit = edge->getDirectCalls().end(); cit!=ecit; ++cit) {
            NodeBS mod = getModSideEffectOfFunction(callGraphNode->getFunction());
            NodeBS ref = getRefSideEffectOfFunction(callGraphNode->getFunction());
            /// ref set include all mods
            ref |= mod;
            CallSite cs = analysisUtil::getLLVMCallSite(*cit);
            // add ref set
            bool refchanged = addRefSideEffectOfCallSite(cs, ref);
            // add mod set
            bool modchanged = addModSideEffectOfCallSite(cs, mod);
            if(refchanged || modchanged)
                worklist.push(edge->getSrcID());
        }
        /// handle indirect callsites
        for(PTACallGraphEdge::CallInstSet::iterator cit = edge->getIndirectCalls().begin(),
                ecit = edge->getIndirectCalls().end(); cit!=ecit; ++cit) {
            NodeBS mod = getModSideEffectOfFunction(callGraphNode->getFunction());
            NodeBS ref = getRefSideEffectOfFunction(callGraphNode->getFunction());
            /// ref set include all mods
            ref |= mod;
            CallSite cs = analysisUtil::getLLVMCallSite(*cit);
            // add ref set
            bool refchanged = addRefSideEffectOfCallSite(cs, ref);
            // add mod set
            bool modchanged = addModSideEffectOfCallSite(cs, mod);
            if(refchanged || modchanged)
                worklist.push(edge->getSrcID());
        }
    }
}

/*!
 * Recurisively collect all points-to of the whole struct fields
 */
NodeBS& MRGenerator::CollectPtsChain(NodeID id, NodeToPTSSMap& cachedPtsMap) {
    NodeID baseId = pta->getPAG()->getBaseObjNode(id);
    NodeToPTSSMap::iterator it = cachedPtsMap.find(baseId);
    if(it!=cachedPtsMap.end())
        return it->second;
    else {
        PointsTo& pts = cachedPtsMap[baseId];
        pts |= pta->getPAG()->getFieldsAfterCollapse(baseId);

        WorkList worklist;
        for(PointsTo::iterator it = pts.begin(), eit = pts.end(); it!=eit; ++it)
            worklist.push(*it);

        while(!worklist.empty()) {
            NodeID nodeId = worklist.pop();
            PointsTo& tmp = pta->getPts(nodeId);
            for(PointsTo::iterator it = tmp.begin(), eit = tmp.end(); it!=eit; ++it) {
                pts |= CollectPtsChain(*it,cachedPtsMap);
            }
        }
        return pts;
    }

}

  void Profiler::results(Env* env, rtable profile, rtable nodes, rtable methods,
                         KeyMap& keys, uint64_t runtime)
  {

    current_me_->stop_all(this, env);

    WorkList work;

    // If we haven't even gone for a total of longer than 10x the threshold,
    // just disable the threshold.
    if(runtime < 10 * threshold_) threshold_ = 0;

    env->table_store(profile, env->symbol("total_nodes"), env->integer_new(nodes_));

    rarray roots = env->array_new(root_->count_sub_nodes());
    env->table_store(profile, env->symbol("roots"), roots);

    int idx = 0;
    Node* sub = root_->sub_nodes();

    while(sub) {
      if(sub->total() >= threshold_) {
        env->array_set(roots, idx++, env->integer_new(sub->id()));
        work.push_back(sub);
      }

      sub = sub->sibling();
    }

    while(work.size() > 0) {
      Node* node = work.back();
      work.pop_back();

      add_node(env, nodes, methods, node, work, keys, threshold_);
    }
  }

  static void add_node(Env* env, rtable nodes, rtable methods, Node* node,
                       WorkList& work, KeyMap& keys, uint32_t threshold)
  {
    // We haven't exited this method yet, so its stats won't be accurate
    if(node->method()->timer.started()) return;

    rinteger key = env->integer_new(node->id());

    rarray tbl = env->array_new(5);

    env->table_store(nodes, key, tbl);

    robject meth_key = add_method(env, methods, node->method(), keys);

    env->array_set(tbl, 0, meth_key);
    env->array_set(tbl, 1, env->integer_new(node->total()));
    env->array_set(tbl, 2, env->integer_new(node->called()));

    int count = node->count_sub_nodes();
    env->array_set(tbl, 3, env->integer_new(count));

    rarray ary = env->array_new(count);

    int idx = 0;

    Node* sub = node->sub_nodes();

    while(sub) {
      if(sub->total() >= threshold) {
        env->array_set(ary, idx++, env->integer_new(sub->id()));
        work.push_back(sub);
      }

      sub = sub->sibling();
    }

    env->array_set(tbl, 4, ary);
  }

void eliminateDeadCode(Trace* trace, IRFactory* irFactory) {
  auto removeEmptyExitTraces = [&] {
    trace->getExitTraces().remove_if([](Trace* exit) {
      return exit->getBlocks().empty();
    });
  };

  // kill unreachable code and remove any traces that are now empty
  BlockList blocks = removeUnreachable(trace, irFactory);
  removeEmptyExitTraces();

  // mark the essential instructions and add them to the initial
  // work list; this will also mark reachable exit traces. All
  // other instructions marked dead.
  DceState state(irFactory, DceFlags());
  WorkList wl = initInstructions(trace, blocks, state, irFactory);

  // process the worklist
  while (!wl.empty()) {
    auto* inst = wl.front();
    wl.pop_front();
    for (uint32_t i = 0; i < inst->getNumSrcs(); i++) {
      SSATmp* src = inst->getSrc(i);
      if (src->getInstruction()->getOpcode() == DefConst) {
        continue;
      }
      IRInstruction* srcInst = src->getInstruction();
      if (state[srcInst].isDead()) {
        state[srcInst].setLive();
        wl.push_back(srcInst);
      }
      // <inst> consumes <srcInst> which is an IncRef, so we mark <srcInst> as
      // REFCOUNT_CONSUMED. If the source instruction is a GuardType and guards
      // to a maybeCounted type, we need to trace through to the source for
      // refcounting purposes.
      while (srcInst->getOpcode() == GuardType &&
             srcInst->getTypeParam().maybeCounted()) {
        srcInst = srcInst->getSrc(0)->getInstruction();
      }
      if (inst->consumesReference(i) && srcInst->getOpcode() == IncRef) {
        if (inst->getTrace()->isMain() || !srcInst->getTrace()->isMain()) {
          // <srcInst> is consumed from its own trace.
          state[srcInst].setCountConsumed();
        } else {
          // <srcInst> is consumed off trace.
          if (!state[srcInst].countConsumed()) {
            // mark <srcInst> as REFCOUNT_CONSUMED_OFF_TRACE unless it is
            // also consumed from its own trace.
            state[srcInst].setCountConsumedOffTrace();
          }
        }
      }
    }
  }

  // Optimize IncRefs and DecRefs.
  forEachTrace(trace, [&](Trace* t) { optimizeRefCount(t, state); });

  if (RuntimeOption::EvalHHIREnableSinking) {
    // Sink IncRefs consumed off trace.
    sinkIncRefs(trace, irFactory, state);
  }

  // now remove instructions whose id == DEAD
  removeDeadInstructions(trace, state);
  for (Trace* exit : trace->getExitTraces()) {
    removeDeadInstructions(exit, state);
  }

  // and remove empty exit traces
  removeEmptyExitTraces();
}

PointerAnalysis::ArgumentAttributes 
PointerAnalysis::objectPass(Function *funct, PointerAnalysis::ArgumentAttributes argAttrs)
{
	ArgumentAttributes ret(1);
	ret[0] = UNBOUND_ATTR;
	ArgumentAttributes UNBOUND(1);
	ret[0] = UNBOUND_ATTR;

	WorkList<Node> worklist;
	NodeSet visits;
	ValueMap exactOut, boundOut;

	ValueSet exactArgs, boundArgs;
	BoundMap exactBounds;
	
	llvm::DataLayout DL(module);

	// how to test no funct body?
	if (funct->begin() == funct->end())
		return ret;

	for (auto &globalVal: module->globals()) {
		GlobalVariable *gv = dyn_cast<GlobalVariable>(&globalVal);
		exactBounds[gv] = globalBounds[gv];
	}

	auto args = funct->arg_begin();
	for (size_t i = 0; i < funct->arg_size(); i++) {
		if (argAttrs[i] == UNBOUND_ATTR) {
			++args;
			continue;
		}

		Value *arg = &(*args);
		boundArgs.insert( arg );
		if (argAttrs[i] != DYNBOUND_ATTR) {
			exactArgs.insert( arg );
			exactBounds[arg] = argAttrs[i];
		}
		++args;
	}
	
	outs() << "********** visiting " << funct->getName() << " **********\n";
	printX(argAttrs);
	printX(exactArgs);
	printX(boundArgs);

	Node entry = &funct->getEntryBlock();
	worklist.enqueue(entry);

	std::unordered_set<Node> exits;
	for (auto &bb: *funct)
		if ( llvm::succ_begin(&bb) == llvm::succ_end(&bb) )
			exits.insert(&bb);

	while (!worklist.empty()) {
		Node next = worklist.dequeue();
		bool changed = false;
	
		bool visited = (visits.count(next) != 0);
		visits.insert(next);

		outs() << "visiting " << next->getName() << "\n";

		ValueSet oldExact = getOrInsert(next, exactOut), oldBound = getOrInsert(next, boundOut);
		ValueSet exactTemp, boundTemp;

		if (next == entry) {
			exactTemp = merge( exactTemp, exactArgs );
			exactTemp = merge( exactTemp, globals );
			boundTemp = merge( boundTemp, boundArgs );
			boundTemp = merge( boundTemp, globals );
		} else {
			for (auto i = pred_begin(next); i != pred_end(next); ++i) {
				exactTemp = merge( exactTemp, getOrInsert(*i, exactOut) );
				boundTemp = merge( boundTemp, getOrInsert(*i, boundOut) );
			}
		}

		for (auto &i : *next) {
			Instruction *inst = &i;

			if (isa<CallInst>(inst)) {
				// do inter-procedual analysis
				// what if I am calling some external library: handle that either
				// if (is a well-known exteral function) {
					// some external library
					// analyze it at best effort
				// } else {
					// not an external function
					// compare the args to the last time we enter this callsite
					// if they are the same, skip (TODO: pull out what we've got last time)
					// otherwise analyze it again
				// }

				CallInst *call_inst = dyn_cast<CallInst> (inst);
				Function *callee = call_inst->getCalledFunction();
				if (callee == nullptr)
					continue;

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

/*
 * Sink IncRefs consumed off trace.
 * Assumptions: Flow graph must not have critical edges, and the instructions
 * have been annotated already by the DCE algorithm.  This pass uses
 * the REFCOUNT_CONSUMED* flags to copy IncRefs from the main trace to each
 * exit trace that consumes the incremented pointer.
 * 1. toSink = {}
 * 2. iterate forwards over the main trace:
 *    * when a movable IncRef is found, insert into toSink list and mark
 *      it as DEAD.
 *    * If a decref of a dead incref is found, remove the corresponding
 *      incref from toSink, and mark the decref DEAD because too.
 *    * the first time we see a branch to an exit trace, process the
 *      exit tace.
 * 3. to process an exit trace:
 *    * clone each IncRef found in toSink then prepend to the exit trace.
 *    * replace each use of the original incref's result with the new
 *      incref's result.
 */
void sinkIncRefs(Trace* trace, IRFactory* irFactory, DceState& state) {
  assert(trace->isMain());

  auto copyPropTrace = [] (Trace* trace) {
    forEachInst(trace, copyProp);
  };

  WorkList toSink;

  auto processExit = [&] (Trace* exit) {
    // Sink REFCOUNT_CONSUMED_OFF_TRACE IncRefs before the first non-label
    // instruction, and create a mapping between the original tmps to the sunk
    // tmps so that we can later replace the original ones with the sunk ones.
    std::vector<SSATmp*> sunkTmps(irFactory->numTmps(), nullptr);
    for (auto* inst : boost::adaptors::reverse(toSink)) {
      // prepend inserts an instruction to the beginning of a block, after
      // the label. Therefore, we iterate through toSink in the reversed order.
      IRInstruction* sunkInst = irFactory->gen(IncRef, inst->getSrc(0));
      state[sunkInst].setLive();
      exit->front()->prepend(sunkInst);

      auto dstId = inst->getDst()->getId();
      assert(!sunkTmps[dstId]);
      sunkTmps[dstId] = sunkInst->getDst();
    }
    forEachInst(exit, [&](IRInstruction* inst) {
      // Replace the original tmps with the sunk tmps.
      for (uint32_t i = 0; i < inst->getNumSrcs(); ++i) {
        SSATmp* src = inst->getSrc(i);
        if (SSATmp* sunkTmp = sunkTmps[src->getId()]) {
          inst->setSrc(i, sunkTmp);
        }
      }
    });
    // Do copyProp at last, because we need to keep REFCOUNT_CONSUMED_OFF_TRACE
    // Movs as the prototypes for sunk instructions.
    copyPropTrace(exit);
  };

  // An exit trace may be entered from multiple exit points. We keep track of
  // which exit traces we already pushed sunk IncRefs to, so that we won't push
  // them multiple times.
  boost::dynamic_bitset<> pushedTo(irFactory->numBlocks());
  forEachInst(trace, [&](IRInstruction* inst) {
    if (inst->getOpcode() == IncRef) {
      // Must be REFCOUNT_CONSUMED or REFCOUNT_CONSUMED_OFF_TRACE;
      // otherwise, it should be already removed in optimizeRefCount.
      if (state[inst].countConsumedOffTrace()) {
        inst->setOpcode(Mov);
        // Mark them as dead so that they'll be removed later.
        state[inst].setDead();
        // Put all REFCOUNT_CONSUMED_OFF_TRACE IncRefs to the sinking list.
        toSink.push_back(inst);
      } else if (!state[inst].isDead()) {
        assert(state[inst].countConsumed());
      }
    }
    if (inst->getOpcode() == DecRefNZ) {
      IRInstruction* srcInst = inst->getSrc(0)->getInstruction();
      if (state[srcInst].isDead()) {
        state[inst].setDead();
        // This may take O(I) time where I is the number of IncRefs
        // in the main trace.
        toSink.remove(srcInst);
      }
    }
    if (Block* target = inst->getTaken()) {
      if (!pushedTo[target->getId()]) {
        pushedTo[target->getId()] = 1;
        Trace* exit = target->getTrace();
        if (exit != trace) processExit(exit);
      }
    }
  });

  // Do copyProp at last, because we need to keep REFCOUNT_CONSUMED_OFF_TRACE
  // Movs as the prototypes for sunk instructions.
  copyPropTrace(trace);
}

void SCCP::analyze() {
    // Queue the first block to start iteration.
    cfgwork.push(ir->begin);
    while (!cfgwork.empty()) {
        while (!cfgwork.empty())
            analyzeBlock(cfgwork.pop());
        while (!ssawork.empty())
            analyzeSSA(ssawork.pop());
    }
    // TODO own cmdline flag? something less intrusive
    // if ((enable_verbose || enable_printir) && ir->size() > 1000)
    //  printCounts(ir, eval_counts);
}

/**
 * helper - add the users of the Defs of a given
 * instruction to the passed worklist.
 *
 * This encapsulates several nontrivial pieces of logic:
 * 1. Skip use instructions that haven't been reached yet.
 * 2. Skip over dead arms of constant conditionals.
 * 3. Jump the call-site gap between block delims.
 *    (goto -> label, cond -> arm)
 * 4. When reaching a block the first time, mark all its instructions reached
 *    *and* enque them, because they could have been previously skipped.
 */
void SCCP::addInstrUsers(Instr* instr) {
    for (AllUsesRange u(instr); !u.empty(); u.popFront()) {
        Instr* use_instr = user(u.front());
        if (mark.get(use_instr->id))
            ssawork.add(use_instr);
    }
}

EXTERN_C    int  worklist_remove(long*              rpcmsg,
                                 ccs_pipe_t*        pipe,
                                 k5_ipc_stream*      stream,
                                 time_t*            sst) {
        WorkItem*   item    = NULL;
        cc_int32    err     = worklist.remove(&item);

        *rpcmsg         = item->type();
        *pipe           = item->take_pipe();
        *stream         = item->take_payload();
        *sst            = item->sst();
        delete item;
        return err;
        }

EXTERN_C    int worklist_add(   const long          rpcmsg, 
                                const ccs_pipe_t    pipe, 
                                const k5_ipc_stream stream, 
                                const time_t        serverStartTime) {
        return worklist.add(new WorkItem(stream, pipe, rpcmsg, serverStartTime) );
        }

/**
 * Enque the block.  If it is already visited, just enqueu it.
 * Otherwise, mark it reached and enque all the instructions in the block.
 */
void SCCP::addBlock(BlockStartInstr* block) {
    if (!mark.get(block->id))
        cfgwork.push(block);
    else
        ssawork.add(block);
}