code_handler.hpp

#ifndef CPPAD_CG_CODE_HANDLER_INCLUDED
#define CPPAD_CG_CODE_HANDLER_INCLUDED
/* --------------------------------------------------------------------------
 *  CppADCodeGen: C++ Algorithmic Differentiation with Source Code Generation:
 *    Copyright (C) 2012 Ciengis
 *
 *  CppADCodeGen is distributed under multiple licenses:
 *
 *   - Eclipse Public License Version 1.0 (EPL1), and
 *   - GNU General Public License Version 3 (GPL3).
 *
 *  EPL1 terms and conditions can be found in the file "epl-v10.txt", while
 *  terms and conditions for the GPL3 can be found in the file "gpl3.txt".
 * ----------------------------------------------------------------------------
 * Author: Joao Leal
 */

namespace CppAD {
namespace cg {

template<class Base>
class CodeHandler {
    friend class CodeHandlerVectorSync<Base>;
public:
    using PathNode = OperationPathNode<Base>;
    using SourceCodePath = std::vector<PathNode>;
    using ScopePath = std::vector<ScopePathElement<Base> >;
    using Node = OperationNode<Base>;
    using Arg = Argument<Base>;
    using CGB = CG<Base>;
    using ScopeIDType = unsigned short;
protected:
    struct LoopData; // forward declaration

protected:
    // counter used to determine visitation IDs for the operation tree
    size_t _idVisit;
    // counter used to generate variable IDs
    size_t _idCount;
    // counter used to generate array variable IDs
    size_t _idArrayCount;
    // counter used to generate sparse array variable IDs
    size_t _idSparseArrayCount;
    // counter used to generate IDs for atomic functions
    size_t _idAtomicCount;
    // the independent variables
    std::vector<Node *> _independentVariables;
    // the current dependent variables
    ArrayView<CGB>* _dependents;
    std::vector<Node*> _codeBlocks;
    std::set<CodeHandlerVectorSync<Base>*> _managedVectors;
    CodeHandlerVector<Base, size_t> _lastVisit;
    CodeHandlerVector<Base, ScopeIDType> _scope;
    CodeHandlerVector<Base, size_t> _evaluationOrder;
    CodeHandlerVector<Base, size_t> _lastUsageOrder;
    CodeHandlerVector<Base, size_t> _totalUseCount;
    CodeHandlerVector<Base, size_t> _operationCount;
    CodeHandlerVector<Base, size_t> _varId;
    std::vector<Node*> _variableOrder;
    std::vector<std::set<Node*>> _variableDependencies;
    std::vector<std::vector<Node*> > _scopedVariableOrder;
    LoopData _loops;
    std::map<size_t, CGAbstractAtomicFun<Base>*> _atomicFunctions;
    std::map<std::string, size_t> _atomicFunctionName2Index;
    std::vector<std::string>* _atomicFunctionsOrder;
    std::vector<int> _atomicFunctionsMaxForward;
    std::vector<int> _atomicFunctionsMaxReverse;
    // a flag indicating if this handler was previously used to generate code
    bool _used;
    // a flag indicating whether or not to reuse the IDs of destroyed variables
    bool _reuseIDs;
    // scope color/index counter
    ScopeIDType _scopeColorCount;
    // the current scope color/index counter
    ScopeIDType _currentScopeColor;
    // all scopes
    std::vector<ScopePath> _scopes;
    // possible altered nodes due to scope conditionals (altered node <-> clone of original)
    std::list<std::pair<Node*, Node* > > _alteredNodes;
    // the language used for source code generation
    Language<Base>* _lang;
    // the lowest ID used for temporary variables
    size_t _minTemporaryVarID;
    bool _zeroDependents;
    //
    bool _verbose;
    JobTimer* _jobTimer;
    Node* _auxIndexI;
    IndexOperationNode<Base>* _auxIterationIndexOp;
public:

    CodeHandler(size_t varCount = 50);

    CodeHandler(const CodeHandler&) = delete;

    CodeHandler& operator=(const CodeHandler&) = delete;

    inline virtual ~CodeHandler();

    inline void setReuseVariableIDs(bool reuse);

    inline bool isReuseVariableIDs() const;

    template<class VectorCG>
    inline void makeVariables(VectorCG& variables) {
        for (size_t i = 0; i < variables.size(); i++) {
            makeVariable(variables[i]);
        }
    }

    inline void makeVariables(std::vector<AD<CGB> >& variables);

    inline void makeVariable(AD<CGB>& variable);

    inline void makeVariable(CGB& variable);

    size_t getIndependentVariableSize() const;

    size_t getIndependentVariableIndex(const Node& var) const;

    inline const CodeHandlerVector<Base, size_t>& getVariablesIDs() const;

    inline size_t getMaximumVariableID() const;

    inline bool isVerbose() const;

    inline void setVerbose(bool verbose);

    inline JobTimer* getJobTimer() const;

    inline void setJobTimer(JobTimer* jobTimer);

    inline bool isZeroDependents() const;

    inline void setZeroDependents(bool zeroDependents);

    inline size_t getOperationTreeVisitId() const;

    inline void startNewOperationTreeVisit();

    inline bool isVisited(const Node& node) const;

    inline void markVisited(const Node& node);

    inline std::string getAtomicFunctionName(size_t id) const;

    inline const std::map<size_t, CGAbstractAtomicFun<Base>* >& getAtomicFunctions() const;

    const std::vector<int>& getExternalFuncMaxForwardOrder() const;

    const std::vector<int>& getExternalFuncMaxReverseOrder() const;

    inline const std::string* getLoopName(size_t id) const;

    inline const std::vector<ScopePath>& getScopes() const;

    /**************************************************************************
     *                       Graph management functions
     *************************************************************************/
    inline std::vector<SourceCodePath> findPaths(Node& root,
                                                 Node& target,
                                                 size_t max);

    inline BidirGraph<Base> findPathGraph(Node& root,
                                          Node& target) ;

    inline BidirGraph<Base> findPathGraph(Node& root,
                                          Node& target,
                                          size_t& bifurcations,
                                          size_t maxBifurcations = (std::numeric_limits<size_t>::max)());

    /**************************************************************************
     *                       Source code generation
     *************************************************************************/

    virtual void generateCode(std::ostream& out,
                              Language<Base>& lang,
                              CppAD::vector<CGB>& dependent,
                              VariableNameGenerator<Base>& nameGen,
                              const std::string& jobName = "source");

    virtual void generateCode(std::ostream& out,
                              Language<Base>& lang,
                              std::vector<CGB>& dependent,
                              VariableNameGenerator<Base>& nameGen,
                              const std::string& jobName = "source");

    virtual void generateCode(std::ostream& out,
                              Language<Base>& lang,
                              ArrayView<CGB>& dependent,
                              VariableNameGenerator<Base>& nameGen,
                              const std::string& jobName = "source");

    virtual void generateCode(std::ostream& out,
                              Language<Base>& lang,
                              CppAD::vector<CGB>& dependent,
                              VariableNameGenerator<Base>& nameGen,
                              std::vector<std::string>& atomicFunctions,
                              const std::string& jobName = "source");

    virtual void generateCode(std::ostream& out,
                              Language<Base>& lang,
                              std::vector<CGB>& dependent,
                              VariableNameGenerator<Base>& nameGen,
                              std::vector<std::string>& atomicFunctions,
                              const std::string& jobName = "source");

    virtual void generateCode(std::ostream& out,
                              Language<Base>& lang,
                              ArrayView<CGB>& dependent,
                              VariableNameGenerator<Base>& nameGen,
                              std::vector<std::string>& atomicFunctions,
                              const std::string& jobName = "source");

    size_t getTemporaryVariableCount() const;

    size_t getTemporaryArraySize() const;

    size_t getTemporarySparseArraySize() const;

    /**************************************************************************
     *                       Reusing handler and nodes
     *************************************************************************/

    virtual void reset();

    inline void resetNodes();

    /**************************************************************************
     *                         access to managed memory
     *************************************************************************/

    inline Node* cloneNode(const Node& n);

    inline Node* makeNode(CGOpCode op);

    inline Node* makeNode(CGOpCode op,
                          const Arg& arg);

    inline Node* makeNode(CGOpCode op,
                          std::vector<Arg>&& args);

    inline Node* makeNode(CGOpCode op,
                          std::vector<size_t>&& info,
                          std::vector<Arg>&& args);

    inline Node* makeNode(CGOpCode op,
                          const std::vector<size_t>& info,
                          const std::vector<Arg>& args);

    inline LoopStartOperationNode<Base>* makeLoopStartNode(Node& indexDcl,
                                                           size_t iterationCount);

    inline LoopStartOperationNode<Base>* makeLoopStartNode(Node& indexDcl,
                                                           IndexOperationNode<Base>& iterCount);

    inline LoopEndOperationNode<Base>* makeLoopEndNode(LoopStartOperationNode<Base>& loopStart,
                                                       const std::vector<Arg >& endArgs);

    inline PrintOperationNode<Base>* makePrintNode(const std::string& before,
                                                   const Arg& arg,
                                                   const std::string& after);

    inline IndexOperationNode<Base>* makeIndexNode(Node& indexDcl);

    inline IndexOperationNode<Base>* makeIndexNode(LoopStartOperationNode<Base>& loopStart);

    inline IndexOperationNode<Base>* makeIndexNode(IndexAssignOperationNode<Base>& indexAssign);

    inline IndexAssignOperationNode<Base>* makeIndexAssignNode(Node& index,
                                                               IndexPattern& indexPattern,
                                                               IndexOperationNode<Base>& index1);

    inline IndexAssignOperationNode<Base>* makeIndexAssignNode(Node& index,
                                                               IndexPattern& indexPattern,
                                                               IndexOperationNode<Base>* index1,
                                                               IndexOperationNode<Base>* index2);

    inline Node* makeIndexDclrNode(const std::string& name);

    inline size_t getManagedNodesCount() const;

    inline const std::vector<Node *>& getManagedNodes() const;

    inline void deleteManagedNodes(size_t start,
                                   size_t end);

    /**************************************************************************
     *                           Value generation
     *************************************************************************/
    CGB createCG(const Arg& arg);

    /**************************************************************************
     *                           Loop management
     *************************************************************************/

    const std::map<size_t, LoopModel<Base>*>& getLoops() const;

    inline LoopModel<Base>* getLoop(size_t loopId) const;

    inline size_t addLoopDependentIndexPattern(IndexPattern& jacPattern);

    inline void manageLoopDependentIndexPattern(const IndexPattern* pattern);

    inline size_t addLoopIndependentIndexPattern(IndexPattern& pattern, size_t hint);

    /***********************************************************************
     *                           Index patterns
     **********************************************************************/
    static inline void findRandomIndexPatterns(IndexPattern* ip,
                                               std::set<RandomIndexPattern*>& found);

    /**************************************************************************
     *                      Operation graph manipulation
     *************************************************************************/

    inline CGB solveFor(Node& expression,
                             Node& var);

    inline bool isSolvable(Node& expression,
                           Node& var);

    inline void substituteIndependent(const CGB& indep,
                                      const CGB& dep,
                                      bool removeFromIndeps = true);

    inline void substituteIndependent(Node& indep,
                                      Node& dep,
                                      bool removeFromIndeps = true);

    inline void undoSubstituteIndependent(Node& indep);

    inline void removeIndependent(Node& indep);

    inline bool manageOperationNodeMemory(Node* code);

protected:

    virtual Node* manageOperationNode(Node* code);

    inline void addVector(CodeHandlerVectorSync<Base>* v);

    inline void removeVector(CodeHandlerVectorSync<Base>* v);

    virtual void markCodeBlockUsed(Node& code);

    inline bool handleTemporaryVarInDiffScopes(Node& code,
                                               size_t oldScope, size_t newScope);

    inline void replaceWithConditionalTempVar(Node& tmp,
                                              IndexOperationNode<Base>& iterationIndexOp,
                                              const std::vector<size_t>& iterationRegions,
                                              ScopeIDType oldScope,
                                              ScopeIDType commonScopeColor);

    inline void updateTemporaryVarInDiffScopes(Node& code);

    inline void restoreTemporaryVar(Node& tmp);

    inline void restoreTemporaryVar(Node* tmp,
                                    Node* opClone);

    inline void updateVarScopeUsage(Node* node,
                                    ScopeIDType usageScope,
                                    ScopeIDType oldUsageScope);

    inline void addScopeToVarOrder(size_t scope,
                                   size_t& e);

    inline size_t findFirstDifferentScope(size_t color1,
                                          size_t color2);

    inline void optimizeIfs();

    inline void replaceScope(Node* node,
                             ScopeIDType oldScope,
                             ScopeIDType newScope);

    inline void breakCyclicDependency(Node* node,
                                      size_t scope,
                                      Node* endIf);

    inline bool containedInScope(const Node& node,
                                 ScopeIDType scope);

    inline static bool containsArgument(const Node& node,
                                        const Node& arg);

    virtual void registerAtomicFunction(CGAbstractAtomicFun<Base>& atomic);

    /***********************************************************************
     *
     **********************************************************************/
    virtual void checkVariableCreation(Node& code);

    inline void addToEvaluationQueue(Node& arg);

    inline void reduceTemporaryVariables(ArrayView<CGB>& dependent);

    inline void reorderOperations(ArrayView<CGB>& dependent);

    inline void reorderOperation(Node& node);

    inline size_t findLastTemporaryLocation(Node& node);

    inline void repositionEvaluationQueue(size_t fromPos,
                                          size_t toPos);

    inline void determineLastTempVarUsage(Node& node);

    inline void findVariableDependencies();

    inline void findVariableDependencies(size_t i,
                                         Node& node);

    inline void dependentAdded2EvaluationQueue(Node& node);

    inline void updateEvaluationQueueOrder(Node& node,
                                           size_t newEvalOrder);

    inline bool isIndependent(const Node& arg) const;

    inline bool isTemporary(const Node& arg) const;

    inline static bool isTemporaryArray(const Node& arg);

    inline static bool isTemporarySparseArray(const Node& arg);

    inline static Node* getOperationFromAlias(Node& alias);

    inline size_t getEvaluationOrder(const Node& node) const;

    inline void setEvaluationOrder(Node& node,
                                   size_t order);

    inline size_t getLastUsageEvaluationOrder(const Node& node) const;

    inline void setLastUsageEvaluationOrder(const Node& node,
                                            size_t last);

    inline size_t getTotalUsageCount(const Node& node) const;

    inline void setTotalUsageCount(const Node& node,
                                   size_t cout);

    inline void increaseTotalUsageCount(const Node& node);

    inline void resetManagedNodes();

    /**************************************************************************
     *                       Graph management functions
     *************************************************************************/

    inline void findPaths(SourceCodePath& path2node,
                          Node& code,
                          std::vector<SourceCodePath>& found,
                          size_t max);

    static inline std::vector<SourceCodePath> findPathsFromNode(const std::vector<SourceCodePath> nodePaths,
                                                                Node& node);

    /**************************************************************************
     *                        Operation graph manipulation
     *************************************************************************/
    inline CGB solveFor(const SourceCodePath& path);

    inline CGB collectVariable(Node& expression,
                               const SourceCodePath& path1,
                               const SourceCodePath& path2,
                               size_t bifPos);

    inline CGB collectVariableAddSub(const SourceCodePath& pathLeft,
                                     const SourceCodePath& pathRight);

    inline bool isCollectableVariableAddSub(const SourceCodePath& pathLeft,
                                            const SourceCodePath& pathRight,
                                            bool throwEx);

    inline bool isSolvable(const SourceCodePath& path) const;

    /**************************************************************************
     *                     Loop related structure/methods
     *************************************************************************/
    struct LoopData {
        // maps the loop ids of the loop atomic functions
        std::map<size_t, LoopModel<Base>*> loopModels;
        std::vector<LoopEndOperationNode<Base>*> endNodes;
        // the used indexes
        std::set<const Node*> indexes;
        // the used random index patterns
        std::set<RandomIndexPattern*> indexRandomPatterns;
        //
        std::vector<IndexPattern*> dependentIndexPatterns;
        std::vector<const IndexPattern*> dependentIndexPatternManaged; // garbage collection
        std::vector<IndexPattern*> independentIndexPatterns;
        // variables used inside a loop which are assigned outside (for different loop depths)
        std::vector<std::set<Node*> > outerVars;
        // the current loop depth (-1 means no loop)
        int depth;
        // the evaluation order of the loop start for each loop depth
        std::vector<size_t> startEvalOrder;

        inline LoopData() :
            depth(-1) {
        }

        inline void prepare4NewSourceGen();

        inline void reset();

        inline const std::string* getLoopName(size_t id) const;

        inline void registerModel(LoopModel<Base>& loop);

        inline LoopModel<Base>* getLoop(size_t loopId) const;

        size_t addDependentIndexPattern(IndexPattern& jacPattern);

        void manageDependentIndexPattern(const IndexPattern* pattern);

        size_t addIndependentIndexPattern(IndexPattern& pattern, size_t hint);

        void addLoopEndNode(Node& node);
    };

    /**************************************************************************
     *                                friends
     *************************************************************************/
    friend class CG<Base>;
    friend class CGAbstractAtomicFun<Base>;
    friend class BaseAbstractAtomicFun<Base>;
    friend class LoopModel<Base>;

};

} // END cg namespace
} // END CppAD namespace

#endif