bool compareDfaOrigins(const DfaStates& nfasWithInput, DfaVertex* dfa2p) {
	// Return true if the NFA nodes both DFAs came from are the same list
	// Assume there are no duplicates in either input list or NFAs under dfa2
	nextStep();
	// Mark all input vertexes
	int num1s = 0;
	for (DfaStates::const_iterator nfaIt=nfasWithInput.begin(); nfaIt!=nfasWithInput.end(); ++nfaIt) {
	    DfaVertex* nfaStatep = *nfaIt;
	    nfaStatep->user(m_step);
	    num1s++;
	}
	if (!num1s) v3fatalSrc("DFA node construction that contains no NFA states");

	// Check comparison; must all be marked
	// (Check all in dfa2p were in dfa1p)
	int num2s = 0;
	for (V3GraphEdge* dfaEdgep = dfa2p->outBeginp(); dfaEdgep; dfaEdgep=dfaEdgep->outNextp()) {
	    if (nfaState(dfaEdgep->top())) {
		if (dfaEdgep->top()->user() != m_step) return false;
		num2s++;
	    }
	}
	// If we saw all of the nodes, then they have the same number of hits
	// (Else something in dfa1p that wasn't in dfa2p)
	if (num1s != num2s) return false;
	// Match
	return true;
    }

uint32_t V3GraphVertex::outHash() const {
    uint32_t hash=0;
    for (V3GraphEdge* edgep = this->outBeginp(); edgep; edgep=edgep->outNextp()) {
	hash += cvtToHash(edgep->top());
    }
    return hash;
}

    void optimize_orphans() {
	// Remove states that don't come from start
	// Presumably the previous optimization orphaned them.

	// Vertex::m_user begin: 1 indicates on the work list, 2 processed
	// (Otherwise we might have nodes on the list twice, and reference after deleting them.)
	m_graphp->userClearVertices();

	DfaVertex* startp = graphp()->findStart();
	stack<V3GraphVertex*> workps;  workps.push(startp);

	// Mark all nodes connected to start
	while (!workps.empty()) {
	    V3GraphVertex* vertexp = workps.top(); workps.pop();
	    vertexp->user(2);  // Processed
	    // Add nodes from here to the work list
	    for (V3GraphEdge* edgep = vertexp->outBeginp(); edgep; edgep=edgep->outNextp()) {
		V3GraphVertex* tovertexp = edgep->top();
		if (!tovertexp->user()) {
		    workps.push(tovertexp);
		    tovertexp->user(1);
		}
	    }
	}

	// Delete all nodes not connected
	for (V3GraphVertex* nextp,*vertexp = m_graphp->verticesBeginp(); vertexp; vertexp=nextp) {
	    nextp = vertexp->verticesNextp();
	    if (!vertexp->user()) {
		vertexp->unlinkDelete(m_graphp); vertexp=NULL;
	    }
	}
    }

    // Returns only the result from the LAST vertex iterated over
    AstNUser* iterateInEdges(GateGraphBaseVisitor& v, AstNUser* vup=NULL) {
	AstNUser* retp = NULL;
	for (V3GraphEdge* edgep = inBeginp(); edgep; edgep = edgep->inNextp()) {
	    retp = dynamic_cast<GateEitherVertex*>(edgep->fromp())->accept(v, vup);
	}
	return retp;
    }

    bool isDead(DfaVertex* vertexp) {
	// A state is dead if not accepting, and goes nowhere
	if (vertexp->accepting() || vertexp->start()) return false;
	for (V3GraphEdge* edgep = vertexp->outBeginp(); edgep; edgep=edgep->outNextp()) {
	    if (edgep->top() != vertexp) return false;
	}
	return true;
    }

    // Populate *outp with a minimal perfect matching of *this.
    // *outp must be initially empty.
    void perfectMatching(const std::vector<T_Key>& oddKeys,
                         TspGraphTmpl* outp) {
        UASSERT(outp->empty(), "Output graph must start empty");

        std::list<Vertex*> odds = keysToVertexList(oddKeys);
        vl_unordered_set<Vertex*> unmatchedOdds;
        typedef typename std::list<Vertex*>::iterator VertexListIt;
        for (VertexListIt it = odds.begin(); it != odds.end(); ++it) {
            outp->addVertex((*it)->key());
            unmatchedOdds.insert(*it);
        }

        UASSERT(odds.size() % 2 == 0, "number of odd-order nodes should be even");

        // TODO: The true Chrisofides algorithm calls for minimum-weight
        // perfect matching. Instead, we have a simple greedy algorithm
        // which might get close to the minimum, maybe, with luck?
        //
        // TODO: Revisit this. It's possible to compute the true minimum in
        // N*N*log(N) time using variants of the Blossom algorithm.
        // Implementing Blossom looks hard, maybe we can use an existing
        // open source implementation -- for example the "LEMON" library
        // which has a TSP solver.

        // -----

        // Reuse the comparator from Prim's routine. The logic is the same
        // here.  Note that the two V3GraphEdge's representing a single
        // bidir edge will collide in the pendingEdges set here, but this
        // is OK, we'll ignore the direction on the edge anyway.
        EdgeCmp cmp;
        typedef std::set<V3GraphEdge*, EdgeCmp&> PendingEdgeSet;
        PendingEdgeSet pendingEdges(cmp);

        for (VertexListIt it = odds.begin(); it != odds.end(); ++it) {
            for (V3GraphEdge* edgep = (*it)->outBeginp();
                 edgep; edgep = edgep->outNextp()) {
                pendingEdges.insert(edgep);
            }
        }

        // Iterate over all edges, in order from low to high cost.
        // For any edge whose ends are both odd-order vertices which
        // haven't been matched yet, match them.
        for (typename PendingEdgeSet::iterator it = pendingEdges.begin();
             it != pendingEdges.end(); ++it) {
            Vertex* fromp = castVertexp((*it)->fromp());
            Vertex* top = castVertexp((*it)->top());
            if ((unmatchedOdds.find(fromp) != unmatchedOdds.end())
                && (unmatchedOdds.find(top) != unmatchedOdds.end())) {
                outp->addEdge(fromp->key(), top->key(), (*it)->weight());
                unmatchedOdds.erase(fromp);
                unmatchedOdds.erase(top);
            }
        }
        UASSERT(unmatchedOdds.empty(), "Algorithm should have processed all vertices");
    }

    void nafgMarkRecurse(V3GraphVertex* vertexp, uint32_t generation) {
	// Backwards mark user() on the path we recurse
	//UINFO(9," nafgMark: v "<<(void*)(vertexp)<<" "<<vertexp->name()<<endl);
	for (V3GraphEdge* edgep = vertexp->inBeginp(); edgep; edgep = edgep->inNextp()) {
	    //UINFO(9," nafgMark: "<<(void*)(edgep)<<" "<<edgep->name()<<endl);
	    edgep->user(generation);
	    nafgMarkRecurse(edgep->fromp(), generation);
	}
    }

void V3Graph::userClearEdges() {
    // Clear user() in all of tree
    for (V3GraphVertex* vertexp = verticesBeginp(); vertexp; vertexp=vertexp->verticesNextp()) {
	for (V3GraphEdge* edgep = vertexp->outBeginp(); edgep; edgep=edgep->outNextp()) {
	    edgep->user(0);
	    edgep->userp(NULL);	 // Its a union, but might be different size than user()
	}
    }
}

void GateVisitor::consumedMarkRecurse(GateEitherVertex* vertexp) {
    if (vertexp->user()) return;	// Already marked
    vertexp->user(true);
    if (!vertexp->consumed()) vertexp->setConsumed("propagated");
    // Walk sources and mark them too
    for (V3GraphEdge* edgep = vertexp->inBeginp(); edgep; edgep = edgep->inNextp()) {
	GateEitherVertex* eFromVertexp = (GateEitherVertex*)edgep->fromp();
	consumedMarkRecurse(eFromVertexp);
    }
}

 void dumpGraph(std::ostream& os, const string& nameComment) const {
     // UINFO(0) as controlled by caller
     os<<"At "<<nameComment<<", dumping graph. Keys:\n";
     for (V3GraphVertex* vxp = verticesBeginp(); vxp; vxp = vxp->verticesNextp()) {
         Vertex* tspvp = castVertexp(vxp);
         os<<" "<<tspvp->key()<<endl;
         for (V3GraphEdge* edgep = tspvp->outBeginp(); edgep; edgep = edgep->outNextp()) {
             Vertex* neighborp = castVertexp(edgep->top());
             os<<"   has edge "<<edgep->user()<<" to "<<neighborp->key()<<endl;
         }
     }
 }

void V3GraphVertex::rerouteEdges(V3Graph* graphp) {
    // Make new edges for each from/to pair
    for (V3GraphEdge* iedgep = inBeginp(); iedgep; iedgep=iedgep->inNextp()) {
	for (V3GraphEdge* oedgep = outBeginp(); oedgep; oedgep=oedgep->outNextp()) {
	    new V3GraphEdge (graphp, iedgep->fromp(), oedgep->top(),
			     min(iedgep->weight(),oedgep->weight()),
			     iedgep->cutable() && oedgep->cutable());
	}
    }
    // Remove old edges
    unlinkEdges(graphp);
}

 std::vector<T_Key> getOddDegreeKeys() const {
     std::vector<T_Key> result;
     for (V3GraphVertex* vxp = verticesBeginp(); vxp; vxp = vxp->verticesNextp()) {
         Vertex* tspvp = castVertexp(vxp);
         vluint32_t degree = 0;
         for (V3GraphEdge* edgep = vxp->outBeginp(); edgep; edgep = edgep->outNextp()) {
             degree++;
         }
         if (degree & 1) {
             result.push_back(tspvp->key());
         }
     }
     return result;
 }

void V3Graph::dump(ostream& os) {
    // This generates a file used by graphviz, http://www.graphviz.org
    os<<" Graph:\n";
    // Print vertices
    for (V3GraphVertex* vertexp = verticesBeginp(); vertexp; vertexp=vertexp->verticesNextp()) {
	os<<"\tNode: "<<vertexp->name();
	if (vertexp->color()) os<<"  color="<<vertexp->color();
	os<<endl;
	// Print edges
	for (V3GraphEdge* edgep = vertexp->inBeginp(); edgep; edgep=edgep->inNextp()) {
	    dumpEdge (os, vertexp, edgep);
	}
	for (V3GraphEdge* edgep = vertexp->outBeginp(); edgep; edgep=edgep->outNextp()) {
	    dumpEdge (os, vertexp, edgep);
	}
    }
}

    AstNode* nafgCreateRecurse(V3GraphVertex* vertexp, uint32_t generation) {
	// Forewards follow user() marked previously and build tree
	AstNode* nodep = NULL;
	// OR across all edges found at this level
	//UINFO(9," nafgEnter: v "<<(void*)(vertexp)<<" "<<vertexp->name()<<endl);
	for (V3GraphEdge* edgep = vertexp->outBeginp(); edgep; edgep = edgep->outNextp()) {
	    if (edgep->user() == generation) {
		GaterEdge* cedgep = static_cast<GaterEdge*>(edgep);
		AstNode* eqnp = NULL;
		//UINFO(9," nafgFollow: "<<(void*)(edgep)<<" "<<edgep->name()<<endl);
		if (dynamic_cast<GaterHeadVertex*>(edgep->fromp())) {
		    // Just OR in all lower terms
		    eqnp = nafgCreateRecurse(edgep->top(), generation);
		} else if (GaterIfVertex* cVxp = dynamic_cast<GaterIfVertex*>(edgep->fromp())) {
		    // Edges from IFs represent a real IF branch in the equation tree
		    //UINFO(9,"  ifver "<<(void*)(edgep)<<" cc"<<edgep->dotColor()<<endl);
		    eqnp = cVxp->nodep()->condp()->cloneTree(true);
		    if (eqnp && cedgep->ifelseFalse()) {
			eqnp = new AstNot(eqnp->fileline(),eqnp);
		    }
		    // We need to AND this term onto whatever was found below it
		    AstNode* belowp = nafgCreateRecurse(edgep->top(), generation);
		    if (belowp) eqnp = new AstAnd(eqnp->fileline(),eqnp,belowp);
		}
		// Top level we could choose to make multiple gaters, or ORs under the gater
		// Right now we'll put OR lower down and let other optimizations deal
		if (nodep) nodep = new AstOr(eqnp->fileline(),nodep,eqnp);
		else nodep = eqnp;
		//if (debug()>=9) nodep->dumpTree(cout,"      followExpr: ");
	    }
	}
	//UINFO(9," nafgExit:  "<<(void*)(vertexp)<<" "<<vertexp->name()<<endl);
	return nodep;
    }

 void pruneDepsOnInputs() {
     for (V3GraphVertex* vertexp = m_graph.verticesBeginp();
          vertexp; vertexp=vertexp->verticesNextp()) {
         if (!vertexp->outBeginp()
             && dynamic_cast<SplitVarStdVertex*>(vertexp)) {
             if (debug() >= 9) {
                 SplitVarStdVertex* stdp = (SplitVarStdVertex*)(vertexp);
                 UINFO(0, "Will prune deps on var "<<stdp->nodep()<<endl);
                 stdp->nodep()->dumpTree(cout, "- ");
             }
             for (V3GraphEdge* edgep = vertexp->inBeginp();
                  edgep; edgep=edgep->inNextp()) {
                 SplitEdge* oedgep = dynamic_cast<SplitEdge*>(edgep);
                 oedgep->setIgnoreThisStep();
             }
         }
     }
 }

    uint32_t hashDfaOrigins(DfaVertex* dfaStatep) {
	// Find the NFA states this dfa came from,
	// Record a checksum, so we can search for it later by the list of nfa nodes.
	// The order of the nodes is not deterministic; the hash thus must not depend on order of edges
	uint32_t hash = 0;
	// Foreach NFA state (this DFA state was formed from)
	if (debug()) nextStep();
	for (V3GraphEdge* dfaEdgep = dfaStatep->outBeginp(); dfaEdgep; dfaEdgep=dfaEdgep->outNextp()) {
	    if (nfaState(dfaEdgep->top())) {
		DfaVertex* nfaStatep = static_cast<DfaVertex*>(dfaEdgep->top());
		hash ^= hashVertex(nfaStatep);
		if (debug()) {
		    if (nfaStatep->user()==m_step) v3fatalSrc("DFA state points to duplicate NFA state.");
		    nfaStatep->user(m_step);
		}
	    }
	}
	return hash;
    }

    virtual AstNUser* visit(GateVarVertex *vvertexp, AstNUser*) {
	// Check that we haven't been here before
	if (vvertexp->varScp()->user2()) return NULL;
	vvertexp->varScp()->user2(true);

	AstNodeVarRef* dupVarRefp = (AstNodeVarRef*) vvertexp->iterateInEdges(*this, (AstNUser*) vvertexp);

	if (dupVarRefp && vvertexp->inSize1()) {
	    V3GraphEdge* edgep = vvertexp->inBeginp();
	    GateLogicVertex* lvertexp = (GateLogicVertex*)edgep->fromp();
	    if (!vvertexp->dedupable()) vvertexp->varScp()->v3fatalSrc("GateLogicVertex* visit should have returned NULL if consumer var vertex is not dedupable.");
	    GateOkVisitor okVisitor(lvertexp->nodep(), false, true);
	    if (okVisitor.isSimple()) {
		AstVarScope* dupVarScopep = dupVarRefp->varScopep();
		GateVarVertex* dupVvertexp = (GateVarVertex*) (dupVarScopep->user1p());
		UINFO(4,"replacing " << vvertexp << " with " << dupVvertexp << endl);
		++m_numDeduped;
		// Replace all of this varvertex's consumers with dupVarRefp
		for (V3GraphEdge* outedgep = vvertexp->outBeginp();outedgep;) {
		    GateLogicVertex* consumeVertexp = dynamic_cast<GateLogicVertex*>(outedgep->top());
		    AstNode* consumerp = consumeVertexp->nodep();
		    GateElimVisitor elimVisitor(consumerp,vvertexp->varScp(),dupVarRefp);
		    outedgep = outedgep->relinkFromp(dupVvertexp);
		}

		// Propogate attributes
		dupVvertexp->propagateAttrClocksFrom(vvertexp);

		// Remove inputs links
		while (V3GraphEdge* inedgep = vvertexp->inBeginp()) {
		    inedgep->unlinkDelete(); VL_DANGLING(inedgep);
		}
		// replaceAssigns() does the deleteTree on lvertexNodep in a later step
		AstNode* lvertexNodep = lvertexp->nodep();
		lvertexNodep->unlinkFrBack();
		vvertexp->varScp()->valuep(lvertexNodep);
		lvertexNodep = NULL;
		vvertexp->user(true);
		lvertexp->user(true);
	    }
	}
	return NULL;
    }

void V3Graph::clear() {
    // Empty it of all points, as if making a new object
    // Delete the old edges
    for (V3GraphVertex* vertexp = verticesBeginp(); vertexp; vertexp=vertexp->verticesNextp()) {
	for (V3GraphEdge* edgep = vertexp->outBeginp(); edgep; /*BELOW*/) {
	    V3GraphEdge* nextp = edgep->outNextp();
	    delete edgep;
	    edgep = nextp;
	}
	vertexp->outUnlink();
    }
    // Delete the old vertices
    for (V3GraphVertex* vertexp = verticesBeginp(); vertexp; /*BELOW*/) {
	V3GraphVertex* nextp = vertexp->verticesNextp();
	delete vertexp;
	vertexp = nextp;
    }
    verticesUnlink();
}

int GaterVertex::sortCmp(const V3GraphVertex* rhsp) const {
    const GaterVertex* crhsp = static_cast<const GaterVertex*>(rhsp);
    // We really only care about ordering Var's together, but...
    // First put same type together
    if (typeNum() < crhsp->typeNum()) return -1;
    if (typeNum() > crhsp->typeNum()) return 1;
    // If variable, group by same input fanin
    // (know they're the same type based on above compare)
    if (dynamic_cast<const GaterVarVertex*>(this)) {
	// We've already sorted by edges, so just see if same tree
	// If this gets too slow, we could compute a hash up front
	V3GraphEdge* lEdgep = this->inBeginp();
	V3GraphEdge* rEdgep = rhsp->inBeginp();
	while (lEdgep && rEdgep) {
	    const GaterEdge* clEdgep = static_cast<const GaterEdge*>(lEdgep);
	    const GaterEdge* crEdgep = static_cast<const GaterEdge*>(rEdgep);
	    if (lEdgep->fromp()->rank() < rEdgep->fromp()->rank()) return -1;
	    if (lEdgep->fromp()->rank() > rEdgep->fromp()->rank()) return 1;
	    if (clEdgep->ifelse() < crEdgep->ifelse()) return -1;
	    if (clEdgep->ifelse() > crEdgep->ifelse()) return 1;
	    lEdgep = lEdgep->inNextp();
	    rEdgep = rEdgep->inNextp();
	}
	if (!lEdgep && !rEdgep) return 0;
	return lEdgep ? -1 : 1;
    }
    // Finally by rank of this vertex
    if (rank() < rhsp->rank()) return -1;
    if (rank() > rhsp->rank()) return 1;
    return 0;
}

    void optimize_no_outbound() {
	// Non-accepting states with no outbound transitions may be
	// deleted.  Then, any arcs feeding those states, and perhaps those
	// states...

	// Vertex::m_user begin: 1 indicates on the work list
	// (Otherwise we might have nodes on the list twice, and reference after deleting them.)
	m_graphp->userClearVertices();

	// Find all dead vertexes
	stack<DfaVertex*> workps;
	for (V3GraphVertex* vertexp = m_graphp->verticesBeginp(); vertexp; vertexp=vertexp->verticesNextp()) {
	    if (DfaVertex* vvertexp = dynamic_cast<DfaVertex*>(vertexp)) {
		workps.push(vvertexp);
		vertexp->user(1);
	    } else {
		// If ever remove this, need dyn cast below
		v3fatalSrc("Non DfaVertex in dfa graph");
	    }
	}

	// While deadness... Delete and find new dead nodes.
	while (!workps.empty()) {
	    DfaVertex* vertexp = workps.top(); workps.pop();
	    vertexp->user(0);
	    if (isDead(vertexp)) {
		// Add nodes that go here to the work list
		for (V3GraphEdge* edgep = vertexp->inBeginp(); edgep; edgep=edgep->inNextp()) {
		    DfaVertex* fromvertexp = static_cast<DfaVertex*>(edgep->fromp());
		    if (fromvertexp != vertexp
			&& !fromvertexp->user()) {
			workps.push(static_cast<DfaVertex*>(fromvertexp));
			fromvertexp->user(1);
		    }
		}
		// Transitions to this state removed by the unlink function
		vertexp->unlinkDelete(m_graphp); vertexp=NULL;
	    }
	}
    }