[PTree] Replace left/right with PointerIntPair

3 files changed, 29 insertions, 24 deletions

diff --git a/lib/Core/PTree.cpp b/lib/Core/PTree.cpp
index 26de37fb..2962e3c2 100644
--- a/lib/Core/PTree.cpp
+++ b/lib/Core/PTree.cpp
@@ -24,28 +24,27 @@ PTree::PTree(ExecutionState *initialState) {
 }
 
 void PTree::attach(PTreeNode *node, ExecutionState *leftState, ExecutionState *rightState) {
-  assert(node && !node->left && !node->right);
-
+  assert(node && !node->left.getPointer() && !node->right.getPointer());
   node->state = nullptr;
-  node->left = new PTreeNode(node, leftState);
-  node->right = new PTreeNode(node, rightState);
+  node->left = PTreeNodePtr(new PTreeNode(node, leftState));
+  node->right = PTreeNodePtr(new PTreeNode(node, rightState));
 }
 
 void PTree::remove(PTreeNode *n) {
-  assert(!n->left && !n->right);
+  assert(!n->left.getPointer() && !n->right.getPointer());
   do {
     PTreeNode *p = n->parent;
     if (p) {
-      if (n == p->left) {
-        p->left = nullptr;
+      if (n == p->left.getPointer()) {
+        p->left = PTreeNodePtr(nullptr);
       } else {
-        assert(n == p->right);
-        p->right = nullptr;
+        assert(n == p->right.getPointer());
+        p->right = PTreeNodePtr(nullptr);
       }
     }
     delete n;
     n = p;
-  } while (n && !n->left && !n->right);
+  } while (n && !n->left.getPointer() && !n->right.getPointer());
 }
 
 void PTree::dump(llvm::raw_ostream &os) {
@@ -67,13 +66,13 @@ void PTree::dump(llvm::raw_ostream &os) {
     if (n->state)
       os << ",fillcolor=green";
     os << "];\n";
-    if (n->left) {
-      os << "\tn" << n << " -> n" << n->left << ";\n";
-      stack.push_back(n->left);
+    if (n->left.getPointer()) {
+      os << "\tn" << n << " -> n" << n->left.getPointer() << ";\n";
+      stack.push_back(n->left.getPointer());
     }
-    if (n->right) {
-      os << "\tn" << n << " -> n" << n->right << ";\n";
-      stack.push_back(n->right);
+    if (n->right.getPointer()) {
+      os << "\tn" << n << " -> n" << n->right.getPointer() << ";\n";
+      stack.push_back(n->right.getPointer());
     }
   }
   os << "}\n";
@@ -82,5 +81,6 @@ void PTree::dump(llvm::raw_ostream &os) {
 
 PTreeNode::PTreeNode(PTreeNode *parent, ExecutionState *state) : parent{parent}, state{state} {
   state->ptreeNode = this;
+  left = PTreeNodePtr(nullptr);
+  right = PTreeNodePtr(nullptr);
 }
-
diff --git a/lib/Core/PTree.h b/lib/Core/PTree.h
index 6456b57f..115ea83f 100644
--- a/lib/Core/PTree.h
+++ b/lib/Core/PTree.h
@@ -11,15 +11,20 @@
 #define KLEE_PTREE_H
 
 #include "klee/Expr/Expr.h"
+#include "llvm/ADT/PointerIntPair.h"
 
 namespace klee {
   class ExecutionState;
+  class PTreeNode;
+  using PTreeNodePtr = llvm::PointerIntPair<PTreeNode*,3,uint8_t>;
+
 
   class PTreeNode {
   public:
     PTreeNode *parent = nullptr;
-    PTreeNode *left = nullptr;
-    PTreeNode *right = nullptr;
+
+    PTreeNodePtr left; 
+    PTreeNodePtr right;
     ExecutionState *state = nullptr;
 
     PTreeNode(const PTreeNode&) = delete;
diff --git a/lib/Core/Searcher.cpp b/lib/Core/Searcher.cpp
index 0a1e6152..27a92b49 100644
--- a/lib/Core/Searcher.cpp
+++ b/lib/Core/Searcher.cpp
@@ -271,17 +271,17 @@ ExecutionState &RandomPathSearcher::selectState() {
   unsigned flips=0, bits=0;
   PTreeNode *n = executor.processTree->root;
   while (!n->state) {
-    if (!n->left) {
-      n = n->right;
-    } else if (!n->right) {
-      n = n->left;
+    if (!n->left.getPointer()) {
+      n = n->right.getPointer();
+    } else if (!n->right.getPointer()) {
+      n = n->left.getPointer();
     } else {
       if (bits==0) {
         flips = theRNG.getInt32();
         bits = 32;
       }
       --bits;
-      n = (flips&(1<<bits)) ? n->left : n->right;
+      n = (flips&(1<<bits)) ? n->left.getPointer() : n->right.getPointer();
     }
   }