Changeset 1600


Ignore:
Timestamp:
Dec 4, 2009 11:54:16 AM (11 years ago)
Author:
bradbell
Message:

trunk: In optimize, factor out (parameter op variable) case to a function.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/cppad/local/optimize.hpp

    r1599 r1600  
    236236this operation in the new operation sequence.
    237237
    238 \param new_arg
    239 The input value of \c new_arg[0] does not matter.
    240 The output value of \c new_arg[0] is the argument for this unary
    241 operator in the new operation sequence.
    242 
    243238\return
    244239If the return value is zero,
     
    260255        const CppAD::vector<size_t>&                   hash_table_var ,
    261256        const CppAD::vector<struct optimize_variable>& tape           ,
    262         unsigned short&                                code           ,
    263         size_t*                                        new_arg        )
    264 {       
     257        unsigned short&                                code           )
     258{       size_t new_arg[1];
     259       
    265260        CPPAD_ASSERT_UNKNOWN( NumArg(op) == 1 );
    266261        CPPAD_ASSERT_UNKNOWN( NumRes(op) > 0  );
     
    284279        return 0;
    285280}
     281
     282/*!
     283Check a (parameter op variable) for a complete match with a previous operator.
     284
     285A complete match means that the result of the previous operator
     286can be used inplace of the result for this operator.
     287
     288\param old_res
     289is the index in the old operation sequence for
     290the variable corresponding to the result for this unary operator.
     291
     292\param op
     293is the unary operator that we are checking a match for.
     294The value of op be the same for a match; i.e., the commutative case
     295of an AddpvOp matching an AddvpOp or MulpvOp matching a MulvpOp
     296is not checked for.
     297Assertion: NumArg(op) == 2 and NumRes(op) > 0.
     298
     299\param old_arg
     300The value \c old_arg[0] is the index of the
     301first operand (parameter) in the \a par vector.
     302Assertion: old_arg[0] < npar.
     303The value \c old_arg[1] is the index of the second operand (variable)
     304in the old operation sequence.
     305Assertion: old_arg[1] < old_res.
     306
     307\param npar
     308is the number of paraemters corresponding to this operation sequence.
     309
     310\param par
     311is a vector of length \a npar containing the parameters
     312for this operation sequence; i.e.,
     313given a parameter index \c i, the corresponding parameter value is
     314\a par[i].
     315
     316\param hash_table_var
     317is a vector with size CPPAD_HASH_TABLE_SIZE
     318that maps a hash code to the corresponding
     319variable index in the old operation sequence.
     320All the values in this table must be less than \c old_res.
     321
     322\param tape
     323is a vector that maps a variable index, in the old operation sequence,
     324to the corresponding \c optimze_variable information.
     325For indices \c i less than \c old_res,
     326the following must be true of \c tape[i]:
     327
     328\li tape[i].op
     329is the operator in the old operation sequence
     330corresponding to the old variable index \c i.
     331Assertion: NumRes(tape[i].op) > 0.
     332
     333\li tape[i].arg
     334For j < NumArg( tape[i].op ),
     335tape[i].arg[j] is the j-th the operand, in the old operation sequence,
     336corresponding to the old variable index \c i.
     337Assertion: tape[i].arg[j] < i.
     338
     339\li \c tape[i].new_var
     340is the variable in the new operation sequence
     341corresponding to the old variable index \c i.
     342Assertion: tape[i].new_var < old_res.
     343
     344\param code
     345The input value of \c code does not matter.
     346The output value of \c code is the hash code corresponding to
     347this operation in the new operation sequence.
     348
     349\return
     350If the return value is zero,
     351no match was found.
     352If the return value is greater than zero,
     353it is the index of a new variable that can be used to replace the
     354old variable.
     355
     356\par Check Assertions
     357\li
     358*/
     359template <class Base>
     360inline size_t optimize_par_op_var_match(
     361        size_t                                         old_res        ,
     362        OpCode                                         op             ,
     363        const size_t*                                  old_arg        ,
     364        size_t                                         npar           ,
     365        const Base*                                    par            ,
     366        const CppAD::vector<size_t>&                   hash_table_var ,
     367        const CppAD::vector<struct optimize_variable>& tape           ,
     368        unsigned short&                                code           )
     369{       size_t new_arg[2];
     370       
     371        CPPAD_ASSERT_UNKNOWN( NumArg(op) == 2 );
     372        CPPAD_ASSERT_UNKNOWN( NumRes(op) > 0  );
     373        CPPAD_ASSERT_UNKNOWN( old_arg[0] < npar );
     374        CPPAD_ASSERT_UNKNOWN( old_arg[1] < old_res );
     375        new_arg[0] = old_arg[0];
     376        new_arg[1] = tape[old_arg[1]].new_var;
     377        CPPAD_ASSERT_UNKNOWN( new_arg[1] < old_res );
     378        code = hash_code(
     379                op                  ,
     380                new_arg             ,
     381                npar                ,
     382                par
     383        );
     384        size_t  i  = hash_table_var[code];
     385        CPPAD_ASSERT_UNKNOWN( i < old_res );
     386        if( op == tape[i].op )
     387        {       size_t k = tape[i].arg[0];
     388                CPPAD_ASSERT_UNKNOWN( k < npar );
     389                // check if parameter values match
     390                if( IdenticalEqualPar( par[ old_arg[0] ] , par[k] ) )
     391                {       k = tape[i].arg[1];
     392                        CPPAD_ASSERT_UNKNOWN( k < i );
     393                        // check if same new variable
     394                        if (new_arg[1] == tape[k].new_var );
     395                                return tape[i].new_var;
     396                }
     397        }
     398        return 0;
     399}
     400
    286401
    287402/*!
     
    682797                                hash_table_var      ,
    683798                                tape                ,
    684                                 code                , // outputs
    685                                 new_arg
     799                                code                  // outputs
    686800                        );
    687801                        if( match_var > 0 )
    688802                                tape[i_var].new_var = match_var;
    689803                        else
    690                         {       rec->PutArg( new_arg[0] );
    691                                 tape[i_var].new_var = rec->PutOp(op);
     804                        {       new_arg[0] = tape[ arg[0] ].new_var;
     805                                rec->PutArg( new_arg[0] );
     806                                i                   = rec->PutOp(op);
     807                                tape[i_var].new_var = i;
     808                                CPPAD_ASSERT_UNKNOWN( new_arg[0] < i );
    692809                        }
    693810                        break;
     
    735852                        case PowpvOp:
    736853                        case SubpvOp:
    737                         CPPAD_ASSERT_UNKNOWN( NumArg(op) == 2 );
    738                         CPPAD_ASSERT_UNKNOWN( NumRes(op) >  0 );
    739                         new_arg[1] = tape[arg[1]].new_var;
    740                         CPPAD_ASSERT_UNKNOWN( new_arg[1] < num_var );
    741                         new_arg[0] = arg[0];
    742                         code       = hash_code(
    743                                 op                  ,
    744                                 new_arg             ,
     854                        match_var = optimize_par_op_var_match(
     855                                i_var               ,  // inputs
     856                                op                  ,
     857                                arg                 ,
    745858                                play->num_rec_par() ,
    746                                 play->GetPar()
     859                                play->GetPar()      ,
     860                                hash_table_var      ,
     861                                tape                ,
     862                                code                  // outputs
    747863                        );
    748                         hash_var   = hash_table_var[code];
    749                         hash_arg   = tape[hash_var].arg;
    750                         //
    751                         par        = play->GetPar( arg[0] );
    752                         if( op == tape[hash_var].op )
    753                         {       match   = (
    754                                         new_arg[1] == tape[hash_arg[1]].new_var
    755                                 );
    756                                 hash_par= play->GetPar( hash_arg[0] );
    757                                 match  &= IdenticalEqualPar(par, hash_par);
    758                         }
    759                         if( match )
    760                                 tape[i_var].new_var = tape[hash_var].new_var;
     864                        if( match_var > 0 )
     865                                tape[i_var].new_var = match_var;
    761866                        else
    762                         {
    763                                 new_arg[0] = rec->PutPar(par);
     867                        {       new_arg[0] = rec->PutPar(
     868                                        play->GetPar( arg[0] )
     869                                );
     870                                new_arg[1] = tape[ arg[1] ].new_var;
    764871                                rec->PutArg( new_arg[0], new_arg[1] );
    765                                 tape[i_var].new_var = rec->PutOp(op);
     872                                i                   = rec->PutOp(op);
     873                                tape[i_var].new_var = i;
     874                                CPPAD_ASSERT_UNKNOWN( new_arg[1] < i );
    766875                        }
    767876                        break;
     
    834943                                        tmp_op = MulpvOp;
    835944                                size_t tmp_arg[2];
    836                                 tmp_arg[0] = new_arg[1];
    837                                 tmp_arg[1] = new_arg[0];
    838                                 unsigned short tmp_code = hash_code(
    839                                         tmp_op              ,
     945                                tmp_arg[0] = arg[1];
     946                                tmp_arg[1] = arg[0];
     947                                unsigned short tmp_code;
     948                                match_var = optimize_par_op_var_match(
     949                                        i_var               ,  // inputs
     950                                        tmp_op              ,
    840951                                        tmp_arg             ,
    841952                                        play->num_rec_par() ,
    842                                         play->GetPar()
     953                                        play->GetPar()      ,
     954                                        hash_table_var      ,
     955                                        tape                ,
     956                                        tmp_code              // outputs
    843957                                );
    844958                                hash_var = hash_table_var[tmp_code];
    845                                 if( tmp_op == tape[hash_var].op )
    846                                 {
    847                                 hash_arg = tape[hash_var].arg;
    848                                 match    = (
    849                                         new_arg[0] == tape[hash_arg[1]].new_var
    850                                 );
    851                                 hash_par = play->GetPar( hash_arg[0] );
    852                                 match   &= IdenticalEqualPar(par, hash_par);
    853                                 }
     959                                match    = match_var > 0;
    854960                        }
    855961                        if( match )
     
    867973                        case AddpvOp:
    868974                        case MulpvOp:
    869                         CPPAD_ASSERT_UNKNOWN( NumArg(op) == 2 );
    870                         CPPAD_ASSERT_UNKNOWN( NumRes(op) >  0 );
    871                         new_arg[1] = tape[arg[1]].new_var;
    872                         CPPAD_ASSERT_UNKNOWN( new_arg[1] < num_var );
    873                         new_arg[0] = arg[0];
    874                         code       = hash_code(
    875                                 op                  ,
    876                                 new_arg             ,
     975                        match_var = optimize_par_op_var_match(
     976                                i_var               ,  // inputs
     977                                op                  ,
     978                                arg                 ,
    877979                                play->num_rec_par() ,
    878                                 play->GetPar()
     980                                play->GetPar()      ,
     981                                hash_table_var      ,
     982                                tape                ,
     983                                code                  // outputs
    879984                        );
    880                         hash_var   = hash_table_var[code];
    881                         hash_arg   = tape[hash_var].arg;
    882                         //
    883                         par        = play->GetPar( arg[0] );
    884                         if( op == tape[hash_var].op )
    885                         {       match   = (
    886                                         new_arg[1] == tape[hash_arg[1]].new_var
    887                                 );
    888                                 hash_par= play->GetPar( hash_arg[0] );
    889                                 match  &= IdenticalEqualPar(par, hash_par);
    890                         }
    891                         if(! match )
     985                        if( match_var == 0 )
    892986                        {       OpCode tmp_op = AddvpOp;
    893987                                if(op == MulpvOp)
    894988                                        tmp_op = MulvpOp;
    895989                                size_t tmp_arg[2];
    896                                 tmp_arg[0] = new_arg[1];
    897                                 tmp_arg[1] = new_arg[0];
     990                                tmp_arg[0] = tape[arg[1]].new_var;
     991                                tmp_arg[1] = arg[0];
    898992                                unsigned short tmp_code = hash_code(
    899993                                        tmp_op              ,
     
    9071001                                hash_arg = tape[hash_var].arg;
    9081002                                match    = (
    909                                         new_arg[1] == tape[hash_arg[0]].new_var
    910                                 );
     1003                                        tmp_arg[0] == tape[hash_arg[0]].new_var
     1004                                );
     1005                                par      = play->GetPar( arg[0] );
    9111006                                hash_par = play->GetPar( hash_arg[1] );
    9121007                                match   &= IdenticalEqualPar(par, hash_par);
    9131008                                }
    914                         }
    915                         if( match )
    916                                 tape[i_var].new_var = tape[hash_var].new_var;
     1009                                if( match )
     1010                                        match_var = tape[hash_var].new_var;
     1011                                       
     1012                        }
     1013                        if( match_var > 0 )
     1014                                tape[i_var].new_var = match_var;
    9171015                        else
    9181016                        {
    919                                 new_arg[0] = rec->PutPar(par);
     1017                                new_arg[1] = tape[arg[1]].new_var;
     1018                                new_arg[0] = rec->PutPar(
     1019                                        play->GetPar( arg[0] )
     1020                                );
    9201021                                rec->PutArg( new_arg[0], new_arg[1] );
    921                                 tape[i_var].new_var = rec->PutOp(op);
     1022                                i                   = rec->PutOp(op);
     1023                                tape[i_var].new_var = i;
     1024                                CPPAD_ASSERT_UNKNOWN( new_arg[1] < i );
    9221025                        }
    9231026                        break;
Note: See TracChangeset for help on using the changeset viewer.