Optimize predicate expression evaluation

- Inhibited evaluating RHS of OR expression when not needed
- Inhibited evaluating RHS of AND expression when not needed

Change-Id: I4288b0e708f747b8113416df38414327a61aaa49
Reviewed-on: http://gfw160.austin.ibm.com:8080/gerrit/6120
Reviewed-by: Brian H. Horton <brianh@linux.ibm.com>
Tested-by: Jenkins Server
Reviewed-by: A. Patrick Williams III <iawillia@us.ibm.com>

1 files changed, 88 insertions, 19 deletions

diff --git a/src/usr/targeting/common/predicates/predicatepostfixexpr.C b/src/usr/targeting/common/predicates/predicatepostfixexpr.C
index c38814a11..700d38149 100644
--- a/src/usr/targeting/common/predicates/predicatepostfixexpr.C
+++ b/src/usr/targeting/common/predicates/predicatepostfixexpr.C
@@ -43,7 +43,7 @@
 #include <targeting/common/trace.H>
 
 //******************************************************************************
-// Macros 
+// Macros
 //******************************************************************************
 
 #undef TARG_NAMESPACE
@@ -51,7 +51,7 @@
 #undef TARG_FN
 
 //******************************************************************************
-// Interface 
+// Interface
 //******************************************************************************
 
 namespace TARGETING
@@ -99,7 +99,7 @@ PredicatePostfixExpr& PredicatePostfixExpr::push(
 //******************************************************************************
 
 PredicatePostfixExpr& PredicatePostfixExpr::And()
-{   
+{
     #define TARG_FN "And()"
 
     Operation l_op = {AND,NULL};
@@ -144,14 +144,21 @@ PredicatePostfixExpr& PredicatePostfixExpr::Or()
 //******************************************************************************
 
 bool PredicatePostfixExpr::operator()(
-    const Target* const i_pTarget) const 
+    const Target* const i_pTarget) const
 {
     #define TARG_FN "operator()(...)"
-   
+
     TARG_ASSERT(i_pTarget != NULL,
            TARG_LOC "Caller supplied a NULL target");
-  
-    std::vector<bool> l_stack;
+
+    // The "stack" is a vector of unsigned values, such that each is guaranteed
+    // to be the size of a pointer no matter what architecture the code is
+    // compiled under.  Any value on the stack is either 0 (a predicate
+    // previously evaluated false), 1 (a predicate previously evaluated true),
+    // or the address of a predicate that still needs to be evaluated.
+    std::vector<uintptr_t> l_stack;
+    uintptr_t lhs = false;
+    uintptr_t rhs = false;
     bool l_result = false;
 
     for (std::vector<Operation>::const_iterator
@@ -162,30 +169,87 @@ bool PredicatePostfixExpr::operator()(
         switch((*opsIter).logicalOp)
         {
             case EVAL:
-                l_stack.push_back((*(*opsIter).pPredicate)(i_pTarget));
+
+                // Push address of the predicate to the stack, but don't
+                // evaluate it yet so that we can do it on an opportunistic
+                // basis
+                l_stack.push_back(reinterpret_cast<uintptr_t>(
+                    (*opsIter).pPredicate));
                 break;
+
             case AND:
+
                 TARG_ASSERT(l_stack.size() >= 2,
                        TARG_LOC "Stack for AND must be >=2 but is %d",
-                       l_stack.size());              
-                l_result = l_stack.back();
+                       l_stack.size());
+
+                // The stack now has two trailing items, LHS + RHS (back).  If
+                // LHS is still in predicate form, evaluate it first, otherwise
+                // use it directly.  If 0, then logically ANDing LHS with
+                // RHS (even if RHS is stil in predicate form), will always be
+                // 0.  Therefore replace LHS/RHS on the stack with 0.
+                // Otherwise, if RHS is still in predicate form, evaluate it
+                // (else use directly), logically AND LHS/RHS, and replace
+                // LHS/RHS on the stack with the result
+                rhs = l_stack.back();
                 l_stack.pop_back();
-                l_stack.back() = (l_stack.back() & l_result);
+                lhs = l_stack.back();
+                lhs = alreadyEvaluated(lhs) ? lhs :
+                    (*reinterpret_cast<const PredicateBase*>(lhs))(i_pTarget);
+                if(lhs == false)
+                {
+                    l_stack.back() = false;
+                    break;
+                }
+                rhs = alreadyEvaluated(rhs) ? rhs :
+                    (*reinterpret_cast<const PredicateBase*>(rhs))(i_pTarget);
+                l_stack.back() = (lhs && rhs);
                 break;
+
             case OR:
+
                TARG_ASSERT(l_stack.size() >= 2,
                        TARG_LOC "Stack for OR must be >= 2 but is %d",
-                       l_stack.size());    
-                l_result = l_stack.back();
+                       l_stack.size());
+
+                // The stack now has two trailing items, LHS + RHS (back).  If
+                // LHS is still in predicate form, evaluate it first, otherwise
+                // use it directly.  If 1, then logically ORing LHS with
+                // RHS (even if RHS is stil in predicate form), will always be
+                // 1.  Therefore replace LHS/RHS on the stack with 1.
+                // Otherwise, if RHS is still in predicate form, evaluate it
+                // (else use directly), logically OR LHS/RHS, and replace
+                // LHS/RHS on the stack with the result
+                rhs = l_stack.back();
                 l_stack.pop_back();
-                l_stack.back() = (l_stack.back() | l_result);
+                lhs = l_stack.back();
+                lhs = alreadyEvaluated(lhs) ? lhs :
+                    (*reinterpret_cast<const PredicateBase*>(lhs))(i_pTarget);
+                if(lhs == true)
+                {
+                    l_stack.back() = true;
+                    break;
+                }
+                rhs = alreadyEvaluated(rhs) ? rhs :
+                    (*reinterpret_cast<const PredicateBase*>(rhs))(i_pTarget);
+                l_stack.back() = (lhs || rhs);
                 break;
-            case NOT:
+
+             case NOT:
                 TARG_ASSERT(l_stack.size() >= 1,
                        TARG_LOC "Stack for NOT must be >= 1 but is %d",
                        l_stack.size());
-                l_stack.back() = !l_stack.back();
+
+                // The stack now has a trailing item, LHS (back). If LHS is
+                // still in predicate form, evaluate it first, otherwise
+                // use it directly.  Logically negate the value, and replace
+                // LHS on the stack with the result
+                lhs = l_stack.back();
+                lhs = alreadyEvaluated(lhs) ? lhs :
+                    (*reinterpret_cast<const PredicateBase*>(lhs))(i_pTarget);
+                l_stack.back() = !lhs;
                 break;
+
            default:
                 TARG_ASSERT(0,
                        TARG_LOC "Attempted to evaluate unsupported "
@@ -195,9 +259,9 @@ bool PredicatePostfixExpr::operator()(
         }
     }
 
-    // If no predicates and we haven't asserted (no misformatting), element 
+    // If no predicates and we haven't asserted (no misformatting), element
     // should be returned
-    if(l_stack.size() == 0) 
+    if(l_stack.size() == 0)
     {
         l_result = true;
     }
@@ -208,7 +272,12 @@ bool PredicatePostfixExpr::operator()(
                "size should be 1 but is %d",
                l_stack.size());
 
-        l_result = l_stack.front();
+        // The stack now has a trailing item, LHS (back). If LHS is still in
+        // predicate form, evaluate it first, otherwise use it directly.  This
+        // is the result of the logical expression, so return it to the caller
+        lhs = l_stack.back();
+        l_result = alreadyEvaluated(lhs) ? lhs :
+            (*reinterpret_cast<const PredicateBase*>(lhs))(i_pTarget);
     }
 
     return l_result;