From: bdemsky Date: Sat, 21 Oct 2017 22:55:40 +0000 (-0700) Subject: edits X-Git-Url: http://plrg.eecs.uci.edu/git/?p=satune.git;a=commitdiff_plain;h=e760ac82f9ce120ab2f900caeda89913a9f1fa4e edits --- diff --git a/src/ASTAnalyses/Order/orderanalysis.cc b/src/ASTAnalyses/Order/orderanalysis.cc index 13e26c0..abec0c0 100644 --- a/src/ASTAnalyses/Order/orderanalysis.cc +++ b/src/ASTAnalyses/Order/orderanalysis.cc @@ -11,169 +11,6 @@ #include "mutableset.h" #include "tunable.h" -void DFS(OrderGraph *graph, Vector *finishNodes) { - SetIteratorOrderNode *iterator = graph->getNodes(); - while (iterator->hasNext()) { - OrderNode *node = iterator->next(); - if (node->status == NOTVISITED) { - node->status = VISITED; - DFSNodeVisit(node, finishNodes, false, false, 0); - node->status = FINISHED; - finishNodes->push(node); - } - } - delete iterator; -} - -void DFSReverse(OrderGraph *graph, Vector *finishNodes) { - uint size = finishNodes->getSize(); - uint sccNum = 1; - for (int i = size - 1; i >= 0; i--) { - OrderNode *node = finishNodes->get(i); - if (node->status == NOTVISITED) { - node->status = VISITED; - DFSNodeVisit(node, NULL, true, false, sccNum); - node->sccNum = sccNum; - node->status = FINISHED; - sccNum++; - } - } -} - -void DFSNodeVisit(OrderNode *node, Vector *finishNodes, bool isReverse, bool mustvisit, uint sccNum) { - SetIteratorOrderEdge *iterator = isReverse ? node->inEdges.iterator() : node->outEdges.iterator(); - while (iterator->hasNext()) { - OrderEdge *edge = iterator->next(); - if (mustvisit) { - if (!edge->mustPos) - continue; - } else - if (!edge->polPos && !edge->pseudoPos) //Ignore edges that do not have positive polarity - continue; - - OrderNode *child = isReverse ? edge->source : edge->sink; - if (child->status == NOTVISITED) { - child->status = VISITED; - DFSNodeVisit(child, finishNodes, isReverse, mustvisit, sccNum); - child->status = FINISHED; - if (finishNodes != NULL) { - finishNodes->push(child); - } - if (isReverse) - child->sccNum = sccNum; - } - } - delete iterator; -} - -void resetNodeInfoStatusSCC(OrderGraph *graph) { - SetIteratorOrderNode *iterator = graph->getNodes(); - while (iterator->hasNext()) { - iterator->next()->status = NOTVISITED; - } - delete iterator; -} - -void computeStronglyConnectedComponentGraph(OrderGraph *graph) { - Vector finishNodes; - DFS(graph, &finishNodes); - resetNodeInfoStatusSCC(graph); - DFSReverse(graph, &finishNodes); - resetNodeInfoStatusSCC(graph); -} - - - -/** This function computes a source set for every nodes, the set of - nodes that can reach that node via pospolarity edges. It then - looks for negative polarity edges from nodes in the the source set - to determine whether we need to generate pseudoPos edges. */ - -void completePartialOrderGraph(OrderGraph *graph) { - Vector finishNodes; - DFS(graph, &finishNodes); - resetNodeInfoStatusSCC(graph); - HashtableNodeToNodeSet *table = new HashtableNodeToNodeSet(128, 0.25); - - Vector sccNodes; - - uint size = finishNodes.getSize(); - uint sccNum = 1; - for (int i = size - 1; i >= 0; i--) { - OrderNode *node = finishNodes.get(i); - HashsetOrderNode *sources = new HashsetOrderNode(4, 0.25); - table->put(node, sources); - - if (node->status == NOTVISITED) { - //Need to do reverse traversal here... - node->status = VISITED; - DFSNodeVisit(node, &sccNodes, true, false, sccNum); - node->status = FINISHED; - node->sccNum = sccNum; - sccNum++; - sccNodes.push(node); - - //Compute in set for entire SCC - uint rSize = sccNodes.getSize(); - for (uint j = 0; j < rSize; j++) { - OrderNode *rnode = sccNodes.get(j); - //Compute source sets - SetIteratorOrderEdge *iterator = rnode->inEdges.iterator(); - while (iterator->hasNext()) { - OrderEdge *edge = iterator->next(); - OrderNode *parent = edge->source; - if (edge->polPos) { - sources->add(parent); - HashsetOrderNode *parent_srcs = (HashsetOrderNode *)table->get(parent); - sources->addAll(parent_srcs); - } - } - delete iterator; - } - for (uint j = 0; j < rSize; j++) { - //Copy in set of entire SCC - OrderNode *rnode = sccNodes.get(j); - HashsetOrderNode *set = (j == 0) ? sources : sources->copy(); - table->put(rnode, set); - - //Use source sets to compute pseudoPos edges - SetIteratorOrderEdge *iterator = node->inEdges.iterator(); - while (iterator->hasNext()) { - OrderEdge *edge = iterator->next(); - OrderNode *parent = edge->source; - ASSERT(parent != rnode); - if (edge->polNeg && parent->sccNum != rnode->sccNum && - sources->contains(parent)) { - OrderEdge *newedge = graph->getOrderEdgeFromOrderGraph(rnode, parent); - newedge->pseudoPos = true; - } - } - delete iterator; - } - - sccNodes.clear(); - } - } - - table->resetAndDeleteVals(); - delete table; - resetNodeInfoStatusSCC(graph); -} - -void DFSMust(OrderGraph *graph, Vector *finishNodes) { - SetIteratorOrderNode *iterator = graph->getNodes(); - while (iterator->hasNext()) { - OrderNode *node = iterator->next(); - if (node->status == NOTVISITED) { - node->status = VISITED; - DFSNodeVisit(node, finishNodes, false, true, 0); - node->status = FINISHED; - finishNodes->push(node); - } - } - delete iterator; -} - void DFSClearContradictions(CSolver *solver, OrderGraph *graph, Vector *finishNodes, bool computeTransitiveClosure) { uint size = finishNodes->getSize(); HashtableNodeToNodeSet *table = new HashtableNodeToNodeSet(128, 0.25); @@ -257,8 +94,8 @@ void DFSClearContradictions(CSolver *solver, OrderGraph *graph, Vector finishNodes; //Topologically sort the mustPos edge graph - DFSMust(graph, &finishNodes); - resetNodeInfoStatusSCC(graph); + graph->DFSMust(&finishNodes); + graph->resetNodeInfoStatusSCC(); //Find any backwards edges that complete cycles and force them to be mustNeg DFSClearContradictions(solver, graph, &finishNodes, computeTransitiveClosure); diff --git a/src/ASTAnalyses/Order/orderanalysis.h b/src/ASTAnalyses/Order/orderanalysis.h index 89665a1..24ec85c 100644 --- a/src/ASTAnalyses/Order/orderanalysis.h +++ b/src/ASTAnalyses/Order/orderanalysis.h @@ -4,14 +4,6 @@ #include "structs.h" #include "mymemory.h" -void computeStronglyConnectedComponentGraph(OrderGraph *graph); -void initializeNodeInfoSCC(OrderGraph *graph); -void DFSNodeVisit(OrderNode *node, Vector *finishNodes, bool isReverse, bool mustvisit, uint sccNum); -void DFS(OrderGraph *graph, Vector *finishNodes); -void DFSReverse(OrderGraph *graph, Vector *finishNodes); -void completePartialOrderGraph(OrderGraph *graph); -void resetNodeInfoStatusSCC(OrderGraph *graph); -void DFSMust(OrderGraph *graph, Vector *finishNodes); void DFSClearContradictions(CSolver *solver, OrderGraph *graph, Vector *finishNodes, bool computeTransitiveClosure); void reachMustAnalysis(CSolver *solver, OrderGraph *graph, bool computeTransitiveClosure); void localMustAnalysisTotal(CSolver *solver, OrderGraph *graph); diff --git a/src/ASTAnalyses/Order/ordergraph.cc b/src/ASTAnalyses/Order/ordergraph.cc index 07d7f7f..a2e52f8 100644 --- a/src/ASTAnalyses/Order/ordergraph.cc +++ b/src/ASTAnalyses/Order/ordergraph.cc @@ -6,8 +6,6 @@ #include "order.h" OrderGraph::OrderGraph(Order *_order) : - nodes(new HashsetOrderNode()), - edges(new HashsetOrderEdge()), order(_order) { } @@ -110,43 +108,44 @@ void OrderGraph::addMustOrderEdge(OrderNode *node1, OrderNode *node2, BooleanOrd OrderNode *OrderGraph::getOrderNodeFromOrderGraph(uint64_t id) { OrderNode *node = new OrderNode(id); - OrderNode *tmp = nodes->get(node); + OrderNode *tmp = nodes.get(node); if ( tmp != NULL) { delete node; node = tmp; } else { - nodes->add(node); + nodes.add(node); + allNodes.push(node); } return node; } OrderNode *OrderGraph::lookupOrderNodeFromOrderGraph(uint64_t id) { OrderNode node(id); - OrderNode *tmp = nodes->get(&node); + OrderNode *tmp = nodes.get(&node); return tmp; } OrderEdge *OrderGraph::getOrderEdgeFromOrderGraph(OrderNode *begin, OrderNode *end) { OrderEdge *edge = new OrderEdge(begin, end); - OrderEdge *tmp = edges->get(edge); + OrderEdge *tmp = edges.get(edge); if ( tmp != NULL ) { delete edge; edge = tmp; } else { - edges->add(edge); + edges.add(edge); } return edge; } OrderEdge *OrderGraph::lookupOrderEdgeFromOrderGraph(OrderNode *begin, OrderNode *end) { OrderEdge edge(begin, end); - OrderEdge *tmp = edges->get(&edge); + OrderEdge *tmp = edges.get(&edge); return tmp; } OrderEdge *OrderGraph::getInverseOrderEdge(OrderEdge *edge) { OrderEdge inverseedge(edge->sink, edge->source); - OrderEdge *tmp = edges->get(&inverseedge); + OrderEdge *tmp = edges.get(&inverseedge); return tmp; } @@ -163,21 +162,16 @@ void OrderGraph::addMustOrderConstraintToOrderGraph(BooleanOrder *bOrder) { } OrderGraph::~OrderGraph() { - SetIteratorOrderNode *iterator = nodes->iterator(); - while (iterator->hasNext()) { - OrderNode *node = iterator->next(); - delete node; - } - delete iterator; + uint size=allNodes.getSize(); + for(uint i=0;iiterator(); + SetIteratorOrderEdge *eiterator = edges.iterator(); while (eiterator->hasNext()) { OrderEdge *edge = eiterator->next(); delete edge; } delete eiterator; - delete nodes; - delete edges; } bool OrderGraph::isTherePath(OrderNode *source, OrderNode *destination) { @@ -227,3 +221,164 @@ bool OrderGraph::isTherePathVisit(HashsetOrderNode &visited, OrderNode *current, delete iterator; return found; } + +void OrderGraph::DFS(Vector *finishNodes) { + SetIteratorOrderNode *iterator = getNodes(); + while (iterator->hasNext()) { + OrderNode *node = iterator->next(); + if (node->status == NOTVISITED) { + node->status = VISITED; + DFSNodeVisit(node, finishNodes, false, false, 0); + node->status = FINISHED; + finishNodes->push(node); + } + } + delete iterator; +} + +void OrderGraph::DFSMust(Vector *finishNodes) { + SetIteratorOrderNode *iterator = getNodes(); + while (iterator->hasNext()) { + OrderNode *node = iterator->next(); + if (node->status == NOTVISITED) { + node->status = VISITED; + DFSNodeVisit(node, finishNodes, false, true, 0); + node->status = FINISHED; + finishNodes->push(node); + } + } + delete iterator; +} + +void OrderGraph::DFSReverse(Vector *finishNodes) { + uint size = finishNodes->getSize(); + uint sccNum = 1; + for (int i = size - 1; i >= 0; i--) { + OrderNode *node = finishNodes->get(i); + if (node->status == NOTVISITED) { + node->status = VISITED; + DFSNodeVisit(node, NULL, true, false, sccNum); + node->sccNum = sccNum; + node->status = FINISHED; + sccNum++; + } + } +} + +void OrderGraph::DFSNodeVisit(OrderNode *node, Vector *finishNodes, bool isReverse, bool mustvisit, uint sccNum) { + SetIteratorOrderEdge *iterator = isReverse ? node->inEdges.iterator() : node->outEdges.iterator(); + while (iterator->hasNext()) { + OrderEdge *edge = iterator->next(); + if (mustvisit) { + if (!edge->mustPos) + continue; + } else + if (!edge->polPos && !edge->pseudoPos) //Ignore edges that do not have positive polarity + continue; + + OrderNode *child = isReverse ? edge->source : edge->sink; + if (child->status == NOTVISITED) { + child->status = VISITED; + DFSNodeVisit(child, finishNodes, isReverse, mustvisit, sccNum); + child->status = FINISHED; + if (finishNodes != NULL) { + finishNodes->push(child); + } + if (isReverse) + child->sccNum = sccNum; + } + } + delete iterator; +} + +void OrderGraph::resetNodeInfoStatusSCC() { + SetIteratorOrderNode *iterator = getNodes(); + while (iterator->hasNext()) { + iterator->next()->status = NOTVISITED; + } + delete iterator; +} + +void OrderGraph::computeStronglyConnectedComponentGraph() { + Vector finishNodes; + DFS(&finishNodes); + resetNodeInfoStatusSCC(); + DFSReverse(&finishNodes); + resetNodeInfoStatusSCC(); +} + +/** This function computes a source set for every nodes, the set of + nodes that can reach that node via pospolarity edges. It then + looks for negative polarity edges from nodes in the the source set + to determine whether we need to generate pseudoPos edges. */ + +void OrderGraph::completePartialOrderGraph() { + Vector finishNodes; + DFS(&finishNodes); + resetNodeInfoStatusSCC(); + HashtableNodeToNodeSet *table = new HashtableNodeToNodeSet(128, 0.25); + + Vector sccNodes; + + uint size = finishNodes.getSize(); + uint sccNum = 1; + for (int i = size - 1; i >= 0; i--) { + OrderNode *node = finishNodes.get(i); + HashsetOrderNode *sources = new HashsetOrderNode(4, 0.25); + table->put(node, sources); + + if (node->status == NOTVISITED) { + //Need to do reverse traversal here... + node->status = VISITED; + DFSNodeVisit(node, &sccNodes, true, false, sccNum); + node->status = FINISHED; + node->sccNum = sccNum; + sccNum++; + sccNodes.push(node); + + //Compute in set for entire SCC + uint rSize = sccNodes.getSize(); + for (uint j = 0; j < rSize; j++) { + OrderNode *rnode = sccNodes.get(j); + //Compute source sets + SetIteratorOrderEdge *iterator = rnode->inEdges.iterator(); + while (iterator->hasNext()) { + OrderEdge *edge = iterator->next(); + OrderNode *parent = edge->source; + if (edge->polPos) { + sources->add(parent); + HashsetOrderNode *parent_srcs = (HashsetOrderNode *)table->get(parent); + sources->addAll(parent_srcs); + } + } + delete iterator; + } + for (uint j = 0; j < rSize; j++) { + //Copy in set of entire SCC + OrderNode *rnode = sccNodes.get(j); + HashsetOrderNode *set = (j == 0) ? sources : sources->copy(); + table->put(rnode, set); + + //Use source sets to compute pseudoPos edges + SetIteratorOrderEdge *iterator = node->inEdges.iterator(); + while (iterator->hasNext()) { + OrderEdge *edge = iterator->next(); + OrderNode *parent = edge->source; + ASSERT(parent != rnode); + if (edge->polNeg && parent->sccNum != rnode->sccNum && + sources->contains(parent)) { + OrderEdge *newedge = getOrderEdgeFromOrderGraph(rnode, parent); + newedge->pseudoPos = true; + } + } + delete iterator; + } + + sccNodes.clear(); + } + } + + table->resetAndDeleteVals(); + delete table; + resetNodeInfoStatusSCC(); +} diff --git a/src/ASTAnalyses/Order/ordergraph.h b/src/ASTAnalyses/Order/ordergraph.h index 2bb8812..7460b20 100644 --- a/src/ASTAnalyses/Order/ordergraph.h +++ b/src/ASTAnalyses/Order/ordergraph.h @@ -27,14 +27,23 @@ public: Order *getOrder() {return order;} bool isTherePath(OrderNode *source, OrderNode *destination); bool isTherePathVisit(HashsetOrderNode &visited, OrderNode *current, OrderNode *destination); - SetIteratorOrderNode *getNodes() {return nodes->iterator();} - SetIteratorOrderEdge *getEdges() {return edges->iterator();} - + SetIteratorOrderNode *getNodes() {return nodes.iterator();} + SetIteratorOrderEdge *getEdges() {return edges.iterator();} + void DFS(Vector *finishNodes); + void DFSMust(Vector *finishNodes); + void computeStronglyConnectedComponentGraph(); + void resetNodeInfoStatusSCC(); + void completePartialOrderGraph(); + void removeNode(OrderNode *node) {nodes.remove(node);} + CMEMALLOC; private: - HashsetOrderNode *nodes; - HashsetOrderEdge *edges; + HashsetOrderNode nodes; + Vector allNodes; + HashsetOrderEdge edges; Order *order; + void DFSNodeVisit(OrderNode *node, Vector *finishNodes, bool isReverse, bool mustvisit, uint sccNum); + void DFSReverse(Vector *finishNodes); }; OrderGraph *buildOrderGraph(Order *order); diff --git a/src/ASTTransform/decomposeordertransform.cc b/src/ASTTransform/decomposeordertransform.cc index 51d6a51..d4a2d5f 100644 --- a/src/ASTTransform/decomposeordertransform.cc +++ b/src/ASTTransform/decomposeordertransform.cc @@ -36,12 +36,15 @@ void DecomposeOrderTransform::doTransform() { continue; } + DecomposeOrderResolver *dor=new DecomposeOrderResolver(order); + order->setOrderResolver(dor); + OrderGraph *graph = buildOrderGraph(order); if (order->type == SATC_PARTIAL) { //Required to do SCC analysis for partial order graphs. It //makes sure we don't incorrectly optimize graphs with negative //polarity edges - completePartialOrderGraph(graph); + graph->completePartialOrderGraph(); } bool mustReachGlobal = GETVARTUNABLE(solver->getTuner(), order->type, MUSTREACHGLOBAL, &onoff); @@ -60,7 +63,6 @@ void DecomposeOrderTransform::doTransform() { } } - bool mustReachPrune = GETVARTUNABLE(solver->getTuner(), order->type, MUSTREACHPRUNE, &onoff); HashsetOrderEdge *edgesRemoved = NULL; @@ -70,8 +72,8 @@ void DecomposeOrderTransform::doTransform() { } //This is needed for splitorder - computeStronglyConnectedComponentGraph(graph); - decomposeOrder(order, graph, edgesRemoved); + graph->computeStronglyConnectedComponentGraph(); + decomposeOrder(order, graph, edgesRemoved, dor); if (edgesRemoved != NULL) delete edgesRemoved; } @@ -80,8 +82,7 @@ void DecomposeOrderTransform::doTransform() { } -void DecomposeOrderTransform::decomposeOrder (Order *currOrder, OrderGraph *currGraph, HashsetOrderEdge *edgesRemoved) { - Vector ordervec; +void DecomposeOrderTransform::decomposeOrder (Order *currOrder, OrderGraph *currGraph, HashsetOrderEdge *edgesRemoved, DecomposeOrderResolver *dor) { Vector partialcandidatevec; uint size = currOrder->constraints.getSize(); for (uint i = 0; i < size; i++) { @@ -92,9 +93,11 @@ void DecomposeOrderTransform::decomposeOrder (Order *currOrder, OrderGraph *curr OrderEdge *invedge = currGraph->lookupOrderEdgeFromOrderGraph(to, from); if (edgesRemoved != NULL) { if (edgesRemoved->contains(edge)) { + dor->mustOrderEdge(from->getID(), to->getID()); solver->replaceBooleanWithTrue(orderconstraint); continue; } else if (edgesRemoved->contains(invedge)) { + dor->mustOrderEdge(to->getID(), from->getID()); solver->replaceBooleanWithFalse(orderconstraint); continue; } @@ -103,8 +106,11 @@ void DecomposeOrderTransform::decomposeOrder (Order *currOrder, OrderGraph *curr if (from->sccNum != to->sccNum) { if (edge != NULL) { if (edge->polPos) { + dor->mustOrderEdge(from->getID(), to->getID()); solver->replaceBooleanWithTrue(orderconstraint); } else if (edge->polNeg) { + if (currOrder->type == SATC_TOTAL) + dor->mustOrderEdge(to->getID(), from->getID()); solver->replaceBooleanWithFalse(orderconstraint); } else { //This case should only be possible if constraint isn't in AST @@ -114,6 +120,7 @@ void DecomposeOrderTransform::decomposeOrder (Order *currOrder, OrderGraph *curr } else { if (invedge != NULL) { if (invedge->polPos) { + dor->mustOrderEdge(to->getID(), from->getID()); solver->replaceBooleanWithFalse(orderconstraint); } else if (edge->polNeg) { //This case shouldn't happen... If we have a partial order, @@ -130,12 +137,11 @@ void DecomposeOrderTransform::decomposeOrder (Order *currOrder, OrderGraph *curr } else { //Build new order and change constraint's order Order *neworder = NULL; - if (ordervec.getSize() > from->sccNum) - neworder = ordervec.get(from->sccNum); + neworder = dor->getOrder(from->sccNum); if (neworder == NULL) { MutableSet *set = solver->createMutableSet(currOrder->set->getType()); neworder = solver->createOrder(currOrder->type, set); - ordervec.setExpand(from->sccNum, neworder); + dor->setOrder(from->sccNum, neworder); if (currOrder->type == SATC_PARTIAL) partialcandidatevec.setExpand(from->sccNum, neworder); else @@ -154,10 +160,10 @@ void DecomposeOrderTransform::decomposeOrder (Order *currOrder, OrderGraph *curr partialcandidatevec.setExpand(from->sccNum, NULL); } orderconstraint->order = neworder; + dor->setEdgeOrder(from->getID(), to->getID(), from->sccNum); neworder->addOrderConstraint(orderconstraint); } } - currOrder->setOrderResolver( new DecomposeOrderResolver(currGraph, ordervec) ); solver->getActiveOrders()->remove(currOrder); uint pcvsize = partialcandidatevec.getSize(); for (uint i = 0; i < pcvsize; i++) { @@ -209,6 +215,7 @@ void DecomposeOrderTransform::bypassMustBeTrueNode(OrderGraph *graph, OrderNode solver->setUnSAT(); delete iterout; delete iterin; + graph->removeNode(node); return; } //Add new order constraint @@ -227,6 +234,7 @@ void DecomposeOrderTransform::bypassMustBeTrueNode(OrderGraph *graph, OrderNode delete iterout; } delete iterin; + graph->removeNode(node); } void DecomposeOrderTransform::removeMustBeTrueNodes(OrderGraph *graph, HashsetOrderEdge *edgesRemoved) { diff --git a/src/ASTTransform/decomposeordertransform.h b/src/ASTTransform/decomposeordertransform.h index 8351ae0..3f8092f 100644 --- a/src/ASTTransform/decomposeordertransform.h +++ b/src/ASTTransform/decomposeordertransform.h @@ -21,7 +21,7 @@ public: private: bool isMustBeTrueNode(OrderNode *node); void bypassMustBeTrueNode(OrderGraph *graph, OrderNode *node, HashsetOrderEdge *edgesRemoved); - void decomposeOrder(Order *currOrder, OrderGraph *currGraph, HashsetOrderEdge *edgesRemoved); + void decomposeOrder(Order *currOrder, OrderGraph *currGraph, HashsetOrderEdge *edgesRemoved, DecomposeOrderResolver *dor); void removeMustBeTrueNodes(OrderGraph *graph, HashsetOrderEdge *edgesRemoved); }; diff --git a/src/Collections/structs.cc b/src/Collections/structs.cc index 96b85e7..09dc419 100644 --- a/src/Collections/structs.cc +++ b/src/Collections/structs.cc @@ -6,6 +6,7 @@ #include "ordergraph.h" #include "orderelement.h" #include "structs.h" +#include "decomposeorderresolver.h" unsigned int table_entry_hash_function(TableEntry *This) { unsigned int h = 0; @@ -56,3 +57,12 @@ unsigned int order_pair_hash_function(OrderPair *This) { bool order_pair_equals(OrderPair *key1, OrderPair *key2) { return key1->first == key2->first && key1->second == key2->second; } + +unsigned int doredge_hash_function(DOREdge *key) { + return (uint) (key->newfirst << 2) ^ key->newsecond; +} + +bool doredge_equals(DOREdge *key1, DOREdge *key2) { + return key1->newfirst == key2->newfirst && + key1->newsecond == key2->newsecond; +} diff --git a/src/Collections/structs.h b/src/Collections/structs.h index 6d06f54..2515f8f 100644 --- a/src/Collections/structs.h +++ b/src/Collections/structs.h @@ -19,11 +19,15 @@ bool order_element_equals(OrderElement *key1, OrderElement *key2); unsigned int order_pair_hash_function(OrderPair *This); bool order_pair_equals(OrderPair *key1, OrderPair *key2); +unsigned int doredge_hash_function(DOREdge *key); +bool doredge_equals(DOREdge *key1, DOREdge *key2); + typedef Hashset HashsetTableEntry; typedef Hashset HashsetOrderNode; typedef Hashset HashsetOrderEdge; typedef Hashset HashsetOrderElement; +typedef Hashset HashsetDOREdge; typedef Hashset HashsetBoolean; typedef Hashset HashsetElement; typedef SetIterator SetIteratorBoolean; @@ -43,5 +47,5 @@ typedef SetIterator SetIteratorOrderEdge; typedef SetIterator SetIteratorOrderNode; typedef SetIterator SetIteratorOrderElement; - +typedef SetIterator SetIteratorDOREdge; #endif diff --git a/src/Translator/decomposeorderresolver.cc b/src/Translator/decomposeorderresolver.cc index 1e5fdf0..f0d3e2a 100644 --- a/src/Translator/decomposeorderresolver.cc +++ b/src/Translator/decomposeorderresolver.cc @@ -11,38 +11,61 @@ #include "ordernode.h" #include "ordergraph.h" -DecomposeOrderResolver::DecomposeOrderResolver(OrderGraph *_graph, Vector &_orders) : - graph(_graph), - orders(_orders.getSize(), _orders.expose()) +DecomposeOrderResolver::DecomposeOrderResolver(Order * _order) : + graph(NULL), + order(_order) { } DecomposeOrderResolver::~DecomposeOrderResolver() { + if (graph != NULL) + delete graph; + uint size=edges.getSize(); + edges.resetAndDelete(); } -void processNode(HashsetOrderNode * set, OrderNode *node, bool outedges) { - if (node->removed) { - Vector toprocess; - HashsetOrderNode visited; - toprocess.push(node); - while(toprocess.getSize()!=0) { - OrderNode *newnode=toprocess.last();toprocess.pop(); - SetIteratorOrderEdge *iterator=outedges ? newnode->outEdges.iterator() : newnode->inEdges.iterator(); - while(iterator->hasNext()) { - OrderEdge *edge=iterator->next(); - OrderNode *tmpnode=outedges ? edge->sink : edge->source; - if (tmpnode->removed) { - if (visited.add(tmpnode)) { - toprocess.push(tmpnode); - } - } else { - set->add(tmpnode); - } - } - delete iterator; - } - } else - set->add(node); +void DecomposeOrderResolver::mustOrderEdge(uint64_t first, uint64_t second) { + DOREdge edge(first, second, 0, first, second); + if (!edges.contains(&edge)) { + DOREdge *newedge=new DOREdge(first, second, 0, first, second); + edges.add(newedge); + } +} + +void DecomposeOrderResolver::remapEdge(uint64_t first, uint64_t second, uint64_t newfirst, uint64_t newsecond) { + DOREdge edge(first, second, 0, first, second); + DOREdge *oldedge=edges.get(&edge); + if (oldedge != NULL) { + edges.remove(oldedge); + oldedge->newfirst=newfirst; + oldedge->newsecond=newsecond; + edges.add(oldedge); + } else { + DOREdge *newedge=new DOREdge(first, second, 0, newfirst, newsecond); + edges.add(newedge); + } +} + +void DecomposeOrderResolver::setEdgeOrder(uint64_t first, uint64_t second, uint sccNum) { + DOREdge edge(first, second, 0, first, second); + DOREdge *oldedge=edges.get(&edge); + if (oldedge != NULL) { + oldedge->orderindex=sccNum; + } else { + DOREdge *newedge=new DOREdge(first, second, sccNum, first, second); + edges.add(newedge); + } +} + +void DecomposeOrderResolver::setOrder(uint sccNum, Order *neworder) { + orders.setExpand(sccNum, neworder); +} + +Order * DecomposeOrderResolver::getOrder(uint sccNum) { + Order *neworder = NULL; + if (orders.getSize() > sccNum) + neworder = orders.get(sccNum); + return neworder; } bool DecomposeOrderResolver::resolveOrder(uint64_t first, uint64_t second) { @@ -52,8 +75,8 @@ bool DecomposeOrderResolver::resolveOrder(uint64_t first, uint64_t second) { ASSERT(to != NULL); if (from->removed || to->removed) { HashsetOrderNode fromset, toset; - processNode(&fromset, from, true); - processNode(&toset, to, false); + // processNode(&fromset, from, true); + // processNode(&toset, to, false); SetIteratorOrderNode *fromit=fromset.iterator(); while(fromit->hasNext()) { OrderNode * nodefrom=fromit->next(); diff --git a/src/Translator/decomposeorderresolver.h b/src/Translator/decomposeorderresolver.h index 1f3b266..5948e14 100644 --- a/src/Translator/decomposeorderresolver.h +++ b/src/Translator/decomposeorderresolver.h @@ -13,15 +13,41 @@ #include "structs.h" #include "orderresolver.h" +class DOREdge { + public: + DOREdge(uint64_t _origfirst, uint64_t _origsecond, uint _orderindex, uint64_t _newfirst, uint64_t _newsecond) : + origfirst(_origfirst), + origsecond(_origsecond), + orderindex(_orderindex), + newfirst(_newfirst), + newsecond(_newsecond) { + } + uint64_t origfirst; + uint64_t origsecond; + uint orderindex; + uint64_t newfirst; + uint64_t newsecond; + CMEMALLOC; +}; + class DecomposeOrderResolver : public OrderResolver { public: - DecomposeOrderResolver(OrderGraph *graph, Vector &orders); - bool resolveOrder(uint64_t first, uint64_t second); - bool resolvePartialOrder(OrderNode *first, OrderNode *second); + DecomposeOrderResolver(Order *_order); + virtual bool resolveOrder(uint64_t first, uint64_t second); virtual ~DecomposeOrderResolver(); -private: + void mustOrderEdge(uint64_t first, uint64_t second); + void remapEdge(uint64_t oldfirst, uint64_t oldsecond, uint64_t newfirst, uint64_t newsecond); + void setEdgeOrder(uint64_t first, uint64_t second, uint sccNum); + void setOrder(uint sccNum, Order *order); + Order * getOrder(uint sccNum); + CMEMALLOC; + + private: + bool resolvePartialOrder(OrderNode *first, OrderNode *second); OrderGraph *graph; + Order *order; Vector orders; + HashsetDOREdge edges; }; #endif/* DECOMPOSEORDERRESOLVER_H */ diff --git a/src/classlist.h b/src/classlist.h index 69c710e..bb102ad 100644 --- a/src/classlist.h +++ b/src/classlist.h @@ -53,6 +53,7 @@ class OrderEncoding; class OrderGraph; class OrderNode; class OrderEdge; +class DOREdge; class AutoTuner; class SearchTuner;