optimization - a given write can resolve at most one promise from a rmw

diff --git a/model.cc b/model.cc
index 1ec72738ba3d0622bb27c8dedb3eab4c875aa90c..1e730d794baca5dc99387053bb98125b3756193a 100644 (file)
--- a/model.cc
+++ b/model.cc
@@ -1839,7 +1839,7 @@ void ModelChecker::compute_promises(ModelAction *curr)
                                !act->same_thread(curr) &&
                                act->get_location() == curr->get_location() &&
                                promise->get_value() == curr->get_value()) {
                                !act->same_thread(curr) &&
                                act->get_location() == curr->get_location() &&
                                promise->get_value() == curr->get_value()) {

-                       curr->get_node()->set_promise(i);
+                       curr->get_node()->set_promise(i, act->is_rmw());

                }
        }
 }
                }
        }
 }

diff --git a/nodestack.cc b/nodestack.cc
index d08fa5c733e126f1faa710bfb613bb1df6ecccff..22cc3784a1c75476b15c3e4378677158dc911e95 100644 (file)
--- a/nodestack.cc
+++ b/nodestack.cc
@@ -105,11 +105,14 @@ void Node::print_may_read_from()
  * Sets a promise to explore meeting with the given node.
  * @param i is the promise index.
  */
  * Sets a promise to explore meeting with the given node.
  * @param i is the promise index.
  */

-void Node::set_promise(unsigned int i) {
+void Node::set_promise(unsigned int i, bool is_rmw) {

        if (i >= promises.size())
                promises.resize(i + 1, PROMISE_IGNORE);
        if (i >= promises.size())
                promises.resize(i + 1, PROMISE_IGNORE);

-       if (promises[i] == PROMISE_IGNORE)
+       if (promises[i] == PROMISE_IGNORE) {

                promises[i] = PROMISE_UNFULFILLED;
                promises[i] = PROMISE_UNFULFILLED;

+               if (is_rmw)
+                       promises[i] |= PROMISE_RMW;
+       }

 }
 
 /**
 }
 
 /**


@@ -118,7 +121,7 @@ void Node::set_promise(unsigned int i) {
  * @return true if the promise should be satisfied by the given model action.
  */
 bool Node::get_promise(unsigned int i) {
  * @return true if the promise should be satisfied by the given model action.
  */
 bool Node::get_promise(unsigned int i) {

-       return (i < promises.size()) && (promises[i] == PROMISE_FULFILLED);
+       return (i < promises.size()) && ((promises[i] & PROMISE_MASK) == PROMISE_FULFILLED);

 }
 
 /**
 }
 
 /**


@@ -127,16 +130,27 @@ bool Node::get_promise(unsigned int i) {
  */
 bool Node::increment_promise() {
        DBG();
  */
 bool Node::increment_promise() {
        DBG();

-
+       unsigned int rmw_count=0;

        for (unsigned int i = 0; i < promises.size(); i++) {
        for (unsigned int i = 0; i < promises.size(); i++) {

-               if (promises[i] == PROMISE_UNFULFILLED) {
-                       promises[i] = PROMISE_FULFILLED;
+               if (promises[i]==(PROMISE_RMW|PROMISE_FULFILLED))
+                       rmw_count++;
+       }
+       
+       for (unsigned int i = 0; i < promises.size(); i++) {
+               if ((promises[i] & PROMISE_MASK) == PROMISE_UNFULFILLED) {
+                       if ((rmw_count > 0) && (promises[i] & PROMISE_RMW)) {
+                               //sending our value to two rmws... not going to work..try next combination
+                               continue;
+                       }
+                       promises[i] = (promises[i] & PROMISE_RMW) |PROMISE_FULFILLED;

                        while (i > 0) {
                                i--;
                        while (i > 0) {
                                i--;

-                               if (promises[i] == PROMISE_FULFILLED)
-                                       promises[i] = PROMISE_UNFULFILLED;
+                               if ((promises[i] & PROMISE_MASK) == PROMISE_FULFILLED)
+                                       promises[i] = (promises[i] & PROMISE_RMW) | PROMISE_UNFULFILLED;

                        }
                        return true;
                        }
                        return true;

+               } else if (promises[i] == (PROMISE_RMW|PROMISE_FULFILLED)) {
+                       rmw_count--;

                }
        }
        return false;
                }
        }
        return false;


@@ -147,9 +161,22 @@ bool Node::increment_promise() {
  * @return true if we have explored all promise combinations.
  */
 bool Node::promise_empty() {
  * @return true if we have explored all promise combinations.
  */
 bool Node::promise_empty() {

-       for (unsigned int i = 0; i < promises.size();i++)
-               if (promises[i] == PROMISE_UNFULFILLED)
+       unsigned int rmw_count=0;
+       for (unsigned int i = 0; i < promises.size(); i++) {
+               if (promises[i]==(PROMISE_RMW|PROMISE_FULFILLED))
+                       rmw_count++;
+       }
+
+       for (unsigned int i = 0; i < promises.size();i++) {
+               if ((promises[i]& PROMISE_MASK) == PROMISE_UNFULFILLED) {
+                       //if this isn't a feasible option, keep going
+                       if ((rmw_count > 0)&&(promises[i] & PROMISE_RMW))
+                               continue;

                        return false;
                        return false;

+               } else if (promises[i] == (PROMISE_RMW|PROMISE_FULFILLED)) {
+                       rmw_count--;
+               }
+       }

        return true;
 }
 
        return true;
 }
 

diff --git a/nodestack.h b/nodestack.h
index 648ef4dfc318afc38a4e98b1e31bf4a1bcc944eb..986b9c9df4be85f15d57cbf13f46d62626a3c35d 100644 (file)
--- a/nodestack.h
+++ b/nodestack.h
@@ -24,11 +24,14 @@ class Thread;
  * <li>@b fulfilled: satisfied by this Node's ModelAction under the current
  * configuration.</li></ol>
  */
  * <li>@b fulfilled: satisfied by this Node's ModelAction under the current
  * configuration.</li></ol>
  */

-typedef enum {
-       PROMISE_IGNORE = 0, /**< This promise is inapplicable; ignore it */
-       PROMISE_UNFULFILLED, /**< This promise is applicable but unfulfilled */
-       PROMISE_FULFILLED /**< This promise is applicable and fulfilled */
-} promise_t;
+
+#define        PROMISE_IGNORE 0 /**< This promise is inapplicable; ignore it */
+#define        PROMISE_UNFULFILLED 1 /**< This promise is applicable but unfulfilled */
+#define        PROMISE_FULFILLED 2 /**< This promise is applicable and fulfilled */
+#define PROMISE_MASK 0xf
+#define PROMISE_RMW 0x10
+
+typedef int promise_t;

 
 struct future_value {
        uint64_t value;
 
 struct future_value {
        uint64_t value;


@@ -88,7 +91,7 @@ public:
        int get_read_from_size();
        const ModelAction * get_read_from_at(int i);
 
        int get_read_from_size();
        const ModelAction * get_read_from_at(int i);
 

-       void set_promise(unsigned int i);
+       void set_promise(unsigned int i, bool is_rmw);

        bool get_promise(unsigned int i);
        bool increment_promise();
        bool promise_empty();
        bool get_promise(unsigned int i);
        bool increment_promise();
        bool promise_empty();