get_opt_op_info.hpp

Go to the documentation of this file.

# ifndef CPPAD_LOCAL_OPTIMIZE_GET_OPT_OP_INFO_HPP
# define CPPAD_LOCAL_OPTIMIZE_GET_OPT_OP_INFO_HPP

/* --------------------------------------------------------------------------
CppAD: C++ Algorithmic Differentiation: Copyright (C) 2003-17 Bradley M. Bell

CppAD is distributed under multiple licenses. This distribution is under
the terms of the
                    Eclipse Public License Version 1.0.

A copy of this license is included in the COPYING file of this distribution.
Please visit http://www.coin-or.org/CppAD/ for information on other licenses.
-------------------------------------------------------------------------- */
/*!
\file opt_op_info.hpp
Create operator information tables
*/

# include <cppad/local/optimize/opt_op_info.hpp>
# include <cppad/local/optimize/match_op.hpp>
# include <cppad/local/optimize/cexp_info.hpp>
# include <cppad/local/optimize/usage.hpp>

// BEGIN_CPPAD_LOCAL_OPTIMIZE_NAMESPACE
namespace CppAD { namespace local { namespace optimize {

/// Is this an addition or subtraction operator
inline bool add_or_subtract(OpCode op)
{    bool result;
     switch(op)
     {
          case AddpvOp:
          case AddvvOp:
          case SubpvOp:
          case SubvpOp:
          case SubvvOp:
          result = true;
          break;

          default:
          result = false;
          break;
     }
     return result;
}


/*!
Increarse argument usage and propagate cexp_set from result to argument.

\param play
is the player for the old operation sequence.

\param sum_result
is result an addition or subtraction operator (passed for speed so
do not need to call add_or_subtract for result).

\param i_result
is the operator index for the result operator.

\param i_arg
is the operator index for the argument to the result operator.

\param opt_op_info
structure that holds the information for each of the operators.
The output value of opt_op_info[i_arg].usage is increased; to be specific,
If sum_result is true and the input value of opt_op_info[i_arg].usage
is no_usage, its output value is csum_usage.
Otherwise, the output value of opt_op_info[i_arg].usage is yes_usage.

\param cexp_set
This is a vector of sets with one set for each operator. We denote
the i-th set by set[i].

\li
In the special case where cexp_set.n_set() is zero,
cexp_set is not changed.

\li
If cexp_set.n_set() != 0 and opt_op_info[i_arg].usage == no_usage,
the input value of set[i_arg] must be empty.
In this case the output value if set[i_arg] is equal to set[i_result]
(which may also be empty).

\li
If cexp_set.n_set() != 0 and opt_op_info[i_arg].usage != no_usage,
the output value of set[i_arg] is the intersection of
its input value and set[i_result].
*/
template <class Base>
inline void usage_cexp_result2arg(
     const player<Base>*         play           ,
     bool                        sum_result     ,
     size_t                      i_result       ,
     size_t                      i_arg          ,
     vector<struct_opt_op_info>& opt_op_info    ,
     sparse_list&                cexp_set       )
{
     // cexp_set
     if( cexp_set.n_set() > 0 )
     {    if( opt_op_info[i_arg].usage == no_usage )
          {    // set[i_arg] = set[i_result]
               cexp_set.assignment(i_arg, i_result, cexp_set);
          }
          else
          {    // set[i_arg] = set[i_arg] intersect set[i_result]
               cexp_set.binary_intersection(i_arg, i_arg, i_result, cexp_set);
          }
     }
     // usage
     bool csum = sum_result && opt_op_info[i_arg].usage == no_usage;
     if( csum )
     {    OpCode op_a = play->GetOp(i_arg);
          csum = add_or_subtract( op_a );
     }
     if( csum )
          opt_op_info[i_arg].usage = csum_usage;
     else
          opt_op_info[i_arg].usage = yes_usage;
     //
     return;
}

/*!
Get variable to operator map and operator basic operator information

\tparam Base
base type for the operator; i.e., this operation was recorded
using AD< \a Base > and computations by this routine are done using type
\a Base.

\param conditional_skip
If conditional_skip this is true, the conditional expression information
cexp_info will be calculated.
This may be time intensive and may not have much benefit in the optimized
recording.

\param compare_op
if this is true, arguments are considered used if they appear in compare
operators. This is a side effect because compare operators have boolean
results (and the result is not in the tape; i.e. NumRes(op) is zero
for these operators. (This is an example of a side effect.)

\param print_for_op
if this is true, arguments are considered used if they appear in
print forward operators; i.e., PriOp.
This is also a side effect; i.e. NumRes(PriOp) is zero.

\param play
This is the old operation sequence.

\param dep_taddr
is a vector of variable indices for the dependent variables.

\param cexp_info
The input size of this vector must be zero.
If conditional_skip is false, cexp_info is not changed.
Otherwise,
upon return cexp_info has size equal to the number of conditional expressions
in the operation sequence; i.e., the number of CExpOp operators.
The value cexp_info[j] is the information corresponding to the j-th
conditional expression in the operation sequence.
This vector is in the same order as the operation sequence; i.e.
if j1 > j2, cexp_info[j1].i_op > cexp_info[j2].i_op.
Note that skip_op_true and skip_op_false could be part of this structure,
but then we would allocate and deallocate two vectors for each conditonal
expression in the operation sequence.

\param skip_op_true
This vector of sets is empty on input.
Upon return, the j-th set is the operators that are not used when
comparison result for cexp_info[j] is true.
Note that UsrapOp, UsravOp, UsrrpOp, and UsrrvOp, are not in this
set and should be skipped when the corresponding UserOp are skipped.

\param skip_op_false
This vector of sets is empty on input.
Upon return, the j-th set is the operators that are not used when
comparison result for cexp_info[j] is false.
Note that UsrapOp, UsravOp, UsrrpOp, and UsrrvOp, are not in this
set and should be skipped when the corresponding UserOp are skipped.

\param vecad_used
The input size of this vector must be zero.
Upon retun it has size equal to the number of VecAD vectors
in the operations sequences; i.e., play->num_vecad_vec_rec().
The VecAD vectors are indexed in the order that thier indices apprear
in the one large play->GetVecInd that holds all the VecAD vectors.

\param opt_op_info
The input size of this vector must be zero.
Upon return it has size equal to the number of operators
in the operation sequence; i.e., num_op = play->nun_var_rec().
The value opt_op_info[i]
have been set to the values corresponding to the i-th operator
in the operation sequence.
*/

template <class Base>
void get_opt_op_info(
     bool                          conditional_skip    ,
     bool                          compare_op          ,
     bool                          print_for_op        ,
     const player<Base>*           play                ,
     const vector<size_t>&         dep_taddr           ,
     vector<struct_cexp_info>&     cexp_info           ,
     sparse_list&                  skip_op_true        ,
     sparse_list&                  skip_op_false       ,
     vector<bool>&                 vecad_used          ,
     vector<struct_opt_op_info>&   opt_op_info         )
{
     CPPAD_ASSERT_UNKNOWN( cexp_info.size() == 0 );
     CPPAD_ASSERT_UNKNOWN( vecad_used.size() == 0 );
     CPPAD_ASSERT_UNKNOWN( opt_op_info.size() == 0 );

     // number of operators in the tape
     const size_t num_op = play->num_op_rec();
     opt_op_info.resize( num_op );
     //
     // initialize mapping from variable index to operator index
     CPPAD_ASSERT_UNKNOWN(
          std::numeric_limits<addr_t>::max() >= num_op
     );
     //
     // information set by forward_user
     size_t user_old=0, user_m=0, user_n=0, user_i=0, user_j=0;
     enum_user_state user_state;
     //
     // ----------------------------------------------------------------------
     // Forward pass to determine num_cexp_op
     // ----------------------------------------------------------------------
     OpCode        op;     // operator
     const addr_t* arg;    // arguments
     size_t        i_op;   // operator index
     size_t        i_var;  // variable index of first result
     i_op = 0;
     play->get_op_info(i_op, op, arg, i_var);
     CPPAD_ASSERT_UNKNOWN( op              == BeginOp );
     CPPAD_ASSERT_UNKNOWN( NumRes(BeginOp) == 1 );
     CPPAD_ASSERT_UNKNOWN( i_op            == 0 );
     CPPAD_ASSERT_UNKNOWN( i_var           == 0 );
     //
     size_t num_cexp_op = 0;
     user_state = start_user;
     while(op != EndOp)
     {    // next operator
          play->get_op_info(++i_op, op, arg, i_var);
          //
          if( op == CExpOp )
          {    // count the number of conditional expressions.
               ++num_cexp_op;
          }
     }
     // vector that maps conditional expression index to operator index
     vector<size_t> cexp2op( num_cexp_op );
     // ----------------------------------------------------------------------
     // Reverse pass to compute usage and cexp_set for each operator
     // ----------------------------------------------------------------------
     // work space used by user defined atomic functions
     typedef std::set<size_t> size_set;
     vector<Base>     user_x;       // parameters in x as integers
     vector<size_t>   user_ix;      // variables indices for argument vector
     vector<size_set> user_r_set;   // set sparsity pattern for result
     vector<size_set> user_s_set;   // set sparisty pattern for argument
     vector<bool>     user_r_bool;  // bool sparsity pattern for result
     vector<bool>     user_s_bool;  // bool sparisty pattern for argument
     vectorBool       user_r_pack;  // pack sparsity pattern for result
     vectorBool       user_s_pack;  // pack sparisty pattern for argument
     //
     atomic_base<Base>* user_atom = CPPAD_NULL; // current user atomic function
     bool               user_pack = false;      // sparsity pattern type is pack
     bool               user_bool = false;      // sparsity pattern type is bool
     bool               user_set  = false;      // sparsity pattern type is set
     // -----------------------------------------------------------------------
     // vecad information
     size_t num_vecad      = play->num_vecad_vec_rec();
     size_t num_vecad_ind  = play->num_vec_ind_rec();
     //
     vecad_used.resize(num_vecad);
     for(size_t i = 0; i < num_vecad; i++)
          vecad_used[i] = false;
     //
     vector<size_t> arg2vecad(num_vecad_ind);
     for(size_t i = 0; i < num_vecad_ind; i++)
          arg2vecad[i] = num_vecad; // invalid value
     size_t arg_0 = 1; // value of arg[0] for theh first vecad
     for(size_t i = 0; i < num_vecad; i++)
     {
          // mapping from arg[0] value to index for this vecad object.
          arg2vecad[arg_0] = i;
          //
          // length of this vecad object
          size_t length = play->GetVecInd(arg_0 - 1);
          //
          // set to proper index in GetVecInd for next VecAD arg[0] value
          arg_0        += length + 1;
     }
     CPPAD_ASSERT_UNKNOWN( arg_0 == num_vecad_ind + 1 );
     // -----------------------------------------------------------------------
     // parameter information (used by atomic function calls)
     size_t num_par = play->num_par_rec();
     const Base* parameter = CPPAD_NULL;
     if( num_par > 0 )
          parameter = play->GetPar();
     // -----------------------------------------------------------------------
     // Set of conditional expressions comparisons that usage of each
     /// operator depends on. The operator can be skipped if any of the
     // comparisons results in the set holds. A set for operator i_op is
     // not defined and left empty when opt_op_info[i_op].usage = no_usage.
     /// It is also left empty for the result of any VecAD operations.
     sparse_list cexp_set;
     //
     // number of sets
     size_t num_set = 0;
     if( conditional_skip && num_cexp_op > 0)
          num_set = num_op;
     //
     // conditional expression index   = element / 2
     // conditional expression compare = bool ( element % 2)
     size_t end_set = 2 * num_cexp_op;
     //
     if( num_set > 0 )
          cexp_set.resize(num_set, end_set);
     // -----------------------------------------------------------------------
     //
     // initialize operator usage
     for(size_t i = 0; i < num_op; i++)
          opt_op_info[i].usage = no_usage;
     for(size_t i = 0; i < dep_taddr.size(); i++)
     {    i_op                = play->var2op(dep_taddr[i]);
          opt_op_info[i_op].usage = yes_usage;    // dependent variables
     }
     //
     // Initialize reverse pass
     size_t last_user_i_op = 0;
     size_t cexp_index     = num_cexp_op;
     user_state            = end_user;
     i_op = num_op;
     while(i_op != 0 )
     {    --i_op;
          //
          // this operator information
          play->get_op_info(i_op, op, arg, i_var);
          //
          // Is the result of this operation used.
          // (This only makes sense when NumRes(op) > 0.)
          enum_usage use_result = opt_op_info[i_op].usage;
          //
          bool sum_op = false;
          switch( op )
          {
               // =============================================================
               // normal operators
               // =============================================================

               // Only one variable with index arg[0]
               case SubvpOp:
               sum_op = true;
               //
               case AbsOp:
               case AcosOp:
               case AcoshOp:
               case AsinOp:
               case AsinhOp:
               case AtanOp:
               case AtanhOp:
               case CosOp:
               case CoshOp:
               case DivvpOp:
               case ErfOp:
               case ExpOp:
               case Expm1Op:
               case LogOp:
               case Log1pOp:
               case PowvpOp:
               case SignOp:
               case SinOp:
               case SinhOp:
               case SqrtOp:
               case TanOp:
               case TanhOp:
               case ZmulvpOp:
               CPPAD_ASSERT_UNKNOWN( NumRes(op) > 0 );
               if( use_result != no_usage )
               {    size_t j_op = play->var2op(arg[0]);
                    usage_cexp_result2arg(
                         play, sum_op, i_op, j_op, opt_op_info, cexp_set
                    );
               }
               break; // --------------------------------------------

               // Only one variable with index arg[1]
               case AddpvOp:
               case SubpvOp:
               sum_op = true;
               //
               case DisOp:
               case DivpvOp:
               case MulpvOp:
               case PowpvOp:
               case ZmulpvOp:
               CPPAD_ASSERT_UNKNOWN( NumRes(op) > 0 );
               if( use_result != no_usage )
               {    size_t j_op = play->var2op(arg[1]);
                    usage_cexp_result2arg(
                         play, sum_op, i_op, j_op, opt_op_info, cexp_set
                    );
               }
               break; // --------------------------------------------

               // arg[0] and arg[1] are the only variables
               case AddvvOp:
               case SubvvOp:
               sum_op = true;
               //
               case DivvvOp:
               case MulvvOp:
               case PowvvOp:
               case ZmulvvOp:
               CPPAD_ASSERT_UNKNOWN( NumRes(op) > 0 );
               if( use_result != no_usage )
               {    for(size_t i = 0; i < 2; i++)
                    {    size_t j_op = play->var2op(arg[i]);
                         usage_cexp_result2arg(
                              play, sum_op, i_op, j_op, opt_op_info, cexp_set
                         );
                    }
               }
               break; // --------------------------------------------

               // Conditional expression operators
               // arg[2], arg[3], arg[4], arg[5] are parameters or variables
               case CExpOp:
               --cexp_index;
               cexp2op[ cexp_index ] = i_op;
               CPPAD_ASSERT_UNKNOWN( NumRes(op) > 0 );
               if( use_result != no_usage )
               {    CPPAD_ASSERT_UNKNOWN( NumArg(CExpOp) == 6 );
                    // propgate from result to left argument
                    if( arg[1] & 1 )
                    {    size_t j_op = play->var2op(arg[2]);
                         usage_cexp_result2arg(
                              play, sum_op, i_op, j_op, opt_op_info, cexp_set
                         );
                    }
                    // propgate from result to right argument
                    if( arg[1] & 2 )
                    {    size_t j_op = play->var2op(arg[3]);
                         usage_cexp_result2arg(
                                   play, sum_op, i_op, j_op, opt_op_info, cexp_set
                         );
                    }
                    // are if_true and if_false cases the same variable
                    bool same_variable = bool(arg[1] & 4) && bool(arg[1] & 8);
                    same_variable     &= arg[4] == arg[5];
                    //
                    // if_true
                    if( arg[1] & 4 )
                    {    size_t j_op = play->var2op(arg[4]);
                         bool can_skip = conditional_skip & (! same_variable);
                         can_skip     &= opt_op_info[j_op].usage == no_usage;
                         usage_cexp_result2arg(
                              play, sum_op, i_op, j_op, opt_op_info, cexp_set
                         );
                         if( can_skip )
                         {    // j_op corresponds to the value used when the
                              // comparison result is true. It can be skipped when
                              // the comparison is false (0).
                              size_t element = 2 * cexp_index + 0;
                              cexp_set.add_element(j_op, element);
                              //
                              opt_op_info[j_op].usage = yes_usage;
                         }
                    }
                    //
                    // if_false
                    if( arg[1] & 8 )
                    {    size_t j_op = play->var2op(arg[5]);
                         bool can_skip = conditional_skip & (! same_variable);
                         can_skip     &= opt_op_info[j_op].usage == no_usage;
                         usage_cexp_result2arg(
                              play, sum_op, i_op, j_op, opt_op_info, cexp_set
                         );
                         if( can_skip )
                         {    // j_op corresponds to the value used when the
                              // comparison result is false. It can be skipped when
                              // the comparison is true (0).
                              size_t element = 2 * cexp_index + 1;
                              cexp_set.add_element(j_op, element);
                              //
                              opt_op_info[j_op].usage = yes_usage;
                         }
                    }
               }
               break;  // --------------------------------------------

               // Operations that are never used
               // (new CSkip options are generated if conditional_skip is true)
               case CSkipOp:
               case ParOp:
               break;

               // Operators that are always used
               case InvOp:
               case BeginOp:
               case EndOp:
               opt_op_info[i_op].usage = yes_usage;
               break;  // -----------------------------------------------

               // The print forward operator
               case PriOp:
               CPPAD_ASSERT_NARG_NRES(op, 5, 0);
               if( print_for_op )
               {    opt_op_info[i_op].usage = yes_usage;
                    if( arg[0] & 1 )
                    {    // arg[1] is a variable
                         size_t j_op = play->var2op(arg[1]);
                         usage_cexp_result2arg(
                              play, sum_op, i_op, j_op, opt_op_info, cexp_set
                         );
                    }
                    if( arg[0] & 2 )
                    {    // arg[3] is a variable
                         size_t j_op = play->var2op(arg[3]);
                         usage_cexp_result2arg(
                              play, sum_op, i_op, j_op, opt_op_info, cexp_set
                         );
                    }
               }
               break; // -----------------------------------------------------

               // =============================================================
               // Comparison operators
               // =============================================================

               // Compare operators where arg[1] is only variable
               case LepvOp:
               case LtpvOp:
               case EqpvOp:
               case NepvOp:
               CPPAD_ASSERT_UNKNOWN( NumRes(op) == 0 );
               if( compare_op )
               {    opt_op_info[i_op].usage = yes_usage;
                    //
                    size_t j_op = play->var2op(arg[1]);
                    usage_cexp_result2arg(
                         play, sum_op, i_op, j_op, opt_op_info, cexp_set
                    );
               }
               break; // ----------------------------------------------

               // Compare operators where arg[0] is only variable
               case LevpOp:
               case LtvpOp:
               CPPAD_ASSERT_UNKNOWN( NumRes(op) == 0 );
               if( compare_op )
               {    opt_op_info[i_op].usage = yes_usage;
                    //
                    size_t j_op = play->var2op(arg[0]);
                    usage_cexp_result2arg(
                         play, sum_op, i_op, j_op, opt_op_info, cexp_set
                    );
               }
               break; // ----------------------------------------------

               // Compare operators where arg[0] and arg[1] are variables
               case LevvOp:
               case LtvvOp:
               case EqvvOp:
               case NevvOp:
               if( compare_op )
               CPPAD_ASSERT_UNKNOWN( NumRes(op) == 0 );
               if( compare_op )
               {    opt_op_info[i_op].usage = yes_usage;
                    //
                    for(size_t i = 0; i < 2; i++)
                    {    size_t j_op = play->var2op(arg[i]);
                         usage_cexp_result2arg(
                              play, sum_op, i_op, j_op, opt_op_info, cexp_set
                         );
                    }
               }
               break; // ----------------------------------------------

               // =============================================================
               // VecAD operators
               // =============================================================

               // load operator using a parameter index
               case LdpOp:
               CPPAD_ASSERT_UNKNOWN( NumRes(op) > 0 );
               if( use_result != no_usage )
               {    size_t i_vec = arg2vecad[ arg[0] ];
                    vecad_used[i_vec] = true;
               }
               break; // --------------------------------------------

               // load operator using a variable index
               case LdvOp:
               CPPAD_ASSERT_UNKNOWN( NumRes(op) > 0 );
               if( use_result != no_usage )
               {    size_t i_vec = arg2vecad[ arg[0] ];
                    vecad_used[i_vec] = true;
                    //
                    size_t j_op = play->var2op(arg[1]);
                    opt_op_info[j_op].usage = yes_usage;
               }
               break; // --------------------------------------------

               // Store a variable using a parameter index
               case StpvOp:
               CPPAD_ASSERT_UNKNOWN( NumRes(op) == 0 );
               if( vecad_used[ arg2vecad[ arg[0] ] ] )
               {    opt_op_info[i_op].usage = yes_usage;
                    //
                    size_t j_op = play->var2op(arg[2]);
                    opt_op_info[j_op].usage = yes_usage;
               }
               break; // --------------------------------------------

               // Store a variable using a variable index
               case StvvOp:
               CPPAD_ASSERT_UNKNOWN( NumRes(op) == 0 );
               if( vecad_used[ arg2vecad[ arg[0] ] ] )
               {    opt_op_info[i_op].usage = yes_usage;
                    //
                    size_t j_op = play->var2op(arg[1]);
                    opt_op_info[j_op].usage = yes_usage;
                    size_t k_op = play->var2op(arg[2]);
                    opt_op_info[k_op].usage = yes_usage;
               }
               break; // -----------------------------------------------------

               // =============================================================
               // cumulative summation operator
               // ============================================================
               case CSumOp:
               CPPAD_ASSERT_UNKNOWN( NumRes(op) == 1 );
               {
                    size_t num_add = size_t( arg[0] );
                    size_t num_sub = size_t( arg[1] );
                    for(size_t i = 0; i < num_add + num_sub; i++)
                    {    size_t j_op = play->var2op( arg[3 + i] );
                         usage_cexp_result2arg(
                              play, sum_op, i_op, j_op, opt_op_info, cexp_set
                         );
                    }
               }
               // =============================================================
               // user defined atomic operators
               // ============================================================

               case UserOp:
               // start or end atomic operation sequence
               if( user_state == end_user )
               {    // revese_user using opt_op_info instead of play
                    size_t user_index = arg[0];
                    user_old          = arg[1];
                    user_n            = arg[2];
                    user_m            = arg[3];
                    user_j            = user_n;
                    user_i            = user_m;
                    user_state        = ret_user;
                    user_atom  = atomic_base<Base>::class_object(user_index);
                    // -------------------------------------------------------
                    last_user_i_op = i_op;
                    CPPAD_ASSERT_UNKNOWN( i_op > user_n + user_m + 1 );
                    CPPAD_ASSERT_UNKNOWN(
                         opt_op_info[last_user_i_op].usage == no_usage
                    );
# ifndef NDEBUG
                    if( cexp_set.n_set() > 0 )
                    {    sparse_list_const_iterator itr(cexp_set, last_user_i_op);
                         CPPAD_ASSERT_UNKNOWN( *itr == cexp_set.end() );
                    }
# endif
                    //
                    user_x.resize(  user_n );
                    user_ix.resize( user_n );
                    //
                    user_pack  = user_atom->sparsity() ==
                                   atomic_base<Base>::pack_sparsity_enum;
                    user_bool  = user_atom->sparsity() ==
                                   atomic_base<Base>::bool_sparsity_enum;
                    user_set   = user_atom->sparsity() ==
                                   atomic_base<Base>::set_sparsity_enum;
                    CPPAD_ASSERT_UNKNOWN( user_pack || user_bool || user_set );
                    //
                    // Note that q is one for this call the sparsity calculation
                    if( user_pack )
                    {    user_r_pack.resize( user_m );
                         user_s_pack.resize( user_n );
                         for(size_t i = 0; i < user_m; i++)
                              user_r_pack[ i ] = false;
                    }
                    if( user_bool )
                    {    user_r_bool.resize( user_m );
                         user_s_bool.resize( user_n );
                         for(size_t i = 0; i < user_m; i++)
                              user_r_bool[ i ] = false;
                    }
                    if( user_set )
                    {    user_s_set.resize(user_n);
                         user_r_set.resize(user_m);
                         for(size_t i = 0; i < user_m; i++)
                              user_r_set[i].clear();
                    }
               }
               else
               {    // reverse_user using opt_op_info instead of play
                    CPPAD_ASSERT_UNKNOWN( user_state == start_user );
                    CPPAD_ASSERT_UNKNOWN( user_n == size_t(arg[2]) );
                    CPPAD_ASSERT_UNKNOWN( user_m == size_t(arg[3]) );
                    CPPAD_ASSERT_UNKNOWN( user_j == 0 );
                    CPPAD_ASSERT_UNKNOWN( user_i == 0 );
                    user_state = end_user;
                    // -------------------------------------------------------
                    CPPAD_ASSERT_UNKNOWN(
                         i_op + user_n + user_m + 1 == last_user_i_op
                    );
                    // call users function for this operation
                    user_atom->set_old(user_old);
                    bool user_ok  = false;
                    size_t user_q = 1; // as if sum of dependent variables
                    if( user_pack )
                    {    user_ok = user_atom->rev_sparse_jac(
                              user_q, user_r_pack, user_s_pack, user_x
                         );
                         if( ! user_ok ) user_ok = user_atom->rev_sparse_jac(
                              user_q, user_r_pack, user_s_pack
                         );
                    }
                    if( user_bool )
                    {    user_ok = user_atom->rev_sparse_jac(
                              user_q, user_r_bool, user_s_bool, user_x
                         );
                         if( ! user_ok ) user_ok = user_atom->rev_sparse_jac(
                              user_q, user_r_bool, user_s_bool
                         );
                    }
                    if( user_set )
                    {    user_ok = user_atom->rev_sparse_jac(
                              user_q, user_r_set, user_s_set, user_x
                         );
                         if( ! user_ok ) user_ok = user_atom->rev_sparse_jac(
                              user_q, user_r_set, user_s_set
                         );
                    }
                    if( ! user_ok )
                    {    std::string s =
                              "Optimizing an ADFun object"
                              " that contains the atomic function\n\t";
                         s += user_atom->afun_name();
                         s += "\nCurrent atomic_sparsity is set to ";
                         //
                         if( user_set )
                              s += "set_sparsity_enum.\n";
                         if( user_bool )
                              s += "bool_sparsity_enum.\n";
                         if( user_pack )
                              s += "pack_sparsity_enum.\n";
                         //
                         s += "This version of rev_sparse_jac returned false";
                         CPPAD_ASSERT_KNOWN(false, s.c_str() );
                    }

                    if( opt_op_info[last_user_i_op].usage != no_usage )
                    for(size_t j = 0; j < user_n; j++)
                    if( user_ix[j] > 0 )
                    {    // This user argument is a variable
                         bool use_arg_j = false;
                         if( user_set )
                         {    if( ! user_s_set[j].empty() )
                                   use_arg_j = true;
                         }
                         if( user_bool )
                         {    if( user_s_bool[j] )
                                   use_arg_j = true;
                         }
                         if( user_pack )
                         {    if( user_s_pack[j] )
                                   use_arg_j = true;
                         }
                         if( use_arg_j )
                         {    size_t j_op = play->var2op(user_ix[j]);
                              usage_cexp_result2arg(play,
                                   sum_op, last_user_i_op, j_op, opt_op_info, cexp_set
                              );
                         }
                    }
                    // copy set infomation from last to first
                    if( cexp_set.n_set() > 0 )
                         cexp_set.assignment(i_op, last_user_i_op, cexp_set);
                    // copy user information from last to all the user operators
                    // for this call
                    for(size_t j = 0; j < user_n + user_m + 1; ++j)
                         opt_op_info[i_op + j].usage = opt_op_info[last_user_i_op].usage;
               }
               break; // -------------------------------------------------------

               case UsrapOp:
               // parameter argument in an atomic operation sequence
               CPPAD_ASSERT_UNKNOWN( size_t(arg[0]) < num_par );
               //
               // reverse_user using opt_op_info instead of play
               CPPAD_ASSERT_NARG_NRES(op, 1, 0);
               CPPAD_ASSERT_UNKNOWN( 0 < user_j && user_j < user_n );
               --user_j;
               if( user_j == 0 )
                    user_state = start_user;
               // -------------------------------------------------------------
               user_ix[user_j] = 0;
               //
               // parameter arguments
               user_x[user_j] = parameter[arg[0]];
               //
               break;

               case UsravOp:
               // variable argument in an atomic operation sequence
               CPPAD_ASSERT_UNKNOWN( 0 < arg[0] );
               //
               // reverse_user using opt_op_info instead of play
               CPPAD_ASSERT_NARG_NRES(op, 1, 0);
               CPPAD_ASSERT_UNKNOWN( 0 < user_j && user_j <= user_n );
               --user_j;
               if( user_j == 0 )
                    user_state = start_user;
               // -------------------------------------------------------------
               user_ix[user_j] = arg[0];
               //
               // variable arguments as parameters
               user_x[user_j] = CppAD::numeric_limits<Base>::quiet_NaN();
               //
               break;

               case UsrrvOp:
               // variable result in an atomic operation sequence
               //
               // reverse_user using opt_op_info instead of play
               CPPAD_ASSERT_NARG_NRES(op, 0, 1);
               CPPAD_ASSERT_UNKNOWN( 0 < user_i && user_i <= user_m );
               --user_i;
               if( user_i == 0 )
                    user_state = arg_user;
               // -------------------------------------------------------------
               if( use_result )
               {    if( user_set )
                         user_r_set[user_i].insert(0);
                    if( user_bool )
                         user_r_bool[user_i] = true;
                    if( user_pack )
                         user_r_pack[user_i] = true;
                    //
                    usage_cexp_result2arg(
                         play, sum_op, i_op, last_user_i_op, opt_op_info, cexp_set
                    );
               }
               break; // --------------------------------------------------------

               case UsrrpOp:
               CPPAD_ASSERT_UNKNOWN( size_t(arg[0]) < num_par );
               //
               // reverse_user using opt_op_info instead of play
               CPPAD_ASSERT_NARG_NRES(op, 0, 1);
               CPPAD_ASSERT_UNKNOWN( 0 < user_i && user_i < user_m );
               --user_i;
               if( user_i == 0 )
                    user_state = arg_user;
               break;
               // ============================================================

               // all cases should be handled above
               default:
               CPPAD_ASSERT_UNKNOWN(0);
          }
     }
     // ----------------------------------------------------------------------
     // compute previous in opt_op_info
     // ----------------------------------------------------------------------
     sparse_list  hash_table_op;
     hash_table_op.resize(CPPAD_HASH_TABLE_SIZE, num_op);
     //
     user_state = start_user;
     for(i_op = 0; i_op < num_op; ++i_op)
     {    opt_op_info[i_op].previous = 0;

          if( opt_op_info[i_op].usage == yes_usage )
          switch( play->GetOp(i_op) )
          {
               case NumberOp:
               CPPAD_ASSERT_UNKNOWN(false);
               break;

               case BeginOp:
               case CExpOp:
               case CSkipOp:
               case CSumOp:
               case EndOp:
               case InvOp:
               case LdpOp:
               case LdvOp:
               case ParOp:
               case PriOp:
               case StppOp:
               case StpvOp:
               case StvpOp:
               case StvvOp:
               case UserOp:
               case UsrapOp:
               case UsravOp:
               case UsrrpOp:
               case UsrrvOp:
               // these operators never match pevious operators
               break;

               case AbsOp:
               case AcosOp:
               case AcoshOp:
               case AddpvOp:
               case AddvvOp:
               case AsinOp:
               case AsinhOp:
               case AtanOp:
               case AtanhOp:
               case CosOp:
               case CoshOp:
               case DisOp:
               case DivpvOp:
               case DivvpOp:
               case DivvvOp:
               case EqpvOp:
               case EqvvOp:
               case ErfOp:
               case ExpOp:
               case Expm1Op:
               case LepvOp:
               case LevpOp:
               case LevvOp:
               case LogOp:
               case Log1pOp:
               case LtpvOp:
               case LtvpOp:
               case LtvvOp:
               case MulpvOp:
               case MulvvOp:
               case NepvOp:
               case NevvOp:
               case PowpvOp:
               case PowvpOp:
               case PowvvOp:
               case SignOp:
               case SinOp:
               case SinhOp:
               case SqrtOp:
               case SubpvOp:
               case SubvpOp:
               case SubvvOp:
               case TanOp:
               case TanhOp:
               case ZmulpvOp:
               case ZmulvpOp:
               case ZmulvvOp:
               // check for a previous match
               match_op(play, opt_op_info, i_op, hash_table_op );
               if( opt_op_info[i_op].previous != 0 )
               {    // like a unary operator that assigns i_op equal to previous.
                    size_t previous = opt_op_info[i_op].previous;
                    bool sum_op = false;
                    CPPAD_ASSERT_UNKNOWN( previous < i_op );
                    usage_cexp_result2arg(
                         play, sum_op, i_op, previous, opt_op_info, cexp_set
                    );
               }
               break;
          }
     }
     // ----------------------------------------------------------------------
     // compute cexp_info
     // ----------------------------------------------------------------------
     if( cexp_set.n_set() == 0 )
          return;
     //
     // initialize information for each conditional expression
     cexp_info.resize(num_cexp_op);
     skip_op_true.resize(num_cexp_op, num_op);
     skip_op_false.resize(num_cexp_op, num_op);
     //
     for(size_t i = 0; i < num_cexp_op; i++)
     {    CPPAD_ASSERT_UNKNOWN(
               opt_op_info[i].previous == 0 || opt_op_info[i].usage == yes_usage
          );
          i_op            = cexp2op[i];
          play->get_op_info(i_op, op, arg, i_var);
          CPPAD_ASSERT_UNKNOWN( op == CExpOp );
          //
          struct_cexp_info info;
          info.i_op       = i_op;
          info.cop        = CompareOp( arg[0] );
          info.flag       = arg[1];
          info.left       = arg[2];
          info.right      = arg[3];
          //
          // max_left_right
          size_t index    = 0;
          if( arg[1] & 1 )
               index = std::max(index, info.left);
          if( arg[1] & 2 )
               index = std::max(index, info.right);
          CPPAD_ASSERT_UNKNOWN( index > 0 );
          info.max_left_right = index;
          //
          cexp_info[i] = info;
     };
     // Determine which operators can be conditionally skipped
     i_op = 0;
     while(i_op < num_op)
     {    size_t j_op = i_op;
          bool keep = opt_op_info[i_op].usage != no_usage;
          keep     &= opt_op_info[i_op].usage != csum_usage;
          keep     &= opt_op_info[i_op].previous == 0;
          if( keep )
          {    sparse_list_const_iterator itr(cexp_set, i_op);
               if( *itr != cexp_set.end() )
               {    if( play->GetOp(i_op) == UserOp )
                    {    // i_op is the first operations in this user atomic call.
                         // Find the last operation in this call.
                         ++j_op;
                         while( play->GetOp(j_op) != UserOp )
                         {    switch( play->GetOp(j_op) )
                              {    case UsrapOp:
                                   case UsravOp:
                                   case UsrrpOp:
                                   case UsrrvOp:
                                   break;

                                   default:
                                   CPPAD_ASSERT_UNKNOWN(false);
                              }
                              ++j_op;
                         }
                    }
               }
               while( *itr != cexp_set.end() )
               {    size_t element = *itr;
                    size_t index   = element / 2;
                    bool   compare = bool( element % 2 );
                    if( compare == false )
                    {    // cexp_info[index].skip_op_false.push_back(i_op);
                         skip_op_false.add_element(index, i_op);
                         if( j_op != i_op )
                         {    // cexp_info[index].skip_op_false.push_back(j_op);
                              skip_op_false.add_element(index, j_op);
                         }
                    }
                    else
                    {    // cexp_info[index].skip_op_true.push_back(i_op);
                         skip_op_true.add_element(index, i_op);
                         if( j_op != i_op )
                         {    // cexp_info[index].skip_op_true.push_back(j_op);
                              skip_op_true.add_element(index, j_op);
                         }
                    }
                    ++itr;
               }
          }
          CPPAD_ASSERT_UNKNOWN( i_op <= j_op );
          i_op += (1 + j_op) - i_op;
     }
     return;
}

} } } // END_CPPAD_LOCAL_OPTIMIZE_NAMESPACE

# endif