New Resolver Design for Decompose Order
authorbdemsky <bdemsky@uci.edu>
Sun, 22 Oct 2017 00:21:22 +0000 (17:21 -0700)
committerbdemsky <bdemsky@uci.edu>
Sun, 22 Oct 2017 00:21:22 +0000 (17:21 -0700)
src/ASTAnalyses/Order/orderanalysis.cc
src/ASTAnalyses/Order/ordergraph.cc
src/ASTAnalyses/Order/ordergraph.h
src/ASTTransform/decomposeordertransform.cc
src/Test/ordertest.cc
src/Translator/decomposeorderresolver.cc

index abec0c0..c8c7e36 100644 (file)
@@ -39,6 +39,8 @@ void DFSClearContradictions(CSolver *solver, OrderGraph *graph, Vector<OrderNode
                        SetIteratorOrderNode *srciterator = sources->iterator();
                        while (srciterator->hasNext()) {
                                OrderNode *srcnode = srciterator->next();
+                               if (srcnode->removed)
+                                       continue;
                                OrderEdge *newedge = graph->getOrderEdgeFromOrderGraph(srcnode, node);
                                newedge->mustPos = true;
                                newedge->polPos = true;
index d518b1b..85a0207 100644 (file)
@@ -12,7 +12,6 @@ OrderGraph::OrderGraph(Order *_order) :
 OrderGraph *buildOrderGraph(Order *order) {
        ASSERT(order->graph == NULL);
        OrderGraph *orderGraph = new OrderGraph(order);
-       order->graph = orderGraph;
        uint constrSize = order->constraints.getSize();
        for (uint j = 0; j < constrSize; j++) {
                orderGraph->addOrderConstraintToOrderGraph(order->constraints.get(j));
@@ -124,7 +123,6 @@ OrderNode *OrderGraph::getOrderNodeFromOrderGraph(uint64_t id) {
                node = tmp;
        } else {
                nodes.add(node);
-               allNodes.push(node);
        }
        return node;
 }
@@ -172,16 +170,8 @@ void OrderGraph::addMustOrderConstraintToOrderGraph(BooleanOrder *bOrder) {
 }
 
 OrderGraph::~OrderGraph() {
-       uint size=allNodes.getSize();
-       for(uint i=0;i<size;i++)
-               delete allNodes.get(i);
-
-       SetIteratorOrderEdge *eiterator = edges.iterator();
-       while (eiterator->hasNext()) {
-               OrderEdge *edge = eiterator->next();
-               delete edge;
-       }
-       delete eiterator;
+       nodes.resetAndDelete();
+       edges.resetAndDelete();
 }
 
 bool OrderGraph::isTherePath(OrderNode *source, OrderNode *destination) {
@@ -236,7 +226,7 @@ void OrderGraph::DFS(Vector<OrderNode *> *finishNodes) {
        SetIteratorOrderNode *iterator = getNodes();
        while (iterator->hasNext()) {
                OrderNode *node = iterator->next();
-               if (node->status == NOTVISITED) {
+               if (node->status == NOTVISITED && !node->removed) {
                        node->status = VISITED;
                        DFSNodeVisit(node, finishNodes, false, false, 0);
                        node->status = FINISHED;
@@ -250,7 +240,7 @@ void OrderGraph::DFSMust(Vector<OrderNode *> *finishNodes) {
        SetIteratorOrderNode *iterator = getNodes();
        while (iterator->hasNext()) {
                OrderNode *node = iterator->next();
-               if (node->status == NOTVISITED) {
+               if (node->status == NOTVISITED && !node->removed) {
                        node->status = VISITED;
                        DFSNodeVisit(node, finishNodes, false, true, 0);
                        node->status = FINISHED;
index fc82966..e7e958e 100644 (file)
@@ -35,12 +35,10 @@ public:
        void computeStronglyConnectedComponentGraph();
        void resetNodeInfoStatusSCC();
        void completePartialOrderGraph();
-       void removeNode(OrderNode *node) {nodes.remove(node);}
        
        CMEMALLOC;
 private:
        HashsetOrderNode nodes;
-       Vector<OrderNode *> allNodes;
        HashsetOrderEdge edges;
        Order *order;
        void DFSNodeVisit(OrderNode *node, Vector<OrderNode *> *finishNodes, bool isReverse, bool mustvisit, uint sccNum);
index 01a667d..4c95db8 100644 (file)
@@ -81,7 +81,7 @@ void DecomposeOrderTransform::doTransform() {
 }
 
 
-void DecomposeOrderTransform::decomposeOrder (Order *currOrder, OrderGraph *currGraph, HashsetOrderEdge *edgesRemoved, DecomposeOrderResolver *dor) {
+void DecomposeOrderTransform::decomposeOrder(Order *currOrder, OrderGraph *currGraph, HashsetOrderEdge *edgesRemoved, DecomposeOrderResolver *dor) {
        Vector<Order *> partialcandidatevec;
        uint size = currOrder->constraints.getSize();
        for (uint i = 0; i < size; i++) {
@@ -203,18 +203,21 @@ void DecomposeOrderTransform::bypassMustBeTrueNode(OrderGraph *graph, OrderNode
                OrderNode *srcNode = inEdge->source;
                srcNode->outEdges.remove(inEdge);
                edgesRemoved->add(inEdge);
+               bool removeOutgoingEdges = !iterin->hasNext();
+
                SetIteratorOrderEdge *iterout = node->outEdges.iterator();
                while (iterout->hasNext()) {
                        OrderEdge *outEdge = iterout->next();
                        OrderNode *sinkNode = outEdge->sink;
-                       sinkNode->inEdges.remove(outEdge);
-                       edgesRemoved->add(outEdge);
+                       if (removeOutgoingEdges) {
+                               sinkNode->inEdges.remove(outEdge);
+                               edgesRemoved->add(outEdge);
+                       }
                        //Adding new edge to new sink and src nodes ...
                        if (srcNode == sinkNode) {
                                solver->setUnSAT();
                                delete iterout;
                                delete iterin;
-                               graph->removeNode(node);
                                return;
                        }
                        //Add new order constraint
@@ -233,7 +236,6 @@ void DecomposeOrderTransform::bypassMustBeTrueNode(OrderGraph *graph, OrderNode
                delete iterout;
        }
        delete iterin;
-       graph->removeNode(node);
 }
 
 void DecomposeOrderTransform::removeMustBeTrueNodes(OrderGraph *graph, HashsetOrderEdge *edgesRemoved) {
index 148235a..74d5eba 100644 (file)
@@ -16,7 +16,6 @@ int main(int numargs, char **argv) {
 
        solver->addConstraint(solver->applyLogicalOperation(SATC_OR, b1, solver->applyLogicalOperation(SATC_NOT, b2)));
        solver->addConstraint(solver->applyLogicalOperation(SATC_OR, b2, solver->applyLogicalOperation(SATC_NOT, b1)));
-       solver->serialize();
        if (solver->solve() == 1) {
                printf("SAT\n");
                printf("O(5,1)=%d O(1,4)=%d O(5,4)=%d O(1,5)=%d\n",
index 0e652d8..c2e9db4 100644 (file)
@@ -79,6 +79,8 @@ void DecomposeOrderResolver::buildGraph() {
                        bool isEdge = suborder->encoding.resolver->resolveOrder(doredge->newfirst, doredge->newsecond);
                        if (isEdge)
                                graph->addEdge(doredge->origfirst, doredge->origsecond);
+                       else if (order->type == SATC_TOTAL)
+                               graph->addEdge(doredge->origsecond, doredge->origfirst);
                }
        }
        delete iterator;
@@ -92,9 +94,15 @@ bool DecomposeOrderResolver::resolveOrder(uint64_t first, uint64_t second) {
                buildGraph();
 
        OrderNode *from = graph->lookupOrderNodeFromOrderGraph(first);
-       ASSERT(from != NULL);
+       if (from == NULL) {
+               ASSERT(order->type != SATC_TOTAL);
+               return false;
+       }
        OrderNode *to = graph->lookupOrderNodeFromOrderGraph(second);
-       ASSERT(to != NULL);
+       if (to == NULL) {
+               ASSERT(order->type != SATC_TOTAL);
+               return false;
+       }
        switch (order->type) {
        case SATC_TOTAL:
                return from->sccNum < to->sccNum;